Semantic Routing via Autoregressive Modeling
Authors: Eric Zhao
Pranjal Awasthi
Zhengdao Chen
Sreenivas Gollapudi
Daniel Delling
Venue: NeurIPS 2024 poster (2024)
Keywords: semantic routing
routing on graphs
autoregressive modeling
Primary area: machine_learning_for_other_sciences_and_fields

Abstract: We study learning-based approaches to semantic route planning, which concerns producing routes in response to rich queries that specify various criteria and preferences. Semantic routing is already widely found in industry applications, especially navigational services like Google Maps; however, existing implementations only support limited route criteria and narrow query sets as they rely on repurposing classical route optimization algorithms. We argue for a learning-based approach to semantic routing as a more scalable and general alternative. To foster interest in this important application of graph learning, we are releasing a large-scale publicly-licensed benchmark for semantic routing consisting of real-world multi-objective navigation problems---expressed via natural language queries---on the richly annotated road networks of US cities. In addition to being intractable with existing approaches to semantic routing, our benchmark poses a significant scaling challenge for graph learning methods. As a proof-of-concept, we show that---at scale---even a standard transformer network is a powerful semantic routing system and achieves non-trivial performance on our benchmark. In the process, we demonstrate a simple solution to the challenge of scaling up graph learning: an autoregressive approach that decomposes semantic routing into smaller ``next-edge'' prediction problems.

Semantic Routing via Autoregressive Modeling
Eric Zhao
Pranjal Awasthi Google Research
UC Berkeley and Google Research eric. zric.kh@berkeley. edu
baanjalasasth:@ooglle..co
Zhengdao Chen
Sreenivas Gollapudi Google Research
Daniel Delling Google de delling@google.cm com
Google Research zhengdaoc@google..om
sgollapu@google.com com
Abstract
We study learning-bai sraning-basedd approaches to semantic route planning, which concerns producing routes in response rich queries that specify various criteria and prefer- ences. Semantic routing is already widely found industry applications, especially navigational services like Google Maps; however, existing implemenations only support limited route criteria and narrow query sets as they rely on repurposing classical route optimization algorithms. We argue for learning-based approach to semantic routing as more scalable and general alternative. To foster inter- est in this important application of graph learning, we are releasing a large-scale publicly- -icensed benchmark for semantic routing consisting of real-world multi- objective navigation problems-expresedd via natural language queries-on the richly annotated road networks of US cities. In addition to being intractable with existing approaches to semantic routing, our benchmark poses significant scaling challenge for graph learning methods. As proof-of-concept, we show that-at at standard transformer network is a powerful semantic routing sys- tem and achieves non-trivial performance on our benchmark. In the process, we demonstrate a simple solution to the challenge of scaling up graph learning: an autoregressive approach that decomposes semantic routing into smaller "next-edge" prediction problems.
Introduction
The route planning problem arises in diverse applications including navigating transportation networks and supply chain logistics (Dantzig and Ramser 1959). Route planning is classically formulated in the language of graph theory as searching for paths between source and a destination that optimize single static objective (Dijkstra 1959). usually travel time. In practice, route planning systems are not as simple. For example, navigation services like Google Maps do not only optimize for travel time time-they allow drivers to specify multiple modes of transportation. add intermediate stops, and convey preferences about avoiding roads with bike lanes (Ratliff' al., 2009). Modern routing systems are better described as performing semantic routing: contextual and multi-objective generalization of route planning that involves processing rich user query that specifies not only a source and destination but also various criteria such as bike lanes preferences. and responding with satisfactory route (Delling et al., 2017).
Current routing systems implement semantic routing capabilities in an ad hoc way, customizing classical route optimization algorithms to support specific and limited types of route criteria. For example, the technique of "cost modifiers" rescales edge weights according to whether the edge type is preferred/disppeeerred such as doubling travel time along small roads when is indicated that small roads should be avoided (Ratliff et al. 2009), and then runs standard shortest-patte
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

CAN WE PICK INGREDIENTS FOR DINNET AND GET THE WASHED WAY
LET'S PICK UP INIS DIENT'S
DINNER STOP BY CAR
WASH, PLEASE DON'T PARKE DRIVE
Figure I: Examples of semantic routing tasks from our benchmark that involve navigating between two locations in the Glenview neighborhood of Chicago. The user query is specified in pink, while we outline the path of the optimal route (according to our automated evaluation scheme) in red.
algorithm. As industry routing services transition to offering increasingly rich experiences, it has become clear that the current paradigm is unscalable. First, this ad hoc approach can only support the limited types of route criteria that can be efficiently achieved through classical graph algorithms; for example, cost modifiers only support "linear" criteria (Ratliff et al. 2009). Second, modern routing systems are complex ensembles of combinatorial algorithms and expensive to maintain; supporting new features requires adding new customized algorithms into an already messy ensemble and even then different route criteria can often not be efficiently combined. Third, current systems cannot take full advantage of rich graph metadata as they require explicit instructions on what and how to use each data field (Cormen et al., 2022); this is major opportunity cost as, for example, modern road network metadata include live road conditions, the businesses along each road (OpenStreettMa)) contributors] 2017), and even the locations and types of fruit trees (Welty and Phillips] 2013). One can directly observe how these limitations manifest in industry services. For example, Google Maps allows for specifying an intermediate stop if an explicit address is given but cannot automatically plan short stop to purchase dental floss; it can provide routes that use public transportation but not when an intermediate stop is specified. In this paper, we study the open question of building a semantic routing system that is truly scalable and offers general open-ended capabilities.
We argue for learning- based approach to semantic routing, where systems are trained on historical, and potentially simulated, data consisting of tuples of queries, rich graphs, and satisfactory routes. learning-bea approach avoids all three key limitations of the current paradigm. transfers the complexity of semantic routing from handcrafting ensembles of combinatorial graph algorithms to instead creating a rich dataset that demonstrates desired capabilities. Moreover, as we will demon- strate, learned models can approximately fulfill route criteria that may not admit efficient classical solutions and take advantage of available rich graph metadata that may be impractical to manually engineer support for. Semantic routing also exhibits the usual hallmarks of a practical machine learning application: though undesirable, having latency and errors in a semantic routing system is not typically catastrophic dangerous, unlike higher-stakes applications such as autonomous driving. With the cost of deploying large neural networks plummeting and the toolkit of graph learning methods exploding in recent years, we believe that learned semantic routing systems are now a viable short-term goal. Our contributions are two-fold and aimed at fostering interest in this important application of graph learning.
1. First, we release large-scale publicly- benchmark for semantic routing, which can be found at www.gooolleesseerrclleeeeoooeeee
reseanc/rree/masttrr/smaaat bttpeeemmatnntrtcnnnggtae This benchmark, and the remainder of our paper, focuses on real-world multi-objective navigation problems that involve providing route suggestions to drivers. These problems include providing efficient routes for errand running, planning recreational day trips, avoiding highway driving, and providing waypoint routes that make stops by, e.g., grocery stores. Each problem in this benchmark is a tuple consisting of (1) a subgraph of a real-world road network with rich metadata including local businesses, sourced from the OpenStreetMap project (OpenStreetMap contributors 2017), and (2) an unstructured natural language user query. Our benchmark also includes an automated evaluation mechanism that, given problem tuple, scores candidate routes. Consisting of 1,000,00++ user queries and 300,000+ miles of real-world road networks, our benchmark provides a comprehensive platform for evaluating semantic routing systems and tests capabilities that are intractable with existing methods.
2. Second, we demonstrate the viability of learning- based semantic routing systems with a proof- of-concept. Specifically, we show that-when done at sufficient training even standard

---

