Early Stopping

The core mechanism of early stopping is the short-circuit evaluation of the candidate sequence. During the target model's parallel verification pass, it scores each draft token against its own probability distribution. The moment a token's probability falls below the required threshold (typically a comparison to a random sample), the verification process immediately terminates. This avoids the unnecessary forward computation for all subsequent tokens in that candidate sequence, directly converting a token rejection into a computational saving.

When early stopping triggers a rejection, the system must rollback the generation state. This involves:

• Discarding all unverified tokens in the current candidate sequence.
• Appending the single, corrected token sampled from the target model's distribution at the rejection point.
• Resuming standard autoregressive generation from this new position. This rollback is efficient because the Key-Value (KV) cache for the target model is only updated through the last accepted token, preserving the correct context for the next generation step.

Early stopping directly enhances the speedup factor of speculative decoding. The theoretical maximum speedup is limited by the acceptance rate and the cost of drafting. By eliminating verification work on rejected tails of sequences, early stopping improves the effective verification cost. The speedup is modeled as Speedup ≈ (Acceptance Rate * Speculative Factor + 1) / (Acceptance Rate * Draft Cost + Verification Cost), where early stopping minimizes the realized verification cost, pushing the actual speedup closer to the theoretical limit.

Early stopping is often contrasted with full-sequence verification, a simpler but less efficient alternative.

• Full-Sequence Verification: The target model verifies all k tokens in the candidate sequence, regardless of early rejections. This wastes FLOPs on tokens that will be discarded.
• Early Stopping: Verification halts at the first rejection r (where r ≤ k). This saves computation proportional to k - r tokens. The performance delta between the two strategies grows with longer speculative factors (k) and in contexts where the draft model's confidence varies, making early stopping essential for optimal throughput.

In advanced speculative decoding frameworks that use tree attention to verify multiple candidate branches, early stopping becomes a per-branch operation. The verification process traverses a tree of candidate tokens. If a token on a given branch is rejected, that entire branch is pruned, and computation is reallocated to other, more promising branches. This allows for dynamic resource allocation during a single verification forward pass, maximizing the utility of each compute operation and exploring a wider space of potential continuations without linear cost increases.

Early stopping improves hardware utilization by reducing memory bandwidth pressure. A full-sequence verification requires loading the KV cache and performing attention computations for all k tokens. An early stop after r tokens reduces the amount of data read from GPU memory and the number of floating-point operations executed. This is particularly beneficial on hardware where memory bandwidth is a bottleneck, as it directly translates to lower latency and higher effective throughput for the same hardware footprint.

Speculative decoding is the overarching inference acceleration technique where a smaller, faster draft model proposes a sequence of future tokens. A larger, more accurate target model then verifies these tokens in a single, parallel forward pass. The core innovation is trading a small, cheap draft computation for a large reduction in the number of slow, sequential target model steps. The theoretical speedup is bounded by the acceptance rate of the draft tokens.

A draft model is a small, fast language model used to propose candidate tokens ahead of the target model. Its sole purpose is to generate plausible continuations cheaply. Key characteristics include:

• Low Latency: Often 3-10x faster per token than the target model.
• Architectural Simplicity: May be a distilled version of the target or a separate, shallower network.
• High Recall: Optimized to maximize the chance its proposed tokens match the target's distribution, as measured by the acceptance rate.

The target model is the primary, high-quality model whose output distribution the system aims to preserve. In speculative decoding, it shifts from an autoregressive generator to a parallel verifier. Its role is to:

• Perform a verification forward pass on the batch of candidate tokens.
• Compare its own probability distribution for each position against the draft token.
• Accept tokens where its probability is higher, or reject and sample from its corrected distribution.
• The computational verification cost of this batched pass must be less than generating the same number of tokens autoregressively.

Token verification is the deterministic process where the target model validates draft tokens. For a candidate sequence of length k, the target model runs one forward pass to compute probabilities for all k positions in parallel. The verification algorithm:

• Checks if the target model's probability for the draft token at position i is greater than or equal to a random threshold.
• If true, the token is accepted.
• If false, the token is rejected, the correct token is sampled from the target's distribution, and the early stopping mechanism halts verification for the rest of the sequence. This batched scoring is the source of the latency reduction.

The acceptance rate is the most critical metric determining the efficacy of speculative decoding. It is the percentage of draft-proposed tokens that are accepted by the target model during verification. The speedup factor is approximately 1 / (1 - acceptance_rate). For example:

• A 70% acceptance rate yields a ~3.3x potential speedup.
• A 50% acceptance rate yields a ~2x speedup.
• A 30% acceptance rate yields only a ~1.4x speedup. The rate depends on the draft model's quality and the speculative factor (how many tokens are drafted).

The rollback mechanism is the corrective action taken when the target model rejects a draft token. Upon rejection:

1. Early stopping is triggered, halting verification of subsequent tokens in the candidate sequence.
2. Generation rolls back to the position of the first rejected token.
3. The target model's sampled token for that position becomes the new, verified output.
4. Generation continues autoregressively from this new point, or a new speculative decoding cycle begins. This mechanism ensures the final output distribution is mathematically identical to that of the target model generating alone, preserving quality.