Routing with Rich Text Queries via Next-Vertex Prediction Models

We appreciate the reviewer’s thoughtful feedback. We address your main questions below.

Complexity of natural language queries

Our method does not use structured query inputs that can be directly mapped to one-hot encodings. Rather, it directly takes as input unstructured natural language queries from users. Our dataset of natural language user queries are complex and diverse (see Table 24), and involve “and”/”or” combinations that require explicit reasoning. We can be confident that our models perform some form of non-trivial natural language processing since we use a test set that exclusively includes previously unseen user queries.

Why does the method work despite using only local information? Are there instances where the model performs poorly? Why does the model not benefit from a larger receptive field?

We agree it may be initially surprising that only local information is needed for constrained routing. Two factors play a role.

1. Real-world road networks (which is what our experiments use) are easier to route on than worst-case graphs. This is because travel time between locations usually approximates geographic distance up to small constant factors. Our model performs poorly on graphs that deviate from this, e.g. where the fastest route to a destination 1km away is to route through a midpoint 50km away.

2. In beam search, each candidate route allows our model to explore a different local region of the graph. Our models may therefore be limited to using local information but can be strategic about where to collect this local information. In fact, we can think of beam search as performing some efficient graph search. Even with a 1-hop receptive field, a sufficiently large beam width lets one observe the entire graph before choosing a route. Our model not benefiting from a larger receptive field (Figure 11) is also therefore because the most effective way to give our model more global information is to increase its beam width (Figure 4).

Comparisons

The main contribution of our paper is demonstrating that a next-vertex prediction approach yields surprisingly good results for natural language constrained routing. To the best of our knowledge, there are only two alternative approaches: the use of cost modifiers (learning edge costs so one can run an algorithm like Dijkstra’s) and the use of unguided search algorithms (e.g., using electrical flows). For the former, it is immediate that it is impossible for cost modifiers to handle point-of-interest-like queries, which would require route-level costs that cannot be decomposed additively into edge costs. For the latter, we do include an electrical flows baseline, which clearly demonstrates that the routing problems in our experiment are non-trivial and difficult. We are open to implementing other baseline alternatives to our next-vertex prediction approach, but are not aware of any others.

We also want to note that there are ways that one could have implemented our next-vertex prediction approach differently. One could have used a different network to embed the receptive field, e.g. with a graph neural network rather than a transformer. However, we believe that we already have found a reasonable and effective implementation that demonstrates the efficacy of a next-vertex prediction approach; further architectural tunings are interesting but beyond the scope of this paper.

Does the performance of the model change as the routes become longer?

We evaluated our models on routing problems that require, on average, >21 non-trivial instructions, e.g., turn left (Table 5). This is among the complex end of problems that one would encounter in real-world applications. We did observe some degradation in performance with longer routes, but found the degradation disappears as one scales up one’s model. We will add a section to the Appendix with said result.

Does the model observe coordinates during planning?

Our model is able to observe the coordinates of the destination, source, and every vertex within a k-hop neighborhood of one’s candidate route.

We thank the reviewer for their response. We address your questions below.

Replication

Experiment details for reproducibility are already provided in Section C. This includes dataset details and dataset statistics, details on the choice of model architecture (C.1-C.3) and model hyperparameters (C.4). Hyperparameter tuning details are also already provided in Section B.7. We will be releasing the full source code for these experiments in the de-anonymized version of this paper post-acceptance.

Ablation studies

We have conducted extensive ablation studies. As noted on the bottom of Page 9, we include in the Appendix additional experiments that study the relationship between model performance and (1) how much of the road network the models observe (Figure 11), (2) the scale of the models’ network architectures (Figure 12, 13), (3) the difficulty of a dataset’s route customization queries (Figure 14), and (4) one’s choice of inference algorithm (Figure 23). We also perform ablation studies of the road embedding network (Figure 17) and secondary scoring model (Figure 22). We also visualize and analyze the attention matrices of our networks (Figures 15, 16) and the road embeddings that our networks learn (Figure 18).

Scalability on Larger Graphs and More Complicated Queries

We already conduct experiments where we vary the scale of our model (Section B.2) and the density of points-of-interest in the road network (Section B.3). Our experiments also already study how our performance varies for simpler vs more complicated queries; for instance, compare the left and right-hand columns of Table 1.

Are there any potential limitations or challenges in applying the proposed method to real-world scenarios with more complex constraints and larger datasets?

Experiments are conducted on the US road network and on a dataset of natural language text queries with almost 1 billion unique sentences.

We thank the reviewer for their response. We address your questions below.

Relying only on local graph context could limit long-range reasoning?

We found that local graph context is sufficient for real world routing problems. Our experiment in Section B.1 compares the performance of models allowed differing amounts of graph context, and finds that one does not gain any statistically significant amount of long-range reasoning capability by using a more than three-hop neighborhood as context.

There are two main reasons local graph context is sufficient.

1. Real-world road networks (which is what our experiments use) are easier to route on than worst-case graphs. This is because travel time between locations usually approximates geographic distance up to small constant factors.
2. In beam search, each candidate route allows our model to explore a different local region of the graph. Our models may therefore be limited to using local information but can be strategic about where to collect this local information. In fact, we can think of beam search as performing some efficient graph search. Even with a 1-hop receptive field, a sufficiently large beam width lets one observe the entire graph before choosing a route. We also note that we train a secondary model to choose from the final set of candidate routes; this secondary model has the full context of each of the routes when scoring/ranking a solution.

Query fulfillment prioritized over efficiency may lead to suboptimal routes?

Our networks are neither directly trained to maximize efficiency nor directly trained to maximize query fulfillment. Rather, they are trained auto-regressively on ground-truth routes that reflect both efficient and fulfilling solutions. The models therefore already jointly optimize for both efficiency and fulfillment, weighting the two concerns in accordance with the training data. Moreover, all of our results (Tables 1, 2, 3) show minimal loss of travel time efficiency (<3%).

Lacking comparisons to attention-based, reinforcement learning, and graph neural network routing methods?

The main contribution of our paper is demonstrating that a next-vertex prediction approach yields surprisingly good results for natural language constrained routing. To the best of our knowledge, there are only two alternative approaches: the use of cost modifiers (learning edge costs so one can run an algorithm like Dijkstra’s) and the use of unguided search algorithms (e.g., using electrical flows). For the former, it is immediate that it is impossible for cost modifiers to handle point-of-interest-like queries, which would require route-level costs that cannot be decomposed additively into edge costs. For the latter, we do include an electrical flows baseline, which clearly demonstrates that the routing problems in our experiment are non-trivial and difficult. We are open to implementing other baseline alternatives to our next-vertex prediction approach, but are not aware of any others.

We also want to note that there are ways that one could have implemented our next-vertex prediction approach differently. One could have used a different network to embed the receptive field, e.g. with a graph neural network rather than a transformer. However, we believe that we already have found a reasonable and effective implementation that demonstrates the efficacy of a next-vertex prediction approach; further architectural tunings are interesting but beyond the scope of this paper. Similarly, we agree that one could have used reinforcement learning to tune our model, in the same way that people finetune large language models with reinforcement learning; however, we see this slightly orthogonal question to be beyond the scope of this work.