PaperlayerView exact revision on arXiv

Source-linked AI summary

Correctness Forensics for Batch Speculative Decoding: Diagnosing the Ragged Tensor Problem

Ranran Haoran Zhang, Soumik Dey, Ashirbad Mishra, Hansi Wu, Binbin Li, Rui Zhang

arXiv:2510.22876v4cs.CLcs.AI

TL;DR

Batch speculative decoding can silently corrupt outputs when variable token acceptance desynchronizes batch state, yet inference optimizations are often evaluated by throughput alone. The paper audits these failures, formalizes synchronization invariants, and introduces EQSPEC and EXSPEC to enforce them and reduce alignment costs. EXSPEC reaches 3× throughput at batch size 8, while the methods achieve 90.8–97.3% exact match against batch-size-1 non-speculative decoding.

  • Problem

    Inference optimizations are routinely evaluated by throughput without verifying output equivalence, while batch speculative decoding can desynchronize position IDs, attention masks, and KV-cache as sequences accept different numbers of draft tokens.

    Source: §1 · p. 1

  • Method

    The paper audits batch speculative decoding, formalizes rectangular-alignment and position/KV-cache synchronization invariants, and presents EQSPEC and same-length scheduling in EXSPEC.

    Source: §1 · p. 1, §6 · p. 9

  • Results

    3× throughput at batch size 8 is reached by EXSPEC, and the methods achieve 90.8–97.3% exact match against batch-size-1 non-speculative decoding.

    Source: §1 · p. 2, §6 · p. 9

  • Takeaways & Limitations

    Throughput comparisons for batch speculative decoding should be paired with correctness checks, since published implementations can produce corrupted outputs that standard metrics such as ROUGE may mask.

    Source: §1 · p. 1, §6 · p. 9

    The case study is limited to contiguous KV-cache and does not integrate EQSPEC or EXSPEC into continuous-batching systems such as vLLM or SGLang.

    Source: Limitations · p. 9

Abstract

from arXiv · show

Inference optimizations are routinely evaluated by throughput alone, without verifying output correctness. We conduct a forensic analysis of batch speculative decoding and find that several widely-used implementations silently produce corrupted outputs (repetitive tokens, <unk> symbols) while reporting competitive speed; failures invisible to metrics like ROUGE. We trace the root cause to the ragged tensor problem: variable token acceptance desynchronizes position IDs, attention masks, and KV-cache across a batch. We formalize the synchronization invariants (rectangular alignment and position-ID contiguity) that valid batched inference must preserve and show that maintaining them incurs superlinear alignment overhead under contiguous layouts. EQSPEC enforces the invariants without custom kernels; EXSPEC schedules same-length sequences to bypass realignment. On SpecBench across three model families, EXSPEC reaches 3 x throughput at batch size 8 with 95% exact match to standard decoding; residual divergence traces to floating-point non-determinism, not synchronization error. Code:https://github.com/eBay/spec_dec

1 Introduction

Inference optimizations are often judged by throughput without verifying output equivalence, even though batching speculative decoding can desynchronize sequence state. The paper audits these failures, formalizes synchronization invariants, and presents methods that preserve correctness while reducing alignment costs.

1 Introduction

  • Variable draft-token acceptance desynchronizes position IDs, attention masks, and KV-cache across a batch, creating the ragged tensor problem.The paper formalizes rectangular alignment and position/KV-cache correspondence as synchronization conditions for algorithmic output equivalence.Source: §1 · p. 1
  • BSP and DSD report competitive throughput but produce repetitive tokens or <unk> symbols under greedy decoding, failures that ROUGE can mask.The audit uses exact and partial match to detect corruption and distinguish immediate position-ID errors from gradual KV-cache drift.Source: §1 · p. 1, Figure 1 · p. 2
  • 3× throughput at batch size 8 is reached by EXSPEC, which groups same-length sequences to bypass realignment; under contiguous layouts, realignment overhead reaches 40%.The overhead grows superlinearly with batch size.Source: §1 · pp. 1–2
  • The audit contributes diagnostics that identify failure signatures and isolate root causes in batch speculative decoding.The paper argues that output correctness should be evaluated alongside throughput.Source: §1 · pp. 1–2
  • 90.8–97.3% exact match against batch-size-1 non-speculative decoding is achieved across three model families by methods enforcing two synchronization invariants.EQSPEC enforces the invariants without custom kernels.Source: §1 · p. 2

