Response to Reviewer zUgA

We 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.

Weakness 1.

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.

Thank 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.

• 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.

• 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.

  (1) Drafting (Thought-Level): A small model rapidly drafts multiple candidate reasoning thoughts.

  (2) Evaluating (Thought-Level): These drafts are scored by the thought evaluator to assess their contextual quality.

  (3) Rejection (Thought-Level): Thoughts deemed lower in quality than the large model’s outputs are discarded.

  (4) Correction (Token-Level): Rejected thoughts are refined using a lossless token-level speculative decoding method, ensuring accuracy and robustness.

This bi-level design allows SpecSearch to accelerate generation significantly while maintaining high-quality reasoning throughout the search process.

Response to Reviewer EXez

We 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.

Due to limited space, we provide Tables and Figures in 14604.pdf in Anonymous Link.

Weakness 1.

1. Use more, non-mathematical reasoning datasets

We 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.

Weakness 2.

2. Error bars from running across random seeds

We 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.

3. Comparison with newer speculative approaches

We 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.

[1] Break the Sequential Dependency of LLM Inference Using Lookahead Decoding, ICML24.

[2] EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty, ICML24

[3] TreeBoN: Enhancing Inference-Time Alignment with Speculative Tree-Search and Best-of-N Sampling, 2024.10

Weakness 3.

4. A deeper comparison with SEED or other structured speculative decoding (SD) methods.

1) The novelty over SEED and SD

We 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.

It 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.

2) The novelty over a recent structured speculative tree search method

We 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.

Weakness 4.

5. Compare wall-clock time on real hardware with parallelization overhead considered

We 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.

Weakness 5.

6. Discussion on failure cases where the small model’s generation misleads the system

We 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.

Weakness 6.

7. Speedup sensitivity to the small draft model’s performance

We 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.

Response to Reviewer uX9o

We 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.

Weakness 1.

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.

We 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.

Weakness 2.

2. The core idea of combining small and large models resembles existing speculative decoding (SD) techniques (e.g., token-level draft-then-verify).

We 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.

• 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 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.
• 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.
• 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.

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.)

We 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.

• 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.
• 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.
• 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.
• 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.

Response to Reviewer cNpL

We 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.

Weakness 1.

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.

We 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.

• 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.
• Results
  • 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.
  • 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.
  • 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.