'Lossless' speculative decoding is a property of the math, not your deployment.

A team turns on speculative decoding, and the reason it reaches for this optimization rather than another is the strongest claim in the inference-speedup catalog: this one is lossless. Most ways to make a model faster cost something — quantization spends a little accuracy, a smaller model spends more, aggressive caching spends correctness at the edges. Speculative decoding, the team has read, spends nothing. A small, fast draft model proposes the next several tokens; the large target model verifies all of them in a single forward pass; a rejection-sampling step accepts the prefix it can and corrects the first token it cannot; and a theorem guarantees that the result is distributed exactly as the target model’s own sampling would have produced. Same output distribution, fewer expensive forward passes. The team enables it in its batched serving stack, measures a speedup, and ships it as the free lunch it was advertised to be.

The theorem is real. Speculative decoding, the algorithm, is genuinely distribution-preserving, and the proofs are not in question. But a theorem is a statement about a specific object, and the object this theorem is about is the speculative-decoding algorithm. The team did not deploy the algorithm. It deployed an implementation of the algorithm, running many sequences together in a batch, on a GPU whose arithmetic is not the arithmetic the theorem assumes.

“The algorithm is lossless” and “the system I shipped reproduces the target model’s outputs” are different claims, and the distance between them is the subject of this post.

This post is about what the losslessness theorem actually guarantees, why a batched implementation has routinely failed to deliver it, why even a correct implementation does not give you bitwise-reproducible output, and why the speedup — the other half of the free lunch — is a measured, regime-dependent quantity rather than a constant.

Lossless is a theorem, and theorems have hypotheses

The losslessness of speculative decoding is not a vendor’s phrasing; it is a proved result. Fast Inference from Transformers via Speculative Decoding (arXiv 2211.17192) and Accelerating Large Language Model Decoding with Speculative Sampling (arXiv 2302.01318) both establish that the accept-or-reject rule reproduces the target model’s output distribution exactly. Leviathan et al. describe the method as sampling “without changing the output distribution.” The result is correct, and nothing here disputes it.

But read what the result is a statement about, because two hypotheses are doing quiet work underneath it.

The first hypothesis: the guarantee is about the probability distribution over outputs, not about any particular output. Speculative decoding, run correctly, produces tokens drawn from the target model’s distribution. It does not produce the same tokens the target model would have produced on a given run with a given seed. “Distribution-preserving” and “produces the identical sequence” are different properties, and only the first is the theorem.

The second hypothesis: the guarantee assumes the rejection-sampling arithmetic is executed as written, in exact arithmetic. Chen et al. were explicit about the gap between that assumption and a real machine — their statement is that speculative sampling “preserves the distribution of the target model within hardware numerics.” The asterisk — within hardware numerics — is in the original paper. It tends not to survive onto the slide that says “lossless,” and the slide is what the team deployed against.

So the theorem, stated honestly, is narrower than the pitch: the algorithm, executed faithfully, draws from the right distribution, up to the limits of floating-point arithmetic. Everything in this post is a way that a deployment falls short of “executed faithfully” — or a way that “the right distribution” was never the property the team actually needed.

Batching breaks the implementation

The single-sequence speculative-decoding algorithm is simple enough to verify by hand. A serving system does not run the single-sequence algorithm. It runs many sequences in one batch, because batching is what makes a GPU economical — and batching introduces bookkeeping the theorem never mentions.

Batch Speculative Decoding Done Right (arXiv 2510.22876) is the paper to read here, and its title is a tell: “done right” implies it was being done wrong. The finding is exactly that. The paper reports that “all existing batch speculative decoding implementations violate” output equivalence — and the violations are not a subtle distributional drift you would need statistics to catch. They are corrupted output, which the paper describes as “ranging from repetitive tokens to gibberish.”

The mechanism has a name: the ragged tensor problem. Within a batch, different sequences accept different numbers of draft tokens at a verification step — one sequence accepts four, its neighbor accepts one. After that step the sequences are different lengths, and the position IDs, the attention masks, and the per-sequence KV-cache state all fall out of alignment. An implementation that does not handle the misalignment exactly produces a forward pass on malformed state, and a malformed forward pass produces malformed tokens.

The paper quantifies the breakage with an exact-match equivalence score — the fraction of sequences whose speculative output is identical to the non-speculative reference. One prior batch implementation scores 0.0 at batch size 1: not a single sequence comes out matching the reference. Another scores 1.9 at batch size 1 and falls to 0.2 by batch size 4 — the equivalence degrades as the batch grows, which is to say it degrades exactly as you scale toward production. The paper’s own corrected methods restore the score to roughly 95%, and they do it at a cost: the realignment bookkeeping consumes a substantial share of compute, which the paper measures at up to 40% at batch size 8. A correct batched implementation is achievable. It is not what “turn on speculative decoding” gave teams by default, and it is not free.

