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

This paper evaluates the Tree of Thought (ToT) reasoning strategies, specifically DPTS and SSDP, under varying compute budgets and model sizes (Llama-3B and Llama-8B) across mathematical reasoning benchmarks (Math500 and GSM8K). The study finds that DPTS struggles with a cold-start bottleneck at low budgets, while SSDP efficiently finds solutions but suffers from frontier depletion, indicating that neither fixed exploration nor pruning strategies are adequate. These insights highlight the need for adaptive search strategies in deploying reasoning agents effectively within constrained computational environments.