Research map / Large language models / Reasoning and chain of thought
LiteSearch: Efficient Tree Search with Dynamic Exploration Budget for Math Reasoning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes LiteSearch, a value-guided tree search with progress-aware selection and dynamic node-level expansion budgets, trained via a Llama-3-8B value network using only final-answer labels, to cut token cost of math reasoning search.
Problem
Tree search methods (BFS, MCTS) for LLM math reasoning require many more generated tokens than greedy decoding because they allocate expansion budgets wastefully and often need step-level annotations.
Approach
A guided tree search that selects nodes by value plus a progress term (relative to greedy decoding) and sets each node's child budget inversely to its calibrated value and depth, with a value network trained only on final-answer correctness.
Key results
- On GSM8K with Mixtral-8x7B, Ours (Incremental) reaches 0.797 accuracy at 0.41k tokens versus ToT-BFS 0.801 at 2.22k tokens.
- On MATH500 with Llama-3-8B-Instruct, Ours (Incremental) achieves 0.420 accuracy at 2.36k tokens versus Soft Voting@10 at 0.392 and 3.12k tokens.
- Dynamic budgeting lowers Batch Expansion cost from 1.79k to 0.55k tokens on GSM8K while raising accuracy from 0.802 to 0.823.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use dynamic rather than static node budgets (ablation) | LiteSearch (Incremental) · GSM8K | Accuracy: .779 -> .797 | Helped |
| Use dynamic rather than static node budgets (ablation) | LiteSearch (Batch) · GSM8K | Accuracy: .802 -> .823 | Helped |
| Add a depth penalty to the budget calculation (ablation) | LiteSearch (Incremental) · GSM8K | Accuracy: .780 -> .797 | Helped |
| Add greedy-value calibration (ablation) | LiteSearch (Incremental) · GSM8K | Accuracy: .783 -> .797 | Helped |
| Add a depth penalty to the budget calculation (ablation) | LiteSearch (Batch) · GSM8K | Accuracy: .815 -> .823 | Helped |
| Add greedy-value calibration (ablation) | LiteSearch (Batch) · GSM8K | Accuracy: .806 -> .823 | Helped |
| Use step number rather than token number to estimate progress (ablation) | LiteSearch (Incremental) · GSM8K | Accuracy: 1.3 points | Mixed |
| Increase progress-term weight to λ=0.15 using step-number progress (ablation) | LiteSearch (Incremental) · GSM8K | #Tokens (k): nearly 20% | Helped |
| Train the value network with mixed-domain data rather than single-domain data (ablation) | LiteSearch (Incremental) · TabMWP | Accuracy: 0.75 vs 0.78 | Helped |
| Add Soft Voting to LiteSearch (Batch) answers below the value threshold (ablation) | LiteSearch (Batch) · GSM8K | Accuracy: .823 -> .841; .823 -> .843; .823 -> .847 | Helped |
| Increase the budget upper bound B (ablation) | LiteSearch · GSM8K | Accuracy | Helped |
| Increase the budget upper bound B (ablation) | LiteSearch · GSM8K | #Tokens (k) | Hurt |
Surprising findings
- Soft Voting@20 still outperforms the guided tree search on accuracy (0.843 vs. 0.823 on GSM8K), so single-path search cannot fully match voting when value estimates are inaccurate.
Limitations
- Guided tree search rarely beats Soft Voting@20 on accuracy because a single path is chosen and value errors are not recoverable.
- Value network quality is imperfect; early-step values have high variance, motivating greedy-value calibration.
- Mixture-of-domain value network results are only preliminary.
Experimental setup
Datasets: GSM8K TabMWP MATH
Benchmarks: GSM8K TabMWP MATH500
Metrics: accuracy number of generated tokens (k)
Baselines: Greedy Decoding Hard Voting ToT-DFS ToT-BFS Soft Voting MCTS
Builds on: Tree-of-Thought Self-Consistency Monte Carlo Tree Search Beam search
Closest papers by meaning
- MARGE: Improving Math Reasoning with Guided Exploration (ICML 2025 · similarity 0.87)
- Policy Guided Tree Search for Enhanced LLM Reasoning (ICML 2025 · similarity 0.87)
- Token-Supervised Value Models for Enhancing Mathematical Problem-Solving Capabilities of Large Language Models (ICLR 2025 · similarity 0.87)
- Aligning Tree-Search Policies with Fixed Token Budgets in Test-Time Scaling of LLMs (ICML 2026 · similarity 0.86)
- AlphaZero-Like Tree-Search can Guide Large Language Model Decoding and Training (ICML 2024 · similarity 0.86)
- A*-Thought: Efficient Reasoning via Bidirectional Compression for Low-Resource Settings (NeurIPS 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.