2 Failure Modes and the Audit Protocol

The audit traces batch speculative-decoding failures to irregular tensor shapes and evaluates approaches according to their cache layout and synchronization behavior. Exact and partial match diagnose output divergence, while the analysis distinguishes contiguous layouts from variable-length layouts.

2 Failure Modes and the Audit Protocol

  • Different accepted draft-token counts produce irregular tensors; contiguous layouts must restore rectangular shape after every verification round, whereas variable-length layouts pack sequences into a flat buffer.Variable-length layouts dissolve the alignment requirement by construction.Source: §2 · p. 2, Figure 2 · p. 3
  • Only dynamic padding can be correct, token-preserving, portable, and memory-bounded among the described contiguous-layout strategies, provided synchronization is done correctly.None of the tested implementations achieves that synchronization; masking leaves the KV-cache desynchronized, while rollback discards verified tokens and batch expansion uses K× memory.Source: §2 · pp. 2–3
  • Variable-length layouts avoid repadding, but still require rejected tokens to be rolled back in both position IDs and KV-cache.The described production systems use this layout, which depends on paged-attention kernels available only on CUDA/Triton.Source: §2 · p. 3

2.1 Output Equivalence as a Diagnostic Criterion

  • Batched floating-point execution can alter argmax decisions, so exact match diagnoses corruption but does not guarantee bit-exact identity.The paper uses greedy decoding because it exposes synchronization errors more clearly than stochastic sampling; BSP and DSD fail this diagnostic regardless of throughput.Source: §2.1 · p. 3

3 Correctness Specification and Cost

The paper formalizes synchronization conditions for correct batch speculative decoding and introduces EQSPEC to enforce them. It analyzes the cost of maintaining those conditions under contiguous layouts and presents EXSPEC’s same-length scheduling as a way to avoid realignment when possible.

3.1 EQSPEC: Formalizing the Correctness Specification (Stage 3)

  • EQSPEC specifies rectangular alignment and position/KV-cache correspondence as synchronization invariants for correct batched inference.It enforces the invariants through realignment without custom kernels; maintaining them with target-model bonus sampling is sufficient for algorithmic output equivalence.Source: §3 · p. 3, §3.1 · p. 4

3.2 EXSPEC: Quantifying and Reducing the Cost of Correctness (Stage 3–4)

  • Realignment overhead grows superlinearly with batch size under contiguous layouts, because each round restores rectangular alignment and realigns KV-cache state.The KV-cache dominates the alignment cost; skipping synchronization breaks equivalence, while paying the full cost limits scaling.Source: §3.2 · pp. 4–5
  • EXSPEC keeps sequences in ragged states and forms batches of identical-length sequences, bypassing realignment when lengths match.When grouping fails, it falls back to unpad–append–repad; a sliding window of more than B sequences increases the chance of finding same-length groups.Source: §3.2 · p. 5

4 Experimental Validation

The experiments assess output equivalence and throughput across model pairs, then validate the diagnostic signatures and the cost of synchronization. EQSPEC and EXSPEC largely match batch-size-1 decoding, while EXSPEC’s grouping and EQSPEC’s realignment expose different throughput and latency tradeoffs.

4.1 Experimental Setup

  • The evaluation uses SpecBench and three target–draft model pairs, measuring tokens per second alongside exact-match and partial-match rates against non-speculative decoding.Experiments generally use greedy decoding, five draft tokens per round, and NVIDIA A100 80GB GPUs.Source: §4.1 · p. 5

