Breaking the Reward Barrier: Accelerating Tree-of-Thought Reasoning via Speculative...
Talkat 20th USENIX Symposium on Operating Systems Design and Implementation (OSDI '26) · 2026-07-13..07-15·
summary
Proposes SPEX, a speculative-exploration system implemented on SGLang that predicts and expands likely Tree-of-Thought branches before reward feedback, using intra-query speculative path selection, inter-query budget allocation and adaptive early termination. Evaluated across MCTS/ASTAR/Rebase/ETS on Llama-like models on A6000/A100 GPUs, SPEX yields 1.2–3× throughput improvement and up to 4.1× cumulative speedup when combined with token-level speculative decoding, preserves or slightly improves accuracy, and ablations show each technique contributes to the overall gain.
AI-written summary · about
chapters (13)
- 0:00Reward barrier in reasoning
- 2:27Reward dependency bottleneck
- 3:52Speculative exploration
- 5:19Specs system techniques
- 8:31Early termination for skewed trees
- 9:15Experimental setup and evaluation
- 10:19Throughput with Specs
- 10:41Reasoning quality with Specs
- 11:26Specs components ablation
- 11:48Specs with token-level speculation
- 12:29Speculative branch accuracy
- 12:51Live demo: Specs in BFS
- 13:13Conclusion and future
related talks
32mScaling Test-time Inference Compute & Rise of Reasoning Models
01h 00mDeepSeek-R1 Thoughtology: ＜Thinking＞ about LLM Reasoning
39mUnlocking reasoning in Large language models
31mMaking the most of test-time compute in LLMs
45mFrom Next Token Prediction to Reasoning and Beyond
15mOlmo-Thinking: Training a Fully Open Reasoning Model
43mAdvanced Prompt Engineering and Beyond
24mThe Rise of Reasoning Models