Aligning Tree-Search Policies with Fixed Token Budgets in Test-Time Scaling of LLMs

• URL: http://arxiv.org/abs/2602.09574v1
• Date: Tue, 10 Feb 2026 09:23:26 GMT
• Title: Aligning Tree-Search Policies with Fixed Token Budgets in Test-Time Scaling of LLMs
• Abstract summary: Existing tree-search policies are largely budget-agnostic, treating the budget as a termination condition, which can lead to late-stage over-branching or premature termination.<n>We propose Budget-Guided MCTS (BG-MCTS), a tree-search decoding algorithm that aligns its search policy with the remaining token budget.<n>BG-MCTS consistently outperforms budget-agnostic tree-search baselines across different budgets on MATH500 and AIME24/25 with open-weight LLMs.
• Score: 16.21023293204606
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Tree-search decoding is an effective form of test-time scaling for large language models (LLMs), but real-world deployment imposes a fixed per-query token budget that varies across settings. Existing tree-search policies are largely budget-agnostic, treating the budget as a termination condition, which can lead to late-stage over-branching or premature termination. We propose {Budget-Guided MCTS} (BG-MCTS), a tree-search decoding algorithm that aligns its search policy with the remaining token budget: it starts with broad exploration, then prioritizes refinement and answer completion as the budget depletes while reducing late-stage branching from shallow nodes. BG-MCTS consistently outperforms budget-agnostic tree-search baselines across different budgets on MATH500 and AIME24/25 with open-weight LLMs.

Related papers

• Exploit More, Explore Smarter for Budget-Constrained Agentic Search [6.894751260400948]
  Budget-constrained agentic search arises when an agent must refine candidates under a small evaluation budget.<n>We introduce ExTS, a tree-search policy that treats expansion itself as a value-of-information decision.
  arXiv  Detail & Related papers  (2026-08-24T21:38:05Z)
• Cost-Aware Diffusion Draft Trees for Speculative Decoding [17.900184934329666]
  We introduce textbfCaDDTree (Cost-aware Diffusion Draft Tree), a method that directly optimize token throughput (expected tokens generated per unit time) by jointly selecting the tree structure and node budget.<n>Experiments on Qwen3-4B and Qwen3-8B across eight benchmarks spanning reasoning, coding, and instruction-following tasks show that caDDTree matches or surpasses DDTree with oracle budget selection on nearly all tasks.
  arXiv  Detail & Related papers  (2026-06-01T07:29:56Z)
• Budget-Efficient Automatic Algorithm Design via Code Graph [2.982218441172364]
  Large language models (LLMs) have emerged as powerful tools for automatic algorithm design (AAD)<n>We formalize budget-efficient automatic algorithm design, wherein the search policy maximizes realized fitness subject to limited computational cost.<n>We validate our method empirically on three optimization problems, demonstrating consistent superiority of our graph-based search over full-algorithm search at equal token budget.
  arXiv  Detail & Related papers  (2026-05-11T14:01:52Z)
• Policy-Guided Search on Tree-of-Thoughts for Efficient Problem Solving with Bounded Language Model Queries [5.268207922548829]
  We show how probabilities assigned to thoughts by Language Models (LMs) can serve as a to guide search within the ToT framework.<n>We adapt a search algorithm, Levin Tree Search (LTS), to the ToT framework.<n>These findings highlight the efficacy of LTS on ToT, particularly in enabling cost-effective and time-efficient problem-solving.
  arXiv  Detail & Related papers  (2026-01-07T05:35:16Z)
• Chain-in-Tree: Back to Sequential Reasoning in LLM Tree Search [4.12237459236889]
  Chain-in-Tree (CiT) is a framework that decides when to branch during search rather than expanding at every step.<n>It achieves 75-85% reductions in token generation, model calls, and runtime on GSM8K and Math500.
  arXiv  Detail & Related papers  (2025-09-30T06:18:44Z)
• Don't Get Lost in the Trees: Streamlining LLM Reasoning by Overcoming Tree Search Exploration Pitfalls [83.89771461061903]
  Recent advancements in tree search algorithms guided by verifiers have significantly enhanced the reasoning capabilities of large language models (LLMs)<n>Recent advancements in tree search algorithms guided by verifiers have significantly enhanced the reasoning capabilities of large language models (LLMs)<n>We identify two key challenges contributing to this inefficiency: $textitover-exploration$ due to redundant states with semantically equivalent content, and $textitunder-exploration$ caused by high variance in verifier scoring.<n>We propose FETCH, a flexible, plug-and-play system compatible with various tree search algorithms.
  arXiv  Detail & Related papers  (2025-02-16T16:12:01Z)
• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  This study introduces a novel guided tree search algorithm with dynamic node selection and node-level exploration budget. Experiments conducted on the GSM8K and TabMWP datasets demonstrate that our approach enjoys significantly lower computational costs compared to baseline methods.
  arXiv  Detail & Related papers  (2024-06-29T05:14:04Z)
• Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits [55.938644481736446]
  Indexed Minimum Empirical Divergence (IMED) is a highly effective approach to the multi-armed bandit problem. It has been observed to empirically outperform UCB-based algorithms and Thompson Sampling. We present novel linear versions of the IMED algorithm, which we call the family of LinIMED algorithms.
  arXiv  Detail & Related papers  (2024-05-24T04:11:58Z)
• Autonomous Tree-search Ability of Large Language Models [58.68735916408101]
  Large Language Models have excelled in remarkable reasoning capabilities with advanced prompting techniques. Recent works propose to utilize external programs to define search logic, such that LLMs can perform passive tree search to solve more challenging reasoning tasks. We propose a new concept called autonomous tree-search ability of LLM, which can automatically generate a response containing search trajectories for the correct answer.
  arXiv  Detail & Related papers  (2023-10-14T14:14:38Z)
• Universal Quantum Speedup for Branch-and-Bound, Branch-and-Cut, and Tree-Search Algorithms [13.152347996965297]
  Mixed Programs (MIPs) model many optimization problems of interest in Computer Science, Operations Research, and Financial Engineering. Branch-and-Cut algorithms, which combine Branch-and-Bound logic with cutting-plane routines, are at the core of modern MIP solvers. We propose a quantum algorithm, Incremental-Quantum-Branch-and-Bound, with universal near-quadratic speedup over classical Branch-and-Bound algorithms for every input.
  arXiv  Detail & Related papers  (2022-10-06T21:08:46Z)
• On $\ell_p$-norm Robustness of Ensemble Stumps and Trees [83.81523991945018]
  We develop an efficient programming based algorithm for sound verification of ensemble stumps. We demonstrate the first certified defense method for training ensemble stumps and trees with respect to $ell_p$ norm perturbations.
  arXiv  Detail & Related papers  (2020-08-20T03:42:40Z)
• Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies [76.83991682238666]
  Branch and Bound (B&B) is the exact tree search method typically used to solve Mixed-Integer Linear Programming problems (MILPs) We propose a novel imitation learning framework, and introduce new input features and architectures to represent branching.
  arXiv  Detail & Related papers  (2020-02-12T17:43:23Z)

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.