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

• URL: http://arxiv.org/abs/2603.05818v1
• Date: Fri, 06 Mar 2026 02:03:06 GMT
• Title: RouteGoT: Node-Adaptive Routing for Cost-Efficient Graph of Thoughts Reasoning
• Abstract summary: Methods such as Tree of Thoughts (ToT), Graph of Thoughts (GoT), and Adaptive Graph of Thoughts (AGoT) can boost accuracy on some benchmarks.<n>We propose RouteGoT, a budget-controllable, node-adaptive routing framework for graph-structured reasoning.
• Score: 12.010368435895627
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Thinking Economically: A Hierarchical Framework for Adaptive-Complexity Reasoning in LLMs [36.73612668202756]
  HAB learns step-specific token budgeting signals from PPL-derived step comparisons.<n>Experiments on GSM8K and MATH500 show that HAB not only surpasses standard CoT in accuracy but also reduces token usage.
  arXiv  Detail & Related papers  (2026-05-31T11:20:00Z)
• AdaptR1: Reinforcement Learning Based Adaptive Interleaved Thinking in Multi-hop Question Answering [76.52199013231484]
  We introduce AdaptR1, a Reinforcement Learning (RL) based framework for adaptive interleaved thinking in multi-hop Question Answering (QA)<n>Under the Graph-R1 setting, AdaptR1 reduces average think tokens by 69.71%, with a 90.35% reduction on HotpotQA.<n>Our analysis reveals that overthinking in multi-hop reasoning is not uniformly distributed but occurs predominantly during the initial planning stages.
  arXiv  Detail & Related papers  (2026-05-29T09:34:45Z)
• CoTJudger: A Graph-Driven Framework for Automatic Evaluation of Chain-of-Thought Efficiency and Redundancy in LRMs [46.51345659234088]
  Large Reasoning Models (LRMs) have demonstrated strong performance by producing extended Chain-of-Thought traces before answering.<n>Existing evaluations largely emphasize final accuracy or coarse token counts, and lack automated tools to separate essential logic from structural redundancy.<n>We introduce CoTJudger, a graph-driven framework that quantifies reasoning efficiency by converting free-form CoTs into directed dependency graphs.
  arXiv  Detail & Related papers  (2026-03-07T07:18:58Z)
• HELP: HyperNode Expansion and Logical Path-Guided Evidence Localization for Accurate and Efficient GraphRAG [53.30561659838455]
  Large Language Models (LLMs) often struggle with inherent knowledge boundaries and hallucinations.<n>Retrieval-Augmented Generation (RAG) frequently overlooks structural interdependencies essential for multi-hop reasoning.<n>Help achieves competitive performance across multiple simple and multi-hop QA benchmarks and up to a 28.8$times$ speedup over leading Graph-based RAG baselines.
  arXiv  Detail & Related papers  (2026-02-24T14:05:29Z)
• Arbitrage: Efficient Reasoning via Advantage-Aware Speculation [71.45710345765528]
  Speculative Decoding accelerates inference by employing a fast but inaccurate draft model to autoregressively propose tokens.<n>But due to unnecessary rejections caused by token mismatches in semantically equivalent steps, traditional token-level Speculative Decoding struggles in reasoning tasks.<n>We propose Arbitrage, a novel step-level speculative generation framework that routes generation dynamically based on the relative advantage between draft and target models.
  arXiv  Detail & Related papers  (2025-12-04T17:50:53Z)
• Scaling Graph Chain-of-Thought Reasoning: A Multi-Agent Framework with Efficient LLM Serving [38.059017394879284]
  Graph Chain-of-Thought (Graph-CoT) enables large language models (LLMs) to perform step-by-step reasoning over graph-structured knowledge.<n>Existing pipelines suffer from low accuracy, excessive token usage, high latency, and low throughput.<n>We present GLM, the first multi-agent Graph-CoT system co-designed with an optimized LLM serving architecture.
  arXiv  Detail & Related papers  (2025-11-03T14:42:53Z)
• EAGER: Entropy-Aware GEneRation for Adaptive Inference-Time Scaling [17.020890684331203]
  We propose EAGer, a training-free generation method that leverages model uncertainty through token-wise entropy distribution.<n>We find that across multiple open-source models on complex reasoning benchmarks such as AIME 2025, EAGer can reallocate the budget without accessing target labels.<n>When target labels are accessible, EAGer generates up to 65% fewer tokens and achieves up to 37% improvement in Pass@k compared to the Full Parallel Sampling.
  arXiv  Detail & Related papers  (2025-10-13T09:04:28Z)
• Lighter-X: An Efficient and Plug-and-play Strategy for Graph-based Recommendation through Decoupled Propagation [49.865020394064096]
  We propose textbfLighter-X, an efficient and modular framework that can be seamlessly integrated with existing GNN-based recommender architectures.<n>Our approach substantially reduces both parameter size and computational complexity while preserving the theoretical guarantees and empirical performance of the base models.<n>Experiments demonstrate that Lighter-X achieves comparable performance to baseline models with significantly fewer parameters.
  arXiv  Detail & Related papers  (2025-10-11T08:33:08Z)
• R-Stitch: Dynamic Trajectory Stitching for Efficient Reasoning [80.104336426172]
  Chain-of-thought (CoT) enhances problem-solving ability of large language models.<n>CoT incurs substantial inference cost due to long autoregressive trajectories.<n>We introduce R-Stitch, a training-free hybrid decoding framework.
  arXiv  Detail & Related papers  (2025-07-23T08:14:36Z)
• Self-Route: Automatic Mode Switching via Capability Estimation for Efficient Reasoning [36.470695895695044]
  Self-Route is a dynamic reasoning framework that automatically selects between general and reasoning modes.<n>We show that Self-Route achieves comparable accuracy to reasoning models while reducing token consumption by 30-55%.
  arXiv  Detail & Related papers  (2025-05-27T03:18:31Z)
• Scalable Chain of Thoughts via Elastic Reasoning [61.75753924952059]
  Elastic Reasoning is a novel framework for scalable chain of thoughts.<n>It separates reasoning into two phases--thinking and solution--with independently allocated budgets.<n>Our approach produces more concise and efficient reasoning even in unconstrained settings.
  arXiv  Detail & Related papers  (2025-05-08T15:01:06Z)
• Flexible Graph Similarity Computation With A Proactive Optimization Strategy [22.212014309562427]
  Graph Edit Distance (GED) offers a principled and flexible measure of graph similarity.<n>GED quantifies the minimum cost needed to transform one graph into another with customizable edit operation costs.<n>Existing methods struggle with adapting to varying operation costs.<n>We propose GEN, a novel learning-based approach for flexible GED approximation.
  arXiv  Detail & Related papers  (2025-04-09T02:16:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.