Correctness Forensics for Batch Speculative Decoding: Diagnosing the Ragged Tensor Problem (v1 title: Batch Speculative Decoding Done Right)

How deeply this was read: the full paper from the arXiv HTML version (v4), fetched 2026-09-24, main text and tables; the appendices (including Appendix F on vLLM and SGLang) did not come through on the fetch and are not summarised here. Every number below is read from the fetched text.

Name and version. Proposed to the KB as "Batch Speculative Decoding Done Right", its title when first posted (v1, 2025-10-26). The current version (v4, revised 2026-08-31) is titled "Correctness Forensics for Batch Speculative Decoding: Diagnosing the Ragged Tensor Problem" and is marked "Accepted to Findings of the Association for Computational Linguistics: EMNLP 2026". Revision dates: v2 2026-01-29, v3 2026-02-15, v4 2026-08-31. Code is released by eBay.

Abstract

Verbatim from arXiv (v4):

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.

The problem, in plain words

Speculative decoding has a small, fast model guess a few tokens ahead, and the big model checks the guesses in one pass. Its promise is that the output is exactly what the big model would have written alone — just faster. Serving many requests at once (a batch) is how a GPU earns its keep. Put the two together and there is a snag: in each round, one request might accept four of the guesses and its neighbour only one. The requests are now different lengths. If the code does not carefully re-line-up the batch — where each token sits, what each token may look at, and the stored memory of earlier tokens (the KV cache) — the model starts reading the wrong memory and writes nonsense. The paper calls this the "ragged tensor problem".

Key Contributions

• Two published implementations produce garbage at speed. With the prompt "The weather today is", normal decoding continues "not as bad as it was yesterday…"; BSP writes "not not not not…" and DSD writes "⟨unk⟩⟨unk⟩ The perfect time…" (Figure 1, Vicuna-7B). Both had reported competitive throughput in their own papers.
• Standard quality scores can hide it. ROUGE can still score repetitive, corrupted text reasonably, so a speed paper that checks output with ROUGE may not notice.
• Two cheap tests that do catch it: exact match (is the whole output identical to normal decoding?) and partial match (how far does it get before the first wrong token?). Both low means the positions are wrong from the start; partial high but exact low means the stored memory is slowly drifting.
• The rules a correct batch must keep, stated formally: every request padded to the same width after each round, and positions counted without gaps so that each stored memory entry matches its token. The paper proves that keeping these (plus sampling the bonus token from the big model) is enough for correct output.
• Correctness costs time. Re-lining-up the batch every round grows faster than the batch does.
• Two fixed versions. EqSpec keeps the rules every round; EXSpec avoids most re-lining-up by grouping requests that happen to be the same length.

Methodology

Three big-model/small-model pairs — Vicuna-7B/68M, Qwen3-8B/0.6B, GLM-4-9B/0.6B — on NVIDIA A100 80GB GPUs, five guessed tokens per round, greedy decoding so any difference from normal decoding is visible. Benchmark: SpecBench. The reference ("oracle") is normal, non-speculative decoding one request at a time.

Results

Exact match (E) and partial match (P) against normal one-at-a-time decoding, % (Table 2):

• Even normal batched decoding does not match one-at-a-time decoding exactly (53.8% on Vicuna at batch 4). The authors attribute the fixed versions' remaining 3–9% mismatch to this same floating-point effect, not to the batching bug. A vLLM check on Qwen3-4B/0.6B (Table 4) shows the same: without batch-invariant kernels, even plain batched decoding diverges on some prompts.
• Cost of keeping the rules: the share of time spent re-lining-up the batch rises from ~13% at batch size 1 to nearly 40% at batch size 32 (Section 4.3; the Figure 5 caption says "up to 38%", and the introduction says "reaching 40% at batch size 8" — the paper is not consistent on which batch size the ~40% belongs to).
• EXSpec against EqSpec (Table 5): 156.4 against 95.6 tokens/s (64% higher), with the re-lining share cut from 27.7% to 14.6%.
• Speed against waiting time (Table 6, simulated online serving): at batch size 2, EXSpec gives 30.54 against 26.70 tokens/s but its 99th-percentile request takes 134.03 s against 19.06 s for EqSpec, because it holds requests back until it finds same-length partners. The authors' recommendation: EXSpec for offline bulk work, EqSpec where waiting time matters.
• The headline "3× at batch size 8" is EXSpec's throughput scaling; the paper does not make clear in the main text whether it is measured against EXSpec's own batch-size-1 speed or against another baseline. Treat it as the authors' figure, not a like-for-like speedup over a production server.

Limitations

• The big production servers mostly avoid this problem. vLLM v1 and SGLang store each request's memory in a flat, variable-length layout ("paged attention"), so the batch never needs re-lining-up. The paper's methods apply to the other case — the fixed-width layout used on hardware without those kernels (the authors name Ascend, Intel Gaudi, Apple Metal) and in offline bulk jobs. They did not build their fixes into vLLM or SGLang.
• The 3× is against a lot of broken company. The implementations it outpaces are the ones the paper shows are wrong. The finding that matters is the correctness failure, not the multiplier.
• Gains are confined to moderate batch sizes; they shrink as request lengths vary more, and are capped by how good the small guessing model is.
• Not bit-exact: 90.8–97.3% exact match.

How it bears on the through-line

The KB tracks the path from a token price to a task price. A speed-up is only worth money if the tokens it produces are the right ones: a server that is 3× faster at writing "not not not" has lowered its price per token and raised its price per finished task to infinity. This paper shows that happened in published code, and that the usual quality check (ROUGE) would not have caught it. For this rung it adds a rule the rest of the speculative-decoding sources assume without testing: a speed-up claim is only a measurement if it comes with an exact-match check against normal decoding. It also prices correctness — up to about 40% of the time at large batch sizes on the fixed-width layout — which is part of why the paged layout won in production. It pairs with the latency model for speculative decoding, which says when the speed-up fades.

Source: Correctness Forensics for Batch Speculative Decoding by Ranran Haoran Zhang, Soumik Dey, Ashirbad Mishra, Hansi Wu, Binbin Li and Rui Zhang (Penn State, eBay), arXiv:2510.22876v4, revised 2026-08-31.