Speculative Decoding — Acceptance, Residual Sampling and Cost

Manufacture known tokens, then verify their conditionals

Autoregressive sampling is sequential because the next sampled token is not known until the current decision finishes. Once a candidate continuation exists, a causal transformer can evaluate its prefix-conditioned distributions in one parallel forward pass, just as teacher-forced training evaluates known sequences. A cheap proposal mechanism can therefore supply several candidate tokens for one target verification pass.

Leviathan, Kalman and Matias v2 and Chen et al. v1 describe distribution-preserving speculative sampling. Their reported speedups belong to their model/hardware/baseline experiments; one target pass is not necessarily the cost of one ordinary token, and extra drafting can make generation slower. A poor draft need not change the ideal target distribution, but implementation errors, changed samplers or approximate verification can.

Prerequisites are conditional probabilities/sampling, causal attention and KV-cache state. You will prove the residual identity, implement greedy and stochastic multi-token decoding, derive a cost model, compare proposal families and retain a versioned runtime procedure. The CPU tests use tiny synthetic categorical models. No pretrained model, target-specific draft head, GPU serving run or speed benchmark is downloaded/executed.

The four-step loop and the first-rejection rule

1. Draft: sample up to k tokens autoregressively from q, saving the full proposal distribution at every candidate prefix.
2. Verify: pass the known continuation to the target and obtain p at each candidate prefix plus the final bonus-token distribution.
3. Accept/repair in order: accept proposed token j with min(1,p_j/q_j). At the first rejection sample from the normalized positive residual max(p−q,0) and discard the rest of that draft suffix.
4. Emit a bonus if all accepted: sample one token from the final target conditional, subject to EOS and the remaining output budget.

The suffix after a rejection was conditioned on a token that was not emitted. Its probabilities/caches answer the wrong question and cannot be reused as if still valid. Parallel target evaluation does not make the decisions independent of the accepted prefix.

Proof: accepted mass plus residual mass equals the target

For a vocabulary token j, accepted mass is q_j*min(1,p_j/q_j)=min(p_j,q_j) for q_j positive. Tokens with q_j=0 cannot be proposed, but can still be emitted through repair. Total rejection mass is

If r is positive, the repair distribution is max(p−q,0)/r. The total emitted probability for j is

If r=0, p=q and rejection has zero theoretical probability; never divide a zero residual by zero. Apply the one-step identity at each actual emitted prefix to get the autoregressive target distribution. This is a direct coupling/rejection identity, not a Markov-chain convergence argument.

For p=[.1,.3,.6], q=[.4,.4,.2], accepted mass is [.1,.3,.2] and rejection mass .4 goes entirely to token three, yielding p. Repairing by sampling p again would yield [.14,.42,.44], which is wrong. The acceptance probability is sum min(p,q)=1−TV(p,q). Vocabulary overlap alone does not predict it: identical token sets can support very different probabilities.

Temperature/top-k/top-p and other transforms define the p/q actually used. Record the proposal distribution after its sampling transforms, and verify against the intended target sampler after its transforms. Matching raw logits but sampling from filtered q violates the contract. Exact distribution equality is a mathematical statement; finite precision can perturb it. A fixed random seed need not yield the same stochastic output string as ordinary decoding because random draws are consumed differently.

Expected tokens and the actual speed equation

Assuming a constant independent acceptance probability alpha at successive positions, expected emitted tokens per iteration, including repair/bonus, are

At alpha=1 the limit is k+1. At alpha=.7,k=5, E=2.94117, not 3.03. At alpha=.8,k=6, E=3.951424. Without the simplifying assumption, use the probabilities of surviving each accepted prefix: 1 + sum_i P(first i proposals accepted), not one plus a sum of unrelated marginal acceptance rates.

Let T be ordinary target time/token, cT one draft step, and v(k)T target block-verification time including relevant overhead. Idealized speedup is E/(k*c+v(k)). With alpha=.8,k=6,c=.1,v=1, it is about 2.47, not 3.95. With alpha=.1 and the same costs it is about .69: slower despite at least one emitted token per pass. Increasing k eventually costs more than the marginal accepted-prefix gain. Measure latency, throughput and memory at the actual batch/context rather than using a universal acceptance=.5 or batch=8 cutoff.

