Research map / Large language models / Reasoning and chain of thought
Accelerating Large Language Model Reasoning via Speculative Search
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 SpecSearch, a bi-level speculative thought generator in which a small model drafts reasoning thoughts, a PRM rejects low-quality ones using an EMA threshold estimated from large-model samples, and rejected thoughts are regenerated by the large model via token-level speculative sampling, yielding up to 2.12x speedup over SpS with comparable accuracy.
Problem
Tree-search-based LLM reasoning (ToT with beam search or MCTS) incurs very high inference latency because thought generation requires producing many candidate reasoning steps with a large model.
Approach
Extends speculative execution from the token level to the thought level: a small model drafts multiple thoughts, a process reward model filters those below a dynamically estimated large-model quality threshold (EMA over historical large-model thought scores), and rejected thoughts are regenerated by the large model with lossless token-level speculative decoding.
Key results
- On MATH-100 with Qwen, SpecSearch reaches 3.35x speedup over AR and 1.72x over SpS at 87% accuracy (AR 87%).
- With Math-Shepherd PRM, SpecSearch achieves 2.12x speedup over SpS (4.11x vs AR) at 94% accuracy vs 95% for SpS.
- On GSM8K-100 with Llama, SpecSearch attains 88% accuracy vs 87% for AR and 1.42x speedup over SpS.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| bi-level speculative thought generation with quality-preserving rejection (vs AR) | Qwen2.5-72B with 7B draft, beam search · MATH-100 | Speedup (vs AR): 3.35x speedup at 87.00 vs 87.00 accuracy | Helped |
| bi-level speculative thought generation with quality-preserving rejection (vs SpS) | Qwen2.5-72B with 7B draft, beam search · GSM8K-100 | Reasoning Accuracy (%): 96.00 vs 97.00 for AR and SpS | Hurt |
| bi-level speculative thought generation (Llama) | Llama3-70B with 8B draft · GSM8K-100 | Reasoning Accuracy (%): 88.00 vs 87.00 AR and 86.00 SpS | Helped |
| bi-level speculative thought generation (Llama) | Llama3-70B with 8B draft · MATH-100 | Reasoning Accuracy (%): 64.00 vs 62.00 AR and 61.00 SpS | Helped |
| replace PRM evaluation with large-model log-probability evaluation (ablation) | SpecSearch · MATH-50 | Reasoning Accuracy (%): 78.00 vs 88.00 for full SpecSearch | Hurt |
| step-wise EMA threshold estimation instead of fixed threshold (ablation) | SpecSearch rejection module · MATH-50 | Reasoning Accuracy (%): 88.00 vs 80.00 with fixed threshold | Helped |
| random rejection of 50% of small-model thoughts instead of quality-based rejection (ablation) | SpecSearch · MATH-50 | Reasoning Accuracy (%): 80.00 vs 88.00 for full | Hurt |
| adaptive thought-level large model engagement (vs fixed large-model engagement) (ablation) | SpecSearch rejection module · MATH-50 | Reasoning Accuracy (%): 88.00 vs 84.00 with FLME | Helped |
| fixed threshold instead of step-wise threshold (speed tradeoff) (ablation) | SpecSearch rejection module · MATH-50 | Speedup (vs AR): 3.72x vs 3.63x full, but accuracy 80.00 vs 88.00 | Mixed |
| SpecSearch with Math-Shepherd PRM vs Math-psa PRM | SpecSearch · GSM8K-100 (PRM generalization) | Reasoning Accuracy (%): 94.00 (Math-Shepherd) vs 96.00 (Math-psa), AR 96.00 | No clear effect |
| SpecSearch with MCTS search instead of beam search | SpecSearch · GSM8K-100 (MCTS) | Speedup (vs AR): 2.61x vs AR, 98.00 accuracy equal to AR | Helped |
Surprising findings
- Over 40% of thoughts from the quantized Qwen2.5-7B-Instruct outscored the average reward of Qwen2.5-72B-Instruct thoughts.
- Simple thought-level large-model engagement (fixed-fraction reprocessing) substantially degraded reasoning accuracy, motivating the adaptive threshold.
Limitations
- Theoretical guarantees rely on normality and descending-quality assumptions and are derived under idealized conditions.
- Evaluation uses only 100-sample subsets of MATH and GSM8K due to latency, and accuracy sometimes drops slightly (e.g., GSM8K 96% vs 97% on Qwen), with degradation attributed to PRM-fooling thoughts.
- Quality depends on the PRM evaluator; mismatched or misleading PRM scores can degrade accuracy.
Experimental setup
Datasets: MATH GSM8K
Benchmarks: MATH-100 GSM8K-100 MATH-50
Metrics: reasoning accuracy average inference latency speedup vs AR speedup vs SpS
Baselines: AR (autoregressive ToT) SpS (speculative sampling) SD SEED TreeBon
Builds on: speculative sampling Tree of Thoughts OpenR Math-Shepherd Chain-of-Thought
Closest papers by meaning
- Algorithm of Thoughts: Enhancing Exploration of Ideas in Large Language Models (ICML 2024 · similarity 0.90)
- RATT: A Thought Structure for Coherent and Correct LLM Reasoning (AAAI 2025 · similarity 0.90)
- Training Language Models to Reason Efficiently (NeurIPS 2025 · similarity 0.89)
- SpecExit: Accelerating Large Reasoning Model via Speculative Exit (ICML 2026 · similarity 0.89)
- Fixing the Broken Compass: Diagnosing and Improving Inference-Time Reward Modeling (ICLR 2026 · similarity 0.89)
- Fleet of Agents: Coordinated Problem Solving with Large Language Models (ICML 2025 · similarity 0.89)
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.