Even correct, the speedup is regime-dependent

Suppose the implementation is one of the correct ones. The losslessness is then back in hand — and the speedup, the other half of the free lunch, turns out not to be a constant.

Nightjar (arXiv 2512.22420) states the regime dependence plainly: speculative decoding “improves throughput in low-load, memory-bound systems but degrades performance in high-load” ones. The mechanism is a resource conflict. The draft model and its activations occupy GPU memory; that memory is no longer available for the KV-cache; a smaller KV-cache holds fewer concurrent sequences; a smaller batch is less efficient. Under light load, where the GPU is idle waiting on memory, speculative decoding fills the idle time and wins. Under heavy load, where the GPU is already saturated, it spends memory it cannot spare and can come out behind plain decoding. The speedup is a function of where on the load curve the system is sitting.

Mistletoe (arXiv 2605.14005) makes the point from the adversarial side, and it is the clarifying result of the batch. It constructs inputs that collapse the speedup — on MT-Bench the average speedup falls by 1.89x, a 51.7% relative reduction; on HumanEval and GSM8K the relative reductions are comparable — and, crucially, it does this “while preserving output quality and perplexity.” That is the cleanest possible demonstration that the speedup and the losslessness are two separate properties: the attack drives the speedup toward nothing and the distribution guarantee never moves. The thing the theorem protects and the thing you turned the feature on for are not the same thing, and only one of them is protected.

The Disparate Impacts of Speculative Decoding (arXiv 2510.02128) shows the same separation in benign use: the speedup is “not uniformly distributed across tasks, consistently diminishing for under-fit, and often underrepresented tasks.” The acceleration a team measures on its benchmark traffic is an average over a distribution, and the slices of that distribution where the draft model agrees with the target least — which can be exactly the slices that matter — get less of it, or none.

Distribution-preserving is not bitwise-reproducible

Return to that residual five percent. Even the corrected implementation in Batch Speculative Decoding Done Right tops out near 95% exact-match equivalence, and the paper attributes the remaining gap not to a lingering bug but to floating-point non-determinism. This is the second hypothesis of the theorem coming due.

A team that hears “lossless” sometimes hears “reproducible” — it assumes that turning the feature on leaves the bytes of the output unchanged, so that a regression eval that diffs outputs, or a verification scheme that re-runs a generation and compares, will keep working. It will not, and the reason is upstream of speculative decoding entirely. GPU arithmetic is not associative, kernel selection and reduction order vary with batch shape, and so the token sequence a model emits is not bitwise-stable even with speculative decoding switched off — a fact this blog has covered as a source of irreproducible eval scores and silent RL-run collapse. Speculative decoding inherits that non-determinism and adds its own batch-dependent control flow on top. “Distribution-preserving” is a statement that the distribution is unchanged. “Reproducible” is a statement that the output is unchanged. The theorem delivers the first. If your system needs the second, “lossless” was never the property that would give it to you, and you have to engineer reproducibility separately — pinned precision, batch-invariant kernels — for speculative and non-speculative decoding alike.

What the numbers do not say

Three honest qualifications, because the version of this argument that overstates loses the reader who knows the field.

First, Batch Speculative Decoding Done Right rescues the thesis as much as it indicts it. The equivalence violation is fixable — the paper fixes it, to about 95%, with the residual being floating-point rather than logic. So “batched implementations violate the guarantee” is a true statement about existing and legacy implementations, not a permanent property of batched speculative decoding. The honest claim is that a batched implementation violates output equivalence unless it has been explicitly engineered not to — and that a team should know which kind its serving stack ships.

Second, the high-load slowdown is real but not universal. MagicDec (arXiv 2408.11049) shows that for long-context generation, speculative decoding can keep a meaningful speedup — it reports up to 2.51x — at large batch sizes from 32 to 256, precisely the regime Nightjar identifies as hostile. Long-context serving is a known exception. The claim is “the speedup can shrink or invert under load,” not “it will”; the regime, including context length, decides.

Third, Mistletoe is an adversarial existence proof. It shows the speedup can be driven to nearly nothing by a crafted input; it is not a measurement of how often that happens on benign traffic. Cite it for what it cleanly proves — that speedup and losslessness are independent — not as a base rate.

