The Draft Is Allowed to Be Wrong

Autoregressive decoding has a serial dependency: token 42 depends on tokens 1 through 41. A target model normally performs one forward step, samples one token, appends it, and repeats.

Speculative decoding asks a clever systems question:

What if a cheaper process proposes the next several tokens, then the target evaluates those proposals in one parallel pass?

If the proposals are good, one expensive target invocation can advance multiple output positions. If they are poor, the system pays for drafting and verification while advancing little. Adding a model can therefore reduce latency, or increase it.

The mechanism is not “trust the small model.” The draft proposes. The target distribution decides.

Why ordinary decoding is serial

For an output x1, x2, ..., xn, an autoregressive model factorizes probability as:

p(x1:n) = product over t of p(xt | x1:t-1)

Ordinary sampling needs the realized xt before constructing the next conditional input. Even when one step underuses the accelerator's parallel arithmetic, the next step cannot begin from an unknown token.

The key observation behind Leviathan, Kalman, and Matias and the independently developed speculative sampling work by Chen et al. is that a transformer can score a short proposed continuation in parallel. A fast approximation creates that continuation. The target then checks it without blindly inheriting the approximation's distribution.

This exchanges fewer serial target steps for extra cheap work and wider target verification.

Exactness comes from correction, not agreement alone

Let q be the draft distribution and p the target distribution at a proposed position. The draft samples token x from q. A simplified view of the acceptance probability is:

accept x with probability min(1, p(x) / q(x))

If the proposal is rejected, the algorithm samples a correction from a residual distribution derived from p and q. When every proposal in the window is accepted, the target can supply an additional token. The full papers specify the procedure and proof.

Why not simply accept whenever the target's top token matches the draft's top token? That can work for deterministic greedy decoding, but it does not in general reproduce a stochastic target sampler. Why not accept a token whenever its target probability exceeds a hand-chosen threshold? That changes the distribution unless an exact correction scheme accounts for it.

“Lossless” needs a precise meaning:

• same greedy token sequence for deterministic decoding;
• same probability distribution for stochastic decoding;
• same benchmark quality within an error bar;
• or merely no observed regression on a test set.

Only the first two are algorithmic equivalence claims. The others are empirical quality claims. Configuration still matters: tokenizer, temperature, top-k or top-p filtering, random-number handling, numerical precision, and target revision must be compatible with the proof and implementation.

Expected progress is the first useful equation

Suppose a draft proposes gamma tokens. For an intuition model only, assume each position is accepted independently with probability alpha. Expected committed progress, including the correction or bonus token supplied by the target, is:

E[progress]
= 1 + alpha + alpha^2 + ... + alpha^gamma
= (1 - alpha^(gamma+1)) / (1 - alpha)

For gamma = 4 and alpha = 0.8:

E[progress] = 1 + .8 + .64 + .512 + .4096
            = 3.3616 tokens per verification round

This does not mean every round advances 3.3616 tokens. It is a long-run expectation under a deliberately simple independence assumption. Real acceptance changes by position, prompt, domain, sampling temperature, and the tokens already proposed. Measure the conditional acceptance curve:

P(d1 accepted)
P(d2 accepted | d1 accepted)
P(d3 accepted | d1,d2 accepted)
...

A single aggregate acceptance percentage hides where rejection truncates useful work.

The breakeven includes time, not just accepted tokens

Let:

• T1 be wall time for one ordinary target decode step at the relevant batch and context;
• Td(gamma) be time to produce the draft window;
• Tv(gamma) be time for the target to verify it;
• To be orchestration, sampling, transfer, and synchronization overhead;
• E[P] be expected committed progress.

An illustrative latency speedup estimate is:

speedup ≈ E[P] * T1 / (Td(gamma) + Tv(gamma) + To)

Speculation wins on latency when the numerator exceeds the denominator.

Take the high-acceptance example above. Let ordinary target decode take 22 ms. Four draft tokens take 8 ms total, parallel target verification takes 18 ms, and overhead takes 2 ms.

ordinary time for 3.3616 expected tokens = 3.3616 * 22 = 73.96 ms
speculative round                         = 8 + 18 + 2 = 28 ms
illustrative speedup                      = 73.96 / 28 = 2.64x

Now use alpha = 0.35, so expected progress is 1.5304 tokens. Suppose a less favorable deployment needs 16 ms to draft, 28 ms to verify, and 3 ms of overhead.

ordinary equivalent = 1.5304 * 22 = 33.67 ms
speculative round   = 16 + 28 + 3 = 47 ms
speedup             = 33.67 / 47 = 0.72x