Complete greedy and sampled CPU reference

The following PyTorch 2.9.0 CPU reference accepts causal models exposing .logits of shape (1,time,vocab). It fully recomputes prefixes for clarity; it is not an optimized cache implementation or speed benchmark. Temperature zero is the separate greedy path. It enforces an output budget, truncates at EOS, validates distributions and rejects unsupported k/temperature values. The tested tiny model below has no downloaded weights.

import math
import torch
from types import SimpleNamespace
 
@torch.no_grad()
def next_distribution(logits, temperature):
    if not math.isfinite(temperature) or temperature <= 0 or not bool(torch.isfinite(logits).all()):
        raise ValueError("finite logits and positive sampling temperature required")
    scaled = logits.double()/temperature
    if not bool(torch.isfinite(scaled).all()):
        raise ValueError("temperature scaling overflow")
    return torch.softmax(scaled, dim=-1)
 
@torch.no_grad()
def speculative_generate(target, draft_model, prompt, max_new=12, k=3,
                         temperature=1., eos_id=None, seed=0):
    if prompt.ndim != 2 or prompt.shape[0] != 1 or prompt.shape[1] == 0:
        raise ValueError("one nonempty prompt required")
    if type(k) is not int or type(max_new) is not int or k < 1 or max_new < 0:
        raise ValueError("integer k >= 1 and max_new >= 0 required")
    if prompt.device.type != "cpu" or not math.isfinite(temperature) or temperature < 0:
        raise ValueError("CPU reference requires finite nonnegative temperature")
    if prompt.dtype != torch.long or bool((prompt < 0).any()):
        raise ValueError("nonnegative int64 token IDs required")
    if eos_id is not None and (type(eos_id) is not int or eos_id < 0):
        raise ValueError("nonnegative integer EOS ID required")
    generator = torch.Generator().manual_seed(seed)
    ids = prompt.clone()
    emitted = 0
    while emitted < max_new:
        prefix_len = ids.shape[1]
        candidate, qs = [], []
        ctx = ids
        for _ in range(min(k, max_new-emitted)):
            logits = draft_model(ctx).logits[0, -1]
            if logits.ndim != 1 or logits.numel() == 0 or not bool(torch.isfinite(logits).all()):
                raise ValueError("finite nonempty draft vocabulary required")
            if temperature == 0:
                token = int(logits.argmax())
            else:
                q = next_distribution(logits, temperature)
                token = int(torch.multinomial(q, 1, generator=generator))
                qs.append(q)
            candidate.append(token)
            ctx = torch.cat([ctx, torch.tensor([[token]], dtype=ids.dtype)], dim=1)
            if token == eos_id:
                break
        block_logits = target(ctx).logits[0, prefix_len-1:]
        if block_logits.ndim != 2 or block_logits.shape[1] != logits.numel():
            raise ValueError("shared vocabulary shape required, including greedy mode")
        if not bool(torch.isfinite(block_logits).all()):
            raise ValueError("finite target logits required")
        if block_logits.shape[0] != len(candidate)+1:
            raise ValueError("causal target must provide candidate and bonus conditionals")
        accepted_all = True
        new_tokens = []
        for i, proposed in enumerate(candidate):
            if temperature == 0:
                token = int(block_logits[i].argmax())
                accepted = token == proposed
            else:
                p = next_distribution(block_logits[i], temperature)
                q = qs[i]
                if p.shape != q.shape:
                    raise ValueError("shared vocabulary contract required")
                accepted = float(torch.rand((), generator=generator)) < min(1., float(p[proposed]/q[proposed]))
                if accepted:
                    token = proposed
                else:
                    residual = (p-q).clamp_min(0)
                    if float(residual.sum()) <= 0:
                        raise ArithmeticError("numerically inconsistent zero-residual rejection")
                    token = int(torch.multinomial(residual/residual.sum(), 1, generator=generator))
            new_tokens.append(token)
            if not accepted or token == eos_id:
                accepted_all = False
                break
        if accepted_all and len(new_tokens) < max_new-emitted:
            if temperature == 0:
                bonus = int(block_logits[len(candidate)].argmax())
            else:
                p = next_distribution(block_logits[len(candidate)], temperature)
                bonus = int(torch.multinomial(p, 1, generator=generator))
            new_tokens.append(bonus)
        for token in new_tokens:
            ids = torch.cat([ids, torch.tensor([[token]], dtype=ids.dtype)], dim=1)
            emitted += 1
            if token == eos_id or emitted == max_new:
                return ids
    return ids
 
