N-Gram Drafting

The core mechanism is a pre-computed, static table of n-grams—contiguous sequences of n tokens—extracted from the target model's training corpus. This table acts as a deterministic, memory-based draft model. Common sequences like " of the " (a 3-gram) are stored and retrieved via a prefix match against the recent context. This eliminates the computational cost of running a separate neural draft model for token generation.

Candidate sequences are generated via a simple prefix lookup. Given the last k tokens of the current output as context, the system queries the n-gram table for all sequences that begin with that prefix. For example, with context " thank you " and a table of 4-grams, it might retrieve candidates like " thank you very " and " thank you for ". The longest matching n-gram is typically selected to maximize the lookahead potential.

This method trades off compute for memory and simplicity.

• Low Compute: Drafting is a hash table lookup, far cheaper than a neural forward pass.
• High Memory: The table size grows exponentially with n, requiring significant RAM/VRAM. Practical implementations use efficient data structures like tries or finite-state transducers and often limit n to 3-5.
• No Trainable Parameters: Unlike a draft model, the table is not fine-tuned, making it robust but potentially less contextually adaptive.

Because it relies on a fixed corpus table, n-gram drafting is deterministic. The same context will always produce the same draft sequence. This leads to predictable, consistent verification costs. However, it cannot adapt to novel phrasing or domain-specific jargon not present in the original training corpus, which can limit acceptance rates in diverse text generation tasks.

The retrieved n-gram is treated as a candidate sequence. The full sequence is submitted to the target model for a parallel verification forward pass. The target model scores all candidate tokens simultaneously against its own predictions. This process is identical to standard speculative decoding, providing a speedup factor if the verification cost is less than autoregressively generating the same number of tokens.

Ideal for:

• Repetitive, formulaic text generation (e.g., code completion, boilerplate text).
• Environments with extreme CPU constraints where even a tiny neural draft model is prohibitive.
• Key Limitations:
• Limited Novelty: Fails on creative or out-of-distribution text.
• Corpus Dependency: Effectiveness is tied to the representativeness of the source corpus.
• Context Window: Only considers the immediate prefix, lacking the broader semantic understanding of a neural draft model.

The overarching inference optimization technique where a smaller, faster draft model proposes a sequence of candidate tokens, which are then verified in parallel by a larger, more accurate target model. The core idea is to replace many slow, sequential autoregressive steps from the target model with fewer, batched verification steps.

• Key Mechanism: Parallel verification of a candidate sequence.
• Goal: Achieve a net speedup factor where the time saved by drafting outweighs the verification cost.

A smaller, faster language model used to generate candidate token sequences in speculative decoding. Its sole purpose is to make cheap, educated guesses about the target model's likely next tokens.

• Characteristics: Has significantly lower latency and computational cost than the target model.
• Training: Often distilled from the target model to improve acceptance rate.
• Contrast with N-gram Drafting: Instead of a neural model, n-gram drafting uses a static frequency table.

The primary, larger, and more capable language model whose output distribution the system aims to preserve. It performs the verification forward pass, scoring all tokens in the candidate sequence in parallel.

• Role: Acts as the arbiter of correctness, accepting or rejecting draft tokens.
• Constraint: Its forward pass for verifying k tokens must be faster than generating those k tokens autoregressively for a net speedup.

The critical process where the target model checks the draft tokens. In a single, batched forward pass, the model computes probability distributions for each position in the candidate sequence.

• Algorithm: For each position i, if the draft token matches the target model's predicted token, it is accepted. The first mismatch triggers a rollback.
• Efficiency Gain: Verifying 5 tokens in one pass is far cheaper than 5 separate autoregressive steps.

The percentage of tokens proposed by the draft mechanism that are accepted by the target model. This is the primary determinant of the practical speedup factor.

• Direct Impact: A low acceptance rate leads to frequent rollbacks, wasting verification compute. A high rate maximizes the benefit of parallel decoding.
• N-gram Consideration: Static n-gram tables often have lower acceptance rates than neural draft models, especially for creative or domain-specific text, but require zero draft model inference.

A family of speculative decoding methods that generate candidate tokens using the target model's own internal states or fixed statistics, eliminating the need for a separate draft model. N-gram drafting is a prime example of lookahead decoding.

• Other Variants: Include techniques like Medusa heads (self-speculative decoding) which add lightweight prediction heads to the target model.
• Advantage: Removes the overhead of loading and running a separate draft model, simplifying deployment.