# Speculative decoding: proposals and verified output Canonical: https://semiaifoundry.com/learn/atlas/speculative-decoding-verification/ Revision: 2026-10-07 Rights: https://semiaifoundry.com/ai-atlas/licenses.html Executable software · Atlas v1.3.0 # Speculative decoding: proposals and verified output Account for target-distributed output tokens while separating draft work, verification and actual elapsed time. [Explore in Atlas](https://semiaifoundry.com/ai-atlas/#speculative-decoding-verification)Logical values and distributed ownership; no physical scale or vendor timing Learning objectiveRecover the target distribution by exact probability accounting, then calculate output-per-round and a conditional throughput without treating proposals or assumptions as measured useful output. ## The mechanism A draft model can propose several next tokens cheaply, but proposals are not yet accepted output. In strict speculative sampling, the target model evaluates the relevant conditional distributions and verifies the draft sequence in order. A proposal is accepted with a probability determined by the target-to-draft probability ratio. The first rejected position is corrected using the positive residual between the two distributions, and later proposals from that speculative branch are discarded. When all proposals are accepted, one additional target token can be emitted. This procedure preserves the target sampling distribution under its stated assumptions; it does not establish factual truth or force the same sampled text from the same random seed. The benefit can come from evaluating several target positions together and reusing data movement, while draft work, rejected work and additional state still consume resources. The exact three-symbol example below checks the sampling correction before considering a separately assumed timing budget. 1. Use target p and draft q distributions over the same token events and the same valid prefix, including any declared sampling transforms. 2. Sample a proposal x from q; when q(x)>0, accept it with probability min(1,p(x)/q(x)). A symbol with q(x)=0 cannot be proposed. 3. After the first rejection, sample a correction from normalized max(p−q,0) at that prefix and discard the later speculative branch. 4. If all γ proposals are accepted, draw the extra token from the target distribution conditioned on the full accepted prefix. 5. Count accepted prefix tokens plus the one correction or bonus token as output; count draft proposals and rejected target work separately. 6. Measure draft, target-verification, synchronization and state-management time on the actual workload before claiming a speedup. Distributional equivalence remains separate from factual or task correctness. ## Science and assumptions ### Acceptance and rejection correction $$ a(x)=\min\!\left(1,\frac{p(x)}{q(x)}\right),\qquad r(x)=\frac{[p(x)-q(x)]_+}{\sum_y[p(y)-q(y)]_+},\qquad \alpha=\sum_x\min(p(x),q(x)) $$ Accept a proposed symbol using the target-to-draft ratio capped at one. After rejection, sample from the normalized positive target-minus-draft residual. Acceptance mass sums the minimum of each pair of probabilities. Symbols and units p(x), q(x) Target and draft probabilities at the same prefix probability a(x) Conditional acceptance probability for q(x)>0 probability r(x) Correction probability when residual mass is positive probability \[z\]+ Positive part max(z,0) value α Total proposal-acceptance probability at this prefix probability For a proposed symbol, accept with a(x). After a rejection, sample from residual r. Total acceptance probability is α=Σx min(p(x),q(x)). Assumptions Finite normalized distributions with q(x)>0 for a proposed x. Use r only when its denominator is positive; if p=q no rejection occurs. Exact probability arithmetic and consistent prefixes are assumed. ### Output count in the iid acceptance scenario $$ \mathbb{E}[K]=\sum_{j=0}^{\gamma}\alpha^j,\qquad R_{\mathrm{scenario}}=\frac{\mathbb{E}[K]}{T_{\mathrm{draft}}+T_{\mathrm{verify}}+T_{\mathrm{overhead}}} $$ With iid acceptance and no early stop, expected output count is one plus powers of acceptance probability through the proposal count. Divide by the separately assumed total round time for a scenario token rate. Symbols and units K Output tokens, including the correction or bonus token tokens/round γ Maximum draft proposals in a verification round count α Assumed identical independent acceptance probability probability Tdraft Total draft time for the round s/round Tverify Target verification time for the round s/round Toverhead Other nonoverlapped round time s/round Rscenario Output rate under the time assumptions tokens/s K counts output tokens, including the correction or bonus. With iid acceptance probability α and no early stopping, the probability of accepting at least j proposals is αʲ. Assumptions The iid assumption is synthetic; actual acceptance varies with prefix. Time terms are separately declared seconds per verification round; no measured speedup, energy reduction or universal latency scaling is implied. ## Engineering example For symbols A/B/C, choose target p=\[0.6,0.3,0.1\] and draft q=\[0.2,0.3,0.5\]. Conditional acceptance is \[1,1,0.2\], so accepted probability mass is \[0.2,0.3,0.1\] and total α=0.6. The rejected mass is 0.4; normalized positive residual p−q is \[1,0,0\], so every correction in this toy case is A. The final output distribution is \[0.2,0.3,0.1\]+0.4×\[1,0,0\]=\[0.6,0.3,0.1\], exactly the target distribution. If γ=2 and acceptance events are independently 0.6 at both positions, output counts 1,2,3 have probabilities 0.4,0.24,0.36. Thus E\[K\]=1.96 tokens. Separately assume the two draft steps together take 2 ms, target verification 6 ms and overhead 1 ms: 1.96/0.009≈217.8 output tokens/s. A 6 ms single-token baseline would be 166.7 tokens/s under those assumptions. At 12 ms verification, the speculative scenario instead gives 130.7 tokens/s. Neither timing is measured or taken from the paper; acceptance alone does not establish acceleration. ## Distinctions and tradeoffs Accepting a draft token validates it against a sampling distribution, not against external facts; higher acceptance does not by itself prove lower latency. More proposals can expose useful parallel verification while increasing draft computation, temporary state and wasted work. Prefix-dependent acceptance and workload-specific target cost determine the result. Useful serving throughput counts the output that survives the verification algorithm and meets the task’s quality requirements. This connects decoding semantics, memory reuse and latency accounting. ## Specifications and interfaces Preserved quantity Target sampling distribution Ideal strict correction; not a guarantee of the same random sample or true statements. Output per verification 1 through γ+1 tokens before stopping rules Accepted prefix plus a correction or a target bonus. Resource boundary Draft and verification both cost work Batch verification latency is an implementation measurement, not implied by token count. ### Interfaces Aligned target and draft distributions Input Prefix-conditioned token probabilities and proposal sequence Verified continuation Output Accepted prefix and corrected or bonus target token ## Check your understanding ### In the stated toy distributions, a rejected proposal must be corrected from which distribution? 1. The original draft \[0.2,0.3,0.5\] 2. The residual \[1,0,0\] 3. Any uniform distribution Answer and reasoning The residual \[1,0,0\] The positive residual is \[0.4,0,0\], which normalizes to \[1,0,0\]. Adding its weighted contribution recovers the target probabilities. ### Under iid α=0.6 with two proposals, what is the expected output count including correction or bonus? 1. 1.2 2. 1.96 3. 3 Answer and reasoning 1.96 The count expectation is 1+0.6+0.36=1.96. ### Does preserving p establish that sampled statements are true? 1. Yes 2. No 3. Only when α=1 Answer and reasoning No The target distribution can assign probability to factually wrong continuations. ## Evidence and scope The cited ICML paper establishes the strict correction algorithm and the explicitly iid output-count formula. The toy probabilities, output-count distribution and all millisecond values are authored. No private model, serving implementation, benchmark speedup or quality improvement is asserted. Explore the KV storage consequence of token length and concurrency. Draft/target acceptance and corrected sampling are worked explicitly in this lesson, not executed by the cache-size calculator. ## Sources - [Leviathan, Kalman and Matias — Fast Inference from Transformers via Speculative Decoding](https://proceedings.mlr.press/v202/leviathan23a.html) [Published lesson data](https://semiaifoundry.com/ai-atlas/lesson-data/speculative-decoding-verification-f6066fe7fb36a164.json) · [Atlas releases and licensing](https://semiaifoundry.com/ai-atlas/licenses.html) ## Continue exploring ### Foundations - [Output head & decoding](https://semiaifoundry.com/learn/atlas/output-head/) - [Autoregressive decode and weight traffic](https://semiaifoundry.com/learn/atlas/decode-bandwidth-trace/) - [Key–value cache](https://semiaifoundry.com/learn/atlas/kv-cache/) - [Evaluation & the AGI frontier](https://semiaifoundry.com/learn/atlas/evaluation/) ### Related lessons - [Prefill and prompt processing](https://semiaifoundry.com/learn/atlas/prefill-resource-trace/) - [Prefill/decode disaggregation and useful serving rate](https://semiaifoundry.com/learn/atlas/disaggregated-serving/) - [Runtime, driver and device dispatch](https://semiaifoundry.com/learn/atlas/runtime-device-dispatch/) - [Place the working set, not just the model](https://semiaifoundry.com/learn/atlas/memory-working-set-placement/)