Taming Speculative Search for Test-Time Scaling in LLM Serving

1 Introduction

• Speculation reduces waiting by expanding candidates as soon as they finish a step, but increases candidate paths and fine-grained verification, which can outweigh its performance gains without system support.More paths amplify decoding computation and KV memory pressure; small, irregular verification tasks underuse GPUs and interrupt decoding.Source: §1 · pp. 1–2
• Early pruning discards candidates that cannot enter the final top-k and can stop exploration once k perfect-score candidates are found.The paper states this reduces aggregate compute without compromising final-output accuracy.Source: §1 · p. 2
• Computation deduplication decodes each distinct shared prefix once, reusing its logits until candidates sample different next tokens.The technique can also be applied to non-speculative execution.Source: §1 · p. 2
• Lazy verification queues requests for larger, GPU-efficient batches, using deferral amount, sibling completion, and per-sample limits to balance throughput against latency.Waiting longer can improve batch efficiency but diminish speculative execution’s latency benefit.Source: §1 · p. 2
• Across datasets, SpecScale improves throughput and end-to-end latency over naive speculation and FastTTS; on MATH, throughput is 2.18× and 1.87× higher, respectively.The quantitative comparison is for Qwen2.5-7B-Instruct paired with Qwen2.5-Math-PRM-7B.Source: §1 · p. 2
• The evaluation uses four Qwen2.5 and Llama3 generator–verifier pairs on math benchmarks, with reported gains preserving answer quality.Experiments use a single NVIDIA A100 GPU.Source: §1 · p. 2

2.1 LLM Inference and Serving

• Inference has prefill and autoregressive decode phases, while serving systems use foundational techniques that do not address test-time scaling’s distinct resource-management challenges.During prefill, the model processes the input sequence in parallel; decode generates subsequent tokens until EOS or the maximum length.Source: §2.1 · p. 2

2.2 Test-Time Scaling

• Beam search expands N candidates, scores intermediate reasoning steps with a PRM, retains the top-k, and expands each selected sequence into M candidates.The selection ratio is set so top-k = N/M; the process continues until N complete sequences are generated.Source: §2.2 · p. 3
• PRM-based test-time scaling with Qwen2.5-3B achieves accuracy comparable to Qwen2.5-32B on three math datasets.Best-of-N sampling scores final responses, whereas beam search and MCTS use intermediate verification; the paper focuses on beam search because MCTS has higher per-iteration cost.Source: §2.2 · p. 3

2.3 Inefficiency of Test-Time Scaling

• Synchronous beam search waits for every candidate to finish verification before selecting the next top-k, leaving early-finishing candidates idle.The paper identifies this waiting as a structural inefficiency of tree-based test-time scaling.Source: §2.3 · p. 3
• Median waiting time accounts for approximately 20–55% of execution time under beam search and increases with problem difficulty across GSM, MATH, and Olympiad.The measurements use Qwen2.5-3B-Instruct, Qwen2.5-Math-PRM-7B, and beam sizes 4 and 8.Source: §2.3 · p. 3, Figure 2 · p. 3

3.1 Speculative Execution

• Speculation expands a candidate as soon as it finishes a step instead of waiting for all candidates, allowing an early-finishing path to progress while another is still generating.The example contrasts a path producing two tokens with one producing four; the timeline’s numeric subscripts indicate decoding order and v denotes verification.Source: §3.1 · pp. 3–4, Figure 3 · p. 4

3.2 Challenges for Speculative Execution in Serving

• With beam size 4, speculative execution explores around six active candidates per request versus roughly three non-speculatively, and the gap widens as requests increase.At beam size 8, the discrepancy is more severe; speculative execution also computes paths that do not contribute to the final result.Source: Figure 4 · p. 4, §3.2.1 · p. 4
• Above 8 concurrent requests, speculative token latency surpasses the non-speculative approach, despite reducing latency at low request counts.The comparison uses MATH and Qwen2.5-3B-Instruct.Source: Figure 5 · p. 4, §3.2.1 · pp. 4–5
• Speculative execution accumulates verifications faster and reaches roughly 2–3× the non-speculative baseline, fragmenting batches and repeatedly preempting generation.The verification workload is prefill-only, with the PRM scoring given tokens in a single forward pass.Source: Figure 6 · p. 5, §3.2.2 · p. 5

4 Towards Efficient Speculation

• The generator builds candidate paths with computation deduplication; the verifier batches queued PRM tasks, returns scores, and enables pruning of branches that cannot reach the final top-k.The system applies deduplication during generation and lazy verification before score-guided early pruning.Source: §4 · p. 5

4.1 Early Pruning of Search Tree

• Once more than k candidates are verified, prune any path ranked below the current top-k; k candidates with perfect PRM scores of 1.0 also allow remaining paths to be pruned.Even Qwen2.5-3B-Instruct on Olympiad often assigns the maximum score of 1.0, indicating opportunities to reduce unnecessary speculation.Source: §4.1 · pp. 5–6