class TinyMarkov:
    def __init__(self, probabilities):
        self.table = torch.tensor(probabilities, dtype=torch.float64).log()
    def __call__(self, input_ids):
        return SimpleNamespace(logits=self.table[input_ids])
 
target = TinyMarkov([[.1,.3,.6], [.6,.3,.1], [.2,.7,.1]])
draft_model = TinyMarkov([[.4,.4,.2], [.2,.5,.3], [.4,.4,.2]])
example = speculative_generate(target, draft_model, torch.tensor([[0]]), max_new=7, k=3)
assert example.shape == (1, 8)
print("bounded speculative output", example.tolist())

The reference checks vocabulary shape, but production compatibility requires more: identical token-to-string mapping, normalization, special-token IDs and template behavior, or a specifically supported cross-tokenizer assisted-decoding algorithm. Equal vocabulary size alone is insufficient. The finite-logit helper rejects exact zero probabilities represented by negative infinity; the separate probability-space oracle below covers zero-support cases directly. This explicit domain boundary is preferable to silently claiming an untested edge.

NumPy repair sampler and exact oracle

This solves the original from-scratch rejection-sampling exercise and handles identical/disjoint support. It uses normalized finite probability vectors directly, not model logits. The returned mass identity can be compared with an independent rational calculation; sampling frequencies alone are weaker.

import numpy as np
 
def repair_sample(p, q, rng):
    p, q = np.asarray(p, dtype=float), np.asarray(q, dtype=float)
    if p.ndim != 1 or p.size == 0 or p.shape != q.shape or not np.isfinite(p).all() or not np.isfinite(q).all():
        raise ValueError("finite matching probability vectors required")
    if min(p.min(), q.min()) < 0 or abs(p.sum()-1.) > 1e-12 or abs(q.sum()-1.) > 1e-12:
        raise ValueError("normalized nonnegative probabilities required")
    proposed = rng.choice(len(q), p=q)
    if rng.random() < min(1., p[proposed]/q[proposed]):
        return proposed
    residual = np.maximum(p-q, 0)
    if residual.sum() <= 0:
        raise ArithmeticError("impossible zero-residual rejection")
    return rng.choice(len(p), p=residual/residual.sum())
 
p, q = np.array([.1,.3,.6]), np.array([.4,.4,.2])
accepted = np.minimum(p, q)
residual = np.maximum(p-q, 0)
np.testing.assert_allclose(accepted + residual, p)
assert abs(accepted.sum()+residual.sum()-1) < 1e-12
rng = np.random.default_rng(23)
assert repair_sample([0.,1.], [1.,0.], rng) == 1
assert repair_sample([1.,0.], [1.,0.], rng) == 0

The probability-space contract is nonempty, finite, nonnegative vectors with sums within 1e-12 of one. The sampler does not silently clip or renormalize malformed inputs. The following independent exact rational oracle checks every three-category distribution on the quarter grid, including zero support and identical distributions. It proves the finite fixture identity, not a vendor binary's implementation or floating-point equivalence at arbitrary logits.

from fractions import Fraction
simplex = [[Fraction(a,4), Fraction(b,4), Fraction(4-a-b,4)]
           for a in range(5) for b in range(5-a)]
for p_exact in simplex:
    for q_exact in simplex:
        accepted = [min(pj,qj) for pj,qj in zip(p_exact,q_exact)]
        residual = [max(pj-qj,0) for pj,qj in zip(p_exact,q_exact)]
        rejected = 1-sum(accepted)
        assert sum(residual) == rejected
        # The r=0 branch must not evaluate residual/r.
        emitted = [a + (rejected*r/rejected if rejected else 0)
                   for a,r in zip(accepted,residual)]
        assert emitted == p_exact
