# RouteGoT: Node-Adaptive Routing for Cost-Efficient Graph of Thoughts Reasoning

arXiv: https://arxiv.org/abs/2603.05818 · HTML: https://mlsanity.com/paper/2603.05818/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 23 of its 56 references that are in the map.
- First posted on arXiv 6 Mar 2026.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Builds on (most cited first, 23 of 23)

- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Least-to-Most Prompting Enables Complex Reasoning in Large Language Models](https://mlsanity.com/paper/2205.10625/) (2022)
- [Compositional Semantic Parsing on Semi-Structured Tables](https://mlsanity.com/paper/1508.00305/) (2015)
- [TabFact: A Large-scale Dataset for Table-based Fact Verification](https://mlsanity.com/paper/1909.02164/) (2019)
- [Towards Reasoning Era: A Survey of Long Chain-of-Thought for Reasoning Large Language Models](https://mlsanity.com/paper/2503.09567/) (2025)
- [Hybrid LLM: Cost-Efficient and Quality-Aware Query Routing](https://mlsanity.com/paper/2404.14618/) (2024)
- [Harnessing Multiple Large Language Models: A Survey on LLM Ensemble](https://mlsanity.com/paper/2502.18036/) (2025)
- [A Survey on Large Language Models for Mathematical Reasoning](https://mlsanity.com/paper/2506.08446/) (2025)
- [A Survey of Large Language Model Agents for Question Answering](https://mlsanity.com/paper/2503.19213/) (2025)
- [MoreHopQA: More Than Multi-hop Reasoning](https://mlsanity.com/paper/2406.13397/) (2024)
- [Route to Reason: Adaptive Routing for LLM and Reasoning Strategy Selection](https://mlsanity.com/paper/2505.19435/) (2025)
- [On the Diagram of Thought](https://mlsanity.com/paper/2409.10038/) (2024)
- [Adaptive Graph of Thoughts: Test-Time Adaptive Reasoning Unifying Chain, Tree, and Graph Structures](https://mlsanity.com/paper/2502.05078/) (2025)
- [Route-and-Reason: Scaling Large Language Model Reasoning with Reinforced Model Router](https://mlsanity.com/paper/2506.05901/) (2025)
- [Scaling Graph Chain-of-Thought Reasoning: A Multi-Agent Framework with Efficient LLM Serving](https://mlsanity.com/paper/2511.01633/) (2025)
- [Putting on the Thinking Hats: A Survey on Chain of Thought Fine-tuning from the Perspective of Human Reasoning Mechanism](https://mlsanity.com/paper/2510.13170/) (2025)
- [LLMTM: Benchmarking and Optimizing LLMs for Temporal Motif Analysis in Dynamic Graphs](https://mlsanity.com/paper/2512.22266/) (2025)
- [Breaking Model Lock-in: Cost-Efficient Zero-Shot LLM Routing via a Universal Latent Space](https://mlsanity.com/paper/2601.06220/) (2026)
- [GraphIF: Enhancing Multi-Turn Instruction Following for Large Language Models with Relation Graph Prompt](https://mlsanity.com/paper/2511.10051/) (2025)
- [CONCUR: A Framework for Continual Constrained and Unconstrained Routing](https://mlsanity.com/paper/2512.09386/) (2025)

## Abstract (arXiv)

Large Language Models (LLMs) excel at multi-step reasoning, yet increasing the structural complexity of inference does not consistently improve system-level returns. Methods such as Tree of Thoughts (ToT), Graph of Thoughts (GoT), and Adaptive Graph of Thoughts (AGoT) can boost accuracy on some benchmarks, but often introduce substantial overhead in token consumption and latency, and their gains can be unstable across task distributions-sometimes underperforming simpler Chain-of-Thought (CoT) or direct input-output prompting (IO). We attribute this inefficiency to stage-wise and node-wise heterogeneity inside GoT-style reasoning pipelines: high-quality planning and final synthesis are globally coupled and typically benefit from strong models, whereas many intermediate subtasks are localized and can be solved accurately by lighter models with far fewer tokens. Motivated by these observations, we propose RouteGoT, a budget-controllable, node-adaptive routing framework for graph-structured reasoning. RouteGoT performs in-graph routing by prioritizing strong models for planning and synthesis, while dynamically allocating lightweight models and cost-effective strategies to leaf subtasks based on predicted difficulty. It further integrates explicit budget constraints into a global inference scheduler to control graph expansion under a user-specified token budget, enabling predictable performance-cost trade-offs. Experiments across reasoning, retrieval, and multi-hop QA benchmarks show that RouteGoT matching or improving accuracy while substantially reducing token usage; specifically, it achieves an average 8.1 percentage points accuracy improvement and 79.1% output token reduction compared to AGoT. Furthermore, RouteGoT outperforms existing routing baselines by maintaining a superior cost-accuracy trade-off, demonstrating improved robustness under varying budget targets and tasks.