Find a suitable place for dog walking and post box along the way. [need: (dog park or park) and (post box)]
Help me plan a kid-friendly adventure through town, with all places no more than a 20-minute drive away.
(visit: (game store or video game store or toy store or arcade))
Please plan route for that includes stop at bakery and car repair shop, avoiding highways whenever possible.
[visit: (bakery) and (car repair shop), dislikes: highways
Figure 2: Examples of queries drawn from our benchmark, demonstrating an errand route planning task (top), a trip planning task (middle), and the combination of waypoint routing task and highway avoidance task (bottom). Annotated labels are underneath queries in gray and are hidden to models.
transformer network on our benchmark's ' dataset creates a powerful semantic routing system, with 60-70% success rate on benchmark tasks even on previously unseen user queries and in a previously unseen American city. As existing semantic routing methods entirely fail on our benchmark- even when implemented with unfair advantages -our proof-of-concee baseline of our benchmark. A major challenge we encountered was scaling up graph learning methods to large road graphs (e.g., 10,000 vertices and 25,000 edges); we identified an autoregressive approach to be critical: performing repeated next-edge predictions to unroll route instead of predicting an entire route at once, allowing us to only provide the model a small local subsection of the road network at time. This approach is similar to that of a language model, except instead of unrolling a sentence by predicting tokens, we unroll a route by predicting edges.
also establishes the first non- trivial
1.1 Related Work
Route Planning in Navigation. Traditional routing tasks are approached as finding shortest paths within road networks and can be solved with dynamic programming algorithms such as Dijkstra's
method (Dijkstra 2022) and its generalizations (Shimbel 1954 Bellman 1958 Ford 1956). Their ef-
ficiency has been improved via priority-queue-basel implementations (Goldberg 2001 Meyer 2001] bidirectional search (Sint and de Champeaux 1977). A search (Hart al. 1968), and contraction hierarchies (Bast et al.) 2016 2016| et al. 2009] Bauer et al. 2010) that specifically make use of the near planar structure the road networks. However, incorporating custom contextual information into these algorithms is challenging, requiring solving a (often NP- NP-complete) combinatorial problem per context. For very narrow set of contextual routing tasks where the "cost" of route can be decomposed into sum of its component edges, it is possible to define context-dependent cost modifiers on edges such that the running shortest-pathi paths on the new costs results in satisfactory solutions (Ratliff et al. 2009). However, this approach is not possible for most routing tasks of interest and even when available- still requires one solve the challenging problem of learning how to design good cost modifiers from complex natural language queries. A more generally available alternative is to run unguided search algorithms such as search or spectral methods based on electrical flows (Sinop et al.) (202T) to compute large set of candidate routes from source to destination, and then extract the best candidate. However, this approach needs one to have a good way of scoring candidate routes and may require iterating through intractably many candidates to find a solution.
Learning on Graphs. In recent years, many data-driven approaches have been explored for combi- natorial problems on graphs. The works Xu al. (2019 2020) show that graph neural networks (GNNs) can learn phraami-programmingg-gaee
algorithms; Veličković et al. (2019) : Ibarz et al. (2022) create GNN based neural learners simulate various combinatorial algorithms by "hinting" them with intermediate computations of the algorithms. Other works have explored the custom models, such as pointer networks and iitentioo-bbsed GNNs, for solving graph problems such as the traveling salesman (Kool et al.] 2018 Vinyals et al. 2015 Khalil et al. [0017] Nowak et al.) 2017] Deudon et al. 2018). However, these approaches are all empirically tested only at small scales: graphs around 100 nodes large. In comparison, the semantic routing applications we explore in this paper concern road networks that are-at smallest-10.,0 10,000 vertices large; naively scaling graph learning algorithms to this setting would require an impractically expensive distributed GNN system. One exception to the small scale studies in previous works Graves et al. (2016), who conducted routing experiments the London underground system using highly specialized and complex variant of
3

---

please guide charping sodtin
Figure 3: Example of semantic routing tasks from our main benchmark (left) and our grid- world (right), visualized in false-color. The optimal route is illustrated orange/pink and colored dots denote points-of-interes.
differential neural computer. In contrast, we present in Section 3 simple approach to scaling graph learning methods to large-scale semantic routing problems: train on an autoregressive objective so that the semantic routing problem decomposes into smaller next-edge prediction problems where suffices to only consider local neighborhood of the graph.
Autoregressive Models. Autoregressive approaches based on the transformer model (Vaswani ctt al. (2017) have achieved remarkable progress for generative tasks from language modeling to image and video generation. The ability of such models generate sequences via the next-token-predittiie paradigm and to incorporate multi-modal information makes them natural fit to tackle semantic routing. Moreover, when trained at scale and augmented with prompting techniques or external tools and operations, autoregressive models appear to demonstrate capabilities of planning (e.g.. Wei et al. (2022); Huang al. (2022); Schiek et al. (203)); Yao al. (2023); Valmeekam al.] (2023)). We take inspiration from autoregressive methods to approach semantic routing, re-discovering strong parallels between the domains of routing and language.
Benchmark for Semantic Routing
We are releasing public dataset of semantic routing problems concerning complex navigation tasks on American roads. To facilitate discussion, we will formalize a semantic routing problem as consisting of a graph G = (V. F)) with vertices V and edges E, a source and destination pair u, u E F, and query s E Σ where Σ" denotes all strings of alphabet Σ. We can denote the metadata associated with each edge in G using the map 0 E + E, where E is the space of possible metadata. Note that single query s may communicate multiple subtasks and objectives. The goal of semantic routing problem is to find path p E E* from source to destination that "satisfies" the query s. We can formalize this goal as finding path that starts at the source u, ends at the destination v, and maximizes f(s {f(c))eep) where f Σ E - R is scoring function and (f(e))eep is the metadata associated with each edge in the path. In our benchmark, each query s natural language user query, Σ can be understood as the English alphabet. Our graph G is road network where each edge corresponds to a road segment, and edge metadata 0 contains road information such colocated businesses and the speed limit.
2.1 Benchmark Overview
This benchmark evaluates semantic routing algorithms on whether they can successfully return a satisfactory route when provided natural language semantic routing query and road graph on which to navigate. To this end, we collected and labeled large dataset of natural language semantic routing queries and curated open-source data from OpenStreetMap contributors (2017) the road

---