p_exact = [Fraction(1,10), Fraction(3,10), Fraction(6,10)]
q_exact = [Fraction(4,10), Fraction(4,10), Fraction(2,10)]
rejected = 1-sum(map(min,p_exact,q_exact))
wrong = [min(pj,qj)+rejected*pj for pj,qj in zip(p_exact,q_exact)]
assert wrong == [Fraction(14,100), Fraction(42,100), Fraction(44,100)]
assert wrong != p_exact  # Negative control: resampling p is biased.

Cache, EOS and rollback are correctness requirements

An optimized target already has a prefix cache and evaluates only the newly required positions. After the first rejection, crop/invalidate target and draft state conditioned on rejected tokens; update positions and attention masks consistently. Depending on implementation, the newest emitted repair/bonus token may not yet be processed into cache. Track processed prefix length plus pending token explicitly, rather than assuming cache length always equals all emitted tokens. The next forward must start from the same logical prefix as a full recomputation.

EOS terminates the emitted sequence immediately; a candidate suffix after EOS must not leak into output. Cap to the requested output budget even when all k candidates plus a bonus would exceed it. Reset per-request counters/cache and sampling state. A recurrent-state or paged-cache implementation may need different rollback bookkeeping, but it must preserve the same prefix contract. Test first/middle/last rejection, all accepted, zero new tokens, k larger than remaining budget, EOS in accepted or repaired output and multiple successive rounds.

Greedy verification accepts a candidate exactly when it equals target argmax and otherwise emits target argmax. It can reproduce the same greedy tokens under matching ties/numerics. Stochastic verification uses probabilities and residual repair; greedy token equality is not proof of sampled distribution equivalence.

Where proposals come from

Small model, distillation and prompt lookup

A smaller compatible model adds weights, its own cache and serial draft latency. Same family does not guarantee high distribution overlap on your domain. A distilled/domain-adapted draft can increase acceptance at a training/data cost, but a larger “better” draft can be too slow. Compare accepted-prefix length per unit total time, not just accuracy or parameter ratio.

Prompt lookup uses a suffix of current context to find an earlier occurrence, proposing tokens that followed it. It adds no neural draft weights, but search/candidate storage are not literally zero cost. A deterministic candidate can be understood as a point-mass proposal in a probability-space verifier. Copy-heavy edits/quotes may suit it; novel output can have low acceptance. Here is the complete bounded proposal exercise:

# CPU-only longest-suffix lookup, choosing the most recent valid earlier match.
def prompt_lookup(tokens, k=4, max_ngram=8):
    if type(k) is not int or type(max_ngram) is not int or k < 1 or max_ngram < 1:
        raise ValueError("positive search limits required")
    for n in range(min(max_ngram, len(tokens)-1), 0, -1):
        suffix = tokens[-n:]
        for start in range(len(tokens)-n-1, -1, -1):
            end = start+n
            if tokens[start:end] == suffix and end < len(tokens):
                return tokens[end:min(end+k, len(tokens))]
    return []
 
assert prompt_lookup([1,2,3,4,1,2], k=2) == [3,4]
assert prompt_lookup([1,2,3], k=2) == []

To compare code versus chat, apply this on already approved held-out traffic, count proposed tokens and verified accepted-prefix lengths, and include lookup/verification time. No numeric acceptance gap is claimed without that workload.

Medusa versus EAGLE generations

Medusa v1 (2024) adds multiple future-token heads and verifies a candidate tree. Medusa-1 freezes the target backbone during head training; Medusa-2 jointly fine-tunes the backbone, so the target function itself can change. The paper also discusses typical acceptance, which is not automatically the exact residual sampler above. Extra heads do have parameters/memory; “no separate model” is not “no additional weights.” Tree attention must mask each node to its own ancestor path rather than unrelated branches.

EAGLE v1 drafts autoregressively in a feature representation and incorporates next-step token information to address sampling uncertainty. EAGLE-2 v1 uses context-aware dynamic draft trees: confidence-guided branch expansion rather than a fixed shape. EAGLE-3 v1 abandons the earlier feature-prediction constraint in favor of direct token prediction, fuses multiple target-layer features and uses training-time test. Calling every generation “predict the final feature then apply the frozen head” loses that distinction.

