Organizations: School of New Media and Communication, Tianjin University, Tianjin, China · School of Computer Science and Engineering, Beihang University, Beijing, China · Shanghai Jiao Tong University, Shanghai, China
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.
Figures & tables
Figure 1. Cost-Accuracy Trade-off. Background colors distinguish low-cost (light green) from high-cost (light red) regions based on the median token consumption across all methods.
Figure 2. Overview of the RouteGoT framework.
Dataset
Count
Dataset
Count
Dataset
Count
2WikiMultihopQA ( Ho et al., 2020 )
4,000
WTQ ( Pasupat and Liang, 2015 )
2,000
GSM8K ( Cobbe et al., 2021 )
250
MuSiQue ( Trivedi et al., 2022 )
3,250
TabFact ( Chen et al., 2019 )
2,000
SQuAD ( Rajpurkar et al., 2016 )
250
MATH ( Hendrycks et al., 2021 )
3,000
StrategyQA ( Geva et al., 2021 )
1,500
SVAMP ( Patel et al., 2021 )
250
QASC ( Khot et al., 2020 )
2,500
CSQA ( Talmor et al., 2019 )
750
OpenBookQA ( Mihaylov et al., 2018 )
250
Table 1. Composition of the Router Training Dataset.
Method
GPQA
HotpotQA
MoreHopQA
HybridQA
Game of 24
Cross.(Let)
Cross.(Wrd)
Avg. Δ
Acc
Tok.
Acc
Tok.
Acc
Tok.
Acc
Tok.
Acc
Tok.
Acc
Tok.
Acc
Tok.
Acc
Tok.
Reasoning Baselines
IO
41.4
7
81.0
11
26.0
9
67.0
21
27.0
380
22
467
6.0
467
+23.7
+1116.2%
CoT
63.1
4,965
86.0
431
68.0
727
84.0
476
58.0
1,948
22.2
13,201
13.5
13,201
+6.2
-52.6%
ToT
44.9
9,077
60.0
3,748
61.0
3,860
91.0
3,538
20.0
2,855
12.4
9,563
2.1
9,563
+20.7
-60.8%
GoT*
59.6
9,468
87.0
812
73.0
814
88.0
1,635
72.0
17,396
22.4
11,674
6.5
11,674
+3.9
-69.0%
Table 2. We report Accuracy (%) and Average Output Tokens. All reasoning baselines utilize Qwen3-30B as the backbone. Router baselines dynamically select from a model pool comprising {Qwen3-4B, 8B, 30B}. The last two columns ( Avg. Δ ) represent the average improvement of RouteGoT compared to the specific baseline across all seven tasks.
Dataset
GoT*
AGoT
RTR
RouteGoT
GPQA
97.01
42.69
31.70
32.64
Game of 24
98.20
112.63
62.13
60.93
Crosswords
116.03
119.00
47.00
37.09
HybridQA
38.66
42.83
10.80
12.93
MoreHopQA
70.38
17.72
7.27
11.79
HotpotQA
22.89
23.93
5.46
6.95
Table 3. Per Question Inference Time Comparison (Seconds).
Figure 3. Performance comparison under varying computational budgets on GPQA.
Figure 4. Evaluation of Routing Mechanism (RQ3). (a) Comparison of decision quality metrics (Regret, Utility). (b) Distribution of node complexity across different methods. (c) Performance analysis of the cost predictor.
Figure 5. Case study on a GPQA biomedical task. RouteGoT dynamically routes nodes based on semantic triggers. Red nodes represent Decompose actions for high-level planning, blue nodes indicate CoT for relational analysis, and green nodes denote IO for efficient pruning. Compared to AGoT, RouteGoT avoids redundant sub-graph expansion on distractors, identifying the correct answer with substantially reduced token consumption.
Method
HotpotQA
MoreHopQA
HybridQA
Acc (%)
Tokens
Acc (%)
Tokens
Acc (%)
Tokens
RouteGoT
88.0
592
77.0
665
91.0
700
w/o BP
86.0
2438
78.0
2649
89.0
1634
w/o BP + PN
78.0
2020
70.0
2951
83.0
1722
Table 4. Comparison of RouteGoT against variants with ablated components.
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Method
GPQA
HotpotQA
MoreHopQA
HybridQA
Game of 24
Cross.(Let)
Cross.(Wrd)
Acc
In.Tok
Acc
In.Tok
Acc
In.Tok
Acc
In.Tok
Acc
In.Tok
Acc
In.Tok
Acc
In.Tok
Reasoning Baselines
IO
41.4
250
81.0
1,685
26.0
442
67.0
10,462
27.0
125
22.0
179
6.0
179
CoT
63.1
247
86.0
1,682
68.0
439
84.0
10,239
58.0
123
22.2
182
13.5
182
ToT
44.9
4,928
60.0
2,416
61.0
2,027
91.0
12,355
20.0
23,334
12.4
790
2.1
790
GoT*
59.6
16,826
87.0
10,864
73.0
4,275
88.0
65,134
72.0
19,814
22.4
13,597
6.5
13,597
Appendix
Table 5. Detailed evaluation results reporting Accuracy (%) and Average Input Tokens . All reasoning baselines utilize Qwen3-30B. Router baselines select from the {Qwen3-4B, 8B, 30B} pool. This table complements the main results by highlighting the context processing overhead across different tasks.
Large language models (LLMs) can achieve strong reasoning performance with sufficient computation, but they do not inherently know how much computation a task requires. We study budgeted inference-time reasoning for multiple problems under a strict global token constraint and formulate it as an Ordered Stochastic Multiple-Choice Knapsack Problem (OS-MCKP). This perspective highlights a meta-cognitive requirement---anticipating problem difficulty and allocating computation strategically. We propose ROI-Reasoning, a two-stage framework that endows LLMs with intrinsic, budget-aware rationality. First, Meta-Cognitive Fine-Tuning teaches models to predict reasoning cost levels and decide whether a problem is worth attempting before generation. Next, Rationality-Aware Reinforcement Learning optimizes sequential decision making under a hard token budget, allowing models to learn long-horizon allocation strategies. Experiments across mathematical reasoning, multiple-choice question answering, and code generation show that ROI-Reasoning improves scores and generally reduces reference-order regret under tight budgets, with up to a 417% relative score improvement over the strongest same-backbone baseline in mathematics.
Muyang Zhao, Chunhao Tian, Qi Qi +1
Gaoling School of Artificial Intelligence, Renmin University of China, Beijing, China
Inference-time computation has greatly enhanced the performance of large language models (LLMs) on challenging reasoning tasks, but this strategy can incur high inference costs. One solution is to route intermediate chain-of-thought (CoT) states to language models of different sizes; however, existing approaches rely on handcrafted routing strategies that limit performance, or on training large process reward models that may be infeasible in many applications. We formulate stepwise model routing as a constrained decision-making problem, which we solve by training a small control policy using reinforcement learning in conjunction with threshold calibration to tune the performance-efficiency tradeoff. We validate our method on three math benchmarks (GSM8K, MATH500, and OmniMath) on both open and closed models. Our method consistently improves the accuracy-cost tradeoff compared to handcrafted approaches, while achieving a comparable tradeoff to methods that require training large process reward models.
Wenwen Si, Insup Lee, Osbert Bastani
Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA 19104, USA
Multi-agent LLM systems coordinate through natural-language messages that consume 40--60% of their token budget. Replacing these with structured graphs reduces cost but fails on tasks requiring adaptive reasoning. We propose Routed Graph Handoff, where a lightweight LLM router (155 tokens, 0.15% overhead) selects between a typed dependency graph and natural language for each delegation. On four benchmarks (1,050+ trajectories), the routed system matches or exceeds NL-only on every task: +12.7,pp on τ-retail at 3.2× compression (p<0.01), +8.7,pp on BrowseComp at 2.2× compression (p<0.05), and parity on BFCL and AppWorld. Without the router, graph-only delegation regresses 14.6,pp on AppWorld; the router eliminates this at near-zero cost. A graph-aware executor prompt is required: the same schema without interpretation guidance yields no gain. An oracle analysis reveals 8.6,pp of additional headroom, motivating execution-time adaptive routing as future work.