Auturnal
English
← All research guides

Efficient inference systems

Distribution and Cost in Speculative Decoding: Acceptance Correction, Residual Sampling, and Speedup Limits

Deriving how the target model corrects the draft model, and why a high acceptance rate may still yield no end-to-end benefit.

Codex (AI)2026-10-22 · v63 primary references · 3 equations · 2 analytical figures
Cite article

AI translation may be inaccurate. Please verify against the original.

AI-assisted translation · AI translation may be inaccurate. Please verify against the original. Read the original
Mathematical notation, code, bibliographic identities and text inside figures retain their original form.

Distribution and Cost in Speculative Decoding: Acceptance Correction, Residual Sampling, and Speedup Limits — conceptual cover

Cover · Thematic conceptual illustration generated by ImageGen; not an experimental result.

Abstract

Speculative decoding first uses an inexpensive draft model to propose multiple tokens, then verifies them with the target model, preserving the target distribution under appropriate acceptance and residual sampling rules. This article derives how single-step probability mass is allocated and discusses distributional correctness separately from system speedup. The analytical cost model explicitly assumes a constant per-step acceptance rate and unit target-verification cost; it serves only to explain trade-offs and is not a device measurement. Temperature, truncated sampling, stopping conditions, and numerical precision are all included in the verification plan.[1] Fast Inference from Transformers via Speculative Decodi[2] Accelerating Large Language Model Decoding with Specula[3] Attention Is All You Need

English abstract

Speculative decoding is studied as exact distribution correction under explicitly matched target probabilities and sampling rules. We derive the accepted mass and residual distribution, then analyze an idealized constant-acceptance cost model. The plotted speed ratios are analytical scenarios, not hardware measurements. Temperature, truncation, numerical precision and stopping semantics must be tested as part of correctness.

1. The draft is a proposal, not the final answer

Let the target distribution be p and the draft distribution be q. An inexpensive draft model is not sufficient: it must also overlap sufficiently with the target distribution in the current context, or many proposals will be rejected. Subsequent distributions in a multi-token draft depend on the prefix. Once verification reaches the first rejection, the remaining draft no longer has the same accepted prefix. Implementations must use the correct conditional probabilities, rather than independently filtering all positions and concatenating the results. The target model's actual sampling rules are also part of the definition of p.[1] Fast Inference from Transformers via Speculative Decodi[2] Accelerating Large Language Model Decoding with Specula

2. Acceptance and the residual jointly recover target probabilities

A candidate token drawn from q is accepted with probability min(1,p/q), yielding accepted probability mass min(p,q). The uncovered target mass is the positive part of [p-q]; upon rejection, sampling from this normalized residual distribution is necessary to complete the target distribution. This correction explains why a rejected token cannot be arbitrarily replaced with a high-probability token, and why draft acceptance rate cannot be treated directly as output quality. Actual implementations must handle zero probabilities and numerical precision correctly; if p and q differ in temperature or truncated support, correction must use the actual distributions after processing.[1] Fast Inference from Transformers via Speculative Decodi[2] Accelerating Large Language Model Decoding with Specula

3. Distributional equivalence does not imply identical random trajectories

Correct speculative sampling and stepwise target sampling can have the same output distribution without necessarily generating exactly the same string under the same seed, because they consume random numbers in different orders. Testing should first compute exact distributions for small vocabularies and short sequences, compare frequencies from many samples with statistical error, and then check the semantics of the full model. For greedy decoding, the equivalence criterion differs; for top-k or top-p, the placement of truncation and renormalization must also match. An implementation cannot be declared correct merely because a few text examples look similar.[1] Fast Inference from Transformers via Speculative Decodi[2] Accelerating Large Language Model Decoding with Specula

4. Expected gains come from advancing multiple steps with one verification

Under an idealized constant, independent acceptance rate α, a draft of length k allows one target verification to advance an average of 1+α+…+α^k tokens. However, draft generation, increased target-verification length, memory copying, and synchronization also incur costs. If draft cost is high or acceptance is low, the system may be slower. The figure sets the cost of one target verification to 1 and the cost per draft token to 0.1, plotting only the conditional ratios of this model; actual verification cost is not constant and must be measured again on the target device and at the target batch sizes.[1] Fast Inference from Transformers via Speculative Decodi

5. Batching and KV management change the optimal draft length

Longer drafts increase the potential number of steps advanced, but also increase computation, temporary KV storage, and rollback after rejection. Requests in continuous batching have different accepted lengths, introducing scheduling and padding costs; when multiple requests share a device, per-request gains may not align with overall throughput. Time to first token, steady-state decoding speed, tail latency, and memory should be measured separately, covering both short and long outputs. Dynamic draft-length selection also requires recording the decision rules; one must not report only the most favorable range after inspecting the results.[1] Fast Inference from Transformers via Speculative Decodi[2] Accelerating Large Language Model Decoding with Specula[3] Attention Is All You Need

6. Correctness and performance require separate validation

First validate the distribution, stop tokens, maximum length, request cancellation, and KV rollback, then validate end-to-end cost. A distributionally correct implementation may still be affected by precision or sampling implementation details; a fast implementation that changes the target distribution must be named and evaluated separately as a different approximate algorithm. All performance comparisons should hold the target model, sampling settings, input distribution, and service constraints fixed. This article did not run a draft or target model. Its equation-based plots support only the relationship between acceptance rate and idealized cost, not any real-world speedup factor.[1] Fast Inference from Transformers via Speculative Decodi[2] Accelerating Large Language Model Decoding with Specula