4.2 Computation Deduplication

• For identical input prefixes, sample multiple independent next tokens from one shared logits computation, then branch sequences by sampled-token group.The resulting tree is probabilistically equivalent to independent sampling, with decode computation proportional to unique prefixes rather than logical candidates.Source: §4.2 · p. 7

4.3 Lazy Verification

• Lazy verification queues completed-step requests and flushes large GPU-efficient batches, balancing throughput against latency with token, sibling-completion, and per-sample deferral policies.Profiling found throughput saturation around 2,048 input tokens for two PRMs; deployment used a six-deferral limit under light load.Source: §4.3 · pp. 7–8

5.1 Experimental Setup

• Evaluation paired four Qwen2.5 and Llama generators with PRM verifiers on GSM8K, MATH-500, and OlympiadBench using one A100 GPU.Comparisons included non-speculative beam search, naive speculation, and FastTTS.Source: §5.1 · p. 8

5.2 Throughput Performance

• Naive speculation often reduced throughput versus Non-spec because it increased decoding computation and verification calls, while all three SpecScale techniques together yielded the highest throughput.For Qwen2.5-3B-Instruct on MATH with eight beams, EP achieved 1.18× the Non-spec throughput, and adding CD improved throughput by a further 1.10×.Source: §5.2 · pp. 8–9
• SpecScale delivered higher throughput than Non-spec and FastTTS, and EP+CD+LV achieved the lowest normalized latency among tested configurations.The reported results cover token throughput and serving latency.Source: Figure 13 · p. 9, §5.2 · p. 9, Figure 14 · p. 10

5.3 Serving Performance

• At about 75 ms average normalized latency, Qwen2.5-7B-Instruct with four beams served roughly 1.6 requests per second, versus about 0.8 for FastTTS.SpecScale can serve more requests at a given latency budget, allowing more candidates to be explored within that budget.Source: Figure 14 · p. 10, §5.3 · p. 10

5.4 Performance Analysis

• Early pruning reduced candidate paths and latency, deduplication further reduced generation work, and lazy verification lowered overall verification time despite modestly increasing wait time.The analysis focused on Qwen2.5-7B-Instruct with four beams on MATH.Source: §5.4 · pp. 10–11, Figure 15 · p. 11

5.5 Impact on Answer Quality

• For Qwen2.5-3B-Instruct, early pruning's accuracy difference from the non-speculative baseline ranged from −1.01 to +2.97 percentage points across beam sizes 4 and 8.The supplied passage says further adding computation deduplication and lazy verification does not materially affect accuracy.Source: Table 2 · p. 11, §5.5 · p. 11

5.6 Analysis of Lazy Verification Technique

• At a 2,048-token threshold, lazy verification reached 1.09× and 1.14× baseline throughput for beam sizes 4 and 8, respectively; at 4,096 tokens, throughput fell below baseline.The baseline is SpecScale with lazy verification disabled (EP+CD) at the corresponding beam size.Source: Figure 16 · p. 11, §5.6 · pp. 11–12

5.7 Scalability

• At 32 beams, SpecScale latency was about 195 ms versus approximately 330 ms for Non-spec, with roughly 22% less KV memory; it also outperformed the other approaches in throughput at 16–128 concurrent requests.For four beams, Non-spec and FastTTS saturated around 64 concurrent requests, while SpecScale throughput continued to increase.Source: Figure 17 · p. 12, Figure 18 · p. 12, §5.7 · p. 12

• FastTTS uses predicted candidate selection and Lookahead Verification, while SpecScale prunes deterministically from verified scores and can flush deferred candidates without waiting for every candidate to finish.FastTTS's Lookahead Verification waits for all candidates to complete their current step, limiting early-pruning opportunities.Source: §6 · p. 12
• SPEX speculatively expands completed candidates while stragglers run and uses a confidence-margin heuristic, but does not explicitly optimize verification-batch efficiency or redundant forward computation.SpecScale's EP instead discards candidates once k verified candidates outrank them.Source: §6 · p. 12
• SPECS and ORCHES use additional lightweight models for drafting or verification, with ORCHES requiring GPU-PIM hardware and both approaches incurring misprediction penalties.SPECS switches to the target model based on problem difficulty; ORCHES verifies in parallel with a target PRM.Source: §6 · p. 12
• Prefix KV reuse and shared-prefix attention still require a separate forward pass per candidate, whereas SpecScale's runtime coalescing removes redundant forward computation for identical candidates.Tree-based speculative decoding shares attention over a token tree drafted by another model and discards mispredicted branches.Source: §6 · pp. 12–13

• Naive speculation can hurt test-time scaling performance despite removing step-level synchronization barriers.The paper identifies this problem and explores system-design solutions.Source: §7 · p. 13
• SpecScale supports speculative execution through early pruning, computation deduplication, and lazy verification.Source: §7 · p. 13
• Experiments found that SpecScale consistently achieved higher throughput and lower end-to-end latency than non-speculative and FastTTS approaches.Source: §7 · p. 13