Beyond Fixed Budgets: Characterizing the Inelasticity and Limitations of Tree-of-Thought Reasoning Strategies
06:00 · June 23, 2026 · arXiv cs.AI RSS
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.
Summary
Tree-of-Thought search extends chain-of-thought prompting by framing LLM reasoning as an explicit tree traversal, where nodes represent partial reasoning states and branches correspond to model-generated expansions. The paper examines how two representative strategies perform when token budgets, model scale, and problem difficulty vary, an issue that matters for scientific workflows running on shared or elastic compute resources.
DPTS applies Monte Carlo tree search with iterative rollouts and value backpropagation, while SSDP uses semantic similarity to merge and prune redundant branches. Both were tested on the Math500 and GSM8K benchmarks with Llama-3B and Llama-8B models across token budgets from 3k to 10k. The experiments tracked not only final accuracy but also when candidate solutions first appear, why search terminates, and how additional tokens translate into deeper or broader exploration.
The results expose complementary weaknesses. At low budgets DPTS exhibits a cold-start bottleneck: its value estimates remain unreliable until enough rollouts accumulate, so up to 74 percent of Math500 problems yield no candidate solution at the 3k budget. SSDP reaches solutions more quickly yet suffers frontier depletion; its aggressive merging permanently discards unexplored paths, causing both accuracy and token consumption to plateau even when larger budgets are supplied. Consequently, neither method converts extra compute into proportional gains across the full range of resource constraints.
These observations indicate that fixed exploration or pruning policies are inherently inelastic. The authors therefore argue that practical scientific reasoning agents will require search strategies capable of shifting between exploration and pruning regimes according to remaining budget and observed search progress.
Why it matters
This research is highly relevant for Dutch AI researchers and engineers developing advanced LLM reasoning agents, particularly in resource-constrained environments. By highlighting the limitations of current ToT strategies under varying compute budgets, it provides actionable insights for building more efficient and scalable AI systems, aligning with the Netherlands' focus on sustainable and practical AI deployment.