Method Name
Waypoint Routing Success Rate
Cost modifiers
% + 0%
Electrical flows (4096 routes)
1.3% + 1.3%
Table 1: This table depicts the success rate of classical semantic routing methods (named in the "Baseline" column) on waypoint routing task sampled from our benchmark. We define a method as being successful if it returns at least one route that visits points-of-interest that together fulfill each part of the user's query. The "cost modifiers" method returns every route that can be elicited by a cost modifying rule (Delling et al. 2009); the "Electrical flows" method returns 4,096 routes sampled with the electrical flows algorithm (Sinop et al. 2021). + denotes standard error (n=100).
networks and points-of-interest (facilities, businesses, restaurants, etc.) of major urban centers in the United States. The benchmark is released under Apache 2.0 license; see supplemental materials. Structured similarly to reinforcement learning benchmark, it is accessible as a software package with three main functions: (1) generates semantic routing tasks by randomly drawing user query from a data bank and choosing the road graph of an American city, (2) given a semantic routing task, featurizes the task by generating feature arrays that describe the road graph in the form of Tensorflow record (Abadi et al. (015), and (3) given semantic routing task and candidate solution, returns a numerical score that describes estimated route quality. Examples of these functionality are provided in Python notebooks available in the previous link.
The benchmark consists of over 1 million natural language queries and navigation tasks drawn from an over 11 million vertex graph representing 375,000 miles of real-world road networks and 1.3 million points-of-interess in 23 major US cities. Figure Iillustrates samples of semantic routing tasks from our benchmark and their solutions.
Benchmarked Tasks. Our benchmark measures semantic routing capability with important real- world problems that involve navigating drivers on roads. The majority of tasks in our benchmark involve a variant of waypoint routing: routing tasks that require planning out (usually multiple) intermediate stops on one's 's route. For example, a user might ask to get coffee and drop off package en route work. Two types of waypoint routing tasks appear in our benchmark: where the user specifies a specific location category to visit (e.g., a grocery store), or where the user specifies a need or errand that they need to complete en route (e.g.. buy a water bottle). The latter allows for more flexibility as, for example, water bottle can be purchased at many types of locations including both grocery stores and gas stations. Fulfilling a waypoint query involves up to four expensive steps:
1. Identifying points-of-interes that fulfill the request (e.g., nearby coffee shops and mail boxes).
2. Choosing which points-of-inte onteereeetttttttt stop by (e.g.. picking coffee shop and mailbox to visit).
3. Picking an order to make the stops (e.g., determining that getting coffee first would be faster). Efficiently navigating through stops by minimizing travel time or fulfilling additional objectives.
One fifth of the tasks in our benchmark require also taking into account driver's 's personal comfort preferences, i.e., whether a driver has an aversion to highways or a preference against driving on small local roads. Another subset of tasks in our benchmark involve planning day trips, i.c. itinerary planning. In these tasks, the user query specifies a time budget and the type of day trip that the user wants to go on; the goal is to return route that takes the user to as many relevant points-of-intered as possible within the time budget. Whereas waypoint routing is a variant of the traveling salesman and set cover problems, trip planning is variant of the knapsack problem.
We provide examples of each of these tasks in Table 2 A challenging aspect of our benchmark is that a single problem typically involves multiple tasks; for example, single query might describe multiple errands that need to run en route and also an aversion to highways. On average, a single query conveys 1.8 distinct tasks or objectives, with maximum of up to 5 tasks per query.
this section, we adapt classical semantic routing methods to our benchmark and evaluate them on their success rate on waypoint routing task. Here, we define route as being successful if it visits points-of-interest that together fulfill every request the user's query; we will ignore further considcrations like travel time for simplicity. As noted in Section I we expect the
Baselines.
5

---

inherent limitations of classical methods to result in poor performance and will therefore generously adapt these methods afford them unfair advantages.
First, we consider the method of cost modifiers (Delling et al. 2009) where-deppnnding on the user query-we rescale travel times along each edge according to the edge's metadata, and then apply classical shortest-patte patts algorithm to find a route. To upper bound the performance of systems that use cost modifiers on our benchmark, for every semantic routing problem, we perform brute-force search over the routes returned by each possible cost modifier scheme (i.e., edge rescaling rule) and check if any of the routes is successful; if so, we mark down the overall method as being successful. Second, we consider a guess-and and-checd method that uses electrical flows (Sinop et al.) (20TT) to generate a large and diverse set of candidate routes and check if any of the routes successful; once again, we mark down the method as being successful if such a route is found.
The performance of these methods, as shown in Table T is unsurprisingly poor. Whereas waypoint routing problems are provably unsolvable with cost modifier methods, the electrical flows method is similarly doomed due the intractably large search space of possible routes from source to destination. For a baseline level of performance on our benchmark, we refer readers to Section
2.2 Technical Details
Road network data. We curated and sourced road network data and points-of-interest data from the OpenStreetMap project for the American cities of New York City, Santa Barbara, Miami, Cambridge (MA), Providence, San Francisco, Orlando, Boulder, Albuquerque, Portland, Madison, New Orleans, Chicago, Palo Alto, Philadelphia, Austin, San Jose, Memphis, Denver, Washington DC, Seattle, Sacramento, Santa Cruz, and Berkeley. Our curated road networks embed rich metadata in every road segment, including each segment's road type (e.g.. interstate, service road), number of lanes, speed limit, length, estimated average transit time, geometry (start and end coordinates), and list of ppints-of-interss that can found along the road segment. Every point-of-interest in our road networks exists in the real world and is annotated with its real-world name and assigned to one of over two hundred point-of-interes categories, such as "gas station" or "mailbox".
Our benchmark produces semantic routing problems by randomly selecting pairs of source and destination edges within the road network of Berkeley, California; for tasks involving trip planning, the destination is the same as the source. We perform rejection sampling to omit source-destination pairs if the optimal route between the two requires traversing more than 600 road segments. Due to its diverse composition, we chose the city of Berkeley as our benchmark 's default hold-out city. meaning that the training datasets that accompany our benchmark do not contain any examples of semantic routing in Berkeley. This means that our benchmark evaluates semantic routing systems on a road network they have never encountered and with points-of-interes and roads they have never seen in training. To simulate live traffic conditions on our road networks, we randomly rescale each road's default transit time in every new semantic routing problem instance.
Query dataset. We collected one million natural language user queries through a combination of human labeling and language model augmentation. The first step in our process produced 1,000+ distinct types of semantic routing queries by manually taxonomizing common road situations (e-g. ran out of gas, passenger spilled drink in backseat), and writing representative queries for each situation in the taxonomy. An industry language model (OpenAl (023) was then applied augment these queries into 10,000+ natural language variations. Multi-objective queries were then formed by randomly merging together combinations of up to 5 queries, where we again applied a language model to refine the writing of combined queries. The resulting queries were spot-checked for correctness and are depicted in Figure 2 and Appendix D Tour planning queries were not merged with other query types.
To define an evaluation rule for our benchmark, i.c. the route scoring function f. we label every query in our dataset with a structured interpretation of its content. For example, queries that specify an aversion to driving on highways have a special flag in their label indicating such. For every waypoint routing task communicated in a query, the query's 's label contains a list of point-of-interes categories that would satisfy the task; for example, a "get waterbottle" task might be labeled with the list ("grocery store", "gas station", etc.). Similarly, for every trip planning task communicated in query, the query's 's label contains a list of point-of-interest categories that the driver might want to visit on the requested trip. Queries are human labeled, though when two queries are rewordings

---

Query ["Get", "coffee"]
Destination 29 Hally .n
Taken So Far 44 Otis Rd. 39 Bear Rd
Receptiive 33 Bear Rd. 21 Bear Rd.
Candicltees Edges
43 Otis Rd
38 Bear Rd, 40 Bear Rd
Token Embeddiin Tabll
Road Embedsing Table
Embed all lotenns verioss, and edopt
(Problam Embediiing Vector)
Transfomme Block
Dut prodlosi
Transformer
Logit for 38
Logit for Bear
Takoo voolor deg.
(Sequence Encoded Vectors)
(Prediction Distribution Logits)
Figure 4: Architecture of proof-of-concee semantic routing model: transformer network trained on an autoregressive objective. Arrows illustrate the flow of data from input to next-edge prediction.
of one another, we may only label one query and propagate its label to the other. Figure depicts random examples of queries and their labels.
Automated route evaluation. Although it is possible use human raters evaluate routing systems on our benchmark's 's collection of semantic routing problems, we also provide an automated system for evaluating candidate routes against problems in our benchmark. Our system-a which simulates generic user's preferences with standard heuristics returns various metrics about the quality of the route, including an overall numerical score and task specific performance metrics like the waypoint routing success metric of Table T Our evaluation system's 's overall score metric should be understood as providing a ground-trute ordering over routes in terms of goodness; similarly, the ground-truth optimal route is the route maximizing this score. We define the overall score as follows. First, we refer to the problem's query label and identify all waypoint requests and points-of-interes that would satisfy the requests. If the route does not visit points-of-interest that satisfy all waypoint requests, an infinitely large penalty is subtracted from the score. The total seconds of travel time is also deducted from the overall score; although if the user specifies aversion/preference for driving on a particular road type, travel time on such roads is increased/decreused by a factor 5/0.5. In trip planning tasks, reward of 1,000 is added to the score for every relevant and unique type of point-of-ines interest visited. When a time budget is communicated in the query, an infinitely large penalty is subtracted from the score if the time budget is exceeded by more than fourth.
Although this evaluation scheme can be succinetly stated, its optimization is non-trivial and gener- alizes various combinations of traveling salesman, shortest path, set cover, and knapsack problems. Moreover, this reward scheme leads to empirically high-quality results as demonstrated in Figure
Training dataset. We are also releasing training dataset consisting of 3 million pairs of semantic routing problems generated from our benchmark and their ground-truth optimal routes. We brute- force solved for these routes by peeking at the query labels and applying ensemble of combinatorial algorithms, mimicking very inefficient classical semantic routing system. Beyond query labeling, this requires 0.3 CPU hours per route.
Grid-world test bed. To provide more flexible test bed for semantic routing algorithms, we are also releasing a purely synthetic semantic routing benchmark. This benchmark simulates a large grid graph with highway roads and populates it with artificial points of interest, as illustrated in Figure 3 Each grid world generated is of size 30x30 and consists of 3560 road segments; these graphs can be understood randomly sampled subgraphs of an infinitely large grid world, taken around a navigation task's source vertex. The query dataset for this grid world consists simple implltt-ggenerated natural language queries and represents only waypoint routing tasks. Some experiments in Section are performed on this grid-world benchmark.
3 A Proof-of-Concept Autoregressive Model
One challenge that has limited the adoption of graph learning methods in routing applications is that routing is naturally large-scale decision decision-making process. Road networks form highly connected
7

---

Success Rate (Waypoint Routing, Errands)
92.0% + 3.7%
Success Rate (Waypoint Routing, Locations)
38.0% + 6.6%
Success Rate (Waypoint Routing, Mixed)
34.0% + 6.9%
Success Rate (Trip Planning)
68% + 4%
Median Excess Penalty (Waypoint Routing, Mixed)
0.8 seconds
Median Total Travel Time (Waypoint Routing, Mixed)
509 seconds
Table 2: The task-level performance metrics of the proof-of-concepp autoregressive transformer model on our benchmark, The evaluated problems represent various semantic routing tasks with queries drawn from holdout test set and conducted on a road network from previously unseen city (Berkeley, CA). "Waypoint Routing Success Rate" is the fraction of waypoint routing problems that successfully completed (see Table D. "Errands" are waypointing needs that can be fulfilled by multiple point-of-interes categories (e.g., buy water bottle), "locations" are those that correspond to a specific chint-of-interest category (e.g.. gas station), and "mixed" refers waypoint routing problems consisting of both errand and location subtasks. "Trip Planning Success Rate" is the fraction of trip planning tasks that are completed under the time budget and where the predicted route provides at least half the experiences of an optimal itinerary. "Excess Penalty" is the median gap between the achieved overall route score and best possible score, conditioned on successfully completed waypoint routing problems; this penalty can be understood as total travel time (in seconds) rescaled by 5x when transiting along an unfavorable road type. Standard error denoted by +.
graphs, and even a 10 kilometer stretch of road involves, on average, 600 different road segments (OpenStreetMap contributors] 2017). Meanwhile, popular deep learning methods for graph-structured data such as GNNs are often difficult to scale, leading to an impression that graph learning methods are an impractical solution semantic routing.
In this section we demonstrate a simple graph learning method that serves as a strong baseline for train autoregressive networks on a natural
semantic routing tasks. Our key observation is that next- vertex prediction objective to unroll routes. We show that, by decomposing semantic routing into next- vextevertex subproblems, it is possible to construct high-quality routes while only needing to engage a small neighborhood of the road network at each point in time. This approach allows standard transformer networks to achieve strong results our semantic routing benchmark.
3.1 Autoregressive Modeling
Autoregressive learning is an approach to learning generative models where one trains network on the task of predicting the next element of string (Brown et al. 2020), which can be a sentence in language generation or, in semantic routing, edge. These networks can be used generate strings by unrolling a solution path through repeated next-element predictions or, in the case of semantic routing, through repeated next-edge predictions. From probabilistic standpoint, this approach circumvents the need to estimate the distribution of the entire solution path by decomposing it into a sequence of conditional distributions via the chain rule.
Despite their greedy nature, autoregressive predictors have demonstrated remarkable success in language generation and showcased their ability effectively navigate complex decision spaces (Huang et al. 2022 Bubeck et al. 2023). Moreover, they are proven theoretically to be universal learners trained on adequate data (Malach 2023). These results suggest autoregressive models to be a viable graph learning solution to semantic routing: one can avoid needing to scale graph learning algorithms to large road networks if they can decompose routing into next-edge prediction problems where only small neighborhood of the graph is relevant at any single time.
3.2 A Proof of Concept
We trained a standard transformer network on our benchmark's training dataset. By truncating the example routes in the dataset at random positions, we optimized our model on an autoregressive objective of predicting subsequent edges. As inputting entire road networks into our model was impractical due to its ((IV(2) memory footprint, we instead input a small neighborhood of the road network around the head of each truncated route. The resulting model fits single GPU.
8

---

Figure 5: Visualization of receptive field consisting of 512 road segments; receptive field is neighborhood that the taken around the head of a partial route. As discussed Section 3.3 our semantic routing model observes 512-edge receptive field instead of the entire road network.
We report the performance metries of this model in Table The model successfully interprets and fulfills roughly in 5 waypoint routing tasks; recall that this evaluation performed on previously unencountered queries and previously unseen city's road network. The model incurs median excess travel time of less than 0.2%; this is including a 5x travel-time penalization for unnecessary travel roads (e.g., highways) that the query specifies aversion against. Our model also provides a satisfactory itinerary for these results those of classical methods, our model's predictions for an intuitive sense of these performance metrics. We believe these figures be strong demonstration of the viability of learning- based semantic routing; these success rates on challenging combinatorial problems expressed in natural language is non-trivial in any application domain. Moreover, we are confident that our proof-of-concee is far from an upper bound of what is achievable with learned semantic routing models.
trip planning queries. Although it is trivial to compare refer readers to Appendix []ror random examples of
3.3 Technical Details
Model description. Our proof of concept implements a simple decoder-only transformer network
(Vaswani al. 2017; Brown al., 2020) which we train using standard cross entropy loss on the task of predicting the subsequent edge to a truncated route. Our network as illustrated in Figure takes as input sequence of "tokens" that contain the user's query, the destination, the partial route that we are trying to predict the subsequent edge for, set of possible subsequent edges, and the small neighborhood (the "receptive field") around the head of the partial route. To featurize the tokens in this sequence, we create feature vector for each edge from their metadata, and process with multi-layer perceptron. This is in contrast to language models which learn an embedding table for their alphabet, which in setting would correspond to learning an embedding vector for every segment in our road networks; we deviate from this embedding approach so we can take advantage of road segment metadata and encourage the model to generalize to edges not seen during training. Because of this, our proof-of-concept can provide high-quality routes city has never encountered during training.
Receptive field. Our autoregressive approach allows us to treat each next-edge inference as local problem: instead of passing in the entire road graph into our model, we only pass in a small neighborhood around the head of the partial route. We refer to this small neighborhood as the receptive field of our model. Our proof-of-concept uses 500-edge receptive field, which we illustrate the size of in Figure 55] In comparison,
navigation tasks are defined 25,000 edge) subgraphs of urban road networks, meaning that our use of a receptive field reduced the memory footprint of our model by factor of over 2,000.
10,000-node (roughly
Inference strategy. Given a next-vertex prediction model, there are several approaches obtaining a candidate path for a given routing task. The first approach is greedy decoding, a popular and computationally efficient baseline approach in language modeling (Chowdhery et al. 2022). To

---

Test-Set Beam Search Performance using Various Scorers
0.07
Excess Travel Time (16
Query Fallure Rate (%)
0.05
0.15
0.04
0.03
0.10
0.02
Cum, Prob Scorer
0.05
Ground-Trutt Scoret
0.00
0.00
Figure 6: The semantic routing performance metrics of an autoregressive transformer under a 10- width beam-search algorithm. The route prediction is extracted from the final beam either using the model's logits (red), a secondary model (purple), or omnipotently choosing the best route (blue).
this, note that the time complexity of our next-vertex prediction framework is independent of the size of the road network. Rather, since each step requires quadratic computation in the length of the route so far, the full time complexity is cubic in the path length O Route] )) for greedy decoding, with improved complexity possible through more efficient attention mechanisms (e.g. Wann 2020 Zaheer et al. 2020 Dao et al. 2022).
Inspired by classical AI and natural language generation, also apply beam search (Reddy 1977
to our next-vertex prediction model during inference. Beam search returns set of candidate paths (as many as the beam width) generated by the model and allows one to cleanly trade-off accuracy for inference complexity, with time of ( Width |Route| We train secondary scoring model to choose final path from this candidate set. The scoring model is trained in contrastive fashion, where ground-truth paths are taken from our training set as positive examples and random paths are sampled from the outputs of our model as negative examples. After embedding these routes with our vertevertex model, we train the scoring model inference time, we select from candidate paths by choosing the one receiving the largest logits from the scoring model. In Figure 6 we ablate this scoring model and notice a significant drop in semantic routing performance. The main results presented in this paper, i.e. Table use beam-search with secondary scoring model.
2-layer MLP with logistic loss. At
3.4 Ablation Studies and Benchmark Demonstrations
Additional experiments, including ablation studies, can be found in Appendix A and illustrate how increasing receptive field sizes only marginally impacts model performance and evaluate how semantic route planning performance scales with model size and aspects of the road graph's 's topology. Appendix lists randomly sampled examples semantic route planning tasks from our benchmark along with the optimal route according to our benchmark' 's labeling system.
4 Discussion
We study a Icarning-basee approach to semantic routing. To facilitate further research on this important graph learning application, release a large-scale benchmark of real-world multi-objective navigation problems. We also introduce proof-of-concep! model to establish a competitive baseline for the benchmark and to demonstrate the viability of learning-based approaches. To this end, formulated an autoregressive architecture that reduces semantic routing to the scalable problem of next-edge prediction. We refer readers to Appendix for continued discussion of open questions.
10

---

References
M. Abadi, A. Agarwal, Barham, E. Brevdo, Z. Chen, C. Citro, G. S. Corrado, A. Davis, J. Dean, M. Devin, S. Ghemawat, I. Goodfellow, A. Harp, G. Irving, M. Isard, Y. Jia, R. Jozefowicz, L. Kaiser, M. Kudlur, J. Levenberg, D. Mané, R. Monga, S. Moore, D. Murray, C. Olah, M. Schuster, Shlens, B. Steiner, Sutskever, K. Talwar, P. Tucker, V. Vanhoucke, V. Vasudevan, F. Viégas, O. Vinyals, P. Warden, M. Wattenberg, M. Wicke, Y. Yu, and X. Zheng. TensorFlow: Large-scale machine learning on heterogeneous systems, 2015.
H. Bast, D. Delling, A. Goldberg, M. Müller-Hannemann, T. Pajor, P. Sanders, D. Wagner, and R. F. Werneck. Route planning in transportation networks. Algorithm engineering: Selected results and surveys, pages 19-80, 2016.
R. Bauer, D. Delling, P. Sanders, D. Schieferdecker, D. Schultes, and D. Wagner. Combining hierarchical and goal-directed speed-up techniques for dijkstra' ' algorithm. Journal of Experimental Algorithmics (JEA), 15:2-1, 2010.
R. Bellman. On routing problem. Quarterly of Applied Mathematics, 16(1):87-90, 1958.
T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, et al. Language models are few-shot learners, Advances neural information processing systems, 33: 33:1877-1901, 2020.
S. Bubeck, V. Chandrasekaran, Eldan, J. Gehrke, Horvitz, Kamar, Lee, T. Lee, Y. Li,
S. Lundberg, et al. Sparks of artificial general intelligence: Early experiments with gpt-4. 2023.
A. Chowdhery, Narang, J. Devlin, M. Bosma, G. Mishra, A. Roberts, Barham, H. W. Chung,
C. Sutton, S. Gehrmann, et al. Palm: Scaling language modeling with pathways. 2022.
T. H. Cormen, C. E. Leiserson, L. Rivest, and Stein. Introduction to algorithms. MIT press, 2022.
G. B. Dantzig and H. Ramser. The truck dispatching problem. Management Science, 6(1):80-91, 1959.
T. Dao, D. Fu, S. Ermon, A. Rudra, and C. Ré. Flashattention: Fast and memory--fficiint exact attention with io-awareness. Advances in Neural Information Processing Systems, 35:16344-16359 2022.
D. Delling, Sanders, D. Schultes, and D. Wagner. Engineering route planning algorithms. In Algorithmics of large and complex networks: design, analysis, and simulation, pages 117-139. Springer, 2009.
D. Delling, A. V. Goldberg, T. Pajor, and R. F. Werneck. Customizable route planning in road networks. Transp. Sci., 51)556666-51, 2017.
M. Deudon, P. Cournut, A. Lacoste, Y. Adulyasak, and L.-M. Rousseau. Learning heuristics for the tsp by policy gradient. In Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 15th International Conference, CPAIOR 2018, Delft, The Netherlands, June 26-29, 2018, Proceedings 15, pages 170-181. Springer, 2018
E. W. Dijkstra. A note on two problems in connexion with graphs. Numer. Math., 1(1):269-22 1959.
E. W. Dijkstra. A note on two problems in connexion with graphs. In Edsger Wybe Dijkstra: His Life, Work, and Legacy, pages 287-290. 2022.
V.P. P. Dwivedi and X. Bresson. generalization of transformer networks to graphs. 2020.
L. R. Ford. Network flow theory. 1956.
A. V. Goldberg, A simple shortest path algorithm with linear average time, European Symposium Algorithms, pages 230-241. Springer, 2001.

---

A. Graves, G. Wayne, M. Reynolds, T. Harley, I. Danihelka, A. menarejo, E. Grefenstette, Ramalho, Agapiou, et al. Hybrid computing using a neural network with dynamic external memory. Nature, 538(7626):471-444
S. G. Col-
2016.
E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Iransactions on Systems Science and Cyberneticx, 4(2): 100-107, 1968.
W. Huang. P. Abbeel, D. Pathak, and I. Mordatch. Language models as zero-shot planners: Extracting actionable knowledge for embodied agents. International Conference on Machine Learning, pages 91 18-9147, PMLR, 2022.
B. Ibarz, V. Kurin, G. Papamakarios, K. Nikiforou, M. Bennani, Csordás, A. J. Dudzik, M. Bošnjak, A. Vitvitskyi, Y. Rubanova, et al. A generalist neural algorithmic learner. In Learming on Graphs Conference, pages 2-1. PMLR, 2022.
E. Khalil, H. Dai, Zhang, Dilkina, and Song. Learning combinatorial optimization algorithms graphs. Advances in neural information processing systems, 30, 2017.
W. Kool, H. Van Hoof, and M. Welling, Attention, learn to solve routing problems! 2018.
E. Malach. Auto-regressive next-token predictors are universal learners. 2023.
U. Meyer. Single-soure shortest-pathe on arbitrary directed graphs in linear average-cass time, In Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, pages 797-806, 2001.
A. Nowak, S. Villar, A. S. Bandeira, and J. Bruna. A note learning algorithms for quadratic assignment with graph neural networks. 1050:22, 2017.
OpenAl. Gpt-4 technical report, 2023.
OpenStreetMap contributors. Planet dump retrieved from https://planet.omm.org 2017.
N. D. Ratliff, D. Silver, and A. Bagnell. Learning to search: Functional gradient techniques for imitation learning. Autonomous Robots, 27:25-53, 2000..
R. Reddy. Multi-system approach to speech understanding. NADC, Proceedings: Voice Technology for Interactive Real-Time Command (Control Systems Application, 1977.
T. Schick, J. Dwivedi-Yoe Yu, R. Dessi, R. Raileanu, M. Lomeli, L. Zettlemoyer, N. Cancedda, and Scialom. Toolformer: Language models can teach themselves to use tools. 2023.
A. Shimbel. Structure in communication nets. In Proceedings of the symposium on information networks, pages 119-203. Polytechnic Institute of Brooklyn, 1954.
A. K. Sinop, Fawcett, S. Gollapudi, and K. Kollias. Robust routing using electrical flows. In Proceedings of the 29th International Conference on Advances in Geographic Information Systems, pages 282-292, 2021.
L. Sint and D. de Champeaux. An improved bidirectional heuristic search algorithm. Journal of the ACM (JACM), 24 1977.
K. Valmeekam, M. Marquez, S. Sreedharan, and S. Kambhampati. On the planning abilities of large language models eritical investigation. In Thirty-sevntth Conference Neural Information Processing Systems, 2023.
A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, ł.. Kaiser, and I. Polosukhin. Attention all you need. Advances neural information processing systems, 30, 2017.
Veličković, R. Ying, M. Padovano, R. Hadsell, and C. Blundell. Neural execution of graph algorithms. 2019.
O. Vinyals, M. Fortunato, and N. Jaitly. Pointer networks. Advances neural information processing systems, 28, 2015.
12

---

S. Wang, B. Z. Li, M. Khabsa, H. Fang, and H. Ma. Linformer: Self-attention with linear complexity. 2020.
Wei, X. Wang. D. Schuurmans, M. Bosma, Xia, E. Chi, Q. V. Le, D. Zhou, et al. Ohain-of-thoughee prompting elicits reasoning in large language models. Advances in Neural Information Processing Systems, 35:24824 24837, 2022.
E. Welty and C. Phillips. Falling Fruit: Global Collaborative Foraging Map, 2013.
K. Xu, J. Li, M. Zhang, S. S. Du, K.-i. Kawarabayashi, and S. Jegelka. What can neural networks reason about? 2019.
K. Xu, M. Zhang, J. Li, S. Du, K.-i. Kawarabayashi, and S. Jegelka. How neural networks extrapolate: From feedforward to graph neural networks. 2020.
S. Yao, D. Yu, J. Zhao, I. Shafran, T. L. Griffiths, Y. Cao, and K. R. Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. Thirty-seventh Conference on Neural Information Processing Systems, 2023.
S. Yun, M. Jeong, R. Kim, J. Kang, and H. J. Kim. Graph transformer networks. Advances in neural information processing systems, 32, 2019.
M. Zaheer, G. Guruganesh, K. A. Dubey, J. Ainslie, C. Alberti, S. Ontanon, P. Pham, A. Ravula,
Q. Wang, L. Yang, al. Big bird: Transformers for longer sequences. Advances in neural information processing systems, 33:17283-17297, 2020.
13

---

A Additional Experiments
In this section, describe some additional brief experiments into the behavior of autoregressive transformers that are trained on semantic routing tasks.
Test-Set Success Rate (%)
Success Rate by Receptive Field Size
60
40
64
128
256
1024
3516
Receptive Field Size
Figure 7: The grid world semantic routing performance of transformer networks of varying receptive field sizes. The largest possible receptive field size the entire road network, which 3516 16 edges.
Receptive field experiment. In this experiment, we measure how model performance scales with receptive field size. As demonstrated by the strong performance of the mroffof--cnncep model, the greedy approach using receptive fields to make next-edge predictions with only local information is surprisingly effective. performance, we consider train autoregressive transformer models our grid-world benchmark, varying the size of each model's receptive fields. As depicted Figure 7 there are no statistically significant gains in performance from passing in the entire road network (3560 edges) even large subset it (1024 edges); rather, the gains from using a larger receptive field almost entirely disappear even when only small fraction of the graph is included (256 edges).
validate that the use of receptive field does not significantly degrade model
We attribute this to two factors. First, real-world road networks are intentionally designed to be amenable to human drivers, which, like our model, are often learning agents making greedy navigation decisions with only local information; similarly, businesses and facilities can usually be found in predictable places. Second, autoregressive methods have demonstrated significant utility even applications where greedy approaches appear to poor For example, recent findings increasingly indicate that language models-al at scale- are capable of long-term planning despite their greedy nature (Huang et al., 2022: Valmeekam et al. 2023).
Test-Set Routing Metrics for Varying Beam Widths
Beam Search Without Scorer
Beam Search With Scorer
Excess Travel Time (%)
0.30
Query Failure Rate (%)
0.25
0.20
0.15
0.10
0.05
0.00
5
10
20
40
1 5 10
20
40
# Routes in Beam
# Routes in Beam
Figure 8: The grid world performance of an autoregressive transformer under beam-search with varying width.
14

---

Beam search width tuning, This experiment studies how beam search width affects the per- formance of autoregressive semantic routing models. To this end, we implement and train our autoregressive Transformer architecture on our grid-world semantic routing dataset, and evaluate the performance of the beam search inference strategy for varying beam widths. The results, depicted in Figure 8 demonstrate monotone but diminishing returns from increasing beam width.
Verteeeeeeewweeeeeeeeeeeeeeeeeee Accuracy vs Points otlinterest Denstty
Test Test-Set Success Rate (9)
Success Rate by POI Density
0.90
90-
0.96
0.94
85
Painta-af-itterd Dans
0.00D4
0.0004
0.002
0.01
40000 n0000 1200c0 160000 200000
Iterations
POI Density
Figure 9: The next-edge prediction accuracy (left) and waypoint routing success (right) of autoregres- sive transformers on tasks in our grid-world benchmark.
Point-of-interest density experiment. In this experiment, we attempt understand how the difficulty of fulfilling a query affects the difficulty of semantic routing and, in particular, waypoint routing tasks. One should expect that, when points-of-interest are extremely plentiful, waypoint routing reduces to finding the shortest path since the shortest path likely encounters the desired points- of-interest by chance. In this experiment, we train autoregressive transformers models on multiple variants of the grid-world benchmark where we vary the density of points- of-interest on our road network. The results plotted in Figure y indicate that while as expected higher point-of-intee ontertesst density results in higher waypoint routing success rates. However, we surprisingly also observe that a higher point-of-intere apparent contradiction is that -oint-of-interest density indeed makes semantic routing easier, but also increases the number of reasonable routes that may exist; the resulting higher entropy distribution over solution routes results in lower next-edge prediction accuracy. This highlights trend we frequently observed while training autoregressive semantic routing models: relative differences in next-edge accuracy often significantly disagree with relative differences in system performance, such as waypoint routing success.
density makes next-edge prediction more difficult. Our interpretation of this
Tesi-Sel, Success Rate by Embbedding Dim.
Next Vertex Accuracy Network Depth
Next Vartox Accuracy Embesding Dim.
0.98
85-
0.96
80-
0.94
Accuracy
25-
0.92
0:97
0:40
Thuroformee
Embeddiing Dimeralor
(4
255
0.86
3024
L8002D 520020
30000 162000
240000
520000 400000
Iterations
Iterations
Figure 10: The semantic routing performance (left) and next-edge prediction accuracy (middle, right) of autoregressive transformers on our grid-world benchmark. On the left, both embedding dimension and network depth are rescaled. In the middle, only depth is rescaled, On the right, only embedding dimension is rescaled.
A scaling study. This experiment studies how network scale interacts with the performance of autoregressive semantic routing models. To this end, we implement our autoregressive Transformer architecture and train multiple copies of on our grid-world semantic routing dataset, where each copy is configured with a different model capacity. We rescale our model in two directions. We first vary the depth of our network from its default depth of 6 transformer blocks to either 3 or 10 blocks deep. We separately vary the width of our network from its default embedding dimension of 256 to
15

---

either a dimension of 64 and 1024; we follow the canonical scaling strategy for transformer networks and maintain intermediate dimension twice that of embedding dimension. The impact these rescalings next-vertex prediction accuracy is depicted in the two right-most plots of Figure [0] As expected, scale leads to gains in prediction power but these gains quickly saturate. If we rescale our model simultaneously in both directions, we again observe quickly diminishing gains from scale; this result is depicted at the left of Figure [0 and is stated in terms of semantic routing success rate rather than next-edge prediction accuracy. This saturation in gains from scaling up model capacity is one reason to believe that our choice of a simple transformer architecture may not be optimal.
B Open Questions
Longer Trips. Most timesteps in real-world routing tasks are uninteresting and, for example, correspond driving straight on a highway for hundreds of road segments. Typically, this is addressed with hierarchical methods that add "shortcut" edges to summarize common sequences of road segments (Delling et al., 2009). To maintain the simplicity of our proof-of-concept, we only implemented simple alternative of contracting vertices with edges of the same road type, which only reduced effective road segment length by a factor of 2-3. This posed an issue as, in longer routes, next-vertex pairs contain sparser signals as more of the route is trivial, making training more expensive. We accordingly configured our benchmark to restrict navigation tasks to those can be solved in 600 road segments. The benchmark can be made more challenging by increasing this cap, which will require integrating techniques like strategically adjusting the coarseness of road segments in contraction hierarchies (Delling et al. 2009).
Alternatives to Vertex Prediction. Although we implemented an autoregressive approach that unrolls routes from source to destination, autoregressive strategies need not unroll routes in this order. For example, one can unroll routes from the destination, or a hierarchical middle-out fashion. As we found that unrolling source to destination resulted in sufficient good performance by real-world measures, we defer consideration of alternative approaches to future work.
Receptive Field Representation. Our model encodes its receptive field inputs in a simple fashion: concatenate all edges into a sequence and pass the sequence through transformer network so different edges can attend to one another. As our proof-of-concept was not aimed at demonstrating that any particular network architecture is superior, we opted for a basic transformer for simplicity and scalability. We expect that performance improvements can be gained by both enlarging the size of the receptive field and including richer graph metadata (e-g., allowing the model retrieve the reviews of relevant local businesses during route finding), for which graph representation learning methods such as GNNs and graph transformers (Yun et al. 2019 Dwivedi and Bresson 2020) are potentially useful thanks to their ability to combine the information from graph connectivity and metadata through learning.
Efficiency and Scaling, The significant attention received by large language models have spurred number of advancements in implementing autoregressive models. especially transformer networks. to be more efficient and scalable Wang et al. (2020)] Zaheer et al. (2020): Dao et al. (2022). As we have shown that autoregressive transformers are indeed viable solutions to semantic routing, these efficiency gains can similarly be realized by semantic routing applications. In particular, the inference efficiency of our model can greatly improved by adopting architectural modifications like more
efficient attention mechanisms (Dao et al. (022).
C Experiment Details
In this section, we review the hyperparameters for each experiment this paper. In terms of grid world experiments. Table ba describes the hyperparameters for the of density experiment, the beam width experiment and the secondary scoring model ablation experiment; Table desseribe the hyperparameters for the receptive field size experiment; and S Table describe the hyperparameters for the scaling study experiment. The hyperparmeters for the experiment on our benchmark are described in Table[6b] We use "Embedding Dim.", "Intermediate Dim.", and "Attention Heads" to denote the embedding dimension, intermediate dimension, and attention head count of the transformer blocks in the network. Similarly, we use "MLP Layers (Road)" and "Intermediate Dim.
16

---

(Road)" to denote the depth and intermediate dimensions of the multi-layer perceptron blocks used to encode road segment features. The "Receptive Field Size" denotes the number of edges provided in the receptive field input. In the "Learning Rate Schedule" key, "Cosine" denotes that cosine one-cycle learning rate schedule is used. The "Seeds" key refers to the number of random seeds the experiment is performed on. Experiments performed in this paper were conducted using computer resources on Google Cloud. Approximately 10,000 CPU hours were used to generate training data from the benchmark software. The experiments described in Appendix were performed GPU cluster for approximately 1,000 GPU hours. The experiments described in Section were performed on GPU cluster for approximately 20,000 GPU hours.
Hyperparameter
Values
Datapoints (# Routes)
million 0.0001
million 0.0001
million 0.0001 0
million 0.0001
million 0.0001 0
million 0.0001
Learning Rate
L2 Weight Decay
0
0
0
Dropout
Batch Size
1024
1024
1024
1024
128
128
Iterations
200,000
200,000
200,000
200,000
400,000
400,000
Seeds
5
5
5
5
5
Learning Rate Schedule
Cosine
Cosine
Cosine
Cosine
Cosine 1024
Cosine
Receptive Field Size
8
64
128
256
3516
Attention Heads
4
4
Embedding Dim.
256
256
256
256
256
256
Intermediate Dim.
512
512
512
512
512
512
Transformer Blocks
6
6
6
6
Intermediate Dim. (Road)
512
512
512
512
512
512
MLP Layers (Road)
2
2
Table 3: Hyperparameters for the receptive field size experiment on the grid-world dataset.
Hyperparameter
Values million 0.0001
Datapoints Routes)
million 0.0001
million 0.0001
million 0.0001
Learning Rate
L2 Weight Decay
0
0
Dropout
Batch Size
1024
1024
1024
1024
Iterations
400,000
400,000
400,000
400,000
Seeds
5
Learning Rate Schedule
Cosine
Cosine
Cosine
Cosine
Receptive Field Size
256
256
256
256
Attention Heads
4
4
4
4
Embedding Dim.
256
1024
256
Intermediate Dim.
512
128
2048
512
Transformer Blocks
6
6
10
Intermediate Dim. (Road)
512
128
2048
512
MLP Layers (Road)
2
Table 4: Hyperparameters for the scaling study experiment on the grid-world dataset.
17

---

Hyperparameter
Datapoints (# Routes)
million 0.0001
4 million 0.0001
million 0.0001
Learning Rate
L.2 Weight Decay
0
Dropout
Batch Size
1024
1024
1024
Iterations
400,000
400,000
400,000
Seeds
5
Learning Rate Schedule
Cosine
Cosine
Cosine
Receptive Field Size
256
256
256
Attention Heads
4
Embedding Dim.
256
64
1024
Intermediate Dim.
512
128
2048
Transformer Blocks
3
10
Intermediate Dim. (Road)
512
128
2048
MLP Layers (Road)
2
2
Table 5: Hyperparameters for the scaling study experiment on the grid-world dataset (continued),
Hyperparameter
Values
Hyperparameter
Values
Datapoints (# Routes)
million
Datapoints (# Routes)
million
Learning Rate
0.0001
Learning Rate
0.00003
1.2 Weight Decay
I.2 Weight Decay
Dropout
Dropout
Batch Size
1024
Batch Size
1024
Iterations
200,000
Iterations
600,000
Seeds
Seeds
Learning Rate Schedule
Cosine
Learning Rate Schedule
Cosine
Receptive Field Size
256
Receptive Field Size
512
Attention Heads
4
Attention Heads
8
Embedding Dim.
256
Embedding Dim.
1024
Intermediate Dim.
512
Intermediate Dim.
2048
Transformer Blocks
Transformer Blocks
Intermediate Dim. (Road)
512
Intermediate Dim. (Road)
2048
MLP Layers (Road)
MLP Layers (Road)
2
(a) Hyperparameters for grid-world experiments varying point-of of onteretest density, beam width, and the scoring model.
(b) Hyperparameters for the proof-of-concept ex- periment on our main benchmark, i.c., the results in Table 2
Hyperparameter
Values
Datapoints
5,000
Learning Rate
0.0005
L2 Weight Decay
0.01
Batch Size
256
Iterations
20,000
Intermediate Dim.
64
Hidden Layers
Activation
GELU
(c) Hyporparameters for the secondary scor- ing model in all experiments.
Table 6: Additional hyperparameters.
18

---

D Example of Predicted Routes
This section provides eight randomly sampled examples of the semantic routing tasks in our bench-
mark. T'esse are depicted in Figure 11 Figure 12 Figure T3
and Figure 14
Find me the nearest supermerket to get ingredients for dinner and also suggest place for quick lurch. Avoid local reeds when possible
Can you guide me lu nearby grocery stores ta gel. dinner ingredients, slation to refuel cat, and stores selling energy dhinks?
Del
Vending marhine
Supermerbet
Butcher
Conuect POre
Coeengroee
Figure 11: Randomly sampled semantic routing tasks from our benchmark, and their optimal routes (orange).
19

---

Suggest supermo fict whore can buy nnner ingrodients and olso dessert.
Deli
Factry
Bakery
Ice cream
Rxpermariett
Buticher
Cafe
Greangrocer
Start
Erd
Mind finding nearby pharmacy?
Pharmacy
Start
End
Figure 12: Randomly sampled semantic routing tasks from our benchmark, and their optimal routes (orange).
20

---

the fostest way snack store a place, avoiding highways.
Del
Car parts
Vending machine
Supermariet
Food cou't
Converience
Tast food
Start
End
Can you guide nearby grocery stores dinner ingredients, gas station to refuel and stores selling energy dhinks?
Del
Vending machine
Susermarket
Butcher
Fuol
Convonience ence
Groengrocer
Start
End
Figure 13: Randomly sampled semantic routing tasks from our benchmark, and their optimal routes (orange).
21

---

Recommend multi stop adventure around town, with all destinations within a 20 mi-umnnuee drive.
Garres
Video garmes
Amuseeeent arcate
Tays
Start
End
stop shops buy ingredients, snacks,
get ges.
Del
Vending machine
Suocrmarket
Butcher
Fucl
Convericnce
Groengrocer
Start
Endl
Figure 14: Randomly sampled semantic routing tasks from our benchmark, and their optimal routes (orange).
22

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Yes, the abstract and introduction clearly state the main two contributions
of the paper: (1) a benchmark for semantic routing (Section 2) and (2) proof-of-concept
demonstration that autoregression can overcome scaling challenges (Section 3
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer:
[Yes]
Justification: The primary limitation of our benchmark is that, as an automated benchmark, it relies on an automated system for scoring solutions rather than human raters; this is discussed in Section along with the note that the benchmark' 's scoring system nonetheless corresponds to reasonable high-quality solutions. The limitations of our proof-of-concepp model are described extensively in our discussion of open questions and future directions in Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
23

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
Justification: The paper does not include theoretical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof's provided in appendix supplemental material. Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Ys]]
Justification: Experiment details including hyperparameters are provided in detail in Sec- tion 3.3 and Appendix C
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should possible for other researchers have some path reproducing verifying the results.

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: All data and code described in this paper, for both our benchmark and proof- of-concept, are available open- open-source under an Apache 2.0 license.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co)
httpi//guuiies/ooeeubbbiiieeee sossssboissioooocccrcooooo for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
Cooeeoooissssseeeeeecee ssioiiolicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: All training and test details are described in the tables of Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[Yes]
Justification: Standard error is provided in the main results of Table
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
25

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Computer resource usage, though estimated and not known exactly, described in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental rums well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
The Code of Ethics is conformed to.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
This paper focuses on semantic routing (e.g., navigation services like Google Maps), application that does lend itself malicious via disinformation, surveil- lance, discrimination, privacy violations, or security risks.
Justification:
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
26

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [Yes]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: The original creators of both data and software used in the paper are cited.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
27

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The released software is accompanied with documentation and example Python notebooks to facilitate usage.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
28


Reviews:
[{"review_id": "bhvDx9Bmou", "reviewer": "Reviewer_oN8k", "summary": "This paper collects a large-scale benchmark for semantic routing based on road networks of US cities with rich metadata, and 1) shows that the benchmark is challenging for previous methods due to its scale and complex user preferences 2) proposes a learning-based method, where a transformer-based model is trained to autoregressively predict the next plausible road segment based on the query, the current partial route and the neighborhood (receptive field) around the wavefront. The proposed method achieves non-trivial performances, opening up the space for developing stronger learning-based approaches for semantic routing.", "questions": "See above.", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The problem of semantic routing is practically useful and technically interesting. The collected benchmark takes a step toward developing systems that can handle problems of realistic difficulty levels.\n\n- The proposed learning-based approach, architecture, and metadata encoding schemes are novel and show impressive transferability to routing problems in unseen cities.\n\n- Further experiments and ablations (though most are in the Appendix) on receptive field size, scoring models, etc. are interesting and could provide insights into future developments in the community.", "weaknesses": "- There is a lack of some details on benchmark construction and quantitative statistics. For example, in line 232, how is the \"human writing\" of queries done? Is it through crowdsourcing via, e.g., Amazon Mechanical Turk? In line 167, \"The majority of tasks in our benchmark involve a variant of waypoint routing:...\" how much is the \"majority\"? Similarly for \"Another subset of tasks ...\" in line 181. These statistics affect the way people think about the examples and the performance here.\n\n- From lines 267-271, it can be seen that the ground-truth optimal routes can actually be found via brute-force search using classical methods in 0.3 CPU hours per route on average - in some sense isn't this suggesting that the problems aren't that difficult after all? Is it possible to do parallelization (this should clearly be possible for the brute-force approach) to speed up the solving process? If the route could be somehow produced in a reasonable time, there seems to be less need for learning-based approaches which have much less transparency and guarantees.\n\n- Some minor ones:\n  - The evaluation metric is very tricky as it's mostly based on human heuristics. But I think this is more of an issue of the nature of the task (similar to how it's hard to design reward functions in reinforcement learning). Would be great if it is possible to collect some actual paths that humans prefer to enable learning of a good metric.\n  - The writing overall could be improved. For example, the description of the collected benchmarks and the results (baselines, proposed methods) are quite scattered.\n  - In the proposed architecture, for the part that encodes the candidate edges, since the model is a decoder transformer, there are unnecessary biases from the orderings of the candidates. May be good to fix this.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your feedback and address your questions below.\n\n**Details on benchmark construction.**\n\nWe appreciate your suggestions on benchmark details that should be elaborated on. We agree these details would be clarifying, and will incorporate the below points—along with additional context—into Section 2.2 of our revision:\n\nThe 1,000+ seed queries were written by manually taxonomizing common road situations (e.g. ran out of gas, passenger spilled drink in backseat), and writing a single representative query for each situation in the taxonomy. This taxonomical approach ensures the final dataset provides strong coverage of recorded use-cases. Since this process requires non-trivial domain knowledge, it was performed by the authors and affiliated assistants rather than through a crowdsourcing platform like Mechanical Turk.\n\nTo form our benchmark’s training dataset, we collected data on a mixture of tasks where 80% of datapoints correspond to waypoint routing tasks. However, our benchmark returns separate performance statistics for waypoint routing and trip planning tasks (e.g., see the decomposition of Table 2), rather than returning summary statistics for mixtures of tasks.\n\n**Brute-force search complexity.**\n\nThe 0.3 CPU hours needed to brute-force a solution is a non-trivial amount of computation for a learning-based method to match, especially since the brute-force algorithm is given unfair access to a structured representation of the user queries that obviates the need to parse the queries in their original natural language form. For this reason, we believe that the benchmark is still a formidable challenge for learning-based methods, as demonstrated in Table 2.\n\nRegarding whether brute-force methods suffice for real-world semantic routing applications, as we elaborate on L54-L59, the motivation for exploring the viability of learning-based semantic routing systems is less about facilitating an otherwise computationally intractable task and more about exploring a scalable approach to supporting diverse natural language queries that require processing large volumes of rich graph metadata. The latter is impractical to scale to real-world application if one's approach is engineering an ensemble of brute-force methods to cover all (or even most) query types.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QiDKSgWVU9", "reviewer": "Reviewer_u4su", "summary": "The paper proposes an extended semantic routing planning task, which includes user queries expressed in natural language. The author released a large-scale dataset for this task, and proposed a method of using autoregressive models instead of graph-related methods for route planning, which has a significant performance improvement on the benchmark.", "questions": "1. How are different input components identified in the autoregressive model?\n2. Why is there such a large performance gap between Errands and Locations in Table 2?\n3. Beam search has been proven useful in language models. Since only a small receptive field is input into the model in this task, will beam search improve performance?", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This task is very interesting. Setting waypoints through natural language in route planning has a great demand in real life;\n2. A large dataset related to the task;\n3. The novel autoregressive method can be regarded as an extension of the multimodal large model.", "weaknesses": "1. I have concerns about the evaluation metrics. If the goal is to plan a path that meets user requirements, then the evaluation should consider the length difference between the planned path and the optimal path, as well as the delay in planning methods under this premise, rather than using user satisfaction as the final evaluation metric.\n2. It is unclear whether the annotated labels in Figure 2 are provided to the method or only used for the evaluator. If not provided, the baseline method needs a more detailed description of how these natural language parts are utilized.\n3. Based on points 1 and 2, is the poor performance of the baseline method due to inadequate adaptation to this new task? For example, reaching points of interest should be considered a prerequisite, and then the shortest path should be searched under this prerequisite, rather than checking if points of interest are included in the shortest path.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your feedback and address your questions below.\n\n**How are different input components identified in the autoregressive model?**\n\nWe follow the standard practice of using categorical encodings. That is, in addition to adding a position encoding to each token in the input sequence, we also add a categorical encoding to each token denoting what type of input component the token belongs to.\n\n**Why is there such a large performance gap between Errands and Locations in Table 2?**\n\nErrands correspond to tasks that can be fulfilled by going to multiple possible points-of-interest; for example, water bottles can be found at both gas stations and grocery stores. Hence, simpler solution routes usually exist. However, location tasks correspond to tasks that can only be fulfilled by going to a specific point-of-interest, which makes the tasks more challenging.\n\n**Will beam search improve performance?**\n\nYour intuition is correct and, for the reasons you noted, we do already use beam search in the paper. For example, the reported figures in Table 2 are using beam search. We found that beam search indeed provided a significant boost in performance, which we verified through the ablation experiment plotted in Figure 9.\n\n**Some additional clarifications.**\n\n1. The “excess penalty” metric generated by our benchmark software does already explicitly factor in travel time. Specifically, “excess penalty” is computed as the excess travel time of the predicted route versus the optimal route, where travel time is scaled up by a factor of 5x along road segments that the user asked to avoid (see Figure 2 caption). We appreciate your highlighting this potential point of confusion and will revise Line 314-318 to be more clear on this point.\n\n2. The annotated labels in Figure 2 are for the benefit of those reading the paper; the autoregressive model only has access to the natural language form of the queries. The annotated labels are, however, provided to the evaluator, and are also given to the baseline methods, giving the baselines an unfair advantage against our autoregressive model. We will add this note to Line 204 in our revision.\n\n3. The baseline methods already consider reaching points-of-interest as a prerequisite (L201, L203). The difficulty is that searching under these prerequisites is expensive.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bLGCR7aM1e", "reviewer": "Reviewer_o9bU", "summary": "This paper releases a large-scale routing dataset consisting of diverse multi-objective navigation queries expressed via natural languages on the richly annotated road networks of US cities. They also propose an autoregressive baseline method based on a standard transformer network and show that the baseline is a powerful method on the task.", "questions": "1. The introduction section says the dataset has 1 million queries. What is the precise composition of these queries? How many queries are written by humans and how many are augmented by language models? How many queries are multi-objective, i.e. merged from multiple queries?", "limitations": "Section B only discusses the limitation of the proposed baseline, not the dataset.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. The released dataset has a training set along with the test set, making it easy to develop learning-based algorithms on the dataset. The authors also provide an automatic evaluation metric based on human-labeled interpretations of all the queries, which enables automatic evaluation and (possible) reinforcement learning on the dataset\n2. The baseline based on the transformer decoder shows promising performance on the benchmark, showing the potential of learning-based methods on the problem.", "weaknesses": "1. Originally there are only 1000+ distinct queries, which are augmented into 10,000+ natural language variations by a language model. Multi-objective queries are formed by randomly merging multiple queries and rephrased by the language model. It is not sure whether the augmentation and the rephrasing of the language model are accurate enough to keep the original meanings. This is important since the structured interpretation used for automatic evaluation is based on the original queries.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your feedback and address your remaining questions below.\n\n**Composition of query dataset.**\n\nWe appreciate your suggestion for clarifying this point in the benchmark’s construction. We agree that clarifying this point is important, and will incorporate the following answer—along with additional context—into Section 2.2 of our revision:\n\nDetails on the composition of the query dataset can be found on L230-L237. The 1,000+ queries were written by manually taxonomizing common road situations (e.g. ran out of gas, passenger spilled drink in backseat), and writing a single representative query for each situation in this taxonomy. A language model was then tasked with finding different ways in which users might write queries in each situation, resulting in 10,000+ variations. The complete dataset was then formed by merging combinations of these queries. As noted on L188-L189, on average, each query in our dataset is the result of merging 1.8 different queries.\n\n**Query dataset augmentation.**\n\nWe believe that, in the absence of tens to hundreds of human experts, the use of a language model to augment the queries is a viable (and practical) approach to developing a large-scale weakly supervised dataset. The queries and their structured interpretations are available in the benchmark for manual inspection. Moreover, a random subset of the query dataset was manually spot-checked for correctness. We agree these points are worth clarifying and will add these notes at Line 237.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies “semantic route planning” or “semantic routing”, which aims to produce routes in response to rich queries that specify various criteria and preferences, and proposes a learning-based approach by formulating the problem as next step prediction. To facilitate further research, the paper releases a large-scale publicly-licensed benchmark for semantic routing, which consists of real-world multi-objective navigation problems (which are expressed in natural language) on the richly annotated road networks of US cities. Overall the reviewers agree that the problem being addressed in this paper is very interesting, the dataset released will be very useful for future research, and the results of the proposed method are promising. There are some confusions related to details of the benchmark construction and existing approaches being “intractable” or “non-trivial” (which might be due to some places in the paper saying “in addition to being intractable with existing approaches to semantic routing”), so the writing of the paper could be improved. Overall, my recommendation is accept, and that the authors should follow the discussions to refine the paper.
Decision: Accept (poster)