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

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 12 of its 38 references that are in the map.
- First posted on arXiv 10 Feb 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, 12 of 12)

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [Qwen2.5 Technical Report](https://mlsanity.com/paper/2412.15115/) (2024)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [Large Language Monkeys: Scaling Inference Compute with Repeated Sampling](https://mlsanity.com/paper/2407.21787/) (2024)
- [Textbooks Are All You Need](https://mlsanity.com/paper/2306.11644/) (2023)
- [A Survey on Test-Time Scaling in Large Language Models: What, How, Where, and How Well?](https://mlsanity.com/paper/2503.24235/) (2025)
- [Accessing GPT-4 level Mathematical Olympiad Solutions via Monte Carlo Tree Self-refine with LLaMa-3 8B](https://mlsanity.com/paper/2406.07394/) (2024)
- [Q*: Improving Multi-step Reasoning for LLMs with Deliberative Planning](https://mlsanity.com/paper/2406.14283/) (2024)
- [GenPRM: Scaling Test-Time Compute of Process Reward Models via Generative Reasoning](https://mlsanity.com/paper/2504.00891/) (2025)
- [Budget-Aware Tool Use Enables Effective Agent Scaling](https://mlsanity.com/paper/2511.17006/) (2025)
- [LiteSearch: Efficacious Tree Search for LLM](https://mlsanity.com/paper/2407.00320/) (2024)

## Built on by (most cited first, 4 of 4)

- [Compute Allocation for Self-Evolving LLMs: From Depth-Breadth to Multi-Armed Bandits](https://mlsanity.com/paper/2605.29268/) (2026)
- [Beyond Fixed Budgets: Characterizing the Inelasticity and Limitations of Tree-of-Thought Reasoning Strategies](https://mlsanity.com/paper/2606.20599/) (2026)
- [Budget-Aware LLM Discovery via Cost-Calibrated Frontier Utility](https://mlsanity.com/paper/2607.26828/) (2026)
- [Make Every Expansion Count: Learning to Search Efficiently in LLM Code Repair](https://mlsanity.com/paper/2610.15894/) (2026)

## Abstract (arXiv)

Tree-search decoding is an effective form of test-time scaling for large language models (LLMs), but real-world deployment often imposes a fixed per-query token budget that varies across settings. Existing tree-search policies are largely budget-agnostic, treating the budget merely as a termination condition, thereby risking 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 remaining budget decreases while reducing late-stage branching from shallow nodes. BG-MCTS consistently outperforms budget-agnostic tree-search baselines across inference budgets on mathematical reasoning benchmarks and an additional physics reasoning benchmark with open-weight LLMs.