4.2 Validating the Diagnostics (Stage 1–2)

  • DSD and BSP show catastrophic degradation that ROUGE misses: DSD diverges immediately, while BSP’s higher partial match reaches 39.7% before KV-cache drift triggers repetition.The two distinct signatures map to position-ID misalignment for DSD and accumulated KV-cache drift for BSP.Source: §4.2 · p. 6
  • 90.8–97.3% exact match against the batch-size-1 non-speculative oracle is achieved by the proposed methods, with residual divergence consistent with floating-point effects and argmax tie-breaking.Non-speculative batched decoding can also diverge from a batch-size-1 anchor, separating numerical divergence from speculative synchronization errors.Source: §4.2 · p. 6, Table 2 · p. 7

4.3 Validating the Cost Analysis (Stage 4)

  • Alignment overhead rises from ∼13% at batch size 1 to nearly 40% at batch size 32, matching the predicted superlinear growth under contiguous layouts.The growing cost comes from unpad–append–repad and KV-cache realignment as sequence lengths diverge.Source: §4.3 · p. 7, Figure 5 · p. 7
  • On Multi30k, random sampling’s grouping rate falls as batch size grows, whereas an identical-length subset maintains high grouping effectiveness and reduces alignment overhead.This comparison isolates sequence-length diversity as the grouping bottleneck.Source: §4.3 · p. 7, Figure 5 · p. 7
  • 64% higher throughput is reported for EXSPEC, which cuts verification calls by one-third and halves alignment overhead through same-length grouping.Despite slower per-verification time from scattered KV-cache entries, fewer total operations win.Source: §4.3 · p. 7, Table 5 · p. 8
  • EXSPEC raises throughput but can inflate tail latency while waiting for matching requests; EQSPEC realigns each round for stable, predictable tail latency.The paper frames EXSPEC for offline throughput and EQSPEC for latency-sensitive serving.Source: §4.3 · p. 8

5 Related Work

Prior work spans exact and approximate speculative decoding, batch extensions, and systems that avoid raggedness through different layouts. The paper distinguishes its synchronization analysis from those approaches and from prior work on numerical nondeterminism.

Speculative Decoding and Batch Extension

  • Exact speculative-decoding variants preserve the target distribution, whereas approximate schemes trade exactness for speed; prior parallel-draft methods still verify drafts independently.The cited approaches include sequential and tree-structured verification as well as multiple drafts per request.Source: §5 · p. 8
  • BSP’s position-ID inconsistencies and DSD’s incorrect bonus-token sampling and KV-cache handling produce corrupted outputs; BASS avoids these issues with custom CUDA kernels but sacrifices portability.Continuous-batching systems such as vLLM v1 and SGLang instead use variable-length storage and paged attention.Source: §5 · pp. 8–9

Correctness Verification and Reproducibility in LLM Inference

  • Prior work reports numerical nondeterminism or batch-size output variation, while this paper’s diagnostics distinguish such effects from synchronization failures.The cited diagnostic framing draws on fault-localization and delta-debugging ideas.Source: §5 · p. 9

6 Conclusion

The audit finds that throughput alone cannot establish correctness: batch speculative decoding can fail silently, so practitioners should verify synchronization and output equivalence.

6 Conclusion

  • Enforcing synchronization invariants removed catastrophic synchronization failures without bit-exact identity, yielding 90.8–97.3% exact match; EXSPEC’s same-length scheduling cut cost and delivered 3× throughput at batch size 8.Source: §6 · p. 9
  • The audit links corrupted outputs to synchronization failures and uses exact match to detect corruption and partial match to localize it.High partial but low exact match indicates cache drift; low values for both indicate position-ID errors.Source: §6 · p. 9
  • The audit approach may transfer to other tensor-batched settings, though validation here covers only batch speculative decoding.Source: §6 · p. 9

Limitations

The case study covers contiguous KV-cache layouts and leaves integration with continuous-batching systems untested. EXSPEC’s benefits also depend on workload and serving priorities, and outputs do not achieve bit-exact identity with the batch-size-1 oracle.

