# Beyond Fixed Budgets: Characterizing the Inelasticity and Limitations of Tree-of-Thought Reasoning Strategies

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 19 of its 34 references that are in the map.
- First posted on arXiv 19 May 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, 19 of 19)

- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Training Compute-Optimal Large Language Models](https://mlsanity.com/paper/2203.15556/) (2022)
- [Alphazero-like Tree-Search can Guide Large Language Model Decoding and Training](https://mlsanity.com/paper/2309.17179/) (2023)
- [Monte Carlo Tree Search Boosts Reasoning via Iterative Preference Learning](https://mlsanity.com/paper/2405.00451/) (2024)
- [Adaptive Risk Minimization: Learning to Adapt to Domain Shift](https://mlsanity.com/paper/2007.02931/) (2020)
- [Interpretable Contrastive Monte Carlo Tree Search Reasoning](https://mlsanity.com/paper/2410.01707/) (2024)
- [Enhancing LLM Reasoning with Reward-guided Tree Search](https://mlsanity.com/paper/2411.11694/) (2024)
- [BPP-Search: Enhancing Tree of Thought Reasoning for Mathematical Modeling Problem Solving](https://mlsanity.com/paper/2411.17404/) (2024)
- [Don't Get Lost in the Trees: Streamlining LLM Reasoning by Overcoming Tree Search Exploration Pitfalls](https://mlsanity.com/paper/2502.11183/) (2025)
- [MITS: Enhanced Tree Search Reasoning for LLMs via Pointwise Mutual Information](https://mlsanity.com/paper/2510.03632/) (2025)
- [MCTS-KBQA: Monte Carlo Tree Search with Information Gain Rewards for Knowledge Base Question Answering](https://mlsanity.com/paper/2502.13428/) (2025)
- [LLM-First Search: Self-Guided Exploration of the Solution Space](https://mlsanity.com/paper/2506.05213/) (2025)
- [Aligning Tree-Search Policies with Fixed Token Budgets in Test-Time Scaling of LLMs](https://mlsanity.com/paper/2602.09574/) (2026)
- [ECR: Manifold-Guided Semantic Cues for Compact Language Models](https://mlsanity.com/paper/2601.00543/) (2026)

## Abstract (arXiv)

Tree of Thought (ToT) search has become a promising direction for improving the reasoning capabilities of large language models, but deploying these methods in practice raises a question that has received little systematic attention: how do different search strategies behave under varying compute budgets, model sizes, and problem difficulties? In this work, we evaluate two representative ToT methods; DPTS, a Monte Carlo tree search based approach, and SSDP, a semantic deduplication based approach, across two mathematical reasoning benchmarks (Math500 and GSM8K), two model scales (Llama-3B and Llama-8B), and four token budgets (3k--10k). Our analysis reveals that the two methods exhibit limitations that pull in opposite directions. DPTS suffers from a cold-start bottleneck at low budgets: it requires sufficient exploration before its value estimates become reliable, making it a poor fit for resource-constrained settings despite strong scaling behavior at higher budgets. SSDP, on the other hand, reaches candidate solutions efficiently but is prone to frontier depletion; its aggressive node merging permanently discards unexplored paths, leaving it unable to improve regardless of how much budget remains. Together, these findings suggest that neither a fixed exploration strategy nor a fixed pruning strategy is sufficient across compute continuum. We argue that effective search for scientific reasoning agents requires strategies that can adapt their behavior based on search progress and available resources.