Batch Verification

The fundamental operation of batch verification is the parallel scoring of multiple candidate token sequences in a single forward pass of the target model. Instead of generating tokens one-by-one (autoregressively), the model processes a batch dimension representing different candidate futures. This is achieved by constructing a batch of input sequences, each identical up to the current generation point but appended with a different speculative continuation. The target model's forward pass computes logits for the next token position for every sequence in this batch simultaneously, leveraging the GPU's parallel compute architecture. The efficiency gain comes from the fact that the cost of this single batched forward pass is often less than the cumulative cost of multiple sequential forward passes would have been.

Batch verification is intrinsically linked to the management of the transformer's Key-Value (KV) Cache. For each candidate sequence in the batch, the KV cache for the shared prefix tokens (the context) can be reused, avoiding redundant computation. However, the cache for the speculative draft tokens must be computed and stored separately for each candidate. Efficient implementations use a speculative KV cache structure that:

• Stores the KVs for the draft tokens of all candidate sequences.
• Enables the target model's attention mechanism to attend to these candidate-specific caches during the parallel verification pass.
• Must be managed carefully to avoid memory bloat, as the cache size scales with the batch size (number of candidates) and the speculative length.

After the parallel forward pass, the target model applies a deterministic algorithm to accept or reject the proposed draft tokens. The standard algorithm performs token-level verification:

• For the first speculative position, the target model's predicted probability distribution is compared to the draft token.
• If the draft token's probability under the target model meets a criterion (e.g., it is sampled from the target distribution), it is accepted.
• The process continues sequentially for subsequent positions in the candidate sequence, but the scoring was done in parallel.
• The verification stops at the first rejected token (early stopping). All subsequent tokens in that candidate sequence are discarded. The final output is the longest prefix of accepted tokens, after which generation continues autoregressively from the target model.

The performance of batch verification is a direct function of the draft model's quality, measured by its acceptance rate. A high acceptance rate means more proposed tokens are validated per batch verification step, leading to a greater speedup factor. Key dependencies include:

• Distribution Alignment: The draft model's output probability distribution must closely approximate the target model's. This is often achieved via draft model distillation.
• Contextual Understanding: The draft must correctly interpret the prompt and generation history to propose plausible continuations.
• Speculative Factor (γ): The number of tokens drafted ahead. A higher γ increases potential speedup but risks lower acceptance rates for later tokens, wasting verification compute. The optimal γ is a hardware-aware parameter balancing compute, memory bandwidth, and draft accuracy.

The net speedup of batch verification is determined by the verification cost relative to the cost of standard autoregressive generation. For a speculative factor γ, the draft model generates γ tokens (low cost). The target model then performs one batched forward pass to verify them. The system achieves a speedup only if: Cost(draft γ tokens) + Cost(verify γ tokens) < γ * Cost(autoregressive step) In practice, because the target model is much larger, the cost of its single verification forward pass is comparable to several of its own autoregressive steps. Therefore, the draft's acceptance rate must be high enough to offset this. The verification cost includes the overhead of managing larger, batched inputs and KV caches. This creates a latency-throughput tradeoff; while latency for a single sequence may decrease, the peak memory usage increases with batch size.

Advanced batch verification schemes move beyond linear candidate sequences. Tree attention mechanisms allow the target model to verify a tree of candidate tokens in parallel. Here, candidates share prefixes, forming branches. This allows verification of multiple divergent futures from a single node, increasing the chance of finding a high-probability path. Speculative beam search integrates batch verification with beam search, where a draft model proposes expansions for multiple beams simultaneously, and the target model verifies this entire batch of beam candidates. These methods increase the computational intensity of the verification step but can lead to higher quality outputs or better acceptance rates by exploring a broader space of possibilities per parallel step.

Speculative decoding is an inference acceleration technique that uses a small, fast draft model to propose a sequence of future tokens. A larger, more accurate target model then verifies these proposals in a single, parallel forward pass. This process amortizes the target model's high computational cost over multiple tokens, achieving a net speedup when most proposals are accepted. It is a fundamental method for reducing latency in large language model inference.

A draft model is a smaller, faster language model used in speculative decoding to generate a candidate sequence of tokens. Its primary objective is to predict the next γ (speculative factor) tokens that the larger target model would likely generate. Draft models are typically 10-100x smaller than the target model and can be:

• A distilled version of the target model.
• A separate, architecturally different model.
• A set of lightweight prediction heads attached to the target model (as in self-speculative decoding). The draft model's accuracy, measured by its acceptance rate, directly determines the efficiency gains of the overall system.

The target model is the primary, high-quality language model whose autoregressive behavior the speculative decoding system aims to preserve and accelerate. It performs the verification forward pass, where it scores all tokens in the draft model's candidate sequence against its own probability distributions in parallel. The target model's parameters are never altered; it acts as an oracle, accepting correct draft tokens and rejecting incorrect ones. The computational cost of this single batched verification must be less than the cost of generating the same number of tokens autoregressively for a net speedup.

Token verification is the deterministic process where the target model validates the draft model's proposed sequence. In a single forward pass, the target model computes probability distributions for each position in the candidate sequence, conditioned on the original context and previously accepted tokens. A draft token is accepted if a random sample from the target model's distribution at that position matches the draft token. If a token is rejected, the system performs a rollback, replaces it with a token sampled from the corrected target distribution, and continues generation autoregressively. This process ensures the output distribution is identical to standard autoregressive sampling from the target model.

The acceptance rate is the critical performance metric for speculative decoding, defined as the percentage of tokens proposed by the draft model that are accepted by the target model. It directly dictates the speedup factor. A high acceptance rate means the target model can verify many tokens per forward pass, efficiently amortizing its computational cost. For example, with a speculative factor (γ) of 5 and a 100% acceptance rate, the system generates 5 tokens for the cost of roughly one target model forward pass. The acceptance rate depends on the draft model's quality and the inherent predictability of the text.

A verification forward pass is the single, batched inference step through the target model that evaluates an entire candidate sequence. Unlike autoregressive decoding, which requires n sequential passes for n tokens, this pass scores all γ candidate tokens in parallel. The target model processes the sequence using a modified attention mask that allows each candidate token to attend only to the original context and preceding candidates. The outputs are logits for each position, which are used for the acceptance/rejection decision. The efficiency of this pass is paramount, as its cost must be less than γ sequential passes for speculative decoding to be beneficial.