Chopping Trees: Semantic Similarity Based Dynamic Pruning for Tree-of-Thought Reasoning
This addresses the problem of semantic redundancy in LLM reasoning for researchers and practitioners, offering a practical incremental improvement.
The paper tackles the computational expense of Tree-of-Thought reasoning in Large Language Models by introducing Semantic Similarity-Based Dynamic Pruning, which achieves up to a 2.3x speedup and reduces explored nodes by 85-90% while maintaining competitive accuracy.
Tree-of-Thought (ToT) reasoning boosts the problem-solving abilities of Large Language Models (LLMs) but is computationally expensive due to semantic redundancy, where distinct branches explore equivalent reasoning paths. We introduce Semantic Similarity-Based Dynamic Pruning (SSDP), a lightweight method that, to the best of our knowledge, is the first framework to integrate online semantic merging into parallelized tree search, enabling the clustering and pruning of redundant steps in real time. Across reasoning benchmarks, including GSM8K and MATH500, SSDP achieves up to a 2.3x speedup over state-of-the-art tree-search baselines while maintaining competitive accuracy (typically within 5% of the strongest baseline) and reducing the number of explored nodes by 85-90%, demonstrating a practical approach to efficient, scalable LLM reasoning. The implementation of SSDP is publicly available at https://github.com/kimjoonghokim/SSDP.