And the overarching qualification: this post is not “speculative decoding is lossy.” The algorithm’s distribution-preservation is a genuine, valuable, correctly proved property. The post’s claim is narrower and more useful — that the guarantee is about the algorithm and the distribution, while the things that bite a deployment live in the implementation, the load regime, and the gap between “same distribution” and “same bytes.”

Verifying speculative decoding honestly

The losslessness is a theorem you can trust about the algorithm. The deployment is a system you have to measure.

Treat output equivalence as something to test, not to assume. Before and after enabling speculative decoding, generate a sample of outputs at your production batch sizes and diff them against a non-speculative reference. You are checking for the corruption signature — repetition, gibberish, truncation — that a broken batched implementation produces, and you are checking that the rate of exact or near-exact matches is what a correct implementation would give. This is an eval you write before you ship the change, not a thing you inspect afterward.

Know whether your serving stack’s batched implementation is one of the engineered-correct ones. The ragged-tensor problem is solved in some implementations and not others. Find out which yours is — read the code or the release notes — rather than inferring correctness from the word “lossless” in the feature’s name.

Benchmark the speedup in your own serving regime, at your own load. The speedup is regime-dependent: light load versus heavy, short context versus long, one task mix versus another. Measure it under production-realistic concurrency, and measure it per task slice, because the average hides the slices where the draft model agrees least.

Do not promise bitwise reproducibility on the strength of “lossless.” Distribution-preserving is not byte-identical. If a downstream system — a regression diff, a re-run verifier — depends on reproducible output, engineer that reproducibility explicitly, and know it is a separate problem from speculative decoding that GPU non-determinism creates with the feature on or off.

Re-test on every draft-model, target-model, or batching change. Acceptance rate, and therefore both the speedup and the stress on the batched bookkeeping, depends on how well the draft model tracks the target. A new draft model, a fine-tuned target, or a change to batch sizing is a new system whose equivalence and speedup are unmeasured until you measure them.

The checklist

Before you call a speculative-decoding deployment a free speedup:

• Output equivalence is tested at production batch sizes — a sample of outputs diffed against a non-speculative reference, checked for corruption and for the expected match rate.
• The serving stack’s batched speculative-decoding implementation is confirmed to handle the ragged-tensor problem correctly, by inspection, not by the feature’s name.
• The speedup is benchmarked under production-realistic load and context length, not only in a light-load microbenchmark.
• The speedup is measured per task slice, not only as an aggregate, because it diminishes on the slices where draft and target agree least.
• No promise of bitwise-reproducible output rests on “lossless”; reproducibility, if needed, is engineered separately and acknowledged as a GPU-non-determinism problem.
• Equivalence and speedup are re-tested on every draft-model, target-model, or batching change.
• Someone has written down that “lossless” is a theorem about the algorithm’s output distribution — not about this system’s outputs, its bytes, or its speed.

Reading list

• Batch Speculative Decoding Done Right (arXiv 2510.22876) — all existing batch speculative-decoding implementations violated output equivalence, producing output “from repetitive tokens to gibberish”; the ragged-tensor problem is the cause, prior implementations score near-zero exact-match equivalence, and the fix costs up to 40% realignment overhead.
• Nightjar: Dynamic Adaptive Speculative Decoding for LLM Serving (arXiv 2512.22420) — speculative decoding improves throughput under light, memory-bound load but degrades it under heavy load, because the draft model’s memory footprint shrinks the KV-cache and the batch.
• Mistletoe: Stealthy Acceleration-Collapse Attacks on Speculative Decoding (arXiv 2605.14005) — crafted inputs collapse the speedup by roughly half (a 51.7% relative reduction on MT-Bench) while preserving output quality and perplexity — a clean proof that the speedup and the losslessness are separate properties.
• The Disparate Impacts of Speculative Decoding (arXiv 2510.02128) — the speedup is not uniform across tasks, consistently diminishing for under-fit and underrepresented ones, so the measured average hides the slices that get little or no acceleration.

The team’s free lunch had two courses, and the theorem only ever paid for one of them. Speculative decoding is distribution-preserving — that is proved, and it holds. But the team did not ship the proof; it shipped a batched implementation whose equivalence depends on bookkeeping the proof does not mention, in a load regime where the speedup can shrink to nothing, producing output that is drawn from the right distribution and is still not the same bytes twice. None of that makes speculative decoding a bad choice. It makes “lossless” a claim about an algorithm, and the thing on the GPU a system — and a system is something you measure. Diff the outputs. Benchmark the speedup where you actually run it. Then call it free, if it still is.