Limitations

  • The study is limited to contiguous KV-cache settings and does not integrate EQSPEC or EXSPEC into continuous-batching systems such as vLLM or SGLang.Those systems use variable-length and paged-attention layouts that avoid the ragged-tensor problem by construction.Source: Limitations · p. 9
  • EXSPEC’s advantage is confined to moderate batch sizes, depends on sequence-length homogeneity, and is bounded by draft-model quality.Heterogeneous workloads erode the gains from grouping same-length sequences.Source: Limitations · p. 9
  • EXSPEC trades tail latency for throughput, while EQSPEC realigns each round and offers stable per-request latency for online serving.Delaying requests to form same-length groups suits offline, throughput-oriented batch processing.Source: Limitations · p. 9
  • Exact match is 90.8–97.3% against batch-size-1 non-speculative decoding, not bit-exact identity; residual mismatches are consistent with batch-dependent floating-point effects.Source: Limitations · p. 9

A Bug Taxonomy in Prior Implementations

Prior batch speculative decoding systems exhibit both batch-independent implementation mistakes and batch-specific synchronization errors. The paper’s invariants and EQSPEC address the latter, which arises from ragged acceptance across sequences.

A Bug Taxonomy in Prior Implementations

  • Prior systems’ errors fall into batch-independent mistakes and batch-specific synchronization failures.The first category includes sampling from the wrong distribution or retaining rejected tokens; the second arises when sequences accept different numbers of draft tokens.Source: A Bug Taxonomy in Prior Implementations · p. 12
  • DSD samples its bonus token from the draft rather than target distribution, while BSP retains rejected KV-cache tokens and relies on position IDs that can become incorrect when padding changes.Source: A Bug Taxonomy in Prior Implementations · p. 12
  • EQSPEC formalizes and addresses the batch-specific synchronization challenge, which has no analog in single-sequence speculative decoding.The invariants specify what must be preserved across position IDs, attention masks, and KV-cache state.Source: A Bug Taxonomy in Prior Implementations · p. 12

B Proof of Synchronization Invariants

The proof establishes that maintaining alignment and cache correspondence preserves output equivalence under exact arithmetic and deterministic decoding. It also identifies cases that require no realignment and describes EXSPEC scheduling and batch verification.

B Proof of Synchronization Invariants

  • EQSPEC realignment relocates retained cache entries, drops rejected-token entries, and preserves the target-computed values for accepted tokens.Position IDs are restored by recomputing them from the attention mask after repadding.Source: B Proof of Synchronization Invariants · pp. 12–13
  • With I1 and I2 maintained at every round and bonus tokens sampled from the target model, deterministic decoding produces the same tokens as per-sequence decoding under exact arithmetic.The target then reads the reference positions and key/value entries within the rectangular batch, yielding the same logits.Source: B Proof of Synchronization Invariants · p. 13
  • No padding adjustment is needed for batch size 1 or when every sequence accepts the same number of tokens.For uniform acceptance, the existing padding is preserved without memory reallocation or shifting.Source: B Proof of Synchronization Invariants · p. 13
  • Realignment work grows superlinearly with batch size under non-degenerate acceptances, while per-sequence cost saturates at K − µ.Source: B Proof of Synchronization Invariants · pp. 13–14

C EXSPEC: Cross-Batch Scheduling Algorithm

D BatchVerify Algorithm Details

  • BatchVerify compares target predictions with draft tokens, accepts the prefix before the first mismatch, and obtains the bonus token from the target distribution.The bonus token has no KV-cache entry until the next forward pass; sampling it from the draft instead would violate output equivalence.Source: D BatchVerify Algorithm Details · p. 14

E Latency-Throughput Tradeoff in Online Serving

Both methods speed up heterogeneous multi-turn workloads, but EXSPEC’s throughput advantage comes with worse tail latency; EQSPEC offers more predictable completion times.

