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.