Choose a compatible trained speculator only after verifying checkpoint identity, runtime support, output-distribution mode, added memory and measured latency at target concurrency. No paper establishes that EAGLE-3 is the universal/default deployment choice, that heads always cost eight H100-hours to train, or that a third-party speed table applies to every workload.

SpecInfer v1 organizes candidate sequences into token trees and verifies them in parallel. Lookahead Decoding v1 offers an exact parallel decoding approach without a separate auxiliary model, trading additional work for fewer sequential steps. These are relevant extensions to the verification/parallelism idea, not synonyms for a vanilla draft-target implementation or a guarantee of a particular speed multiplier.

Runtime reference: versioned APIs and a real comparison procedure

Transformers 4.45.2 generation strategies document assistant_model and prompt_lookup_num_tokens. GenerationConfig in the same tag documents assistant token controls. The following is unexecuted GPU reference code, reading only two approved local compatible checkpoints. It uses the target's verified tokenizer contract and a batch of one.

# Reference only: Transformers 4.45.2 plus a separately locked CUDA/PyTorch environment.
import os
import time
import torch
from transformers import AutoModelForCausalLM, AutoTokenizer
 
target_path, draft_path = os.environ["LOCAL_TARGET"], os.environ["LOCAL_DRAFT"]
tok = AutoTokenizer.from_pretrained(target_path, local_files_only=True, trust_remote_code=False)
draft_tok = AutoTokenizer.from_pretrained(draft_path, local_files_only=True, trust_remote_code=False)
if tok.get_vocab() != draft_tok.get_vocab() or tok.special_tokens_map != draft_tok.special_tokens_map:
    raise ValueError("token identity mismatch; equal vocabulary size is insufficient")
# Also record and compare tokenizer backend/normalizer and chat-template hashes externally.
target = AutoModelForCausalLM.from_pretrained(target_path, local_files_only=True,
    trust_remote_code=False, torch_dtype=torch.float16).to("cuda:0").eval()
draft = AutoModelForCausalLM.from_pretrained(draft_path, local_files_only=True,
    trust_remote_code=False, torch_dtype=torch.float16).to("cuda:0").eval()
draft.generation_config.num_assistant_tokens = 4
draft.generation_config.num_assistant_tokens_schedule = "constant"
draft.generation_config.assistant_confidence_threshold = 0.
inputs = tok("Explain speculative verification in two sentences.", return_tensors="pt").to("cuda:0")
 
def timed(extra):
    with torch.inference_mode():
        for _ in range(2):
            target.generate(**inputs, max_new_tokens=32, do_sample=False, **extra)
        torch.cuda.synchronize()
        start = time.perf_counter()
        out = target.generate(**inputs, max_new_tokens=32, do_sample=False, **extra)
        torch.cuda.synchronize()
        return out, time.perf_counter()-start
 
ordinary, base_seconds = timed({})
assisted, spec_seconds = timed({"assistant_model": draft})
assert torch.equal(ordinary, assisted)  # greedy check only, not stochastic proof
lookup, lookup_seconds = timed({"prompt_lookup_num_tokens": 4})
assert torch.equal(ordinary, lookup)
print({"base_seconds": base_seconds, "assisted_seconds": spec_seconds,
       "lookup_seconds": lookup_seconds})

One timed run after warmup is a smoke comparison, not a statistically reliable benchmark. A real procedure repeats/interleaves runs, records raw latency distributions and hardware/software identities, measures generated tokens and prompt lengths, and sweeps k, batch/concurrency and domain. Include both-model memory, draft time, verification time and accepted-prefix distribution using supported tracing. past_key_values length alone is not an acceptance counter. Measure prefill separately from decode and keep the sampler unchanged.

For vLLM v0.10.0, the tagged documentation uses a speculative_config dictionary, not the old pair of deprecated separate flags. A complete offline entrypoint is below, also unexecuted; actual backend/model-method support is release-specific. That tag warns that latency improvement is not universal and speculative decoding is not compatible with pipeline parallelism. Do not start a server just to inspect the API.

# Reference only: vLLM 0.10.0; approved local artifacts and compatible GPUs required.
import os
from vllm import LLM, SamplingParams
llm = LLM(model=os.environ["LOCAL_TARGET"], tensor_parallel_size=1,
          speculative_config={"model": os.environ["LOCAL_DRAFT"], "num_speculative_tokens": 4})