The same idea is now a 28 percent slowdown. These timings are illustrative, retained in the claim ledger, and make no claim about a named model or GPU.

Acceptance is a property of the pair and workload

A draft model is useful when it is cheap and agrees with the target in the regions that traffic visits. Parameter count alone does not determine either property.

Acceptance can fall when:

• the domain differs from the draft's data or tuning;
• temperature or sampling truncation increases diversity;
• code, identifiers, numbers, or rare languages require precise continuations;
• the target has changed but the draft has not;
• tool-call syntax narrows acceptable tokens;
• safety or policy tuning separates the two distributions;
• long context changes which evidence controls the next token.

Acceptance can rise on repetitive, predictable, or strongly formatted text. A workflow may therefore enable speculation for one route and disable it for another.

Build an acceptance matrix rather than a global average:

Slice	Draft tokens/round	Accepted tokens/round	Verification time	Net TPOT
prose completion	measured	measured	measured	measured
code generation	measured	measured	measured	measured
JSON tool calls	measured	measured	measured	measured
multilingual	measured	measured	measured	measured
long-context RAG	measured	measured	measured	measured

Version the target-draft pair as one serving artifact. A silent target update can turn an economic win into rejection overhead without changing API correctness.

Longer draft windows have diminishing and sometimes negative returns

Increasing gamma creates more possible progress, but later tokens are reached only if earlier tokens survive. Under the toy constant-alpha model, the marginal expected contribution of draft position i is alpha^i. At alpha = 0.5, the fifth proposed position contributes only 0.03125 expected token while still adding draft work and verification width.

Longer windows can also increase:

• draft latency before verification begins;
• temporary KV and candidate memory;
• target verification compute;
• wasted work after early rejection;
• synchronization and scheduling complexity;
• interference with other requests in a continuous batch.

Tune window length per workload or adapt it using observed acceptance. A high-confidence region may justify a longer draft; a rejection-prone region should shorten or bypass speculation.

One draft model is not the only proposer

The original small-draft-model pattern is only one point in the design space.

Medusa adds multiple decoding heads to a model to predict future tokens and verifies a tree of candidates. It avoids maintaining a completely separate conventional draft model, but the heads require training or adaptation, candidate trees consume verification work, and operating modes need their own quality claims.

EAGLE drafts using target-model features and explicitly addresses uncertainty in the next feature. EAGLE-2 makes draft-tree structure context-aware rather than fixed.

Other families use self-speculation, early-exit layers, n-gram matches, prompt lookup, or multiple candidate branches. They differ along important axes:

Proposer	Extra trained artifact	Candidate shape	Typical dependency
separate draft LM	yes	chain	target-draft tokenizer and distribution compatibility
extra prediction heads	yes	tree	target architecture and head training
feature drafter	yes	chain or tree	access to target hidden features
prompt/ngram lookup	no learned model	matched spans	repetition in context or corpus
self-speculation	no separate full model	chain	skippable layers or target internals

Do not collapse their paper results into one leaderboard. Measure the implementation you can actually operate.

Serving concurrency can reverse a single-request win

Speculative decoding is often strongest when ordinary single-request decode is memory-bandwidth limited and target verification can use otherwise idle parallel compute. Under high concurrency, continuous batching may already fill that parallel capacity.

Drafting then competes for accelerators, memory bandwidth, KV space, and scheduler slots. A target verification batch is wider than an ordinary one. If draft and target live on different devices, transfer and synchronization enter. If they share a device, their kernels interfere.

Therefore measure two surfaces:

inter-token latency versus concurrent requests
verified output throughput versus concurrent requests

A technique can improve TPOT for one stream and reduce fleet throughput, or the reverse. Connect the test to Continuous Batching rather than benchmarking an isolated decoding loop.

Memory deserves its own ledger:

• draft weights and KV state;
• target KV state;
• candidate-tree or proposed-token tensors;
• verification activations and workspace;
• reduction in maximum active sequences;
• prefix-cache eviction caused by the extra footprint.

The cheapest draft in FLOPs may be expensive in scarce accelerator memory.

Automation value depends on where decoding sits in the loop

A 2x decode speedup does not imply a 2x faster automated task. Decompose task time before setting a rollout target:

task time = queue + prefill + decode + tools + verification + persistence + human wait

Suppose an agent task spends 600 ms queueing, 400 ms in prefill, 1,200 ms decoding, 2,000 ms in tools, and 800 ms verifying. Total time is 5,000 ms. Halving decode saves 600 ms, so the task becomes 4,400 ms, a 12 percent improvement rather than 50 percent.

