# Dynamic Parallel Tree Search for Efficient LLM Reasoning

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

## Key facts

- Cited by 42 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 35 of its 47 references that are in the map.
- First posted on arXiv 22 Feb 2025.

## 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, 30 of 35)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [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)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Qwen Technical Report](https://mlsanity.com/paper/2309.16609/) (2023)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022)
- [AWQ: Activation-aware Weight Quantization for LLM Compression and Acceleration](https://mlsanity.com/paper/2306.00978/) (2023)
- [Reasoning with Language Model is Planning with World Model](https://mlsanity.com/paper/2305.14992/) (2023)
- [Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads](https://mlsanity.com/paper/2401.10774/) (2024)
- [ReST-MCTS*: LLM Self-Training via Process Reward Guided Tree Search](https://mlsanity.com/paper/2406.03816/) (2024)
- [Break the Sequential Dependency of LLM Inference Using Lookahead Decoding](https://mlsanity.com/paper/2402.02057/) (2024)
- [Alphazero-like Tree-Search can Guide Large Language Model Decoding and Training](https://mlsanity.com/paper/2309.17179/) (2023)
- [Inference Scaling Laws: An Empirical Analysis of Compute-Optimal Inference for Problem-Solving with Language Models](https://mlsanity.com/paper/2408.00724/) (2024)
- [Monte Carlo Tree Search Boosts Reasoning via Iterative Preference Learning](https://mlsanity.com/paper/2405.00451/) (2024)
- [V-STaR: Training Verifiers for Self-Taught Reasoners](https://mlsanity.com/paper/2402.06457/) (2024)
- [Thoughts Are All Over the Place: On the Underthinking of o1-Like LLMs](https://mlsanity.com/paper/2501.18585/) (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)
- [Marco-o1: Towards Open Reasoning Models for Open-Ended Solutions](https://mlsanity.com/paper/2411.14405/) (2024)
- [Multi-Step Reasoning with Large Language Models, a Survey](https://mlsanity.com/paper/2407.11511/) (2024)
- [Forest-of-Thought: Scaling Test-Time Compute for Enhancing LLM Reasoning](https://mlsanity.com/paper/2412.09078/) (2024)
- [Concise Thoughts: Impact of Output Length on LLM Reasoning and Cost](https://mlsanity.com/paper/2407.19825/) (2024)
- [Escape Sky-high Cost: Early-stopping Self-Consistency for Multi-step Reasoning](https://mlsanity.com/paper/2401.10480/) (2024)
- [Skeleton-of-Thought: Prompting LLMs for Efficient Parallel Generation](https://mlsanity.com/paper/2307.15337/) (2023)
- [Q*: Improving Multi-step Reasoning for LLMs with Deliberative Planning](https://mlsanity.com/paper/2406.14283/) (2024)

## Built on by (most cited first, 30 of 42)

- [Stop Overthinking: A Survey on Efficient Reasoning for Large Language Models](https://mlsanity.com/paper/2503.16419/) (2025)
- [Towards Reasoning Era: A Survey of Long Chain-of-Thought for Reasoning Large Language Models](https://mlsanity.com/paper/2503.09567/) (2025)
- [Reasoning Models Can Be Effective Without Thinking](https://mlsanity.com/paper/2504.09858/) (2025)
- [Efficient Reasoning Models: A Survey](https://mlsanity.com/paper/2504.10903/) (2025)
- [Hogwild! Inference: Parallel LLM Generation via Concurrent Attention](https://mlsanity.com/paper/2504.06261/) (2025)
- [Reasoning on a Budget: A Survey of Adaptive and Controllable Test-Time Compute in LLMs](https://mlsanity.com/paper/2507.02076/) (2025)
- [A Survey of Token Compression for Efficient Multimodal Large Language Models](https://mlsanity.com/paper/2507.20198/) (2025)
- [Two Experts Are All You Need for Steering Thinking: Reinforcing Cognitive Effort in MoE Reasoning Models Without Additional Training](https://mlsanity.com/paper/2505.14681/) (2025)
- [Generative AI Act II: Test Time Scaling Drives Cognition Engineering](https://mlsanity.com/paper/2504.13828/) (2025)
- [Aware First, Think Less: Dynamic Boundary Self-Awareness Drives Extreme Reasoning Efficiency in Large Language Models](https://mlsanity.com/paper/2508.11582/) (2025)
- [From Efficiency to Adaptivity: A Deeper Look at Adaptive Reasoning in Large Language Models](https://mlsanity.com/paper/2511.10788/) (2025)
- [AALC: Large Language Model Efficient Reasoning via Adaptive Accuracy-Length Control](https://mlsanity.com/paper/2506.20160/) (2025)
- [Not All Errors Are Created Equal: ASCoT Addresses Late-Stage Fragility in Efficient LLM Reasoning](https://mlsanity.com/paper/2508.05282/) (2025)
- [Exploring the System 1 Thinking Capability of Large Reasoning Models](https://mlsanity.com/paper/2504.10368/) (2025)
- [Optimizing Diversity and Quality through Base-Aligned Model Collaboration](https://mlsanity.com/paper/2511.05650/) (2025)
- [Neural Chain-of-Thought Search: Searching the Optimal Reasoning Path to Enhance Large Language Models](https://mlsanity.com/paper/2601.11340/) (2026)
- [Mitigating Overthinking in Large Reasoning Language Models via Reasoning Path Deviation Monitoring](https://mlsanity.com/paper/2603.14251/) (2026)
- [Supervised Optimism Correction: Be Confident When LLMs Are Sure](https://mlsanity.com/paper/2504.07527/) (2025)
- [PREMISE: Scalable and Strategic Prompt Optimization for Efficient Mathematical Reasoning in Large Models](https://mlsanity.com/paper/2506.10716/) (2025)
- [CoRE: Enhancing Metacognition with Label-free Self-evaluation in LRMs](https://mlsanity.com/paper/2507.06087/) (2025)
- [InfoSeeker: A Scalable Hierarchical Parallel Agent Framework for Web Information Seeking](https://mlsanity.com/paper/2604.02971/) (2026)
- [LogicOCR: Do Your Large Multimodal Models Excel at Logical Reasoning on Text-Rich Images?](https://mlsanity.com/paper/2505.12307/) (2025)
- [SSR: Speculative Parallel Scaling Reasoning in Test-time](https://mlsanity.com/paper/2505.15340/) (2025)
- [The Thinking Spectrum: An Empirical Study of Tunable Reasoning in LLMs through Model Merging](https://mlsanity.com/paper/2509.22034/) (2025)
- [Efficient Tree-Structured Deep Research with Adaptive Resource Allocation](https://mlsanity.com/paper/2510.05145/) (2025)
- [Mitigating Premature Exploitation in Particle-based Monte Carlo for Inference-Time Scaling](https://mlsanity.com/paper/2510.05825/) (2025)
- [ArborKV: Structure-Aware KV Cache Management for Scaling Tree-based LLM Reasoning](https://mlsanity.com/paper/2605.22106/) (2026)
- [Can Past Experience Accelerate LLM Reasoning?](https://mlsanity.com/paper/2505.20643/) (2025)
- [OptScale: Probabilistic Optimality for Inference-time Scaling](https://mlsanity.com/paper/2506.22376/) (2025)
- [Mitigating Overthinking through Reasoning Shaping](https://mlsanity.com/paper/2510.09535/) (2025)

## Abstract (arXiv)

Tree of Thoughts (ToT) enhances Large Language Model (LLM) reasoning by structuring problem-solving as a spanning tree. However, recent methods focus on search accuracy while overlooking computational efficiency. The challenges of accelerating the ToT lie in the frequent switching of reasoning focus, and the redundant exploration of suboptimal solutions. To alleviate this dilemma, we propose Dynamic Parallel Tree Search (DPTS), a novel parallelism framework that aims to dynamically optimize the reasoning path in inference. It includes the Parallelism Streamline in the generation phase to build up a flexible and adaptive parallelism with arbitrary paths by fine-grained cache management and alignment. Meanwhile, the Search and Transition Mechanism filters potential candidates to dynamically maintain the reasoning focus on more possible solutions and have less redundancy. Experiments on Qwen-2.5 and Llama-3 with Math500 and GSM8K datasets show that DPTS significantly improves efficiency by 2-4x on average while maintaining or even surpassing existing reasoning algorithms in accuracy, making ToT-based reasoning more scalable and computationally efficient.