outputs = llm.generate(["Explain a cache rollback invariant."],
                       SamplingParams(temperature=0., max_tokens=32))
for result in outputs:
    print(result.outputs[0].text)

A supported runtime name, including TensorRT-LLM, TGI or another backend, is not proof that its chosen version supports every Medusa/EAGLE mode. Inspect its actual model/method support and exact-versus-approximate sampler before benchmarking; this lesson makes no claim of testing those services.

When speculation hurts and how to investigate

If verification work becomes compute-bound at high batching, unused draft/target positions consume real capacity. If domain shift lowers overlap, accepted prefixes shrink. If the draft is slow or takes cache memory away from target concurrency, high acceptance may still lose. If tokenizer identity is wrong, stop for correctness; do not tune speed around mismatched token IDs. If speculative and base sampled strings differ for the same seed, that alone is expected; compare distributions/proof invariants, while deterministic greedy mismatch requires investigation of ties/numerics/state.

Start with prompt lookup for a copy-heavy workload only if its measured overhead is low; use a separate draft where a compatible cheap checkpoint fits; use trained heads/feature-based proposals when the checkpoint and runtime are supported and their lifecycle is worth the work. Turning speculation off is a valid measured choice, not failure to follow a “2025 default.”

Worked recall and transfer answers

1. One sentence? A cheap proposer supplies known candidate tokens so the target can evaluate multiple causal conditionals together, then a correct verifier emits a target-distributed prefix/repair.
2. Why lossless? Accepted mass is min(p,q); rejected mass redistributed as the positive residual fills exactly p−min(p,q). Repeat at each real prefix. This guarantees a distribution under the assumptions, not universally identical seeded strings or free speed.
3. Expected tokens? Alpha=.8,k=6 gives 3.951424 under the independent constant-alpha model; divide by relative draft-plus-verification cost for speedup. Nonconstant cases require accepted-prefix survival probabilities.
4. Medusa versus EAGLE? Multiple future-token heads/tree verification versus EAGLE's feature/token-informed draft family, with dynamic trees in EAGLE-2 and direct-token/multilayer-feature changes in EAGLE-3. Training and acceptance modes determine the exact target-preservation claim.
5. When slower? When total draft+verification cost per emitted token exceeds ordinary target cost: large compute-heavy batches, low acceptance, expensive drafts or memory pressure are plausible causes, not fixed numerical thresholds.
6. Tokenizer test? Equal vocab size is insufficient. Compare token meanings, special IDs, normalizer/template and supported cross-tokenizer machinery if used.
7. Greedy versus sampled implementation? Target argmax match/repair for greedy; probability-ratio acceptance plus positive residual for sampling. The complete CPU decoder and NumPy repair sampler above solve both original coding exercises.
8. Prompt-lookup stretch? Longest suffix [1,2] in [1,2,3,4,1,2] proposes [3,4]. Compare accepted-prefix counts/time on code versus chat without inventing a universal domain gap.

Spaced review: tomorrow prove the three-category identity and compute the overhead-adjusted speed; in a week test rejection/EOS/cache edge cases against full recomputation. Bring back the four-step loop, a compatible tokenizer contract and a measured reason to enable or disable speculation. Continuous batching next changes the compute/memory regime in which that decision is made.

Previous: ← DL S068 · Next: DL S070 →

Original optional resource links

The original optional video/reading destinations are retained here for continuity, not as current API, price, benchmark or publication-date evidence. The versioned primary citations in the teaching above govern the corrected claims. These supplementary destinations were not all fetched or watched; a missing or changed resource does not replace the local derivations, procedures and answers.

• https://www.youtube.com/watch?v=S-8yr_RibJ4
• https://www.youtube.com/watch?v=hm7VEgxhOvk
• https://arxiv.org/abs/2211.17192
• https://huggingface.co/blog/assisted-generation
• https://github.com/apoorvumang/prompt-lookup-decoding
• https://arxiv.org/abs/2406.16858
• https://arxiv.org/abs/2503.01840
• https://arxiv.org/abs/2401.10774
• https://arxiv.org/abs/2401.15077
• https://arxiv.org/abs/2402.02057
• https://arxiv.org/abs/2305.09781