Token Verification

The core mechanism of token verification is a single, batched forward pass through the target model. Instead of generating tokens one-by-one (autoregressively), the model processes the entire candidate sequence simultaneously. This is achieved by arranging the draft tokens in a batch dimension, allowing the model's attention mechanism to compute logits for all positions in parallel. The computational cost of this verification pass must be less than the cost of generating the same number of tokens autoregressively for a net speedup.

Verification determines which draft tokens to accept or reject. The standard algorithm compares probabilities:

• For each position i, the target model computes the probability of the draft token.
• A draft token at position i is accepted if a random sample is less than min(1, p_target(x_i) / p_draft(x_i)).
• This probabilistic acceptance ensures the final output distribution matches the target model's autoregressive distribution, a property known as distribution preservation. The first rejected token triggers a rollback, and generation continues autoregressively from the target model's corrected token.

The efficiency of token verification hinges on its verification cost. The target model's forward pass for k draft tokens is nearly constant time, similar to processing a single token, due to parallelization. The speedup factor is determined by the acceptance rate (α) and the speculative factor (γ). The theoretical maximum speedup is approximately 1 / ( (1 - α^γ) / (γ * (1 - α)) ). For example, with an 80% acceptance rate and a draft length of 5, a 2-3x speedup is typical. The verification cost must be less than the time saved by avoiding γ autoregressive steps.

Efficient Key-Value (KV) cache usage is essential for fast verification. During the draft phase, KV states for the candidate sequence are computed and stored. The verification forward pass reuses these speculative KV cache entries. Upon token acceptance, these cached states become the new base for subsequent generation. Upon rejection, the cache is rolled back to the state before the first rejected token. Optimal management minimizes memory I/O and is a key component of the overall latency reduction.

Advanced verification schemes extend beyond linear sequences to tree attention. Here, the draft model proposes a tree of multiple candidate branches from a single prefix. The target model verifies all branches in a single pass using a modified attention mask that respects the tree structure. This increases the chance of finding a high-probability continuation, improving the acceptance rate for a given computational budget. Systems like Medusa implement this via multiple parallel prediction heads (Medusa heads) on the target model itself.

In production, token verification is integrated into model serving architectures to maximize system throughput. Techniques include:

• Continuous batching: Dynamically grouping verification requests from multiple users.
• Batch verification: Processing candidate sequences from multiple independent requests or beams in one forward pass.
• Hardware-aware speculation: Tuning the speculative factor (γ) based on GPU memory bandwidth and parallel compute characteristics. This ensures the verification pass fully utilizes available hardware without causing memory bottlenecks.

A draft model is a smaller, faster language model used in speculative decoding to generate a sequence of candidate tokens. Its sole purpose is to propose likely continuations that the larger target model can verify in parallel. An effective draft model is typically 10-100x faster than the target model but has a lower accuracy, making the acceptance rate the critical metric for overall speedup. Common choices include:

• Distilled versions of the target model.
• Smaller, architecturally similar models (e.g., using a 7B parameter model to draft for a 70B parameter model).
• N-gram or lookup-based models in lookahead decoding variants.

The target model is the primary, accurate language model in speculative decoding that performs the verification step. It is the model whose output distribution the system aims to preserve exactly. During verification, it runs a single, batched forward pass to score the entire candidate sequence proposed by the draft model. The target model's parameters and computational graph remain unchanged; speculative decoding is a wrapper around its standard inference. The technique's success depends on the verification cost of this batched pass being less than the cost of generating the same number of tokens autoregressively.

A verification forward pass is the single, parallelized inference step where the target model evaluates a candidate sequence. Instead of generating one token at a time, the model processes the entire sequence in one batch. The core technical mechanism is parallel decoding, where the model computes logits for each position in the candidate sequence simultaneously. This is enabled by:

• Teacher-forcing: The candidate sequence is provided as input.
• Causal masking adjustment: The attention mask is modified to allow each position to attend only to previously verified tokens and the candidate prefix. The output is a probability distribution at each position, which is compared to the draft token to determine acceptance.

Acceptance rate is the percentage of tokens proposed by the draft model that are accepted by the target model. It is the primary determinant of the speedup factor in speculative decoding. Mathematically, if the draft generates γ tokens and k are accepted, the acceptance rate is k/γ. A high acceptance rate means most draft tokens are correct, minimizing the costly rollback and autoregressive correction steps. The theoretical maximum speedup is approximately γ / (1 - acceptance_rate). In practice, acceptance rates of 70-85% are common for well-tuned draft/target pairs, leading to 2-3x latency reductions.

A candidate sequence is the ordered list of γ (the speculative factor) tokens generated by the draft model for verification. This sequence is constructed autoregressively by the draft model, starting from the current context. During the verification forward pass, this sequence is fed into the target model in parallel. The target model scores each position independently. The system then performs token-level acceptance, comparing the target model's predicted probability for the draft token against a random sample. The longest contiguous prefix where all tokens are accepted becomes the final output before a potential rollback.

The rollback mechanism is the corrective process triggered when the target model rejects a token in the candidate sequence. Upon rejection, the system:

1. Discards all tokens in the candidate sequence after the first rejected token.
2. Accepts the contiguous prefix of correct tokens up to the point of rejection.
3. Appends the correct token sampled from the target model's distribution at the rejection position.
4. Continues generation autoregressively from the target model from this new context, or initiates a new speculative cycle. This mechanism guarantees that the output distribution is identical to that of the target model generating purely autoregressively, preserving accuracy.