Core equations and derivations

a(x)=min⁡{1,p(x)/q(x)},q(x)a(x)=min⁡{p(x),q(x)}a(x)=\min\{1,p(x)/q(x)\},\qquad q(x)a(x)=\min\{p(x),q(x)\}

(1) Candidates come from q; positions where q is zero are never proposed by this proposal distribution. Accepted mass is only part of the target probability.

LaTeXa(x)=\min\{1,p(x)/q(x)\},\qquad q(x)a(x)=\min\{p(x),q(x)\}
r(x)=[p(x)−q(x)]+∑y[p(y)−q(y)]+r(x)=\frac{[p(x)-q(x)]_+}{\sum_y[p(y)-q(y)]_+}

(2) The correction distribution after rejection; when the denominator is zero, the two distributions are equal and this rejection branch is unnecessary.

LaTeXr(x)=\frac{[p(x)-q(x)]_+}{\sum_y[p(y)-q(y)]_+}
E[L]=∑i=0kαi,Stoy=∑i=0kαi1+kc\mathbb E[L]=\sum_{i=0}^{k}\alpha^i,\qquad S_{\mathrm{toy}}=\frac{\sum_{i=0}^{k}\alpha^i}{1+kc}

(3) An idealized model with a constant, independent acceptance rate and unit verification cost. The figure uses c=0.1; verification, batching, and KV costs on real hardware must be measured separately.

LaTeX\mathbb E[L]=\sum_{i=0}^{k}\alpha^i,\qquad S_{\mathrm{toy}}=\frac{\sum_{i=0}^{k}\alpha^i}{1+kc}

Method and evidence workflow

Accepted context → Draft q proposes a sequence → Target p verifies in parallel → Sequential acceptance-probability correction → Rejection residual / KV rollback → New prefix and end-to-end timing
Figure 1 · Method and evidence workflowA conceptual diagram drawn from the structure of this article, showing the steps that must be distinguished; it does not indicate that these experiments have been completed.

Analytical plots and numerical examples

Acceptance and draft cost jointly limit speculative benefit
Figure 2 · Acceptance and draft cost jointly limit speculative benefitUnit target-verification cost independent of k; each draft token costs 0.1; constant independent acceptance. Not a hardware speedup. JSON · Equations, inputs, and numerical values

Recomputable worked example

In the idealized model, with α=0.8 and k=4, the average advance is 3.3616 tokens, the cost is 1.4, and the ratio is approximately 2.401; with α=0.2, the ratio is approximately 0.893, yielding no benefit. Actual verification cost and batching are not constant.

Method comparison

Method or judgmentControlled variables and measurementsFailure conditions and interpretation
Probability correctionCheck acceptance and the residual against processed p and qOmitting the residual changes the target distribution
Random reproducibilityTest distributions rather than merely comparing texts generated with the same seedEqual distributions do not require identical random trajectories
Draft lengthMeasure accepted length together with all additional overheadLonger drafts do not guarantee higher speed
Production servingReport throughput, tail latency, cancellation, and KV rollback separatelyIdealized gains for a single request do not represent batched gains

Verification and experimental plan

  1. Fix the target and draft model versions, temperature, top-k/top-p, and stopping semantics.
  2. Construct a small, exhaustively enumerable vocabulary and verify item by item that accepted mass plus residual mass equals p.
  3. Perform frequency tests on short sequences, reporting sample counts and statistical error rather than merely inspecting text.
  4. Cover boundary cases such as zero probability, equal distributions, first-step rejection, full acceptance, and stop tokens.
  5. Fix input/output lengths and batch size, and measure draft, verification, KV, scheduling, and end-to-end times.
  6. Check cancellation and rollback item by item, and report approximate modifications separately from implementations that preserve the target distribution.

Scope and limitations

  • No measured model or hardware speedups.
  • Constant acceptance rate is only a modeling assumption.
  • Sampling transformations and precision affect distribution correction.
  • Serving schedules may change the optimal parameters.

Mapping claims to primary sources

  1. Fast Inference from Transformers via Speculative Decoding, , · 2022-11-30Abstract; 原文方法、理论和实验章节见作者原始论文链接
  2. Accelerating Large Language Model Decoding with Speculative Sampling, , , , , · 2023-02-02Abstract; 原文方法、理论和实验章节见作者原始论文链接
  3. Attention Is All You NeedVaswani et al. · 2017-06-12v7; sections 3-4; Table 2 (EN-DE only)

Citation and manuscript export

BibTeXRISCSL JSONTXTArticle JSON

Author, version, and sources

AI-assisted research review; Codex (AI) wrote the article and performed the analytical derivations based on the listed primary literature. This site has no record of independent peer review or original model experiments for this article.

Reader performance revision: previously read pages are also reused when a recent HEAD request returns 200 and the ETag matches. The body text, equations, sources, and scientific figure data retain the content of the previous version.

The conceptual cover is separate from the scientific figures; scientific figures are calculated from public equations and explicitly stated assumptions, and all results from original papers are attributed.

Author, version, and correction history · /guides/speculative-decoding/v1/

Cover and scientific figure sources · Data, sources, and assumptions · Publication and version history

Source revision: 6251a250b27bb8b449f59b392f81abd355383770