Research map / Graph learning / Graph algorithms and clustering
Semantic Routing via Autoregressive Modeling
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces a large-scale benchmark for semantic routing on US road networks with natural-language queries, and shows a standard decoder-only transformer trained autoregressively to predict next edges (with a 512-edge receptive field) achieves non-trivial success rates.
Problem
Semantic route planning requires satisfying rich, natural-language multi-objective user queries over large road graphs, which classical shortest-path methods with cost modifiers handle poorly and graph learning methods struggle to scale to (10,000+ vertices).
Approach
Decompose route generation into autoregressive next-edge predictions conditioned on a small local receptive field around the route head, so a standard transformer can scale to large road graphs; paired with a public benchmark built on OpenStreetMap data and automated scoring.
Key results
- Autoregressive transformer achieves 92.0% success on waypoint routing (errands) and 38.0% on locations, 34.0% on mixed, and 68% on trip planning on the Berkeley holdout.
- Classical cost modifiers achieve 0% and electrical flows (4096 routes) achieve 1.3% waypoint routing success rate.
- Receptive field experiments show increasing receptive field beyond 256 edges yields no statistically significant gains on the grid world.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use an autoregressive transformer instead of cost modifiers | Semantic routing · Waypoint routing | success rate: 0 % ± 0% -> 92.0% ± 3.7% | Helped |
| Use an autoregressive transformer instead of electrical flows (4096 routes) | Semantic routing · Waypoint routing | success rate: 1.3% ± 1.3% -> 92.0% ± 3.7% | Helped |
| Add a secondary scoring model to select among beam-search candidate routes (ablation) | Autoregressive transformer · Grid world | semantic routing performance | Helped |
| Increase receptive field size (ablation) | Autoregressive transformer · Grid world | semantic routing performance | No clear effect |
| Increase beam-search width (ablation) | Autoregressive transformer · Grid world | semantic routing performance | Helped |
| Increase point-of-interest density (ablation) | Autoregressive transformer · Grid world | waypoint routing success | Helped |
| Increase point-of-interest density (ablation) | Autoregressive transformer · Grid world | next-edge prediction accuracy | Hurt |
| Increase transformer model capacity (ablation) | Autoregressive transformer · Grid world | next-edge prediction accuracy | Helped |
| Increase transformer model capacity (ablation) | Autoregressive transformer · Grid world | semantic routing success rate | Helped |
Surprising findings
- Higher point-of-interest density makes next-edge prediction harder even though waypoint routing success improves.
- Larger receptive fields yield no significant gains, suggesting local information suffices for greedy next-edge decisions.
Limitations
- Automated scoring system rather than human raters for evaluating routes.
- Benchmark restricted to routes solvable within 600 road segments; longer trips are not handled well by the simple approach.
- Greedy autoregressive decoding and simple transformer architecture may not be optimal; scaling gains saturate.
Experimental setup
Datasets: OpenStreetMap road networks and points-of-interest semantic routing benchmark training set (3 million route pairs)
Benchmarks: Semantic routing benchmark (waypoint routing, trip planning; Berkeley holdout) grid-world semantic routing testbed
Metrics: success rate median excess penalty median total travel time next-edge prediction accuracy
Baselines: cost modifiers electrical flows
Builds on: transformer autoregressive language modeling cost modifiers electrical flows
Closest papers by meaning
- ALPINE: Unveiling The Planning Capability of Autoregressive Learning in Language Models (NeurIPS 2024 · similarity 0.85)
- Routing Experts: Learning to Route Dynamic Experts in Existing Multi-modal Large Language Models (ICLR 2025 · similarity 0.85)
- Discrete Diffusion Models Exploit Asymmetry to Solve Lookahead Planning Tasks (NeurIPS 2026 · similarity 0.85)
- Hierarchical Semantic-Augmented Navigation: Optimal Transport and Graph-Driven Reasoning for Vision-Language Navigation (NeurIPS 2025 · similarity 0.84)
- Models Under SCOPE: Scalable and Controllable Routing via Pre-hoc Reasoning (ICML 2026 · similarity 0.84)
- Lookahead Routing for Large Language Models (NeurIPS 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.