Accelerating Large Language Model Reasoning via Speculative Search
Authors: Zhihai Wang
Jie Wang
Jilai Pan
Xilin Xia
Huiling Zhen
Mingxuan Yuan
Jianye HAO
Feng Wu
Venue: ICML 2025 poster (2025)
Keywords: Large Language Model Reasoning
Inference Acceleration
Tree Search
Speculative Execution
Primary area: deep_learning->large_language_models

Abstract: Tree-search-based reasoning methods have significantly enhanced the reasoning capability of large language models (LLMs) by facilitating the exploration of multiple intermediate reasoning steps, i.e., thoughts. However, these methods suffer from substantial inference latency, as they have to generate numerous reasoning thoughts, severely limiting LLM applicability. To address this challenge, we propose a novel Speculative Search (SpecSearch) framework that significantly accelerates LLM reasoning by optimizing thought generation. Specifically, SpecSearch utilizes a small model to strategically collaborate with a large model at both thought and token levels, efficiently generating high-quality reasoning thoughts. The major pillar of SpecSearch is a novel quality-preserving rejection mechanism, which effectively filters out thoughts whose quality falls below that of the large model's outputs. Moreover, we show that SpecSearch preserves comparable reasoning quality to the large model. Experiments on both the Qwen and Llama models demonstrate that SpecSearch significantly outperforms state-of-the-art approaches, achieving up to 2.12$\times$ speedup with comparable reasoning quality.

Accelerating Large Language Model Reasoning via Speculative Search
Zhihai Wang"
Jie Wang
1
Jilai Pan"
Xilin Xia
Huiling Zhen 2 Mingxuan Yuan 2 Jianye Hao 23
Feng Wu
Abstract
MUTS
Thrught Gaaentte
@ floer Search
600
cree-search-based reasoning methods have significantly enhanced the reasoning capability of large language models (LLMs) by facilitating the exploration of multiple intermediate reasoning steps, i.e., thoughts. However, these methods suffer from substantial inference latency, as they have to generate numerous reasoning thoughts, severely limiting LLM applicability. To address this challenge, we propose novel Speculative Search (SpecSearch) framework that significantly accelerates LLM reasoning by optimizing thought generation. Specifically, SpecSearch utilizes a small model to strategically collaborate with a large model at both thought and token levels, efficiently generating high-quality reasoning thoughts. The major pillar of SpecSearch is a novel preseripp rejection mechanism. which effectively filters out thoughts whose quality falls below that of the large model's outputs. Moreover, we show that SpecSearch preserves comparable reasoning quality to the large model. Experiments on both the Qwen and Llama models demonstrate that Seache sig- nificantly outperforms state-of-the-an art approaches, achieving up 2.12x speedup with compa- rable reasoning quality. Code is available https:://itttii LiMReasoning- SpecSerrcc...
Arturay
0000
93.5%
640
640
Direct Hefaaee
025
Inference Time
(a) Latency-Accuracy
(b) Bottleneck of Reasoning
Figure I. (a) The inference lateney increases by several orders of magnitude with the introduction of peessearch-baed reasoning methods. (b) Thought generation acts as an efficiency bottleneck of tree-search- based reasoning methods.
soning methods (Yao et al., 2023; Wan et al., 2024a: Jiang et al., 2024; Wu et al., 2024). These TSB methods en- hance reasoning by following the Ohain-of-Thougee (COT) approach (Wei al., 2022), which decomposes problem- solving into sequence of intermediate reasoning steps, termed thoughts. Building upon this, TSB frameworks such as Tree-of-Thoughes (TOT) (Yao et al., 2023) integrate thought generation and evaluation with search algorithms- such as beam search (Kang et al., 2024) and Monte Carlo Tree Search (MCTS) (Chen et al., 2024; Zhang et al., 2024b)-1o systematically explore diverse reasoning paths. By incorporating these techniques, TSB methods provide LLMs with deliberate and structured reasoning framework, significantly improving their capability to tackle complex and multi-step reasoning tasks.
However, existing TSB reasoning methods often suffer from substantial inference latency (Gao et al., 2024; Wang et al., 2024e), with inference latency increasing by several or- ders of magnitude (see Figure 1a). The primary bottleneck stems from the need to explore vast number of reason- ing thoughts (see Figure 1b). This substantial increase in inference latency poses significant challenges for practical deployment, particularly in real-time applications requir- ing low-latency performance (Zhou et al., 2024; Xia et al., 2024). However, effective and efficient strategies to acceler- ate slow-thinking reasoning in LLMs without compromising reasoning quality remain largely underexplored.
1. Introduction
The reasoning capabilities of large language models (LLMs) have significantly advanced with the adoption of slow- thinking processes based on tree-search- -aaseed (TSB) rea-
This work was done when Zhihai Wang was an intern Huawei. MMoE Key Laboratory of Brain-inspired Intelligent Perception and Cognition, University of Science and Technology of China "Noah's Ark Lab, Huawei Technologies 'College of Intelligence and Computing, Tianjin University. Correspondence to: Jie Wang <jiewangx ustc.edu.en..
In this paper, we propose Speculative Search (SpecSearch), a novel and efficient framework that significantly acceler- ates LLM reasoning while maintaining comparable qual- ity. At its core, SpecSearch features bi-level speculative
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Accelerating Large Language Model Reasoning via Speculative Search
thought generator, where small model strategically collab- orates with large model at both coarse-grained thought and fine-grained token levels. This innovative design optimizes thought generation efficiency, enabling faster yet effective reasoning. To ensure reasoning quality, SpecSearch pro- poses to filter out thoughts that fall below the quality of the large model's outputs. SpecSearch achieves this by accurately and efficiently estimating the quality through non-parametric statistical estimation method, leveraging historical reasoning thoughts from the large model. More- over, we establish theoretical guarantee that SpecSearch preserves comparable reasoning quality to the large model.
dent on the preceding token's completion (Lu al., 2024; Xia al., 2024). To accelerate L.LM decoding, an innova- tive paradigm (Leviathan et al., 2023; Chen et al., 2023a;b; Yang et al., 2024; Li et al., 2024; Kou et al., 2024; Zhong & Bharadwaj, 2024) introduces the idea of speculative ex- ecution (Burton, 1985; Hennessy & Patterson, 2012) as in computer architecture to LLM decoding in a draft-then- verify style. Specificallyy, speculative decoding methods speculatively draft sequence of tokens via small model, and then verify the sequence via a large model in parallel, thus speeding up the LLM decoding process (see Figure 6a in Appendix B). However, speculative decoding- token- level inference acceleration method can be poorly aligned with optimizing search-based reasoning approaches that in- volve intricate, non-seqqential reasoning thought generation, leading to suboptimal acceleration performance. Inspired by speculative execution, we propose novel SpecSearch framework to leverage the inherent structure of TSB reason- ing frameworks by formulating both thought and token gen- eration as speculative tasks. To the best of our knowledge, we are the first to well generalize speculative execution to TSB reasoning, providing novel speculative execution formulation for accelerating LLM reasoning. Moreover, we provide detailed discussion on novelty of SpecSearch over standard speculative decoding and TreeBon (Qiu et al., 2024) in Appendix G.
To demonstrate the effectiveness of SpecSearch, we evaluate it on two complex reasoning datasets: MATH and GSM8K. Experiments using both the Qwen and Llama models demon- strate that method significantly outperforms state-of of-tee art (SOTA) approaches, achieving up to 2.12x speedup while maintaining comparable reasoning quality. More- over, experiments demonstrate that SpecSearch seamlessly integrates with several tree search algorithms and thought evaluators, delivering substantial acceleration without com- promising reasoning quality. These results underscore Spec- Search's ' ability to significantly enhance the efficiency of existing TSB reasoning methods.
We summarize our major contributions as follows. (1) A Novel SpecSearch Framework Observing that thought gen- cration is a major efficiency bottleneck, we propose Spec- Search, which utilizes a small model collaborating with a large model at both coarse- coarse-grained thought and fine-grained token levels. This design significantly improves thought generation efficiency, thereby accelerating LLM reasoning. (2) Presevin Rejection Mechanism To ensure high reasoning quality, we propose to filter out thoughts whose quality falls below that of the large model's outputs, and efficiently estimate the large model's quality via its historical reasoning thoughts. (3) Theoretical Guarantee We provide theoretical analysis showing that SpecSearch preserves reasoning quality comparable to that of the large model. (4) Significant Speedup and Versatility Exper- iments demonstrate that SpecSearch significantly outper- forms SOTA approaches, achieving up to 2.12x speedup while preserving comparable reasoning quality. Moreover, experiments demonstrate the strong compatibility of Spec- Search with different LLMs, search algorithms, and thought evaluators, highlighting its broad applicability.
The Novelty of SpecSearch over Speculative Decoding Methods We discuss the novelty of SpecSearch compared to existing SD techniques, emphasizing key distinctions in terms of speculative formulation, verification and re- jection strategies, and theoretical guarantees. (I) Bi- Level Speculative Formulation: Unlike existing SD meth- ods focused solely on tokens, SpecSearch treats both high- level thoughts and low-level tokens as bi-level speculative tasks. This enables 1) Structural Alignment with rea- soning frameworks, where thoughts are fundamental units, and 2) Compatibiliiyy with standard SD methods through low-level teken-level speculation. (2) Contextual Veri- fication for Higher Acceptance and Speedup: Unlike existing SD methods that enforce strict token-level align- ment, leading to frequent rejections, SpecSearch verifies the contextual quality of reasoning thoughts. This al- lows acceptance of correct but non-aligned outputs, substan- tially boosting acceptance rates and achieving significant Rejection Mechanism: Unlike token-level rejection in standard SD methods, Spec- thought-level rejec- tion based on contextual quality. It discards entire thoughts only when their quality is lower than the large model's, en- suring high-quality reasoning throughout decoding. (4) The- oretical Guarantee of Reasoning Quality: While standard SD methods preserve token-level distributions, SpecSearch guarantees that reasoning quality remains comparable with
speedups. (3) Quality-Preservvvn
Search proposes quality-preserving
2. Related Work
Speculative Decoding As the number of parameters in LLMS increases, inference latency has become major ob- stacle to their broader applications (Zhou et al., 2024; Wan et al., 2024b; Xia et al., 2024; Zhang et al., 2024a). This latency is primarily caused by the autoregressive decoding process, where each token is generated sequentially, depen-
2

---

