# ETS: Efficient Tree Search for Inference-Time Scaling

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

## Key facts

- Cited by 16 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 31 of its 44 references that are in the map.
- First posted on arXiv 19 Feb 2025.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)
- Efficient LLM inference and serving / [Speculative decoding](https://mlsanity.com/inference/speculative-decoding/)

## Builds on (most cited first, 30 of 31)

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Constitutional AI: Harmlessness from AI Feedback](https://mlsanity.com/paper/2212.08073/) (2022)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [Large Language Monkeys: Scaling Inference Compute with Repeated Sampling](https://mlsanity.com/paper/2407.21787/) (2024)
- [Math-Shepherd: Verify and Reinforce LLMs Step-by-step without Human Annotations](https://mlsanity.com/paper/2312.08935/) (2023)
- [Solving math word problems with process- and outcome-based feedback](https://mlsanity.com/paper/2211.14275/) (2022)
- [Graph of Thoughts: Solving Elaborate Problems with Large Language Models](https://mlsanity.com/paper/2308.09687/) (2023)
- [Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm](https://mlsanity.com/paper/1712.01815/) (2017)
- [KVQuant: Towards 10 Million Context Length LLM Inference with KV Cache Quantization](https://mlsanity.com/paper/2401.18079/) (2024)
- [Language Agent Tree Search Unifies Reasoning Acting and Planning in Language Models](https://mlsanity.com/paper/2310.04406/) (2023)
- [Efficiently Scaling Transformer Inference](https://mlsanity.com/paper/2211.05102/) (2022)
- [Diverse Beam Search: Decoding Diverse Solutions from Neural Sequence Models](https://mlsanity.com/paper/1610.02424/) (2016)
- [SqueezeLLM: Dense-and-Sparse Quantization](https://mlsanity.com/paper/2306.07629/) (2023)
- [Inference Scaling Laws: An Empirical Analysis of Compute-Optimal Inference for Problem-Solving with Language Models](https://mlsanity.com/paper/2408.00724/) (2024)
- [RLHF Workflow: From Reward Modeling to Online RLHF](https://mlsanity.com/paper/2405.07863/) (2024)
- [Autonomous Evaluation and Refinement of Digital Agents](https://mlsanity.com/paper/2404.06474/) (2024)
- [Fast Best-of-N Decoding via Speculative Rejection](https://mlsanity.com/paper/2410.20290/) (2024)
- [AI and Memory Wall](https://mlsanity.com/paper/2403.14123/) (2024)
- [LMRL Gym: Benchmarks for Multi-Turn Reinforcement Learning with Language Models](https://mlsanity.com/paper/2311.18232/) (2023)
- [Full Stack Optimization of Transformer Inference: a Survey](https://mlsanity.com/paper/2302.14017/) (2023)
- [Hydragen: High-Throughput LLM Inference with Shared Prefixes](https://mlsanity.com/paper/2402.05099/) (2024)
- [TreeBoN: Enhancing Inference-Time Alignment with Speculative Tree-Search and Best-of-N Sampling](https://mlsanity.com/paper/2410.16033/) (2024)
- [Squeezed Attention: Accelerating Long Context Length LLM Inference](https://mlsanity.com/paper/2411.09688/) (2024)
- [Mutual Information and Diverse Decoding Improve Neural Machine Translation](https://mlsanity.com/paper/1601.00372/) (2016)

## Built on by (most cited first, 16 of 16)

- [A Survey on Test-Time Scaling in Large Language Models: What, How, Where, and How Well?](https://mlsanity.com/paper/2503.24235/) (2025)
- [Learning Adaptive Parallel Reasoning with Language Models](https://mlsanity.com/paper/2504.15466/) (2025)
- [Generative AI Act II: Test Time Scaling Drives Cognition Engineering](https://mlsanity.com/paper/2504.13828/) (2025)
- [Every Rollout Counts: Optimal Resource Allocation for Efficient Test-Time Scaling](https://mlsanity.com/paper/2506.15707/) (2025)
- [SpatialDreamer: Incentivizing Spatial Reasoning via Active Mental Imagery](https://mlsanity.com/paper/2512.07733/) (2025)
- [SPRINT: Enabling Interleaved Planning and Parallelized Execution in Reasoning Models](https://mlsanity.com/paper/2506.05745/) (2025)
- [Reward Modeling for Reinforcement Learning-Based LLM Reasoning: Design, Challenges, and Evaluation](https://mlsanity.com/paper/2602.09305/) (2026)
- [FastTTS: Accelerating Test-Time Scaling for Edge LLM Reasoning](https://mlsanity.com/paper/2509.00195/) (2025)
- [A Survey on Self-Improving Test-Time Intelligence: Feedback-Driven Adapting, Learning, and Scaling at Inference](https://mlsanity.com/paper/2609.01679/) (2026)
- [Adaptive Test-Time Reasoning via Reward-Guided Dual-Phase Search](https://mlsanity.com/paper/2509.25420/) (2025)
- [EdgeReasoning: Characterizing Reasoning LLM Deployment on Edge GPUs](https://mlsanity.com/paper/2511.01866/) (2025)
- [Stepwise Reasoning Checkpoint Analysis: A Test Time Scaling Method to Enhance LLMs' Reasoning](https://mlsanity.com/paper/2505.17829/) (2025)
- [HyPER: Bridging Exploration and Exploitation for Scalable LLM Reasoning with Hypothesis Path Expansion and Reduction](https://mlsanity.com/paper/2602.06527/) (2026)
- [Efficient Reasoning on the Edge](https://mlsanity.com/paper/2603.16867/) (2026)
- [Breaking the Reward Barrier: Accelerating Tree-of-Thought Reasoning via Speculative Exploration](https://mlsanity.com/paper/2605.10195/) (2026)
- [SpecCal: Ambiguity-Aware Candidate Calibration for Infrared Spectrum-Based Molecular Structure Reconstruction](https://mlsanity.com/paper/2607.27788/) (2026)

## Abstract (arXiv)

Test-time compute scaling has emerged as a new axis along which to improve model accuracy, where additional computation is used at inference time to allow the model to think longer for more challenging problems. One promising approach for test-time compute scaling is search against a process reward model, where a model generates multiple potential candidates at each step of the search, and these partial trajectories are then scored by a separate reward model in order to guide the search process. The diversity of trajectories in the tree search process affects the accuracy of the search, since increasing diversity promotes more exploration. However, this diversity comes at a cost, as divergent trajectories have less KV sharing, which means they consume more memory and slow down the search process. Previous search methods either do not perform sufficient exploration, or else explore diverse trajectories but have high latency. We address this challenge by proposing Efficient Tree Search (ETS), which promotes KV sharing by pruning redundant trajectories while maintaining necessary diverse trajectories. ETS incorporates a linear programming cost model to promote KV cache sharing by penalizing the number of nodes retained, while incorporating a semantic coverage term into the cost model to ensure that we retain trajectories which are semantically different. We demonstrate how ETS can achieve 1.8× reduction in average KV cache size during the search process, leading to 1.4× increased throughput relative to prior state-of-the-art methods, with minimal accuracy degradation and without requiring any custom kernel implementation. Code is available at: https://github.com/SqueezeAILab/ETS.