Batch speculative decoding Done right

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

Read Batch speculative decoding Done right by Ranran Haoran Zhang, Soumik Dey, Ashirbad Mishra, Hansi Wu, Binbin Li, Rui Zhang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-22876.txt.

Introduction

Fast decoding methods can silently corrupt model outputs. Ranran Haoran Zhang leads a team with five co-authors. In 2025 they audit batch speculative decoding. Speculative decoding drafts tokens, then verifies them. Several common implementations reported good speed. Yet they produced repeated tokens and unknown symbols.

The root cause is the ragged tensor problem. Variable acceptance desynchronizes batch data. Position IDs, attention masks, and caches fall out of step. The team formalizes invariants that valid batches must keep. Two fixes are proposed, EQSPEC and EXSPEC. EXSPEC groups same length sequences to skip realignment. It reached high throughput with near exact matching.

Catalog record

CREATORRanran Haoran Zhang, Soumik Dey, Ashirbad Mishra, Hansi Wu, Binbin Li, Rui Zhang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE39 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-22876

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Batch speculative decoding Done right Ranran Haoran Zhang, Soumik Dey, Ashirbad Mishra, Hansi Wu, Binbin Li, Rui Zhang Abstract Speculative decoding speeds up LLM inference by using a small draft model to propose multiple tokens that a target model verifies in parallel. Extending this idea to batches is essential for production serving, but it introduces the ragged tensor problem: sequences in the same batch accept different numbers of draft tokens, breaking right-alignment and corrupting position IDs, attention masks, and KV-cache state. We show that several existing batch implementations violate output equivalence—the fundamental requirement that speculative decoding must produce identical token sequences to standard autoregressive generation. These violations occur precisely due to improper handling of the ragged tensor problem. In response, we (1) characterize the synchronization requirements that guarantee correctness, (2) present a correctness-first batch speculative decoding EqSpec that exposes realignment as consuming 40% of overhead, and (3) introduce EXSpec , which maintains a sliding pool of sequences and dynamically forms same-length groups, to reduce the realignment overhead while preserving per-sequence speculative speedups. On the SpecBench dataset, across Vicuna-7B/68M, Qwen3-8B/0.6B, and GLM-4-9B/0.6B target/draft pairs, our approach achieves up to 3× throughput improvement at batch size 8 compared to batch size 1, with efficient scaling through batch size 8, while maintaining 95% output equivalence. Our method requires no custom kernels and integrates cleanly with existing inference stacks. Our code is available at https://github.com/eBay/spec_dec . 1 Introduction Speculative decoding ( Leviathan et al. 2023 ; Chen et al. 2023 ) accelerates LLM inference by using a small draft model to propose multiple tokens that the target model verifies in parallel, shifting from memory-bound sequential generation to compute-intensive verification and delivering single-sequence speedups ( Xia et al. 2024 ) . Batch speculative decoding aims to combine this per-sequence acceleration with standard batching by processing multiple sequences (batch dimension) while verifying multiple draft tokens per sequence (sequence dimension). The core challenge is the ragged-tensor effect ( Qian et al. 2024 ) : in each verification round, sequences accept a single series of the proposed draft tokens, but prefix lengths differ across sequences (e.g., one accepts five tokens while another accepts one), misaligning sequence lengths. This raggedness violates the rectangular-tensor assumption required for GPU-parallel execution. Figure 1 highlights a critical, often overlooked issue in batch speculative decoding: methods with impressive throughput can produce corrupted outputs. For lossless acceleration, speculative decoding must yield identical outputs to standard autoregressive generation ( Leviathan et al. 2023 ) . As a reference point, the widely used HuggingFace implementation ( Wolf et al. 2020 ) preserves this guarantee, but only for batch size 1. By contrast, in our tests of public batch implementations—specifically, BSP ( Su et al. 2023 ) and DSD ( Yan et al. 2025 ) —this requirement is violated at batch sizes >1 , manifesting as repetitive tokens or <unk> symbols under greedy decoding rather than matching standard generation. YES, High Throughput… BUT, Output Gibberish! Method Generated Output Prompt: ”The weather today is” Ground Truth not as bad as it was yesterday… Spec-1 ✓ Matches ground truth BSP ✗ not not not not not not not… DSD ✗ ⟨unk⟩⟨unk⟩ The perfect time… EqSpec ✓ Matches ground truth EXSpec ✓ Matches ground truth Figure 1: Batch speculative decoding on Vicuna-7B/68M: Existing methods achieve high throughput but violate the fundamental requirement of output equivalence by producing corrupted outputs. Our approach maintains perfect correctness while still achieving competitive performance. These failures share a single root cause—broken synchronization invariants (position tracking, attention, KV-cache) across ragged tensors. We first propose EqSpec by formalizing these invariants and enforcing them with synchronization-aware scheduling (Section 3.1 ). Concretely, EqSpec specifies the minimal synchronization needed for correctness and shows that realignment accounts for 40% of computation—an inherent cost of maintaining invariants across ragged tensors. This fundamental overhead helps explain why even production systems struggle: vLLM’s speculative decoding underperforms its non-speculative baseline at higher batch sizes (leading to deprecation in its v1 engine), while SGLang with EAGLE ( Li et al. 2024a ) consistently exhibits negative speedups. Our analysis indicates that the superlinear growth of synchronization overhead is an inevitable cost of correctness in batch speculative decoding—a barrier no existing system has overcome. To address this in practice, our main algorithm EXSpec (Section 3.2 ) expands the scheduling scope: it maintains a sliding window of active sequences and dynamically groups those with identical lengths, eliminating realignment for homogeneous groups. This strategy preserves the scaling efficiency of standard batching—where GPU parallelism drives throughput—while retaining the per-sequence acceleration benefits of speculation. At batch size 8, we achieve a 3\times throughput improvement over batch size 1. Nevertheless, beyond batch size 8, throughput degrades as grouping success rates decline, forcing more frequent fallbacks to expensive realignment. Section 4 examines these scaling dynamics and the relationship between sequence diversity, grouping effectiveness, and alignment overhead. Our experiments on SpecBench ( Xia et al. 2024 ) yield two main results. First, Correctness : unlike prior approaches such as BSP and DSD, which suffer severe output corruption, our method preserves approximately 95% output equivalence across Vicuna-7B/68M ( Zheng et al. 2023 ) , Qwen3-8B/0.6B ( Yang et al. 2025 ) , and GLM-4-9B/0.6B ( GLM et al. 2024 ) model pairs. Second, Scalability : at batch size 8, EXSpec achieves up to a 3\times speedup over batch size 1. Our contributions are summarized as follows: • We provide a correctness-first analysis of the ragged-tensor problem in batch speculative decoding, identifying precise synchronization requirements for correctness and explaining why existing methods fail (Section 2 ). • We present a unified solution that maintains correctness through precise synchronization invariants while avoiding their overhead via cross-batch scheduling of same-length sequence groups (Section 3 ). • We experimentally demonstrate that our approach achieves both > 95% output correctness and positive scaling through batch size 8, successfully multiplying batch parallelism with per-sequence speculation gains, whereas production systems (vLLM, SGLang) exhibit negative speedups (Section 4 ). 2 Design Space Analysis Figure 2: The ragged tensor problem in batch speculative decoding. Differing numbers of accepted draft tokens across sequences in the same batch lead to ragged-shaped input IDs tensors and KV Cache that disrupt subsequent batch operations. When sequences within a batch accept different numbers of draft tokens during verification, tensors become irregular, violating GPUs’ requirement for rectangular layouts—this is the ragged-tensor problem illustrated in Figure 2 . Despite batching’s centrality to production deployments, existing implementations lack a principled design that preserves output equivalence with standard decoding while scaling with batch size. We identify three approaches to handle raggedness: Masking , Rollback , and Dynamic Padding . Yet, as our systematic analysis shows, current instantiations of these approaches fail to simultaneously maintain correctness and performance at scale. To close this gap, we first analyze the pitfalls of each approach and then introduce a correctness-first algorithmic design with explicit synchronization requirements for reliable batch speculative decoding. ✗Masking Approach (non-contiguous position IDs). This approach operates directly on ragged tensors by masking rejected tokens in attention and reassigning position IDs so new tokens align with their content positions. Across verification rounds with varying rejections, sequences accumulate padding in various positions (middle and right), forming non-contiguous position IDs that standard Transformer implementations handle poorly. BSP ( Su

Read the complete text