Parallel Decoding

The target model processes an entire candidate sequence (e.g., 3-5 tokens) in a single, batched forward pass. This contrasts with standard autoregressive decoding, which requires sequential passes. The verification is performed by comparing the target model's probability distribution for each position against the draft token.

• Key Operation: The target model's forward pass receives the concatenated context and the candidate sequence.
• Efficiency Gain: The computational cost of this single batched pass is typically less than the cost of multiple sequential passes to generate the same number of tokens.

Each token in the candidate sequence is accepted or rejected independently based on a probabilistic sampling rule. The standard algorithm compares the target model's probability for the draft token against a random threshold.

• Acceptance Rule: A draft token is accepted if a random sample u ~ Uniform(0,1) is less than or equal to min(1, p_target / p_draft), where p_target is the target model's probability for that token.
• Early Stopping: Verification halts at the first rejected token. All subsequent tokens in that candidate sequence are discarded, as the sequence is no longer plausible.
• Result: This produces a block of accepted tokens, which can be 0 to gamma (the speculative factor) tokens long.

When a token is rejected, the system rolls back to the last accepted position. The target model then samples a corrected token from its adjusted probability distribution at that position.

• Rollback Mechanism: Generation reverts to the context right before the first rejected token.
• Resampling Distribution: The corrected token is sampled from the distribution max(0, p_target - p_draft), renormalized. This ensures the final output distribution is mathematically identical to the target model's autoregressive distribution.
• Process Continuation: After resampling the corrected token, the system continues, either with a new speculative drafting step or via standard autoregressive generation.

To maximize efficiency, the key-value (KV) cache computed during the draft model's forward pass is often reused during the target model's parallel verification.

• Cache Sharing: The KV states for the shared context (tokens before the candidate sequence) are identical between draft and target models and can be shared or recomputed.
• Memory Optimization: For the candidate sequence itself, the target model computes its own KV states. Efficient implementations manage this speculative KV cache to avoid redundant memory allocation and enable fast rollback.
• Hardware Impact: This cache management is critical for minimizing memory bandwidth pressure, which is often the bottleneck for the speedup.

A foundational guarantee of parallel decoding in speculative decoding is that the final output distribution is identical to that of the target model generating autoregressively.

• Mathematical Equivalence: The acceptance and resampling rules are designed to be a provably correct implementation of the target model's next-token distribution.
• No Distribution Shift: Unlike simple distillation or approximation methods, speculative decoding with parallel verification does not alter the model's fundamental statistical behavior. It is a latency optimization, not an accuracy compromise.
• Verification: This property allows the technique to be used in production systems where output quality must be strictly maintained.

The effectiveness of parallel decoding is tightly coupled with the underlying hardware's capabilities, particularly GPU parallelism and memory hierarchy.

• Parallel Compute Utilization: The batched verification pass efficiently saturates the parallel processing units (GPU SMs/TPUs) that would be underutilized by sequential token generation.
• Memory Bandwidth Bound: The primary bottleneck often shifts from compute to memory bandwidth, as loading model weights and the KV cache for the batch can dominate runtime.
• Parameter Tuning: The optimal speculative factor (gamma) is hardware-dependent, balancing the parallelism benefit against the increased memory and compute of longer candidate sequences.

Speculative decoding is the overarching inference optimization technique. A smaller, faster draft model proposes a sequence of future tokens. A larger target model then verifies these candidates in a single, parallel forward pass, accepting correct tokens and rejecting incorrect ones. This bypasses many slow, sequential autoregressive steps of the target model alone.

• Core Mechanism: Relies on the observation that verifying multiple tokens in parallel is cheaper than generating them sequentially.
• Key Requirement: The draft model must be significantly faster than the target model for a net speedup.

A draft model is a small, fast language model used to generate candidate token sequences for the target model to verify. Its sole purpose is speed; accuracy is secondary but impacts the acceptance rate.

• Characteristics: Often 10x-100x smaller and faster than the target model (e.g., a 125M parameter model drafting for a 70B parameter model).
• Training: Can be a general small model or distilled from the target model to better mimic its output distributions.
• Alternatives: In lookahead decoding, a static n-gram table or the target model's own intermediate states can act as the 'draft'.

The target model is the primary, accurate model whose autoregressive behavior is being accelerated. It performs the parallel verification pass, scoring all tokens in the candidate sequence against its own predictions in one batch.

• Role: Acts as the quality gatekeeper. It accepts a draft token if its own predicted probability for that token is higher than the draft model's probability.
• Computational Cost: The cost of its single, batched verification pass must be less than the cost of generating the same number of tokens autoregressively for a net speedup.

Token verification is the critical parallel scoring step. The target model processes the entire candidate sequence in one verification forward pass, producing probability distributions for each position.

• Process: For each position i, the target model checks if its probability for the draft token t_i is greater than the draft model's probability for t_i. If true, the token is accepted.
• Parallelism: Enabled by tree attention or simple batch processing of the candidate sequence.
• Early Stopping: Verification halts at the first rejected token; subsequent draft tokens are discarded.

The acceptance rate is the percentage of draft tokens accepted by the target model. It is the primary determinant of the speedup factor.

• Calculation: (Number of Accepted Tokens) / (Total Draft Tokens Proposed).
• Impact: A low acceptance rate leads to frequent rollbacks, wasting the verification cost. A high rate (e.g., >80%) enables near-ideal speedups.
• Optimization: Improved via draft model distillation, confidence thresholding, or dynamic draft selection.

Lookahead decoding is a variant of speculative decoding that eliminates the separate draft model. Instead, it uses the target model's own context to draft candidates.

• N-Gram Drafting: Uses a static table of frequent token sequences from the training data to propose continuations.
• Self-Speculation: Techniques like Medusa heads add parallel prediction heads to the target model, allowing it to draft multiple future tokens in its own forward pass.
• Advantage: Removes the need to host and manage a separate draft model, simplifying deployment.