If the loop makes ten sequential model calls with similar decode-heavy shapes, the savings can compound along the critical path. If calls run in parallel and a slow database tool dominates the winning branch, faster decoding may change little. Trace critical-path spans, not the sum of every span.

Cost can move independently. Drafting may use an otherwise idle small accelerator, raising energy and model-serving cost while improving latency. Or it may reduce target occupancy enough to serve more verified tasks per target replica, lowering fixed cost per outcome. Calculate:

incremental value per task
= latency value from critical-path reduction
  + avoided target capacity cost
  - draft capacity and memory cost
  - operational cost
  - expected quality or reliability loss

For interactive coding, voice, or search, hundreds of milliseconds may affect completion and abandonment. For a ten-minute background workflow, the same saving may have little business value unless it increases throughput or releases expensive capacity.

Use three independent rollout gates:

1. equivalence gate: deterministic identity or declared stochastic/quality test passes;
2. serving gate: TTFT, TPOT, SLO goodput, memory, and fairness meet limits at target concurrency;
3. outcome gate: verified task success and cost per outcome do not regress.

If equivalence passes but serving fails, bypass speculation for that load region. If serving passes but outcome fails, investigate configuration, stopping, structured decoding, or application assumptions. If both pass but economic value is negligible, the added artifact and operational surface may still not be worth owning.

Quality validation is still required for an exact algorithm

If the implementation follows an exact sampling algorithm, its mathematical target is distribution preservation. Production can still diverge through bugs or configuration mismatches.

Test deterministic decoding first. With fixed target, tokenizer, inputs, and greedy settings, speculative and ordinary paths should emit identical tokens. Then test stochastic distributional behavior over many seeded samples. Compare token frequencies or task outputs within a predeclared statistical procedure.

Also compare:

• stop strings and end tokens;
• logit processors and forbidden tokens;
• structured-output constraints;
• tool-call parsing;
• maximum-length behavior;
• streaming order and cancellation;
• numerical formats and distributed reductions.

If the method intentionally relaxes acceptance for speed, call it approximate. Evaluate verified outcome rate, not merely text similarity.

A builder playbook

1. Establish the non-speculative baseline

Record prompt/output distributions, TTFT, TPOT, completion latency, target-step time by active batch size, throughput, KV memory, and verified outcome rate.

2. Instrument every speculative round

Store draft length, accepted-prefix length, rejection position, draft time, verification time, correction time, memory, and target-draft versions. Histograms by route matter more than one acceptance average.

3. Reproduce the distribution contract

Run token-identity tests for deterministic decoding and statistical tests for stochastic sampling. Include constraints, stops, and tools used in production.

4. Sweep draft length and concurrency

Test gamma from one through the plausible maximum at multiple arrival rates and prompt/output slices. Report both latency and SLO goodput.

5. Add a bypass policy

Disable speculation for low-acceptance slices, memory pressure, small remaining token budgets, overloaded draft routes, or target-draft version mismatch. A stable baseline is a feature.

6. Price verified tokens and outcomes

Include both models, devices, idle reservation, memory opportunity cost, and any quality loss. The unit from Cost per Successful Outcome remains the governing business measure.

The decision

Adopt speculative decoding when measured expected progress times ordinary target-step cost exceeds draft, verification, orchestration, and capacity opportunity cost for the target workload. Preserve the target distribution with an exact algorithm when that is the product contract. Label approximate variants honestly.

More models make inference cheaper only when the proposer is sufficiently cheap, sufficiently aligned, and scheduled into real spare parallelism. The acceptance trace, not the technique's name, tells you whether that condition holds.

References

• Fast Inference from Transformers via Speculative Decoding, Leviathan, Kalman, and Matias, ICML 2023. Gives an exact speculative-decoding method and analysis.
• Accelerating Large Language Model Decoding with Speculative Sampling, Chen et al., 2023 preprint. Independently develops modified rejection sampling for target-distribution preservation.
• Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Heads, Cai et al., ICML 2024. Explores target-attached multi-head candidate generation.
• EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty, Li et al., ICML 2024. Proposes feature-level drafting and uncertainty handling.
• EAGLE-2: Faster Inference of Language Models with Dynamic Draft Trees, Li et al., EMNLP 2024. Adapts candidate tree structure to context.

All numerical timings and speedups in the worked examples are illustrative. Their equations and inputs are preserved in the claim ledger.