E Latency-Throughput Tradeoff in Online Serving

  • EXSPEC delivers 2–14% higher throughput than EQSPEC, but has 1.5–7.7× worse P90/P99 latency under heterogeneous multi-turn workloads.Cross-batch grouping of same-length sequences improves throughput, while delaying early requests can cause head-of-line blocking.Source: E Latency-Throughput Tradeoff in… · p. 14
  • EQSPEC keeps P99 latency under 23 seconds across batch sizes, while EXSPEC’s P99 reaches 134s at batch size 2 and falls to 34s at batch size 8.At batch size 8, EXSPEC sustains 77.5 tokens/s to drain the request queue.Source: E Latency-Throughput Tradeoff in… · p. 15
  • The choice depends on deployment needs: EQSPEC suits latency-sensitive interactive applications, whereas EXSPEC maximizes throughput for offline batch processing.Both methods achieve positive speedups under the tested heterogeneous workloads.Source: E Latency-Throughput Tradeoff in… · pp. 14–15

F Continuous Batching Systems

Continuous-batching systems handle ragged sequences through variable-length layouts, but speculative-decoding throughput and accuracy vary across systems and models. The discussion frames synchronization overhead and production integration as remaining design constraints.

F Continuous Batching Systems

  • vLLM v1 is output-equivalent on H100, while the main comparison used v0 because neither engine then exposed external-draft speculation through continuous batching.The paper attributes the reported divergences below to numerical precision and feature scope; vLLM v1 later added external-draft speculation.Source: F Continuous Batching Systems · p. 15
  • Continuous batching uses variable-length packing to sidestep rectangular alignment, but still requires scatter-gather and rollback of position IDs and KV-cache for rejected tokens.Invariant I2 remains necessary regardless of batching strategy.Source: F Continuous Batching Systems · p. 15
  • Both systems are accurate on Vicuna but degrade on Qwen3; deterministic SGLang improves Vicuna from 69.8% to 85.0%, pointing to floating-point non-determinism as the main divergence source.SGLang supports EAGLE-family drafters, not external draft models.Source: F Continuous Batching Systems · p. 16
  • Batch expansion trades K× memory for implementation simplicity, whereas unpad-append-repad pays synchronization costs when sequences diverge.Integrating synchronization with continuous batching and paged attention remains an open production-deployment problem.Source: F Continuous Batching Systems · p. 16
  • At high concurrency, vLLM’s speculative decoding underperforms its baseline, and SGLang+EAGLE is slower than non-speculative generation.Figure 6 uses maximum batch size on the x-axis because these systems dynamically vary effective batch sizes.Source: F Continuous Batching Systems · p. 15, Figure 6 · p. 16

G Discussion

  • The paper identifies ragged-tensor synchronization as an obstacle to combining batch parallelism with per-sequence speculation, with realignment consuming up to 40% of computation.EXSPEC’s cross-batch scheduling can mitigate, but not eliminate, that overhead while maintaining output equivalence.Source: G Discussion · p. 16

H Reproducibility Statement

The reproducibility statement specifies model and decoding configurations, makes experimental materials and verification procedures available, and discloses the manuscript’s assistive-tool use.

H Reproducibility Statement

  • The supplementary material provides hyperparameters, experimental configurations, and model specifications; exact and partial match support deterministic validation.The experiments use publicly available models and datasets.Source: H Reproducibility Statement · p. 16
  • Experiments cover Vicuna-7B, Qwen3-8B, and GLM-4-9B target-draft pairs using FP16, greedy decoding, and five draft tokens per speculation round unless otherwise specified.The models are paired with draft models of 68M, 0.6B, and 0.6B parameters, respectively.Source: H Reproducibility Statement · p. 16
  • The production-system comparison used vLLM v0 and SGLang EAGLE models for Vicuna and Qwen3; GLM-4 was not evaluated with SGLang because compatible draft models were unavailable.SGLang deterministic mode was also tested to isolate floating-point non-determinism from algorithmic correctness issues.Source: H Reproducibility Statement · pp. 16–17

I Disclose on LLM Usage

  • GPT-5 and Claude Opus 4.1 assisted with manuscript polishing, diagrams, and unit tests, while Parakeet-TDT-0.6B-v3 transcribed voice input.The authors state that LLMs were not used for research ideation, experimental design, data analysis, or scientific conclusions.Source: I Disclose on LLM Usage · p. 17

Related papers

Loading 2510.22876v4…