Accelerating Large Language Model Reasoning via Speculative Search
outputs from the large model.
3. Background
Tree-Search-Basee Reasoning Acceleration In recent years, free-search-based reasoning methods (Yao et al., 2023; Hao et al., 2023; Hui et al., 2024; Wan et al., 2024a; Jiang et al., 2024; Wu et al., 2024; Xie et al., 2023) have significantly enhanced the reasoning capabilities of LLMs. To accelerate tree-search-basee reasoning, Gao et al. (2024) directly integrate standard speculative decoding techniques with reasoning methods. Subsequently, SEED (Wang et al., 2024e) proposes Scheduled Speculative Decoding method, which manages the scheduling of parallel small models based on only one shared large model. These methods improve the efficiency of tree-search- baseed reasoning meth- ods, demonstrating the potential of designing speculative execution strategies in the LLM reasoning framework. How- ever, these methods primarily design speculative execution strategies at the token level, neglecting the inherent struc- ture of LLM frameworks, where reasoning thoughts are fundamental units. This oversight results in suboptimal acceleration performance. In contrast, our SpecSearch pro- poses a novel bi-level speculative thought generator, which utilizes small model collaborating with large model at both barse-grained thought and fine-grained token levels, leading to significant acceleration with comparable quality.
Speculative Sampling in LLM Decoding We introduce Speculative Sampling (SpS) (Leviathan al., 2023; Chen et al., 2023a), decoding technique that accelerates LLM inference while preserving the target model's 's distribution. Given a prefix c, a draft model Mgs a target model Mp. and step size y, SpS operates in two phases. (1) Drafting My autoregressively generates y tokens 21, Tg....., Ez.. (2) Verification M, verifies these tokens in parallel, accepting 2, with probability min (1, M, (agalm ( 1. If x; is (
rejected, a resampling method generates ãς. This process theoretically guarantees alignment with the target model's distribution while significantly enhancing inference speed.
Sre-Search-Baaseee Reasoning Methods Tree-search- based reasoning methods formulate tree nodes as interme- diate reasoning steps (thoughts) and tree paths as potential solutions to multi-step reasoning problems. They comprise a Thought Generator (G), a Thought Evaluator (V), and a search algorithm (see Figure 6b in Appendix B). From the root node (c, input question). G expands the tree by gener- ating N child nodes (thoughts). V evaluates their quality, guiding the search algorithm. This iterative process con- structs reasoning tree, culminating in final reasoning path P. formed by ,....., 21 c. Common search algorithms in- clude Beam Search and MCTS. See Appendix B for details.
The Novelty of SpecSearch over TreeBon (Qiu et al., 2024) We discuss the novelty of SpecSearch compared to Treebon (Qiu et al., 2024), emphasizing key distinctions in terms of motivation, speculative formulation, rejec- tion strategies, and theoretical guarantees. (1) Distinct Motivation: Unlike Treebon, which targets accelerating best-of-n sampling through speculative rejection combined with tree search, SpecSearch is the first to well generalize speculative execution to tree-based LLM reasoning. (2) Bi-Level Speculative Formulation: Treebon treats fixed- length token sequences as speculative tasks, while Spec- Search introduces a flexible bi-level moonelnng full reasoning thoughts high-level tasks and tokens as low-level ones. Unlike Treebon's 's fixed-length design, Spec- Search leverages LLMs' reasoning capabilities to gener- ates semantically coherent thoughts of dynamic length. (3) Rejection Mechanism: Treebon re- jects a fixed proportion of token sequences using preset threshold. SpecSearch, instead, scores reasoning thoughts and adaptively rejects those with lower contextual qual- ity based on the large model's reasoning quality, enabling finer control and better quality preservation. (4) Theoret- ical Guarantee: Unlike Treebon, which lacks theoretical guarantees, SpecSearch provides formal assurance that reasoning quality remains uncompromised, matching that of the large model's outputs.
4. Speculative Search for LLM Reasoning
We begin with an overview of the SpecSearch framework in Section 4.1. Next, we detail the formal procedure underly- ing SpecSearch, describing the bi-level speculative thought generator in Section 4.2 and the quality- preserving rejection mechanism in Section 4.3. Lastly, we present the theoretical guarantee of SpecSearch in Section 4.4.
4.1. Overview of Speculative Search Framework In this part, we first present several key motivations for proposed SpecSearch. Then, we describe the overview of SpecSearch as shown in Figure 3.
Thought generation dominates computa- tion time in tree-search-based reasoning, consuming over 91 of total runtime in reasoning (see Figure lb).
Motivation 1:
Motivation 2: Small models can generate high-quality reasoning thoughts. In multi-step reasoning, some steps are inherently simpler than others. For example, solving +99 requirs computing 992 ("harder")) and 9900-1 ("easier"). Moreover, an analysis of the quantized Qwen2.5- In- model shows that over 40% of its reasoning, thoughts outperformed the average reward score of those from the larger Siven2.5-72B-Instie
model (see Figure 2a). The findings suggest that assigning simple steps to small model and complex ones to a large model can speed
3

---

Accelerating Large Language Model Reasoning via Speculative Search
843
Langr Tmweitin
Leng: KCal Morrayy
fundamental unit (i.e., a node) within the reasoning tree. This structure allows for effective utilization of components such as the thought evaluator, enabling seamless integration into the reasoning process. Second, since single thought typically comprises more than fifty tokens (see Table 8 in Appendix I.2), thought-level speculation facilitates coarse- grained collaboration, increasing the number of tokens gen- erated by the small model throughout the search process. This, in turn, can significantly enhance the efficiency of thought generation. Third, it harnesses the reasoning capa- bilities of small models to generate high-quality thoughts (see Figure 2a). As a result, it carries the potential to main- tain or even improve reasoning quality compared to the original large model (see Tabel in Section 5).
0421
Fraquaro
Accuracy
4.0
Roward Vatue (Small Medil)
% Large Modd
(b) Large Model Engagement Figure 2. (a) Small models can generate thoughts with high re- ward scores. (b) Simple large model engagement strategies at the thought level struggle to preserve comparable reasoning quality.
(a) Scores of Small Model
up reasoning without sacrificing accuracy.
Motivation 3: Simple large model engagement strate- gies at the thought level struggle to maintain reasoning quality. Motivated by Motivation 2, we design simple large-model engagement strategy where thought evaluator scores the small model's outputs, and the bottom X% (X is a hyperparameter)) is reprocessed by the large model for refinement. However, as shown in Figure 2b, maintaining reasoning quality remains challenging when collaboration occurs at the thought level.
Algorithm Design We propose the following bi-level spec- ulative thought generator, which follows draft-evaluate- reject-correct paradigm. First, it drafts multiple reasoning thoughts using small model, then evaluates the quality of these thoughts and rejects those of low quality. Finally, the rejected thoughts are corrected using a lossless token-level speculative decoding method.
(1) Drafting Phase at the Thought Level To leverage the reasoning capabiliiy of small models, as shown in Figure 2a, we propose using a small model to efficiently generate multiple reasoning thoughts. These drafted thoughts serve as potential candidates for further evaluation and correction.
Overview of SpecSearch Building on the aforementioned key motivations, SpecSearch proposes a bi-level specula- tive thought generation framework, leveraging both small model and a large model to efficiently produce high-quality reasoning thoughts. Guided by a thought evaluator, this method operates at both the thought and token levels, inte- grating seamlessly into any search algorithm as an efficient node expansion module.
(2) Evaluating Phase at the Thought Level To evaluate the quality of the generated thoughts. previous speculative decoding methods (Xia et al., 2024; Zhang et al., 2024a) typ- ically use large model to verify the token sequences within each thought. Verifying thoughts with large model poses several challenges. First, it struggles to capture the intrinsic structure and semantics of reasoning thoughts, leading to potential evaluation inaccuracies. Second, while token-level distributions are well understood, preserving thought dis- tributions is far more complex. The exponential growth of possible thoughts makes accurate modeling difficult. Third, in tree-search- based reasoning, multiple valid paths can lead to the same answer, creating ambiguity in defining lossless thought generation. A speculative model may generate dif- ferent reasoning paths than a large model while still being correct. Overall, these challenges significantly limit the accuracy and efficiency of large-model-base verification.
The bi-le speculative thought generation follows draft- evaluate-reject-corree paradigm, where the first three stages operate at coarse-grained thought level, while the final stage refines outputs at a fine-grained token level. Ini- tially, a small model drafts multiple reasoning thoughts, which are then evaluated by thought evaluator to reject low-quality candidates. Finally, lossless speculative decod- ing method corrects the rejected thoughts, ensuring robust and accurate reasoning.
4.2. Bi-Level Speculative Thought Generator
This section first discusses the advantages of using small model in collaboration with a large model at both the coarse- grained thought and fine-grained token levels. We then describe the bi-level speculative thought generator. An il- lustration of the generator is provided in Figure 3. The procedure is summarized in Algorithm
To address these challenges, we propose utilizing the inher- ent thought evaluator within the existing L.M reasoning framework for accurate thought evaluation. For example, a process reward model (PRM) can be employed to assign a reward score to each thought, offering an accurate evaluation of its quality. This approach addresses the aforementioned challenges and offers several advantages. A detailed discus- sion is provided in Appendix H.I
Advantages Compared to standard token-level speculative decoding (Xia et al., 2024; Zhang et al., 2024a; Leviathan et al., 2023; Chen et al., 2023a; Li et al., 2024), thought- level speculative execution offers several key advantages. First, it leverages the inherent structure of the tree-search- based reasoning framework, where each thought serves as

---

Accelerating Large Language Model Reasoning via Speculative Search
Speculative Search Framework
(b) Bi-Level Speculative Thought G Generator
(c) Quality quality-Preseete Preserving Rejection Mechanism
Beam Search Tree
1) T'hought-Lee evell Drafting Small Model
1) Step-WWise I'hreshold from the L arrg Model
077
Input-Question
0.6
Large Model
BI-Loval Speculative
0.5
Qualitty
Step
Thought Geuerator
2) T'houghttL evel Evaluation
T hought Evalustor
Drafted Thoughts
Generated Thoughts
Thought Evaluuttr
Estimate
0,7
0.8
0.5
0.5
2) Statistical Estimation via Historical Reasoning Thoughts
Historical
Selected, Thought
3) Re ection and Correction
Reasoning Thoughts
Bi-Level Spoculative
Thought-Leve Rejection
Step
Thought Generator
X
X
Thought Evaluetor
Token-Level Specullatie Model
Conrect
Generated Thoughts
Update
Accepted Thougghts
Cormectood Thoughts
Gemerated Thoughts
Search Tree
Figure 3. Illustration of our proposed SpeeScarch. SpecSearch proposes a bi-level speculative thought generator with a preeetiip rejection mechanism, which significantly accelerates LLM reasoning while preserving comparable quality.
(3) Rejection Phase at the Thought Level The primary objective of this phase is to effectively reject generated thoughts that are of lower quality than the large model's outputs-a task made particularly challenging by the lack of access the large model's outputs. To address this challenge, we propose novel
(Quality of Thoughts and Thought Gen- erators) The quality of a thought 2 is given by V(z). The reasoning quality of a thought generator G is defined as Ez-G(-I=ew) [V))].
Definition 4.1.
Based on the aforementioned definition, we can compare the quality of our speculative thought generator with that of the large-model-based thought generator. Thus, we present a condition under which our speculative thought generator achieves undegraded quality compared to the large model.
rejection
mechanism, as detailed in Section 4.3.
(4) Correction Phase at the Token Level To correct re- jected low low-quality thoughts, we propose utilizing a lossless token-level speculative decoding method to refine them at fine-grained token level. By applying lossless speculative decoding, we ensure that the corrected thoughts maintain the same distribution the large model's outputs. For token- level correction, we propose regenerating the entire thought using a token-level speculative model to replace the rejected one for simplicity. Unless otherwise specified, we use the terms 'large model" and "token-level speculative model" interchangeably in the following.
Definition 4.2. (Undegraded Quality Condition) Let Gp be the large-model- based thought generator, with quality Up = E.~G,( =<*) [V (=)]. Let G. be our speculative thought generator. The undegraded quality condition is defined as (gNG,((IRC)) [V(=)] 2 Hpp
Based on this condition, we first analyze the quality of our speculative thought generator. In general, the generator op- erates by first generating N thoughts using small model, rejecting M low-quality thoughts, and then correcting the re- jected M thoughts using a large model (speculative model).
4.3. Quality-Preservvng Rejection Mechanism
Unlike standard token-level speculative decoding, our ap- proach has the potential to significantly reduce inference latency through thought-level speculation, as discussed in Section 4.2. However, since reasoning thought consists of more than fifty coken-generation steps, a small model is more prone to generating misleading thoughts, as errors can accumulate across multiple loken-generati steps. There- fore, a robust thought rejection mechanism is essential to ensure reasoning quality. To address this mallit-pressrrvng challenge, we first present several mathematical definitions.
We present an intuitive analysis as follows. In extreme cases, an overly lenient rejection criterion results in M = 0, mean- ing no thoughts are rejected, and the generator relies entirely the small model. Under these conditions, the acceleration ratio is maximized. However, the quality of the generated thoughts tends to be suboptimal, as the small model is gener- ally less capable than the large model. Conversely, if the re- jection criterion is too strict, M = N, meaning all thoughts are rejected, reducing the generator to a fully large-model- based approach. While this guarantees reasoning quality, it significantly diminishes acceleration benefits. Therefore, achieving an optimal balance between rejection stringency and computational efficiency is essential to maintain both reasoning quality and acceleration gains.
Let Z be the set of all possible reasoning thoughts, and let V : z + [0, 1] be a process reward model (PRM) that as- signs a quality score to each thought. Given a sequence of generated thoughts Ek-1, 2k-2; ., 21 and an initial condi- tion e (c.g., input question and prompt), a thought generator G samples thoughts from the distribution G(-|a<k) over Z.
Rejection Mechanism Based on Step-Wiss Threshold from the Large Model To implement the aforementioned
5

---

Accelerating Large Language Model Reasoning via Speculative Search
Algorithm 1 Bi-Level Speculative Thought Generator G.
task would be infeasible. Fortunately, our observations in- dicate that the quality of the large model's outputs tends to decrease as the reasoning process progresses (see Figure 7 in Appendix 1.2). This suggests that at the (k + 1-th reason- ing step, the quality of the large model's outputs from the previous k steps can serve as an approximate upper bound for the current step's s quality estimate. Building on this ob- servation, we propose a two-stage estimation method. First, we estimate the large model's 's quality each of the previous k reasoning steps through any con-parametric estimation method. Then, we apply an ensemble weighting technique to these ls steps to derive an approximate upper bound for the large model's ' quality at the (k + 1))th reasoning step. Specifically, we incorporate an Exponential Moving Aver- age (EMA) (Klinker, 2011) over the preceding k steps. This approach ensures stable estimation, efficient utilization of historical data, adaptability to dynamic quality shifts, and minimal computational overhead. The update method is as follows: ((k+1) = 0,3(k) + (1 - 0)0 (1)) where is a hyperparameter controlling the relative importance of histor- ical data ((k) and current observations V((k) i= 1,..., M in the weighted average. Here, θ represents a nonparametric estimation method, such as the sample mean, the confidence (k) upper bound of pa or the maximum value.
I: Input: A sequence of thoughts kck. token-level spec- ulative model Gp. small model Cy. evaluation model V. step-wise threshold (( expansion width N, EMA weight 0, nonparametric estimation method O.
2: T + (<x)
1 - G. Z<c),, i= L ] Drafting in Parallel > Evaluating in Parallel
3: V+ V(T)
4: Initialize Ty f- 0. Tp + 01
5: for i = to =oo
do
6: if v|o] 2 8(h) then
b Rejection Phase
7: Accept thought: Tg - Ty U {T
8: else
9:
* + Gp =<c))
Correction Phase
10: Tp +- Tp U zxx)
11: end if
12: end for
13: Vp f- -(Tp))
> Evaluating in Parallel
14: 3(++1) + 03((k + (1-1 (10)))())) &> Updating threshold
15: return 3( ,T,
rejection mechanism, we propose a step-wise threshold- based rejection method. This approach involves establishing a dynamic threshold at each reasoning step, filtering out all thoughts that fall below this threshold to achieve quality- preserving rejection. Intuitively, if the dynamic threshold can be calibrated to reflect the quality of the large model, it is possible to maintain undegraded quality while simultane- ously achieving acceleration. This idea is intuitive, and we further validate it theoretically in Section 4.4.
In practice, the number of samples from Gp may be limited, leading to highly inaccurate estimates of the large model's quality and, consequently, a significant decline in the quality of generated thoughts. To better utilize historical sample information from the tree search process and improve esti- mation accuracy, we incorporate data from the small model that passed the rejection phase. We treat these samples as an approximate upper-bound estimate of the large model's 's quality and integrate them into our estimation framework.
However, at the k-th reasoning step, the quality of the large model remains unknown. Fortunately, sampled thought data from the large model is available from previous reasoning steps. Thus, we formulate the step-wise threshold design problem as estimating the large model's 's quality at the cur- rent reasoning step based on historical reasoning thoughts collected during the tree search process.
4.4. Theoretical Guarantee of Undegraded Quality
We provide the following theoretical analysis to demonstrate that our SpecSearch can guarantee undegraded reasoning quality. We provide detailed proof in Appendix A.
In this section, we analyze the integration of SpecSearch with the beam search algorithm, which operates with a max- imum reasoning depth of K. At each step. the algorithm generates N candidate thoughts and selects the best one.
Problem Formulation of Step-Wise Threshold Estima- tion At the k-th reasoning step, we have access to histori- cal data from all previous reasoning steps, along with M corrected thoughts sampled from the large model (spec- ulative model) Gp. whose qualities are represented as vy(4) - (v (x() v "il,,..., v.()) J. The objective is to utilize this sequence of quality values to predict the large model's thought quality the next reasoning step and set this esti- mate as the threshold ((k+1) for the (k + 1)-th step.
Let G, and G. denote the large model (speculative model) and the small model. Due to the complexity of large lan- guage models, rigorous mathematical reasoning is challeng- ing. To simplify the mathematical derivation, we assume that, at the k-th reasoning step, the qualities of thoughts generated by Gp and G2 independently follow normal distri- butions, N
Statistical Estimation via Historical Moving Average To solve the estimation problem, we must leverage the corre- lation between the large model's quality across different reasoning steps. Without this correlation, the estimation
W1p
(14 oop and N
(k) (A)
(Mg o. (()) respectively,
where up 2 mg (k) > O. This assumption is commonly used in data science (Gopinath, 1998; Zhang, 2010).
6

---

Accelerating Large Language Model Reasoning via Speculative Search
Denote our speculative thought generator with threshold
undegraded quality is given by:
((k), = 1,2, K as G. ((B( K )==)) where K is the
(k) P P( 2 Up , kisksk K)
)) 2
maximum number of reasoning steps. Note that we use g(k) to denote general threshold, while ((() represents the esti- mate of the threshold obtained using our estimation method. The following theorem guarantees that, under ideal condi- tions, as long as the threshold meets or exceeds the quality of the large model, our generator ensures the undegraded quality condition defined in Definition 4.2.
(1-
+( (लो+ viz 1o.
This probability bound increases monotonically with respect to the sample size N. Furthermore, as N + oc, the lower bound approaches 1, implying that our speculative generator can achieve higher reasoning quality by generating more samples during the drafting phase. A detailed discussion of this result is provided in Appendix A.5. 5. Experiments
Theorem 4.3. (Quality-Peseervinn Condition on the )(=)) preserves un- degraded quality if the following condition holds: ((0) Z
Threshold) The generator G. (13()) K
(k) wk- Hp
1.2...., K.
Our experiments have four main parts. Experiment 1. We evaluate the performance of SpecSearch and the baselines on different datasets and LLMs. Experiment 2. We eval- uate the generalization performance of SpecSearch across different search algorithms and thought evaluators. Experi- ment 3. We conduct carefully designed ablation studies to demonstrate the effectiveness of SpecSearch. Experiment 4. We perform a visualization analysis of SpecSearch to provide further insight into SpecSearch.
This theorem provides a the threshold in our designed speculative thought generator. Specifically, if the threshold estimation method proposed in Section 4.3 satisfies this condition, then our SpecSearch guarantees undegraded quality.
condition on
We then make the following quality-descending assumption based on our observations in Figure 7 in Appendix I.2.
Assumption 4.4. (Descending Quality and Bounded Vari- ance) At the k-th step in the beam search algorithm, which selects the candidate with optimal quality, we assume that (k-1) Vk: = 1,2,.... K, where 7 1 is the decay factor. We further assume that op
Experimental Setup We use quantized Qwen2.5-72B- Instruct and Qwen2.5-7B-Instru (Team, 2024) as large and small models, respectively, along with quantized Llama3- and Llama3-8B -B-Instruct (Dubey et al., 2024). Unless stated otherwise, experiments follow OpenR (Wang et al., 2024a) settings: tree width of 6, tree depth of 50, MATH-ps psa as the process reward model (PRM), Qwen mod- cls as the main LLMs, and beam search as the main search algorithm. Throughout all experiments, we set the EMA weight 0 in SpecSearch to 0.9
(k) S Tlp "T1("-1),
(k) < Je: Vk-
1, 1. K, where de > 0 is a constant.
Building upon this assumption, the following theorem estab- lishes a lower bound on the probability that our speculative thought generator preserves quality at each reasoning step.
Theorem 4.5. (Probability Bound for Step-Wise Quality- Preserving) Consider speculative thought generator Jkm)). Given that weight 2 y and at step
Baselines This study aims to accelerate thought generation in reasoning trees without modifying search algorithms or prompting techniques. Thus, we compare our method with two baselines: (1) AR, the original ToT method using au- toregressive decoding with a large model, and (2) SpS, a state-of-the aht (SOTA) lossless speculative decoding ap- proach. Details are in Appendix D.
G. (13(k) K k 1²1,, 1, the generator G, preserves undegraded quality, the lower bound for the probability that at step k + 1 it also preserves undegraded quality is given by:
P (B(++)) 2
14p
(k+1)
((k)
2 11
(8)
Datasets We use two well-established mathematical problem datasets, GSM8K (Cobbe et al., 2021) and MATH (Hendrycks et al., 2021), to evaluate the acceleration performance of the proposed framework. GSM8K contains high-quality elementary mathematics word problems, while MATH comprises advanced high school competition-level math problems. Due to the long testing times of tree-search- based reasoning methods, we randomly select 100 samples from both the GSM8K and MATH datasets for evaluation.
?
(1)
(o.)"
Furthermore, for beam search algorithm with up to K reasoning steps, we derive lower bound on the probability that our speculative thought generator maintains undegraded quality, as stated in the following theorem.
Theorem 4.6. (Probability Bound for
For speculative thought generator Gs ((3(k) 1 K J k=l) with a maximum of K reasoning steps, where K E N. and weight 0 2 7/ the lower bound on the probability of G2 preserving
Evaluation Metrics. We use two widely-used metrics, ac- curacy and speedup, to compare our method's 's performance with that of the baselines. We define the accuracy by the
7

---

Accelerating Large Language Model Reasoning via Speculative Search
Table 1. The results demonstrate that SpecSearch significantly accelerates LLM reasoning with comparable reasoning accuracy.
Dataset
MATH-100
JSM8K-100
Reasoning Accuracy (9e)
Average Inference
Speedup (vs AR)
Speedup (vs SpS)
Reasoning Accuracy (8o)
Average Inference I Latency (S}
Speedup (vs AR)
Speedup (vs SpS)r
Models
Methods
Latency (8)
AR SpS
87.00
275.78
NA
0.51
97.00
138.24
NA
0.50
Qwen
88.00
141.55
1.95
NA
97.00
69.43
1.99
NA
SpecSearch (Ours)
87.00
82.35
3,35
1.72
96.00
48.18
2.87
1.44
Reasoning Accuracy (%-)
Average Inference Latency (S]
Speedup (vs AR)
Speedup SpS)
Reasoning Accuracy (9t)
Average Inference Latency (s)
Speedup
Speedup SpS)f
Methods
(vs AR)
AR
62.00
170.84
NA
0.79
87.00
90.04
NA
0.71
Llama
SpS
61.00
134.34
1.27
NA
86.00
64,29
1.40 1.99
NA
SpecSearch (Ours)
64.00
129.65
1.32
1.04
88.00
45,34
1.42
percentage of correct predictions. We define the speedup by the ratio of the baseline's 's latency to our approach's 's latency.
it with two PRMs-MMath-Shpphee (Wang et al., 2024c) and MATH-psa -ssa (Wang et al., 2024a)-on beam search. As shown in Table 2, SpecSearch maintains nearly the same ac- curacy while sigmificantly accelerating inference across dif- ferent PRMs, achieving up to 2. 12x speedup. This demon- strates its strong adaptability to various evaluators.
Experiment 1. Main Evaluation We evaluate SpecSearch against two competitive baselines on two math datasets using the Qwen and Llama models. Table I highlights three key findings. Moreover, we provide additional evaluation on four more distinct dataset categories, including the full GSM8K, AIME, Olympiad Bench, and code-generation benchmark, in Appendix I.1.
Experiment 3. Ablation Study As the MATH dataset is harder than the GSM8K dataset, we perform an abla- tion study and sensitivity analysis on the MATH dataset. Specifically, we further randomly sample 50 problems from MATH-100, called MATH-50.
(1) High Speedup SpecSearch consistently outperforms all baselines, achieving up to 1.72x speedup over SpS and 3.35 over AR on MATH-100 with Qwen. (2) Broad Com- patibility Our method accelerates both Llama and Qwen models, demonstrating strong adaptability across LLMs. (3) Superior Reasoning Ability On Llama, SpecSearch sur- passes baselines in reasoning accuracy on MATH-100 and G008K-100, highlighting the strong ability of our Spec- Search to effectively collaborate the small and large models to maintain reasoning (4) Accuracy Degradation Analysis We conduct case study to explore the reasons GSM8K-
Contribution of Each Component To assess the effec- tiveness of each component, we conduct an ablation study, For the Evaluation Module in SpecSearch, we replace PRM evaluation with evaluation via the log probabilities of a large model. For the Rejection Module, we compare three variations: SpecSearch with Fixed Large Model En- gagement (SpecSearch w/ FLME). SpecSearch with Fixed Threshold (SpecSearch w/ FT), and SpecSearch with Ran- dom Rejection (SpecSearch w/ RR). SpecSearch w/ FLME implements simple collaboration strategy between large and small models. SpecSearch w/ FT replaces the step-wise threshold estimation with a fixed threshold in the rejection process. SpecSearch w/ RR randomly rejects 50% of the small model's s generated thoughts. As shown in Table 3, our evaluation and rejection modules are both essential for pre- serving reasoning quality, suggesting that each component in our proposed SpecSearch are important for its significant performance improvement.
behind the accuracy degradation of SpecSearch 100. The results in Appendix I.3 show that the degradation primarily arises from certain misleading thoughts that de- ceive the PRM.
Experiment 2. Generalization We evaluate SpecSearch's generalization across different search algorithms and thought evaluators on GSM8K-100. Due to limited space, we defer results on MATH-100 to Appendix I.4.
Search Algorithms To demonstrate the broad applicability of SpecSearch, we apply it to two distinct search a algorithms: beam search and MCTS. We compare SpecSearch against AR and SpS on both algorithms. As shown Table 2, Spec- Search significantly outperforms the baselines, reducing inference latency while maintaining comparable accuracy. These results highlight both its efficiency and its adaptability across different search algorithms.
Sensitivity Analysis (1) The EMA Weight 6. We analyze the sensitivity of SpecSearch to the EMA weight B. Due to limited space, we defer results to Appendix 1.6. The results in Table 11 in Appendix I.6 show that SpecSearch achieves similar average performance across a wide range of 0. (2) Draft Model's Size We have investigated SpecSearch's per- formance using multiple small draft models. The results in Table 10 in Appendix 1.5 reveal that SpecSearch achieves speedups ranging from 2. 28x to 2.87x, underscoring its ac- celeration capabilities across diverse small-mode settings.
Different Thought Evaluators To evaluate the general- ization of SpecSearch across thought evaluators, we test
8

---

Accelerating Large Language Model Reasoning via Speculative Search
Table 2. The results demonstrate the Broad Compatibility of Our SpecSearch with different search algorithms and PRMs.
Search Algorithms
Beam Search
MCTS
Reasoning Accuracy (9) f
Average Inference
Speedup AR)t
Speedup (vs SpSJt
Reasoning Accuracy (%) f
Average Inference
Speedup AR)
Speedup (vs SpS)
Methods
Latency (8)
Latency (8) 4
AR SpS SpecSeurch (Ours)
97.00
138.24
NA
0.50
98.00
256.17
NA
0.51 NA
97.00
69.43
1.99 2.87
NA
98.00
129.74
1.97 2.61
96.00
48.18
1.44
98.00
98.16
1.32
PRMs
Math- ShephSh
Math-psa Average Inference
Reasoning Accuracy (%) 1
Average Inference
Speedup (vs AR) f
Speedup (vs SpS)
Reasoning Accuracy (96) f
Speedup (vs AR)
Speedup (vs SpS)
Methods
Latency (s)
Latency (s) J
AR
96.00
124.76
NA
0.51 NA
97.00
138.24 24
NA
0.50
SpS
95.00
64.17
1994
97.00
69.43
1.99
NA
SpeeSearch (Ours)
94,00
30.32
4.11
2.12
96.00
48.18
2.87
1.44
6. Conclusion
Table 3. The results demonstrate that each component within Spec-
We propose Speculative Search (SpecSearch), a framework that accelerates reasoning by enabling small model to gen- erate speculative thoughts with a large model at both thought and token levels. With nism, SpecSearch theoretically maintains reasoning quality comparable to the large model. Experiments show up to 2. 12x speedup while preserving high reasoning quality.
Search is significant for maintaining reasoning accuracy.
Dataset
MATH-50
Methods
Reasoning Accuracy (9-)
Average Inference
Speedup (vs AR)
rejection mecha-
Latency (s),
AR
88.00
256.05
NA
SD
90.00
132.68
1,93
SpecSearch (Ours)
88.00
70.63
3.63
Evaluation Module
SpecSearch w LMV
78.00
172.26
1.49
Acknowledgements
Rejection Module
This work was supported in part by National Key R&D Program of China under contract 2022ZD01 19801, National Nature Science Foundations of China grants U23A20388 and 62021001. This work was supported in part by Huawei as well. We would like to thank all the anonymous reviewers for their insightful comments.
SpecSearch w FT
80.00
68.88 84
3.72
SpeeScarch w RR
80.00
99.73
2.57
SpeeSearch w FLME
84.00
105.25
2.43
Owen Model
Llaasa Models
0.90
Spo
5p5
Impact Statement
Avtrage Rowied
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential socictal consequences of our work, none of which we feel must be specifically highlighted here.
Reasening Stop
Reasening
(a) Qwen Models
(b) Llama Models
Figure 4. To verify that our method preserves comparable reward
References
scores for reasoning thoughts, we visualize the average reward scores each reasoning step during the tree scarch process.
Berto, F., Hua, C., Park. J., Kim, M., Kim, H., Son, J., Kim, H., Kim, J., and Park, J. RL4CO: a unified rein- forcement learning for combinatorial optimization library. In NeurIPS 2023 Workshop: New Frontiers in Gruph Learning, 2023. URL https: /oppnreveevveeeee nne// forum? ? d iddv.
Experiment 4. Visualization Analysis To evaluate whether our SpecSearch can preserve comparable reward scores for reasoning thoughts, we visualize the average reward scores at each reasoning step during the tree search process for SpecSearch and the basclines on the MATH-100 dataset. As shown in Figure 4, SpecSearch achieves reward scores comparable to those of the large model across all reasoning steps. This result highlights SpecSearch's ability to signifi- cantly accelerate inference while maintaining comparable reasoning quality to the large model.
Burkardt, J. The truncated normal distribution. Department of Scientific Computing Website, Florida State University, 1(35):58, 2014.
Burton, E. W. Speculative computation, parallelism, and functional programming. IEEE Trans. Comput-

---

Accelerating Large Language Model Reasoning via Speculative Search
ers, 34(12):119--11)) 1985. doi: 10.1109/TC.1955 6312218. URL htttps::/doi..rgg//. 1109///C... 1985. 6312218.
G., Cucurell, G., Nguyen, H., Korevaar, H., Xu, H., Tou- vron, H., Zarov, I., Ibarra, 1. A., Kloumann, I. M., Misra, I., Evtimov, I., Copet, J., Lee, J., Geffert, J., Vranes, J., Park, J., Mahadeokar. J., Shah, J., van der Linde, J., Bil- lock, J., Hong. J., Lee, J., Fu, J., Chi, J., Huang, J., Liu, J. Wang. J., Yu, J.. Bitton, J., Spisak, J., Park, J., Rocca, J., Johnstun, J., Saxe, J., Jia, J., Alwala, K. V., Upasani,
Chen, C., Borgeaud, S., Irving. G., Lespias, J., Sifree, L., and Jumper, J. Accelerating large language model decoding with speculative sampling. CoRR, abs/2302.01318, 2023a. URL https:// 2302. 01318.
doi: 1048550/ARRXI122322003333 doi. org/10. 4
K., Plawiak, K., Li, K., Heafield. K., Stone, K., and et al. The Ilama 3 herd of models. CoRR, hix/2407.21778. URL https: 2417 21783.
Chen, G., Liao, M., Li, C.. and Fan, K. Alphamath almost zero: process supervision without process. CoRR, abs/2405.03553, 2024. doi: 10.48550/ARXIV.
2024. doi: 10.48550ARRXI.2400...11 //doi. //doi.org//1 wrg. 110
Gao, Z., NIu, B., He, X., Xu, H., Liu, H., Liu, A., Hu, X., and Wen, L. Interpretable contrastive monte carlo tree search reasoning. CoRR, abs/2410.01707, 2024, doi: 10.45550ARRXV.244000000000 URL https: /oii. org/10. 4 2t1p5//0002x11221.001000000 01707.
2405.03553. URL https: / http://ooooooo/// 4805.445//0.4850 48550/ arXiv. 2405, 03553.
Chen, Z., Yang, X., Lin, J., Sun, C., Huang, J., and Chang, K. C. Cascade speculative drafting for even faster LLM inference. CoRR, abs/2312. 1462, 2023b. doi: 10.48550/ ARXIV.2312.11422 URL https: //d:://doii. org/10. 48550/arxiv 2311 20..2.11221.... 11462.
Geng, Z. Wang, J., Liu, Z. Xu, S., Tang, Z., Yuan, M., Hao, J., Zhang, Y., and Wu, F. Reinforcement learning within tree search for fast macro placement. In Forty- first International Conference on Machine Learning, 2024. URL https:/ /ttp:////pe/e//e/eeeeee net/ forum? id=AJGwSXORUV.
Cobbe, K., Kosaraju, V., Bavarian, M., Chen, M., Jun, H., Kaiser, L., Plappert, M., Tworek, J., Hilton, J., Nakano, R., Hesse, C., and Schulman, J. Training verifiers solve math word problems. CoRR, abs/2 wtt.///11..11.e.. 11..111.1166. 2021. URL 2112 18.68.
ht https: /atps://arxivvi www.aiiww.ggaaaaaaaaaaoaaoo
Gopinath, R. A. Maximum likelihood modeling with gaus- sian distributions for classification. In Proceedings of the 1998 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP'99 (Cat. No. 98CH36181), volume 2, pp. 661-664. IEEE, 1998.
Dekking, F. M., Kraaikamp, C., Lopuhaä, H. P., and Meester, L. E. A Modern Introduction to Probubility and Statis- tics: Understanding why and how. Springer Science & Business Media, 2006.
Guo, H., Liu, Z., Zhang, Y., and Wang. Z. Can large lan- guage models play games? case study of self-play approach. arXiv preprint arXiv:2403.0566 2024.
Delarue, A., Anderson, R., and Tjandraatmadja, C. Reinforcement learning with combinatorial actions: An application to vehicle routing. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 609-620. Curran Associates, Inc., 2020. URL htttps:/pproceeddigs..eees Cc cc/paper files//ppperr/22////ll/ (as3555ee22233722667222222222313 pdf.
Hao, S., Gu, Y., Ma, H., Hong, J. J., Wang, 7., Wang, D. 7 and Hu, Z. Reasoning with language model is planning with world model. In Bouamor, H., Pino, J., and Bali, K. (eds.), Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, EMNLP 2023, Singapore, December 6-10, 2023, pp. 8154-8173, Associ- ation for Computational Linguistics, 2023. doi: 10. V 1V2022.EMMLLPMMATI org wttpi/155/////a htap:///m..222..mmmmmmm....... 507.
URL https: /doi.
Dubey, A., Jauhri, A., Pandey, A., Kadian, A., Al-Dahle, A., Letman, A., Mathur, A., Schelten, A., Yang, A., Fan, A., Goyal, A., Hartshorn, A., Yang, A., Mitra, A., Sravanku-
Hendrycks, D., Burns, C., Kadavath, S., Arora, A., Basart, S., Tang, E., Song, D., and Steinhardt, J. Measuring math- ematical problem solving with the MATH dataset. In Van- schoren, and Yeung, S. (eds.), Proceedings of the Neu- ral Information Processing Systems Track Datasets and Benchmarks 1, NeurlPS Datasets and Benchmarks 2021, December 2021, virtual, 2021.
mar, A., Korenev, A., Hinsvark, A., Rao, A., Zhang, A., Rodriguez, A., Gregerson, A., Spataru, A., Rozière, B., Biron, B., Tang, B., Chern, B., Caucheteux. C., Nayak, C., Bi, C., Marra, C., McConnell, C., Keller, C., Touret, C., Wu, C., Wong, C. Ferrer, C. C., Nikolaidis, C., Allonsius, D., Song, D., Pintz, D., Livshits, D., Fsiobu, D., Choud- hary, D., Mahajan, D., Garcia-Olano, D.,, Perino, D., Hup- kes, D., Lakomkin, E., AlBadawy, E., Lobanova, E., Di- nan, E.., Smith, E. M., Radenovic, F., Zhang, F., Synnaeve, G., Lee, G., Anderson, G. I., Nail, G., Mialon, G., Pang,
Hennessy, J. L. and Patterson, D. A. Computer Architectree A Quantitative Approach, 5th Edition. Morgan Kaufmann, 2012. ISBN 978-0-12-38333
10

---

Accelerating Large Language Model Reasoning via Speculative Search
Hu, J. Reinforce++: A simple and efficient approach for aligning large language models.
S., and Scarlett, J. (eds.), International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Hon- olulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pp. 19274-19286. PMLR, 2023. URL.https://prrocta v202 www.aeeeataaaaaaaaa...m
Hui, W., Jiang, C., Wang, Y., and Tu, K. Rot: Enhancing large language models with reflection on search trees.
.
ml press//
CoRR, abs/2404. 05449, 2024. doi: 10.48550/ARXIV. 2404.05449. URL https:://// /tpp:://doii org/10..//./oooo..ooooo.. 10/......11 48550/ arXiv. 2404 05449.
Li, Y., Wei, F., Zhang, C., and Zhang, H. EAGLE: specula- tive sampling requires rethinking feature uncertainty. In Forty-first International Conference Machine Learn- ing, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024. URL net/ iineenddddiiii 1aN.ummekyb..
Janner, M., Fu, J., Zhang, M., and Levine, S. When to trust your model: Model-based policy optimization. Advances in neural information processing systems, 32, 2019.
Jangg J., Chen, Z., Min, Y., Chen, J., Cheng. X., Wang, J. Tang, Y., Sun, H., Deng. J., Zhao, W. X., Liu, Z., Yan, D., Xie, J., Wang, Z. and Wen, J. Tech- nical report: Enhancing LLM reasoning with reward- guided tree search. CoRR, abs/2411.11694, 2024. doi: 10-45550AARXIV2411.1106 URL https: /doo.. org/10. 485404550////
Liu, Z., Hu, H., Zhang, S., Guo, H., Ke, S., Liu, B., and Wang, Z. Reason for future, act for now: A principled architecture for autonomous Ilm agents. In Forty-first International Conference on Machine Learning, 2023.
2411 11694.
Lu, J., Yang. Z., Wang. Y., Liu, X., Namee, B. M., and Huang, C. Padellm-ner: Parallel decoding in large language models for named entity recognition. CoRR, abs/2402.0498 04.08888, 2024. doi: 10.48550/ARXII, 2402.04838. URL https: arXiv. arxiv.2402.0. 2402. 04838.
Kang, J., Li, X. Z., Chen, X., Kazemi, A., and Chen, B. Mindstar: Enhancing math reasoning in pre-trained Ilms at inference time. CoRR, 22s/2405.16266 2024. doi: 10.48550/ARXIV.2405..0 16265. URL https: pectps://do: //doi. org/10. 48550 /tt//aiivvvvv////// www.:iwww..........mm 16265.
48550/
16265.
Mazyavkina, N., Sviridov, S., Ivanov, S., and Burnaev, Reinforcement learning for combinatorial optimiza- tion: A survey. Computers Operations Research, 134: 105400, 2021.
Klinker, F. Exponential moving average versus moving exponential average. Mathematische Semesterberichtte 58:97-107,201 2011.
Kou, S., Hu, L., He, Z., Deng, Z., and Zhang, H. Cllms: Consistency large language models. In Forty-first In- ternational Conference on Machine Learning, ICMI. 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024. URL httttp:://openneviee..... http://weeeee.rteeoeeeeeeee id=8uzBOVmhB2
Qiu, J., Lu, Y., Zeng, Y., Guo, J., Geng, J., Wang, H., Huang, K., Wu, Y., and Wang, M. Treebon: Enhancing inference- time alignment with speculative tree-search and best-of-n sampling. arXiv preprint arXiv:2410. 16033, 2024.
Schulman, J., Levine, S., Abbeel, P., Jordan, M., and Moritz, P. Trust region policy optimization. In International conference machine learning, pp. 1889-1897. PMLR, 2015.
Kwon, W. Li, Z., Zhuang, S., Sheng, Y., Zheng, L., Yu, C. H., Gonzalez, J.. Zhang. H., and Stoica, I. Effi- cient memory management for large language model serving with pagedattention. In Flinn, J., Seltzer, M. I., Druschel, P., Kaufmann, A., and Mace, J. (eds.), Pro- ceedings of the 29th Symposium on Operating Sys- tems Principles, SOSP 2023, Koblenz, Germany, Octo- ber 23-26, 2023, pp. 611-626. ACM, 2023. doi: 10. 1145/36000006.613166 URL https: http://oooorro////o 10.1145/360000 36131166006666.1..
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. Proximal policy optimization algorithms. arXiv preprint arXiv: /00iv:/777.0600 170770637777... 2017.
Shao, Z., Wang, P., 7hu, Q., Xu, R., Song. J., Bi, X., Zhang, H., Zhang, M., Li, Y., Wu, Y., et al. Deepseekmath: Push- ing the limits of mathematical reasoning in open language models. arXiv preprint arXiv:2402.03330 2024.
Langley, P. Crafting papers on machine learning. Langley, P. (ed.). Proceedings of the 17th International Conference Machine Learning (/CMI.2000), pp. 1207-1216, Stan- ford, CA, 2000. Morgan Kaufmann.
Team, Q Qwen2.5: A party of foundation models, Septem- ber 2024. URL https: http::///qqnlnng github.giittbb...... blog/ http///we22/..
Leviathan, Y., Kalman, M., and Matias, Y. Fast infer- ence from transformers via speculative decoding. In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato,
Wan, Z., Feng, X., Wen, M., McAleer, S. M., Wen, Y., Zhang, W., and Wang, J. Alphazero- tree-search can guide large language model decoding and training. In

---

Accelerating Large Language Model Reasoning via Speculative Search
Forty-first International Conference on Machine Learn- ing, ICML. 2024, Vienna, Austria, July 21-27, 2024. Open- Review.net, 2024a. URL https: opwnreviee.ee.eeeeeee net/ www.eooououooorrr..ee
Proceedings of the AAAI Conference on Artificial Intel- ligence, wtl.vv37i..2622. URL https::/ojs.sstttt. index. AAAI http://AA//arrilll/leeee////////
Jun. 2023b. doi: 10.1609/
Wan, Z., Wang, X., Liu, C., Alam, S., Zheng, Y., Liu, J., Qu, Z., Yan, S., Zhu, Y., Zhang, Q. Chowdhury, M.. and Zhang, M. Efficient large language mod- els: A survey. Transactions on Machine Learning Re- search, 2024b. ISSN 2835-8856. URL https: : // openrevies http:/iwwwweeeeeeeeeeeeeeee mert/fouu? d=bCCC......... Sur- vey Certification.
Wang, Z Wang, J., Zuo, D., Yunjie, J., Xia, X., Ma, Y., HAO, J., Yuan, M., Zhang, Y., and Wu, F. A hicrarchical adaptive multi-task reinforcement learning framework for multiplier cireuit design. In Forty-first International Conference on Machine Learning, 2024d. URL https: / //ppnnevview net www.fooooooioooiooooo 7GaUSEE..
Wang, Z., Wu, J., Lai, Y., Zhang, C., and Zhou, D. SEED: accelerating reasoning tree construction via scheduled speculative decoding. CoRR, abs/2406. 18200, 2024c. doi: 10.48550/ARXIV.240000 18200. URL https: doi org.org/10. /0//55////iiii 2406. 18200.
Wang, J., Fang, M., Wan. Z., Wen, M., Zhu, J., Liu, A., Gong. Z., Song, Y., Chen, L., Ni, L. M., Yang. L.., Wen, Y. and Zhang, W. Openr: An open source frame- work for advanced reasoning with large language models. CoRR, 0tss22410.09671/ 2024a. doi: 10.48550/ARXIV. 2410.09671. URL httpt::t///// https://doi.... http::://dd..oo/o arXiv. 0 09671.
/tt.tpp://oo...g//1.... org/ 48550/
Wang. Z., Wang, J., Xia, X., Zuo, D., Chen, L., Ma, Y., H. J., Yuan, M., and Wu, F. Computing circuits op- timization via model-based circuit genetic evolution. In The Thirteenth International Conference on Learning Representations, 2025. URL http:::/tpp/eeeeeeeeee /wpp///eee.....e.e///// net http//oruumii=-<H4UU0
Wang. J., Wang, Z., Li, X., Kuang, Y., Shi, Z., Zhu, F., Yuan, Zeng, J., Zhang, Y., and Wu, F. Learning to cut via hierarchical sequence/set model for efficient mixed- integer programming. IEEE Transactions on Pattern Analysis and Machine Intelligence, 46(12)9997-9711, 2024b. doi: 10.1100//AAM..2224..443
Wei, J., Wang, X., Schuurmans, D., Bosma, M., Ichter, B., Xia, F., Chi, E. H., Le, Q. V., and Zhou, D. Chain-of- thought prompting elicits reasoning in large language models. In Koyejo, S., Mohamed, S., Agarwal, A., Bel- grave, D., Cho, K., and Oh, A. (eds.), Advances in Neu- ral Information Processing Systems 35: Annual Confer- ence on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28- December 9, 2022, 2022.
Wang, P.. Li, L., Shao, Z., Xu, R., Dai, D., Li, Y., Chen, D., Wu, Y., and Sui, Z. Math-shepherd: Verify and reinforce Ilms step-by-step without human annotations. In Ku, I.., Martins, A., and Srikumar, V. (eds.), Pro- ceedings of the 62nd Annual Meeting of the Associa- tion for Computational Linguisties (Volume 1: Long Papers), ACL 2024, Bangkok, Thailand, August 1 11-16, 2024, pp. 9426-9439. Association for Computational Lin- guistics, 2024c. doi: 10. 10.16655/1/222444CLLLLO.. 510. URL https:// / /ww./ioooooo 2024. acl-long .0l.oonn.........
Wikipedia contributors. Wikipedia, the free encyclopedia, 2024. URL
Cantelli's inequality www.wwwiiiieiiaa..mmmm title=Cantelli2275 hrtL=aaarteliiegeeneneeaataaada
https://en..iiiieeaaa.oooo. wttpodii..rgg////n//da php?
Wang, Z., Wang, J., Zhou, Q. Li, B., and Li, H. Sample-efficient reinforcement learning via conserva-
1244860887. [Online; accessed 21 21-January-2025).
Wu, Y., Sun, Z., Li, S., Welleck, S., and Yang, Y. Scaling inference computation: compute-optings inference for problem-solving with language models. In The 4th Work- shop on Mathematical Reasoning and Al at NeurlPS'24 24, 2024. URL https: /ttttt:://ppeeeeeeeee wpw.revieweeeeeeeeeeeeeeee net forum? id= JDDWSccBu.
tive model-based actor-critic. Proceedings of the
AAAI Conference on Artificial Intelligence, 36(8): 8612-8620, Jun. 2022. doi: 10.1609/aaai.v36is. 20839. URL https://ojs. org/ index. ahtp/AAAt/arriiile//eeee////
Wang. Z., Li, X., Wang, J.. Kuang, Y., Yuan, M., Zeng, J.. Zhang, Y., and Wu. F. Learning cut selection for mixed-integer linear programming via hierarchical se- quence model. In The Eleventh International Confer- ence on Learning Representations, 2023a. URL https: //tppn/eviww.nee/// net. forrm 2obb2 9bRNcc.
Xia, H. Yang, Z., Dong, Q.. Wang. P., Li, Y., Ge, T., Liu, T., Li, W., and Sui, Unlocking efficiency in large language model inference: A comprehensive survey of speculative decoding. In Ku, I.., Martins, A., and Srikumar, V. (eds.), Findings the Association for Computational Linguistics, ACL 2024, Bangkok, Thailand and virtual meeting, Au- gust 11-16, 2024, pp. putational Linguisties. 2024. doi: 10.18653/V1/2024
Wang, Z., Pan, T., Zhou, Q., and Wang, J. Efficient ex- ploration in resource-restrrited reinforcement learning.
Association for Com-
12

---

Accelerating Large Language Model Reasoning via Speculative Search
FINDINGS-ACLL456. URL https:///ddo org///....11.. 18653/v1/2024, i minginisaaa. 456.
Zhong, W. and Bharadwaj. M. S3D: A simple and cost-effective self-speculative decoding scheme for low- memory gpus. CoRR, abs/2405, .03 14, 2024. doi: 10.4850/ARXIV22405200444 URL https: /doi. org/10 48550/8r2i1. 2405 20314. 4.
Xie, Y., Kawaguchi, K., Zhao, Y., Zhao, X., Kan, M., He, J., and Xie, Q. Decomposition enhances reasoning via self-evaluation guided decoding. CoRR, abs/2305.00633 000033,, 2023. doi: 10448550AARXIV.2500000666 URL https: //doi. org 10.
Zhou, Q., Li, H., and Wang, J. Deep model-based reinforce- ment learning via estimated uncertainty and conservative policy optimization. In Proceedings of the AAAI Confer- ence on Artificial Intelligence, volume 34, pp. 6941-6948, 2020.
2305 00633.
Yang, R., Wang, J., Geng, Z., Ye, M., Ji, S., Li, B., and Wu, F. Learning task-relevant representations for gener- alization via characteristic functions of reward sequence distributions. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 2242-2252, 2022.
Zhou, Z., Ning, X., Hong. K., Fu, T., Xu, J., Li, S., Lou, Y., Wang, L., Yuan, Z., Li, X., Yan, S., Dai, G., Zhang, X., Dong, Y., and Wang, Y. A survey on efficient inference for large language models. CoRR, abs/2404. 149400.112994 14294, 2024. doi: 10.48550/ARXIV.40000 14294. doi. doi.org/10. 485.0//8550//0000 aarivv 2404. 2404.14294,
Yang, S., Huang, S., Dai, X., and Chen, J. Multi-candidate speculative decoding. CoRR, abs/2401.06 006706, 2024. doi: 10:48500ARR1112240..0066 URL https:/ /doi. 2401 06706.
URL https:/
Yao, S., Yu, D., Zhao, J., Shafran, I.. Griffiths, T., Cao, Y., and Narasimhan, K. Tree of thoughts: Deliberate problem solving with large language models. In Oh, A., Naumann, T., Globerson, A.. Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurlPS 2023, New Orleans,
LA, USA, December 10 - 16, 2023, 2023.
Yu, Q. Zhang, Z., Zhu, R., Yuan, Y., Zuo, X., Yue, Y., Fan, T., Liu, G., Liu, L., Liu, X., et al. Dapo: An open-source Ilm reinforcement learning system at scale. arXiv preprint arXiv:2503. 14476, 2025.
Yue, Y., Yuan, Y., Yu, Q. Zuo, X., Zhu, R., Xu, W., Chen, J., Wang, C., Fan, T., Du, 7., et al. Vapo: Efficient and reliable reinforcement learning for advanced reasoning tasks. arXiv preprint arXiv:2504.05//6 2025.
Zhang, C., Liu, Z., and Song, D. Beyond the specula- tive game: A survey of speculative execution in large language models. CoRR, abs/2404. 14897, 2024a. doi: (0.45550/ARXX1224444444777 URL https: // /doi. org 48550 arxiv. 2404. 14897.
Zhang, D., Zhoubian, S., Yue, Y., Dong, Y., and Tang, *: LLM self-training via process reward guided tree search. CoRR, abs/2406.03816 2024b. doi: 10.48500ARKX12240600822 URL https: /ooi. org/10. www8885555/.... 2406 03816.
Zhang, X. Gaussian distribution., 2010.
Zheng, R., Guo, H., Liu, Z., Zhang, X., Yao, Y., Xu, X., Wang, Z., Xi, Z., Gui, T., Zhang, Q., al. Toward optimal Ilm alignments using two- two-player games. arXiv preprint arXiv:2406. 10997,.00. 2024.
13

---

Accelerating Large Language Model Reasoning via Speculative Search
A. Theoretical Analysis
In this section, we provide proof the theorems in the main paper along with further discussions.
To facilitate analytical clarity, our analysis is confined the case that the sample mean serves as the nonparametric estimation method, i.e.
M+1
B(++1) = -8(() +
1-0
Σ
(k)
M
where assume that the large model generates more thought avoid the where M 0. We present further discussion about those settings in Appendix A.5.3 and Appendix A.5.2.
A.1. Proof for Theorem 4.3
Lemma A.1. Let (px) and ((x) denote the probability density function (PDF) and cumulative distribution function (CDF) of the standard normal, respectively. Then for any R. we have
- ((x))(()))))))))))))))))))))))
(4)
distribution
Proof. Notice that
(xx)
(t)dt
t ttp(t)tt
t. di(())
+ -f p(t)d (1)
Tt(()
1=
= (()))
p(t) 12
((x))
(5)
Then have
p(x) x(1 +(x))
(6)
Then prove Theorem 4.3 as follows.
Proof. At step k, let the qualities of thoughts obtained from the small model G, at the k-th step be denoted as (.(h)) i= 1,2,...., and the threshold of the generator as g((). Among those, U thoughts with qualities (A(A)
V > 8. The rest of M N U thoughts are refined by large model Gp with qualities 2, .. U retained with (k) ((k) i 1.2..... N U, along with an additional thought generated with quality (k) NN-++1 by the target model. Then the probability that sample passes the threshold g(k) is given by
((k)
(K)
pig
P.
Φ
(k)
(7)
Og
14

---

Accelerating Large Language Model Reasoning via Speculative Search
Thus, the number of passing thoughts U follows a binomial distribution over N trials:
IN 11
P(U = u) =
P" (1 Pa) Pa)N~ N-"
(8)
For the qualities of passing thoughts Vi,. their distribution is a truncated normal distributionn 2014). The expected quality is computed as
B(K)
(R)
M4
S0
Oq (k)
1/g = E [2(k) = Mgg + 04
(N)
(9)
((k)
puu (k)
1 - +
(k)
0q
Let the mean quality of the new batch of solutions be denoted as
U
N U-+11
(())
+
Σ
Vi(h)
(10)
N +1
j=1
By the law of total expectation(Dekking et al., 2006), we have
E
V
[k)
E
E
[T]]
Σ
P(U
u)
U
u)
N-ut1
Σ ==0
P(U u)
1
(k)
Σ vn(h))
U-
+
j=1
Σ P(U u)
1
(8)
N-
Σ E BIV,
)
1u-w
N+1
8=0
1=1
u
(4)
P(U = u)
N + 11
+
14
= u
N +
==
P(U u)
(1lg - -1 ( ( U-u
N +
14 1p
(k)
N
+
N + Σ
uP(U = =u)
K=0
1/4 up (k)
14
(K)
N + 1 BEU]
Nps
1 +
N 1 (14 - 11)
(1I)
Let
(xx)
h(z) 1 2(x)
(12)
and we have
R((x) -1p(x)(1 (xx)) (x)) ((x)(((()) xx1 (x)))
(13)
(1- )2))2
(1 -1-48 4(x))2
15

---

Accelerating Large Language Model Reasoning via Speculative Search
According Lemma A.I, (px)) x(1 +(x)) 0, i.e. h(x)) x, so the function h(x) is monotonically increasing. Therefore for any k 2 1,
B(k)
(R)
(k)
(k)
(R)
(R)
(k) 1/g = Hq + q
(b)
Myy
2 1g
(k)
+ 0g
h
Up
P4
2 pg
+
(k)
Mp p4
Hp
(14)
(k)
Oq
0g
0q
Substituting into the (11), we obtain that
V (1)
4k 2
(15)
which is the definition of a lossless thought generator.
A.2. Further Discussion on Theorem 4.3
Additionally, we provide the necessary and sufficient conditions for losslessness the following proposition.
Proposition A.2. (Necessary And Sufficient Lossless Threshold Condition) The generator G.(B) is lossless if and only if
for any reasoning step k 2 1.
B(k) 2 Myg a (
(R)
(16)
where (k) the solution the equation
((x)
Pp p4
(k)
(K)
(17)
4(x)
(k)
04
Proof. As shown in the proof for Theorem 4.3, we have
E
V
up
(K)
+
Np.
(nly -1 ).
(18)
N ++1
The condition is equivalent to
8(k)
(1)
g(k) > My + +a (a (
Hgg
(k)
vk 2 1.
(19)
(k)
By the monotonicity of the function h(x)
p0(2) T=) inequality (19) is equivalent to
g(h)
(R)
09
2 h(((k)))
Mp
ugg
Wk 2 1.
(20)
((k)
(K)
1 +
(R)
04
Rearranging, we obtain
(kk)
(K)
(k)
1
(k)
M4
(1)
(K)
Ak 2 1.
(21)
((())
(K)
(k)
on
16

---

Accelerating Large Language Model Reasoning via Speculative Search Substituting into the (18), obtain that (21) is equivalent to
E
(8) Hp
4k 2 1.
(22)
This is equivalent to the definition lossless thought generator.
A.3. Proof for Theorem 4.5
Let the condition be denoted { (x)) }. and have
[(++1) c = 0E ((() |c] + (1 (1--0) 0)L (T())
c)
01g (k) (1 0)
(k) 1 11+1)
up 7 up
(23)
Thus,
g(++1 |c]
up
(k+1)
2
1 7 (k+1)
up
(24)
Then according to condition variance decomposition (Dekking et al., 2006), we have
Var [(k+2) | |c] Var [B (((+)) ee cu0 [c] E [B[arr (3(+1)) |c, |c]
+ 11
(25)
E [(++1) c, c, [c] and II E Var [3(--1) c, |c] For since
where = Var
E g(++1) c(
E [g(++)) ((k
E (,3(R)) (1 -0) cC
AR. (3(8] [c,
(1 -0) (T())
C, ((0)
= 0,((K) + (1 1) (1)
(26)
and therefore we have,
1 = Var 03(0) + (1 0))(() [c] 02Var [300 |c]
(27)
For TT, now that
17

---

Accelerating Large Language Model Reasoning via Speculative Search
Var 3(++1) c, (()
= Var (0(K) + (1 (1-0)1(h) c, (
= (1 V (T()) |c, (0,)
= (1 - 0) Var [E [ c, _(,,), u(ti] | c, 8(8)
(28)
+ E Var (v()) I, uri)] c, c/ )
= (1 - 0)2 (II1 + 112).
(29)
where (h) is the number retained draft thought. We find that
11 = Var
((())
I c, B(,) (300).0))
cc B(K)
= Var
U1
(R)
C,, (c,,800]= =0,
(30)
and
Var (*)) c c,,30k) v(0]
N -11100+1
v,(0) | 300) Ba, 000)
= Var
N UU( +1
(31)
N +1
Since function g(x)
is concave function, therefore according Jensen's Inequality (Dekking et al., 2006).
N-x
II2 ( c, [(]]
(o.h E
((((()
2
E (1()) c,, ((,
(K) 2
N - E (TA) C, ((K) +1
(k))
Op
(32)
N Np. +1
where Ps is defined in (7). Given condition where 3(k)
Up
(8)
then
(3(h)
(K)
(k)
(R)
(k)
(k)
M4g
Hy
[gg
pig
Ps
(k)
<
1
(k)
(k)
oq
0q
On
18

---

Accelerating Large Language Model Reasoning via Speculative Search
Therefore,
(k)
2 N + 2
2
(g(x))
11 - N N +1
(33)
Overall, we can find the recursive expression of variance of B(k);
Var (((ttt) |c] s Var (3(0) |c] + 2(1 0)2
(o
(34)
N +
Now that (of²) s (oc)², we can derive that
2(1 - 0)2
Var ( |c] s Va
[300|c]
+
(ac)²
N +
2(1 0)3
Var
(3(00
N 2 Σ 0 (ac)²
02k
2
(1 0)2 (1 82k)
(or)
N N+
N 2
02h
2 (1- - 0) (1 62h)
(0.)
N +1
N 2
1+8 8
2
(1 7) 2k
N + 1 +
(oo))
N
1+9
2
+
(ao)²
(35)
N+
N +
By Cantelli's inequality (Wikipedia contributors, 2024),
p (BULND) S up mettl/e) = =P -B - [3 5 - 3B [aattic]] 1 18 (c)
E [[t+ticc] -
1
[c] - 16 (1++)) b
Var ((a+1) a1
[c]
E 13u+2)
1
Var
B
1-7 (6+11)
γ 11
1+
(36)
+
2
(ac)
N + 1
N +
Therefore,
19

---

Accelerating Large Language Model Reasoning via Speculative Search
1
(1++1)
2
Up
P ((kt1) 2 up
e)) 2
?
(37)
7 (k+1)
u
N+1 + N+2
(oo)²
A.4. Proof for Theorem 4.6
When l = 0, we have
E [30]
0u/) 2 7
10) 2 1
(38)
and
Var [00]
1
(0(0))
(39)
N + 1
p
Additionally, we have
P P(B0) s <nb)) P (3()) S (10)
1
(40)
2
Then for k 2 1, according to Theorem 4.5,
2
- 7 (b+1)
Up
P B(tt1) 2 up
( () 2
P
(41)
Mg
(k+1)
+
N +1 N1 +
N N+2 (oc)²
?
Noting the Markov property of 1kk+1) we have
K-1
P ((30)2 2
(8) ,10,,, k K) = P 2 20 ()))
(1)
II
[((+t]]
2 p
(k+1) 1,3(k) 2 11 (1)b)
1 7 (k+1)
2
K-1
2 311-2 2N+1
II
7
(42)
2
2
k=
up
(k+1)
+
N+1
+
N +
(ao)2
A.5. Further Discussion on Theorem 4.6
1. NUMERICAL ANALYSIS FOR PROBABILITY BOUND
We conduct a numerical analysis of the probability lower bound presented in Theorem 4.6 for a common scenario.
(0) 0.85, maximum reasoning quality Specifically, we set decent factor 0.9, quality of large model at the initial step pe
variance o. = 0.01, drafting size N = 10, and maximum reasoning steps K = 10. Using Theorem 4.6, we compute the current probability lower bound up to the k-th step, 1 < le < K. The results of this computation are presented in Figure 5. At the 10-th reasoning step, the probability lower bound remains as high as 0.90. Although this conclusion is derived under highly idealized conditions, still provides theoretical support for the high quality of thoughts generated from our method.
20

---

Accelerating Large Language Model Reasoning via Speculative Search
Probability Bound Reasoning Step Curve
1.00
Probability Bound
0.96
0.94
0.90
0.90
10
Reasoning Step
Figure 5. The bound decent rapidly with the reasoning steps. However, the bound remains high 0.90 even the 10-th step.
A.5.2. THRESHOLD ESTIMATOR WITH MAXIMUM ESTIMATION
In practice, due to the limited number of samples, the accuracy of the average estimation method tends to be lower, which results in decrease in the quality of the thoughts generated by our speculative reasoning algorithm. Therefore, we incorporate the solutions from the small model G, that passed the threshold into the estimation of pe and use the maximum non-maraetttic estimator. Specifically, at reasoning step & 1, denote the set of qualities of thoughts from small model
(k)
Gg that passed ((k) by (ikk)
[(2 (R) (k( ..... AN f. and the set of qualities of thoughts generated by large model
(()
(speculative model) Gp by v/aa (1)))) (M) ..... [<(1]] } Then, our estimator takes the form of:
g(b+1) 0,3(k) + (1 0) max ()() U ())())
(43)
with the initial threshold ((0)- max 1, It's easy to see that ((M) 2 3(0), 1....... Therefore, we have
P (B(tt)) Hpp (k+1) S k k)
K) 2
(3 2 H (k+1)
< k k
(44)
That indicates that the maximum estimation method results in higher probability of producing quality thoughts, at the cost of increased computational resources.
A.5.3. THRESHOLD ESTIMATOR WITH No ADDITIONAL G, SAMPLES
For the sake simplicity the previous analysis, we assumed that large model (speculative model) Gp generates + 1 solutions each step ensure the existence of the large model's solution. reality, we can make more practical assumption that G, still generates M thoughts and M > Then U M follows truncated binomial distribution:
0
W n1
P(U = u)
N
P1 P&) N-
(45)
else,
u
pt
(B(4) -8())_p(()
where = 1 1-
We can calculate that
(k)
0g
N N(p- p
EU
(46)
Then
21

---

Accelerating Large Language Model Reasoning via Speculative Search
E V (b)
+ Ps 1 P
(ug
U1 1)
(47)
Therefore we can draw the same conclusion with Theorem 4.3, In addition, we find (32) changes into
(R) N - E U1k) C, B(k)
2
(R)
Op
Op
2 N
(1(3)
112
(48)
N
MPp.pN
p
1-p5" pp
and the probability bound for quality preserving changes to
1 7 (k+1)
p ( 24p ((+1))
1
II
Mp
(49)
2
k=U
110
(k+1)
N (ar)
7
B. More Background
2) Verification
x
Large Model (Parallel)
1) Search A Algorithm
2) Thought Generator
Inibal Input
*N
1) Drafting
Inpul Thoughs
LIM
Generaled Thoughts
Generttd Thoughts
Thought Evaluator
Small Model (A Retoeegresive)
Generated
PRM
Thought
Thoughts
(a) Speculative Decoding
(b) Search- Baarch-Basedd Reasoning
Figure 6. (a) Illustration of standard speculative decoding methods. (b) Illustration of the heam-search-haseee reasoning method.
Details on Speculative Sampling Here is detailed introduction of speculative sampling (SpS) (Leviathan et al., 2023; Chen et al., 2023a), a state-of-the-arr decoding technique that significantly accelerates LLM inference while preserving the target model's 's distribution. Specifically, let e denote the prefix, M, and Mp be the small and large models, respectively, and represent the number tokens generated per step. SpS operates in two phases: drafting and verification. In the drafting phase, the small model M,, performs autoregressive sampling to generate y tokens, denoted as æ1; 22, ,..., TTy, where each x; M, 24-1, æ1, c). the verification phase, the large model Mp verifies the tokens generated by M, in parallel, obtaining the probability distribution Mp(x 24-1,....,
Each token æ; then verified sequentially using modified rejection sampling mechanism, accepted with probability min (1, Mp [as (1-11,0)1 If I; is rejected, the M, at (.
verification process terminates, and a resampling phase begins to generate a new token T,. Theoretically, this approach ensures that the distribution of accepted tokens matches that of the large model.
Details on Beam Search and MCTS Beam Search a heuristic search algorithm that starts from the root node and generates N child nodes. At each depth level, only the top & most promising nodes (beam size) are retained. This process is repeated for the selected k nodes until termination condition is met. The highest-scoring path is returned the solution. MCTS is simulation-based decision-making method that starts from the root node and selects child nodes according to a specific strategy (c.g., UCB) until an unexpanded node is reached. A new child node is then expanded. From this new node, a series of random steps are executed to simulate the search process until the end or a predefined depth is reached. After the simulation, rewards propagate back up the tree, updating the value each visited node based on the simulation results. Through multiple iterations, MCTS converges to an optimal solution.
22

---

Accelerating Large Language Model Reasoning via Speculative Search
C. More Related Work
Here we discuss more related work as follows.
Reinforcement Learning and Search Recent advancements in enhancing the reasoning capabilities of large language models (LLMs) broadly fall into two categories: reinforcement learning- post-training methods (Shao et al., 2024; Yu et al., 2025; Zheng et al., 2024; Hu; Yue et al., 2025) and search-based slow-thinking frameworks (Yao et al., 2023; Gao et al., 2024; Zhang et al., 2024b). Reinforcement learning-based post-training methods closely align with reinforcement learning techniques (Schulman et al., 2015; Zhou et al., 2020; Wang et al., 2023b; Schulman et al., 2017; Wang et al., 2022; Janner et al., 2019; Yang et al., 2022) employed for combinatorial optimization tasks (Berto et al., 2023; Wang et al., 2025; 2024b; Delarue et al., 2020; Wang al., 2024d; Geng et al., 2024; Mazyavkina et al., 2021; Wang et al., 2023a), predominantly leveraging policy-gradient algorithms to optimize autoregressive models toward improved reasoning performance. In contrast, search-based slow-thinking frameworks augment pretrained LLMs by incorporating external search methodologies such as beam search (Kang et al., 2024) and Monte Carlo Tree Search (MCTS) (Gao et al., 2024; Liu et al., 2023; Zhang et al., 2024b; Guo et al., 2024) to enable systematic and structured deliberation without necessitating further training. This paper specifically emphasizes the exploration and advancement of these search- based slow-thinking frameworks.
D. Implementation Details of the Baselines
We implement the baselines used in our paper based on the OpenR code framework.
D.1.
AR refers Autoregressive Generation, a sequence-based model generation method widely used in language models. In the standard Tree of Thoughts (ToT) method, autoregressive generation involves constructing solutions step by step, where each step uses information from previous steps to guide current choices. This approach is straightforward and intuitive but can be limited in terms of speed. In our work, the AR methods using Beam Search and MCTS are based on existing open-source code from OpenR.
D.2. SpS
SpS refers to Speculative Sampling, parallel decoding method for model generation. By introducing a small model, speculative sampling accelerates the generation process in tree search reasoning methods. We implement an efficient SpS method for Beam Search and MCTS using the vLLM (Kwon et al., 2023) package, building on the open-source code from OpenR.
E. Details of the Datasets Used in This Paper
E.1. The Datasets Used in the Main Evaluation
MATH-100 The MATH dataset (Hendrycks et al., 2021) consists of 12,500 challenging competition mathematics problems, each with a full step-by-step solution. These solutions can be used to teach models to generate answer derivations and explanations. We randomly select 100 problems from this dataset as our test set. We choose this number of problems for our test set because the inference latency of the tree search algorithm is quite long. Even with our efficient SpecSearch acceleration framework, the latency remains significant. To avoid the experiment running time being too long for a single run, we select 100 problems for evaluation.
GSM8K-100 The GSMSK dataset (Cobbe et al., 2021) contains 8.5K high-quality linguistically diverse grade school math word problems. We randomly select 100 problems from this dataset for our test set. The reason for selecting 100 problems is the same as for the MATH dataset: to manage inference latency effectively.
E.2. The Datasets Used in the Ablation Study
MATH-50 For the ablation study, we need to test multiple variants of SpecSearch and conduct hyperparameter robustness experiments, which requires running the experiments multiple times. To facilitate this process, we select 50 mathematical problems from the MATH dataset as the test set for the ablation study.
23

---

Accelerating Large Language Model Reasoning via Speculative Search
F. Illustration of Using Models
Thought Generator For the Qwen series of models, we use the 1ww.:---22----sttu--GPOOO model as the large model and the Sar-S------ntuut--PPPP--- -aaee-----O----sttt------- model.
model as the small model. For the Llama series of models, we use the model as the large model and the -ann-----B--nsru--GPPTO model the small
Thought Evaluator We use two PRM models as thought evaluators, one is Math-Shepherd (Wang et al., 2024c) and the other is Math-psa (Wang et al., 2024a) for Experiment 2.
G. Discussion on the novelty of SpecSearch over standard speculative decoding and TreeBon (Qiu et al., 2024)
G.1. Comparison with Existing Speculative Decoding Techniques
Relation to Standard Speculative Decoding (SD) Methods. We discuss the novelty of SpecSearch compared to existing SD techniques, emphasizing key distinctions in terms of speculative formulation, verification and rejection strategies, and thcoretical guarantees.
Bi-Level Speculative Formulation: Unlike existing SD methods focused solely on tokens, SpecSearch treats both high-level thoughts and low-level tokens as bi-level speculative tasks. This enables (1) Structural Alignment with reasoning frameworks, where thoughts are fundamental units, and (2) Compatibility with standard SD methods through low-level token-level speculation.
Contextual Verification for Higher Acceptance and Speedup: Unlike SD methods that enforce strict token-level alignment, leading to frequent rejections, SpecSearch verifies the contextual quality of reasoning thoughts. This allows acceptance of correct but non-aligned outputs, substantially boosting acceptance rates and achieving significant speedups.
Quelity-rreserving Rejection Mechanism: In contrast to token-level rejection in standard SD methods, SpecSearch introduces quality-preserving thought-level rejection based on contextual quality. It discards entire thoughts only when their quality is lower than the large model's, ensuring high-quality reasoning throughout decoding.
Theoretical Guarantee of Reasoning Quality: While standard SD methods preserve token-level distributions, SpecSearch guarantees that the reasoning quality remains comparable that of the large model.
G.2. Comparison with Treebon (Qiu et al., 2024)
We discuss the novelty of SpecSearch compared to Treebon (Qiu et al., 2024), emphasizing key distinctions in terms of motivation, speculative formulation, rejection strategies, and theoretical guarantees.
Distinet Motivation: Unlike Treebon, which aims to accelerate best-of-n sampling via speculative rejection and tree search, SpecSearch is the first to generalize speculative execution to LLM reasoning tasks.
Bi-Level Speculative Formulation: Treebon treats fixed-length token sequences as speculative units, while SpecSearch adopts flexible bi-level formulation-modeling full reasoning thoughts as high-level tasks and tokens low-level leverages LLMs reasoning capabilities to generate semantically
ones. Unlike Treebon's 's fixed-length coherent thoughts of dynamic length.
Preserv-P Rejection Mechanism: Treebon rejects fixed proportion of token sequences using a preset threshold. In contrast, SpecSearch scores reasoning thoughts and adaptively rejects those with lower contextual quality relative to the large model's output, enabling finer control and better quality preservation.
Theoretical Guarantee: Unlike Treebon, which lacks theoretical guarantees, SpecSearch offers formal assurance that the quality of the output reasoning remains on par with that of the large model.
24

---

Accelerating Large Language Model Reasoning via Speculative Search
Algorithm 2 Pseudo Code for SpecSearch
Input: Input question large model (speculative model) Gp. small model Gg. evaluation model V, expansion width N, beam size b, EMA weight 0, reasoning depth K, nonparametric estimation method θ
Initialize beam: B <- 0
> Each element takes the form of (sequence, quality] b Initial reasoning from large model Gp
Initialize candidate thoughts: T + 0. V +- 0
for = to do
Generate from large model: -- Gp(:Ic) Evaluate generated thought: V V(2)
Update candidates: T < TU ((2, V Vu (c) end for
Initialize threshold: _(1) < ()())
Update beam: B - TTp,
b Retain top b by quality
for == to K do
Initialize candidate thoughts: T 0
for 2c in do
Generate Thoughts: B(k-1), T Go
GZ(Zeez (Zck Gps Go, V, V,8K), N,0,)
Speculatively search
Update candidate thoughts: T + TUT:
end for
Update beam: B (T) if Vagk E B, last(zz*) <STOP> then
Retain top b by quality
break end if end for return B
Finish searching
H. Implementation Details of Our SpecSearch
H.1. Discussion on Advantages of Our Evaluation Method
Here we present a detailed discussion on using a process reward model to evaluate the quality of thoughts. First, the thought evaluator accurately captures a thought's complete semantic meaning. Second, it converts thought distribution into structured, manageable quality distribution, enabling clearer definition of lossless reasoning acceleration. Third, it assigns high scores to different valid reasoning paths, improving the assessment of the small model's thought quality.
H.2. SpecSearch Implementation Details
H.2.1. SMALL MODEL PARALLEL THOUGHT GENERATION
Due to the small memory footprint of small models, they operate in parallel even under limited memory conditions. Generating multiple thoughts simultaneously does not significantly increase latency compared to generating single thought. Therefore, we use small model to generate thoughts in parallel. Although the overall quality of generation from small models may not match that of large models, they still produce high-quality thoughts.
We utilize the small model to generate 2* thoughts in parallel, combining the efficiency of parallel processing with the ability to generate high-quality thoughts. This approach introduces more high-quality thoughts into the Tree of Thoughts (ToT), enhancing both efficiency and thought quality.
H.2.2. ACCEPTANCE-REJEECIOON REJECTION MECHANISM
After generating 2 thoughts with the small model, we evaluate these thoughts using the Process Reward Model (PRM) to determine their rewards. Each thought's 's reward is compared to dynamically calculated threshold. If the reward surpasses the threshold, the thought retained; otherwise, it discarded. If more than thoughts are retained, we select the top N thoughts with the highest rewards for final acceptance.
H.2.3. ALGORITHM IMPLEMENTATION
25

---

Accelerating Large Language Model Reasoning via Speculative Search
Table Full GSM8K. Evaluation on full GSM8K- 1319 dataset. (1) Setup We utilize quantized versions of Qwen2.5-722 -nsstrutt and Dwen2.55-B Instrrctt as the large and small language models, utilize MATH- psa as the Process Reward Model and employ beam search as search algorithm. Unless explicitly stated otherwise, results presented below follow this setting. (2) Results The results demonstrate that SpecSearch achieves comparable accuracy while significantly reducing inference latency.
Qwen models
MATH Dataset
GSMBK-1319
Reasoning Accuracy (%)
Average Inference
Spoedup (vs AR)
Speedup (vs SpS)
Methods
Latency (s)
AR
96.66
144.63
NA
0.48
SpS
96.
70.04
2,06
NA
SpecSearch (Ours)
95.83
50.99
2.84
1.37
Table 5. AIME, Evaluation on the AIME datasct.
The results demonstrate that SpecSearch achieves comparable accuracy while
significantly reducing inference lateney.
Qwen models
MATH Dataset
AIME Average Inference
Reasoning Accuracy (%)
Speedup (vs AR)
Speedup (vs SpS)
Methods
Latency (8)
AR
16.67
562.89
NA
0.57
SpS
13.33
318.71
1.77
NA
SpecSearch (Ours)
13.33
264.44
2,13
1,21
The procedure of our bi-level speculative thought generator is outlined in Algorithm in the main text. Here, we further present the complete SpecSearch algorithm, which based on the beam search algorithm, shown in Algorithm 2.
Furthermore, due to the limited sample size M, we adopt more conservative estimation strategy in the implementation, utilizing the maximum value as an estimate of the upper confidence bound for pp (k+1), Specifically, let / denote the set of qualities of thoughts generated by the small model Gg. and DaAA) denote the set of qualities of thoughts generated by the
large model (speculative model) Gp. The threshold estimation method we employ is as follows:
g(++1) = 03((0 + (1 - 0) max (*() p ()(()
(50)
H.2.4. SPECULATIVE MODEL SERIAL THOUGHT GENERATION
If the number of accepted thoughts from the small model is less than N after filtering through the acceptance-rejectinn mechanism, we use speculative model to serially generate additional thoughts until the total number of thoughts reaches N.
H.3. Hyperparameters
SpecSearch In our experiments, unless otherwise specified, set the EMA weight 0 in the SpecSearch to 0.9.
Beam Search In our experiments, unless otherwise specified, we set the tree width to 6, the tree depth to 50, and the beam size to 2 in the Beam Search.
MCTS In our experiments, unless otherwise specified, we set the tree width to 6, the tree depth to 50, and the iteration number to in the MCTS.
More Results
I.1. More Main Evaluation
We conduct comprehensive evaluations across three distinct dataset categories to rigorously demonstrate the efficiency and generalizability of SpecSearch. Specifically, these include: (1) the full GSM8K dataset comprising 1,319 problems; (2) more challenging mathematical reasoning benchmarks, namely the AIME and Olympiad datasets; and (3) a code-generation benchmark. As illustrated in Tables 4, 5, 6, and 7, SpecSearch consistently and significantly surpasses state-of-the- art approaches across all three dataset categories, achieving speedups ranging from 2.04x 2.84x while maintaining
26

---

Accelerating Large Language Model Reasoning via Speculative Search
Table Olympiad Bench. Evaluation on Olympiad Bench (OE-TO-maths CEE dataset. The results demonstrate that SpecSearch
achieves comparable accuracy while significantly reducing inference latency.
Qwen models
MATH Dataset
Olympiad Bench
Reusoning Accuracy (%))
Average Inference Latency (S)
Speedup (vs AR)
Speedup (vs SpS)
Methods
AR SpS
63.75
358.44
NA
0.67
58.75
241.80
1.48
SpecSearch (Ours)
58.75
176.02
2.04
1.37
Table 7. Code-Generation Benchmark. Evaluation on the HumanEval dataset. The results show that SpeeSearch achieves comparable
accuracy while significantly reducing inference latency.
Qwen models
Coding Dataset
HumanEval
Reasoning Accuracy (5)
Average Inference
Speedup (vs AR)
Speedup (vs SpS)
Methods
Latency
85.37
342.18
NA
0.65
SpS
84.15
223.30
1.53
SpecSearch (Ours)
85.37
158.43
2.16
1.41
comparable reasoning accuracy. These findings highlight SpecSearch's versatility and robustness, demonstrating substantial improvements in inference speed with minimal no compromise in accuracy across diverse tasks.
Setup. Throughout our experiments, we utilize quantized versions of Qwen2. 5-72B-Instruct and as the large and small language models, respectively. Additionally, we incorporate MATH-psa
Qwen2. 5- S as the Process Reward Model and employ beam search as the search algorithm.
Results.
(1) Full GSM8K Dataset (1,319 Problems): SpecSearch achieves substantial 2.84x speedup compared the AR baseline, with only minimal accuracy reduction of 0.83%. This result highlights SpecSearch's is capability to effectively scale to larger problem sets while preserving high reasoning accuracy.
(2) High-Difficulty Mathematics (AIME and Olympiad Bench): We conduct experiments on the AIME and Olympiad Bench (OE_TO mos zh_CEE) datasets. Notably, SpecSearch maintains identical accuracy to the SpS method while achieving speedups of 1.21x and 1.37 x, respectively. These results demonstrate the method's effectiveness in handling challenging, competition- mathematics problems.
(3) Code Generation (HumanEval): To assess SpecSearch beyond mathematical reasoning, we evaluate its performance on the HumanEval code-generation benchmark. The results show that SpecSearch achieves 2.16x speedup over the AR without any reduction in accuracy. Furthermore, it surpasses the SpS by 1.22% in accuracy while simultancously delivering 1.41x speedup. These results underscore SpecSearch's strong generalization capabilities across diverse domains.
L.2. More Motivating Results
Reward Distribution Across Reasoning Steps We analyze the reward distributions across different reasoning steps in our experiments. Figure 7 shows the reward distribution for each step the reasoning path. The figure illustrates that the average reward decreases as the reasoning process moves from initial steps to later stages.
Initially, reasoning steps tend yield higher rewards because they simpler and require less cognitive effort, allowing for higher thresholds. As the reasoning progresses, subsequent steps become more complex, resulting in lower average reward scores and necessitating lower thresholds. This pattern supports our approach of using dynamic thresholds.
Similar Output Lengths Enable Effective Model Collaboration We calculate the average number of tokens generated by large and small models in a single reasoning step. Table shows that both model types produce a similar number of tokens. This similarity suggests that the length of the thought or reasoning process at each step comparable. This feature supports
27

---

Accelerating Large Language Model Reasoning via Speculative Search
0.90
0.85
0.80
Mean Reward
0.75
0.70
0.65
0.55
0.50
10
15
Reasoning Steps
Figure 7. The distribution of rewards for generated thoughts decreases step by step.
Table 8. The results demonstrate that the number of tokens generated by large and small models in a single reasoning step is comparable.
Model
The average number of tokens in reasoning step
Qwen2,5-7B --s-tuutttt Qwen2.5-1.5B --ntntttet
59.088
57.037
collaboration between large and small models, as it implies they can efficiently divide tasks and work together within the same reasoning framework.
I.3. Case Study
Case 1 Figure 8 shows challenging case study. It illustrates how different reasoning steps vary in difficulty. In this process, identifying the curve type from its equation is an easy step, while transforming an equation from polar to Cartesian coordinates is more difficult.
Case Figure 9 presents a simple case study showing how different reasoning steps have different levels difficulty, In this reasoning process, calculating 9900 1 is an easy step while computing the square of 99 is hard step.
Figures 8 and 9 illustrate varying difficulty levels among reasoning steps. Simpler steps efficiently handled by small model, while more complex steps managed by a large model. This division optimizes efficiency and accuracy throughout the reasoning process.
Case We select a problem from the GSM8K- 100 dataset where SpecSearch made an error for case study analysis. Figure 10 shows the PRM score on the incorrect reasoning path. In this scenario, the first three reasoning steps are correct, but an error occurs the fourth step. Subsequent steps remain incorrect. Notably, the fourth step, despite being wrong, achieves a high PRM score of 0.8916015622 This indicates that incorrect steps can mislead the PRM and prevent from accurately identifying errors. This observation clarifies why observed low precision loss in our SpecSearch.
L.4. More Broad Compatibility Results
In this section, we provide more results the broad compatibility experiment. We conduct broad compatibility experiments on the MATH-100 dataset using the Qwen models. The results in Table 9 show the performance of SpecSearch and the baselines in different search algorithms and different thought evaluators. SpecSearch accelerates beam search and MCTS, outperforming baselines by reducing latency with minimal accuracy loss, and shows consistent performance across different PRMs, demonstrating broad applicability and generalization.
This experimental result supplements the broad compatibility experiment in the main text, verifying that our method has broad applicability across different datasets.
28

---

Accelerating Large Language Model Reasoning via Speculative Search
Table The results strae the Broad Compatibility of Our SpecSearch with different search algorithms and PRMs on the MATH-100
dataset.
Search Algorithms
Beam Search
MCTS
Reasoning Accuracy (9) f
Average Inference
Speedup AR)1
Speedup SpS)t
Reasoning Accuracy ($) f
Average Inference
Speedup AR)
Speedup SpS)
Methods
Latency (8)
Latency (8) 4
$7.00
275.78 141.55
0.51
93.00
523.54
NA
0.49
SpS SpecSearch (Ours)
88.00
1.95 3.35
NA
91.00
257.62
2.03 3.05
NA
87.00
$2.35
1.72
90.00
171.59
1.50
PRMs
Math-psa
Math-Shepherr
Reasoning Accuracy (%) f
Average Inference
Speedup (vS AR) f
Speedup (vs SpS) 1
Reasoning Accuracy (%% f
Average Inference
Speedup (vs AR)
Specdup (vs SpS)
Methods
Latency (8)
Latency (8) 4
AR
87.00
275.78
NA
0.51
88.00
265.29
NA 1.82 2.24
0.55 NA
SpS
88.00
141.55
1.95 3.35
NA
85,00
145.53
SpeeSearch (Ours)
87.00
82.35
1.72
85.00
118.67
1.23
Table 10. Sensitivity to Draft Models. We investigate SpecScarch's 's performance using multiple small draft models -wen2.5-3B- Instruct, Qwen2.5-1.5B8 Insssrruutt, and Qwen2.5-0.55 1rrcn..5-0.5B-Instrree The results demonstrate that our method maintains stable accuracy while achieving significant latency reduction across various draft models.
MATH
GSMSK
Methods
Ressoting
Inference
AR)
Dtaft Acceptance
AR
1:34.24
Sp8 (Drah-78)
09:65
1.99
NA
SpecSearch Duaf
SpacReanch Dea
SpecSeerdh 1n0t-11500
SpecSrandh
L.5. Sensitivity Analysis to Draft Model's Size
We have investigated SpecSearch's s performance using multiple small draft models. The results in Table 10 reveal that SpecSearch achieves speedups ranging from 2.18x to 2.87x, underscoring its robust acceleration capabilities across diverse small-model settings.
1.6. More Ablation Study Results
Sensitivity Analysis Hyperparameter 8 which controls the relative importance of reward information from the previous layer when updating the threshold for the current layer, is crucial for balancing between accuracy and latency. To understand the impact of hyperparameter on the performance of SpecSearch, we conduct detailed sensitivity analysis focusing exclusively on this parameter.
We vary 0 across range from Omin 0.8 to 0max 0.95, with increments of A 0.05. For each value of 0 we evaluate SpecSearch using the MATH-50 dataset, ensuring that all other hyperparameters are held constant to isolate the effect of B,
The results in Table 11 show that the accuracy of SpecSearch remains largely unchanged when 0 is large and latency decreases as increases. These findings suggest that while 0 does not significantly affect accuracy, setting closer to can lead to substantial improvements in computational efficiency without compromising the quality of the generated reasoning paths. This demonstrates the robustness of 0.
29

---

Accelerating Large Language Model Reasoning via Speculative Search
Table 11. The results demonstrate that SpecSearch achieves similar average performance across a wide range of 0.
Dataset
MATH-50
Reusoning Accuracy (56
Average Inference
Speedup
Methods
Latency (s)
(vs ARJ
AR
88.00
256.05
NA
90.00
132.68
SpecSearch (Ours 0.95)
88.00
66.48
SpecSearch (Ours.P 0.9)
88.00
70.63
SpecSearch (Ours 0.85)
88.00
73.66
SpecSearch (Ours. 0.8)
88.00
83.29
3.07
30

---

easy Accelerating Large Language Model Reasoning via Speculative Search
Q&A Case
Question:
Find the curve defined by the equation cos 4. Which of following does this represent?
(A)Line Line (B) Circle (C) Parabola
(D) Ellipse
(E) Hyperbola.
Enter the letter of the correct option.
Reason:
Step 1: Recall the polar to Cartesian coordinate transformations:
x r cos 0, y rsin 0
and the identity:
cos cos² sin?
Step 2: Substitute cos 0 and r sin 0 into the identity:
hard
(-)
2.
1/
20
x2
p2
p2
Step 3: Substitute cos 20 back into the original equation:
cos 20 4
?
y¹
x2 2²
x2
Step Analyze resulting Cartesian equation:
This is the standard form of hyperbola. Specifically, it is a hyperbola centered at the origin with its transverse axis along the x-axis.
the answer is:
E
Figure 8. A difficult case study showing how different reasoning steps have different levels of difficulty.
31

---

Accelerating Large Language Model Reasoning via Speculative Search
Q&A Case
Question:
Compute 99² + .99 + 1 in your head.
Reason:
Step Calculate 99?:
hard
99º (100 1)² 1002 - 2 100 1+ 1 10000 - 200 1 9801
Step Add to 99?:
99 99 = 9801 + 99 9900
Step Add the result:
easy
9900 1 9901
So the answer is:
9901
Figure 9. A simple case study showing how different reasoning steps have different levels of difficulty.
32

---

Accelerating Large Language Model Reasoning via Speculative Search
Q&& Case
Question:
Raymond and Samantha are cousins. Raymond was born years before Samantha. Raymond had son at the age of 23. If Samantha is now 31, how many years ago was Raymond's son born?
Reason:
Step 1: Identify the current age of Samantha: Samantha is currently 31 years old, [0.9370117185
Step Determine Raymond's age when his born: Raymond had the age of 23. [0.91845703125]
Step 3: Find the age difference between Raymond and Samantha: We are told that Raymond was born 6 years before Samantha. This means Samantha is 6 years younger than Raymond. (0.92529296875)
Step Calculate Raymond's 's current age: Samantha is 31 she is years older than Raymond, then Raymond is currently
years old, [0.8916015625]
Step 5: Determine the age of Raymond when his born: Raymond had his son the age of 23. [0.8198212187))
Step Calculate the number of years since Raymond's son was born: Since Raymond currently years and had his son at age 23, has been 25 23 2 years since Raymond's son was born. [0.56982421875]
So the answer is:
2
Figure 10. case study showing the PRM score on the wrong reasoning path.
33


Reviews:
[{"review_id": "GSAExTT7AM", "reviewer": "Reviewer_cNpL", "summary": "This paper proposes a speculative search framework, that extends speculative decoding framework to reasoning chains. SpecSearch framework works by rejecting and selecting both at thought and token levels. The authors show both performance and speedup improvements.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer cNpL\n\nWe sincerely thank the reviewer for the insightful, valuable, and positive comments. We address the concerns in detail as follows. We sincerely hope that our response could properly address your concerns. If so, we would deeply appreciate it if you could raise your score. If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our submission. \n\n### Weakness 1.\n\n> **1. The authors only evaluate the approach on subsets of both MATH and GSM8K datasets. The accuracy claims might need more samples for a convincing argument.**\n\nWe have conducted comprehensive evaluations across **three distinct dataset categories** to rigorously demonstrate the efficiency and generalizability of SpecSearch. Specifically, these include: (1) the **full GSM8K** dataset comprising 1,319 problems; (2) more challenging mathematical reasoning benchmarks, namely the **AIME** and **Olympiad** datasets; and (3) a **code-generation** benchmark. As illustrated in the following Table, SpecSearch **consistently** and **significantly surpasses state-of-the-art approaches** across all three dataset categories, achieving speedups ranging from **2.04$\\times$** to **2.84$\\times$** while maintaining comparable reasoning accuracy. These findings highlight SpecSearch's versatility and robustness, demonstrating substantial improvements in inference speed with minimal or no compromise in accuracy **across diverse tasks**. We will include the results in our revised paper.\n\n- **Setup** Throughout our experiments, we utilize quantized versions of Qwen2.5-72B-Instruct and Qwen2.5-7B-Instruct as the large and small language models, respectively. Additionally, we incorporate MATH-psa as the Process Reward Model and employ beam search as the search algorithm.\n- **Results** \n    - **Full GSM8K Dataset (1,319 Problems)**: SpecSearch achieves a substantial **2.84$\\times$ speedup** compared to the AR baseline, with only a minimal accuracy reduction of 0.83%. This result highlights SpecSearch’s capability to effectively scale to larger problem sets while preserving high reasoning accuracy.\n    - **High-Difficulty Mathematics (AIME and Olympiad Bench)**: We conduct experiments on the AIME and Olympiad Bench (OE_TO_maths-zh_CEE) datasets. Notably, SpecSearch **maintains identical accuracy** to the SpS method while achieving **speedups of 1.21$\\times$ and 1.37$\\times$**, respectively. These results demonstrate the method’s effectiveness in handling challenging, competition-level mathematics problems.\n    - **Code Generation (HumanEval)**: To assess SpecSearch beyond mathematical reasoning, we evaluate its performance on the HumanEval code-generation benchmark. The results show that SpecSearch achieves a **2.16$\\times$ speedup** over the AR without any reduction in accuracy. Furthermore, it **surpasses the SpS by 1.22% in accuracy** while simultaneously delivering a **1.41$\\times$ speedup**. These results underscore SpecSearch's strong generalization capabilities across diverse domains.\n\n| **MATH   Dataset** | **GSM8K-1319** |  |  |  |\n|:---:|:---:|:---:|:---:|:---:|\n| Methods | Reasoning      Accuracy (\\%) | Average   Inference      Latency (s) | Speedup      (vs AR) | Speedup      (vs SpS) |\n|  |  |  |  |  |\n| AR | 96.66 | 144.63 | NA | 0.48 |\n| SpS | 96.66 | 70.04 | 2.06 | NA |\n| SpecSearch (Ours) | 95.83 | **50.99** | **2.84** | **1.37** |\n| **MATH Dataset** | **AIME** |  |  |  |\n| Methods | Reasoning      Accuracy (\\%) | Average   Inference      Latency (s) | Speedup      (vs AR) | Speedup      (vs SpS) |\n|  |  |  |  |  |\n| AR | 16.67 | 562.89 | NA | 0.57 |\n| SpS | 13.33 | 318.71 | 1.77 | NA |\n| SpecSearch (Ours) | 13.33 | **264.44** | **2.13** | **1.21** |\n| **MATH Dataset** | **Olypamid Bench** |  |  |  |\n| Methods | Reasoning      Accuracy (\\%) | Average   Inference      Latency (s) | Speedup      (vs AR) | Speedup      (vs SpS) |\n|  |  |  |  |  |\n| AR | 63.75 | 358.44 | NA | 0.67 |\n| SpS | 58.75 | 241.80 | 1.48 | NA |\n| SpecSearch (Ours) | 58.75 | **176.02** | **2.04** | **1.37** |\n| **Coding Dataset** | **HumanEval** |  |  |  |\n| Methods | Reasoning      Accuracy (\\%) | Average   Inference      Latency (s) | Speedup      (vs AR) | Speedup      (vs SpS) |\n|  |  |  |  |  |\n| AR | 85.37 | 342.18 | NA | 0.65 |\n| SpS | 84.15 | 223.30 | 1.53 | NA |\n| SpecSearch (Ours) | 85.37 | **158.43** | **2.16** | **1.41** |", "claims_and_evidence": "The claim is that SpecSearch - applying speculative decoding at both thought and token level improves reasoning quality and provides speedup. It is backed by evidence across both Qwen and LLama models across both MATH-100 and GSM8K-100 datasets.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I did not check the theoretical claims.", "experimental_designs_or_analyses": "The experimental designs and corresponding analyses are sound despite one significant concern. The authors only evaluate the approach on 100 randomly selected subsets of both MATH and GSM8K datasets. While the claims of latency can be adequately claimed, the accuracy claims might not be significant and might need more samples for a convincing argument.", "relation_to_broader_scientific_literature": "The contributions of this paper can be broadly useful. Speculative decoding is a standard technique both in industry and academia, and its extension to reasoning chains, if claims hold, has wide implications.", "essential_references_not_discussed": "None that I am aware of", "other_strengths_and_weaknesses": "(Covered above)", "other_comments_or_suggestions": "(Covered above)", "questions_for_authors": "(Covered above)", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "riuU5QCsN7", "reviewer": "Reviewer_uX9o", "summary": "This paper proposes SpecSearch to optimize thought generation through strategic collaboration between a small model and a large model at both thought and token levels. This approach efficiently produces high-quality reasoning thoughts. A key feature of SpecSearch is its quality-preserving rejection mechanism, which filters out low-quality thoughts, ensuring that only those meeting the standard of the large model are retained. Experimental results on the Qwen and Llama models show that SpecSearch achieves up to a 2.12× speedup compared to state-of-the-art methods, while maintaining comparable reasoning quality.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer uX9o\n\nWe sincerely thank the reviewer for the insightful and valuable feedback. We genuinely hope our response has addressed your concerns. If it has, we would be truly grateful if you would consider raising your score. If not, we warmly welcome any further suggestions and will continue doing our best to improve the submission.\n\n### Weakness 1.\n\n> **1. The experiments are limited to only subsets of MATH and GSM8K. The framework’s effectiveness on more complex reasoning tasks (e.g., AIME and Olympiad bench) remains unverified.**\n\nWe have conducted comprehensive evaluations across **three distinct dataset categories** to rigorously demonstrate the efficiency and generalizability of SpecSearch. Specifically, these include: (1) the **full GSM8K** dataset comprising 1,319 problems; (2) more challenging mathematical reasoning benchmarks, namely the **AIME** and **Olympiad** datasets; and (3) a **code-generation** benchmark. The results show that SpecSearch **consistently** and **significantly surpasses state-of-the-art approaches** across all three dataset categories, achieving speedups ranging from **2.04$\\times$** to **2.84$\\times$** while maintaining comparable reasoning accuracy. Due to limited space, please refer to **Weakness 1** in **Response to Reviewer cNpL** for detailed results.\n\n### Weakness 2.\n\n> **2. The core idea of combining small and large models resembles existing speculative decoding (SD) techniques (e.g., token-level draft-then-verify).**\n\nWe discuss the novelty of SpecSearch compared to existing SD techniques, emphasizing key distinctions in terms of **speculative formulation**, **verification** and **rejection strategies**, and **theoretical guarantees**. We will include the discussion in our revised paper.\n\n- **Bi-Level Speculative Formulation**: Unlike existing SD methods focused solely on tokens, SpecSearch treats both high-level thoughts and low-level tokens as bi-level speculative tasks. This enables (1) **Structural Alignment** with reasoning frameworks, where thoughts are fundamental units, and (2) **Compatibility** with standard SD methods through low-level token-level speculation.\n- **Contextual Verification for Higher Acceptance and Speedup**: Unlike existing SD methods that enforce strict token-level alignment, leading to frequent rejections, SpecSearch verifies the **contextual quality** of reasoning thoughts. This allows acceptance of correct but non-aligned outputs, substantially boosting acceptance rates and achieving significant speedups.\n- **Quality-Preserving Rejection Mechanism**: Unlike token-level rejection in standard SD methods, SpecSearch proposes **quality-preserving thought-level rejection** based on contextual quality. It discards entire thoughts only when their quality is lower than the large model’s, ensuring high-quality reasoning throughout decoding.\n- **Theoretical Guarantee of Reasoning Quality**: While standard SD methods preserve token-level distributions, SpecSearch guarantees that reasoning quality remains comparable with outputs from the large model.\n\n> **3. The claimed \"first generalization\" of speculative execution to reasoning lacks a clear distinction from Treebon [1].** ([1] Treebon: Enhancing inference-time alignment with speculative tree-search and best-of-n sampling.)\n\nWe discuss the novelty of SpecSearch compared to Treebon [1], emphasizing key distinctions in terms of **motivation**, **speculative formulation**, **rejection strategies**, and **theoretical guarantees**. We will include the discussion in our revised paper.\n\n- **Distinct Motivation**: Unlike Treebon, which targets accelerating best-of-n sampling through speculative rejection combined with tree search, SpecSearch is the first to well generalize speculative execution to tree-based LLM reasoning.\n- **Bi-Level Speculative Formulation**: Treebon treats fixed-length token sequences as speculative tasks, while SpecSearch introduces a **flexible bi-level approach**—modeling full reasoning thoughts as high-level tasks and tokens as low-level ones. Unlike Treebon’s fixed-length design, SpecSearch leverages LLMs' reasoning capabilities to generate semantically coherent thoughts of dynamic length.\n- **Quality-Preserving Rejection Mechanism**: Treebon rejects a fixed proportion of token sequences using a preset threshold. SpecSearch, instead, scores reasoning thoughts and **adaptively rejects those with lower contextual quality based on the large model’s reasoning quality**, enabling finer control and better quality preservation.\n- **Theoretical Guarantee**: Unlike Treebon, which lacks theoretical guarantees, SpecSearch provides **formal assurance that reasoning quality remains uncompromised**, matching that of the large model's outputs.", "claims_and_evidence": "yes", "methods_and_evaluation_criteria": "yes", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "yes", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "no", "other_strengths_and_weaknesses": "Strengths:\n\nThe paper proposes a bi-level speculative thought generator that combines a small model and a large model at both thought and token levels. This design leverages the small model’s parallel generation efficiency for proposing diverse reasoning thoughts and the large model’s evaluation capability for filtering, achieving up to 2.12× speedup while maintaining comparable reasoning quality.\n\n\nWeaknesses:\n\n1. The experiments are limited to two mathematical reasoning datasets (only subsets of MATH and GSM8K) and structured tasks. The framework’s effectiveness on more complex reasoning tasks (e.g., AIME and Olympiad bench) remains unverified, raising questions about its effectiveness and generalization ability.\n\n\n2. While the integration of speculative execution with tree-search-based reasoning is practical, the core idea of combining small and large models resembles existing speculative decoding techniques (e.g., token-level draft-then-verify). The claimed \"first generalization\" of speculative execution to reasoning lacks a clear distinction from prior work [1].\n\n[1] Qiu J, Lu Y, Zeng Y, et al. Treebon: Enhancing inference-time alignment with speculative tree-search and best-of-n sampling[J]. arXiv preprint arXiv:2410.16033, 2024.", "other_comments_or_suggestions": "See weaknesses part.", "questions_for_authors": "See weaknesses part.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YhIBGBija4", "reviewer": "Reviewer_EXez", "summary": "This paper introduces a new LLM reasoning method via speculative Tree-Search-Base reasoning. It involved a quality-preserving rejection mechanism and also has theoretical properties that means it can maintain reasoning quality compared to the large model. Experiments on math problems show up to 2–3× speedup over standard autoregressive decoding or token-level speculative decoding, with minimal accuracy drop.\n\n## update after rebuttal\n\nI thank the authors for their detailed rebuttal. I maintain my score after reading all the other rebuttal comments.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer EXez\n\nWe sincerely thank the reviewer for the thoughtful and encouraging feedback! We hope our response has addressed your concerns. If so, we would be truly grateful if you would consider raising your score. If not, we welcome any further comments and will continue working diligently to improve our work.\n\n> ## Due to limited space, **we provide Tables and Figures in 14604.pdf in [Anonymous Link](https://anonymous.4open.science/r/SpecSearch-Rebuttal-4B78/14604.pdf)**.\n\n### Weakness 1.\n\n> **1. Use more, non-mathematical reasoning datasets**\n\nWe have conducted comprehensive evaluations across **three distinct dataset categories** to rigorously demonstrate the efficiency and generalizability of SpecSearch. Specifically, these include: (1) the **full GSM8K** dataset comprising 1,319 problems; (2) more challenging mathematical reasoning benchmarks, namely the **AIME** and **Olympiad** datasets; and (3) a **code-generation** benchmark. The results show that SpecSearch **consistently** and **significantly surpasses state-of-the-art approaches** across all three dataset categories, achieving speedups ranging from **2.04$\\times$** to **2.84$\\times$** while maintaining comparable reasoning accuracy. Please refer to **Weakness 1** in **Response to Reviewer cNpL** for detailed results.\n\n### Weakness 2.\n> **2. Error bars from running across random seeds**\n\nWe have evaluated SpecSearch and baselines under three random seeds to assess stability and performance. As shown in Figure 1 in 14604.pdf, SpecSearch delivers **consistent reasoning accuracy** and **significantly lower inference latency than baselines across all seeds**.\n\n> **3. Comparison with newer speculative approaches**\n\nWe have compared SpecSearch with **three recent speculative methods**: two advanced speculative decoding approaches—Lookahead [1] and Eagle [2]—and one speculative tree search method, Treebon [3]. As shown in Table 5 in 14604.pdf, SpecSearch achieves **1.74× to 2.73× speedups** over these baselines, highlighting its strong acceleration capability while preserving high reasoning quality.\n\n[1] Break the Sequential Dependency of LLM Inference Using Lookahead Decoding, ICML24.\n\n[2] EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty, ICML24\n\n[3] TreeBoN: Enhancing Inference-Time Alignment with Speculative Tree-Search and Best-of-N Sampling, 2024.10\n\n### Weakness 3.\n\n> **4. A deeper comparison with SEED or other structured speculative decoding (SD) methods.**\n\n#### 1) The novelty over SEED and SD\nWe discuss the novelty of SpecSearch compared to Scheduled Speculative Decoding (SEED) and existing SD methods, emphasizing key distinctions in our **bi-level speculative formulation**, **contextual verification**, **quality-preserving rejection strategies**, and **theoretical guarantees for reasoning quality**. Please refer to **Weakness 2** in **Response to Reviewer uX9o** for details.\n\nIt is worth noting that the key distinction between SEED and standard SD methods lies in its use of **N small models** to **generate N token sequences in parallel at each node** of the reasoning tree, followed by a **Rounds-Scheduled strategy** to coordinate a shared large model for verification. However, in terms of the four aspects—**formulation**, **verification** and **rejection**, and **theoretical guarantees**—SEED remains consistent with SD methods. \n\n#### 2) The novelty over a recent structured speculative tree search method \nWe discuss the novelty of SpecSearch compared to Treebon[3], emphasizing key distinctions in terms of **motivation**, **speculative formulation**, **rejection strategies**, and **theoretical guarantees**. Please refer to **Weakness 2** in **Response to Reviewer uX9o** for details.\n\n### Weakness 4.\n> **5. Compare wall-clock time on real hardware with parallelization overhead considered**\n\nWe measured wall-clock inference latency on a dual NVIDIA A800 GPU setup, including parallelization overhead. As shown in Table 6 in 14604.pdf, **SpecSearch achieves a 2.87$\\times$ speedup in total latency**, fully accounting for parallelization costs.\n\n### Weakness 5.\n> **6. Discussion on failure cases where the small model’s generation misleads the system**\n\nWe discussed failure cases in Figure 10 in Appendix G.2 in our initial submission. Specifically, in this case, the small model misinterpreted the statement \"A was born X years before B,\" reversing its meaning. Moreover, our **thought evaluator failed to identify this error** and **assigned a high score** of 0.89 to the incorrect reasoning step, ultimately leading to an incorrect final answer.\n\n### Weakness 6.\n> **7. Speedup sensitivity to the small draft model’s performance**\n\nWe have investigated SpecSearch’s performance using multiple small draft models. The results in Table 7 in 14604.pdf reveal that **SpecSearch achieves speedups ranging from 2.18$\\times$ to 2.87$\\times$**, underscoring its **robust acceleration capabilities across diverse small-model settings**.", "claims_and_evidence": "* \"A Novel SpecSearch Framework\". This claim is substantiated.\n* \"Quality-Preserving Rejection Mechanism\". This claim is substantiated.\n* \"Theoretical Guarantee\", also substantiated.\n* \"Significant Speedup and Versatility\" - Empirical evidence is only given with two mathematical reasoning datasets of MATH and GSM8K, I encourage the authors to also use more, perhaps non-mathematical reasoning datasets if possible.", "methods_and_evaluation_criteria": "The method appears to be novel, and well structured, using a small LM for draft thoughts, and a Large LM for final verification, coupled with a tree-based or beam-based search search and process reward model for scoring. The chosen evaluation metrics of accuracy and inference latency are appropriate, however the results can all benefit from error bars from running across random seeds, and more baselines.", "theoretical_claims": "The paper provides probabilistic bounds that, with sufficient sampling and proper thresholds, SpecSearch retains or approximates the large model’s accuracy. I did not check the proofs in detail, intuitively they make sense.", "experimental_designs_or_analyses": "Experiments are valid, and use MATH and GSM8K math reasoning benchmarks. A potential issue with the current setup is that the just focusing on these two math datasets could mean the approach performs of an unknown ability to other reasoning domains and or diverse tasks.", "relation_to_broader_scientific_literature": "Speculative decoding and chain-of-thought search approaches (like Tree-of-Thoughts, SEED) are cited, but:\n* The paper would benefit from a deeper comparison with closely related works like SEED or other structured speculative decoding methods.", "essential_references_not_discussed": "All essential references are discussed.", "other_strengths_and_weaknesses": "Significance: Significant inference speedup without heavily compromising accuracy with the proposed approach. However the paper could benefit from comparisons with newer speculative approaches.\nClarity: The paper is well-written and easy to follow.\nOriginality: This approach appears to be novel.", "other_comments_or_suggestions": "* Compare wall-clock time on real hardware with parallelization overhead considered.\n* Expand the discussion on failure cases where the small model’s generation misleads the system.", "questions_for_authors": "* How sensitive is speedup to the small draft model’s performance?\n* Can the authors evaluate on a dataset that is not within the math domain?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ADYLRT1Ekr", "reviewer": "Reviewer_zUgA", "summary": "**I am not very familiar with the subarea of this paper, so I am not highly confident in my review. I expect my review not to play a significant role in the decision.** \n\nThis paper introduces SpecSearch, a method that enables a small model to collaborate with a large model at both the thought and token levels in reasoning. It accelerates TSB methods using a large LLM.\n\n## update after rebuttal\nAgain, **I am NOT familiar with the subarea of this paper, so I expect my review NOT to play a significant role in the decision.**", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer zUgA\n\nWe sincerely thank the reviewer for the valuable comments! We address the concerns in detail as follows. We sincerely hope that our response could properly address your concerns. If so, we would deeply appreciate it if you could raise your score. If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our submission.\n\n### Weakness 1.\n> **1. I feel that the writing could be improved. It was difficult for me to understand the framework clearly, and I do feel that the writing makes something overly complicated.**\n\nThank you for the valuable suggestion. We provide a clearer description of our framework below and will incorporate it into the revised version of our paper.\n\n- **Search Framework Overview**: Our framework represents **tree nodes** as intermediate reasoning steps (thoughts) and **tree paths** as candidate solutions to multi-step reasoning problems. Each reasoning step comprises a sequence of tokens decoded by a large language model (LLM). The framework consists of three core components: a **Bi-Level Speculative Thought Generator (G)**, a **Thought Evaluator (V)**, and a **Search Algorithm**. Starting from the root node (containing the input context and question), the generator G expands the reasoning tree by producing $N$ candidate thoughts (child nodes). The evaluator V assesses their quality, which then guides the search algorithm. This iterative process builds a reasoning tree, ultimately selecting a final reasoning path.\n\n- **Bi-Level Speculative Thought Generator**: At each leaf node, the bi-level speculative thought generator produces $N$ high-quality child thoughts **efficiently**, leveraging a **draft-evaluate-reject-correct** paradigm. This process operates on two levels as follows.\n\n  (1) **Drafting (Thought-Level)**: A small model rapidly drafts multiple candidate reasoning thoughts.\n\n  (2) **Evaluating (Thought-Level)**: These drafts are scored by the thought evaluator to assess their contextual quality.\n\n  (3) **Rejection (Thought-Level)**: Thoughts deemed lower in quality than the large model’s outputs are discarded.\n\n  (4) **Correction (Token-Level)**: Rejected thoughts are refined using a lossless token-level speculative decoding method, ensuring accuracy and robustness.\n\nThis bi-level design allows SpecSearch to **accelerate generation** significantly while maintaining **high-quality reasoning** throughout the search process.", "claims_and_evidence": "N/A", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "I feel that the writing could be improved. It was difficult for me to understand the framework clearly, and I do feel that the writing makes something overly complicated.", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper introduces **SpecSearch**, a speculative search framework that accelerates tree-search-based reasoning in large language models (LLMs) by leveraging a small model to draft and verify reasoning thoughts at both the thought and token levels.

Reviewers **cNpL**, **EXez**, and **zUgA** praised the work for its novelty, theoretical guarantees, and strong empirical results. Key strengths highlighted include the broad applicability of speculative decoding to reasoning tasks and the paper’s well-structured presentation. Reviewer **uX9o** raised concerns about limited generalization (initially tested on subsets of MATH/GSM8K) and the novelty of the approach compared to speculative decoding (SD) and Treebon. The authors addressed these concerns in their rebuttal, and no further questions remain.

Given the consistently positive feedback from the reviewers, as well as the work’s completeness and innovation, I recommend **acceptance** of this paper.
Decision: Accept (poster)