semiAIfoundry

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 AtlasLogical 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⁡ ⁣(1,p(x)q(x)),r(x)=[p(x)−q(x)]+∑y[p(y)−q(y)]+,α=∑xmin⁡(p(x),q(x))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

E[K]=∑j=0γαj,Rscenario=E[K]Tdraft+Tverify+Toverhead\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

Published lesson data · Atlas releases and licensing

Continue exploring

Foundations

Related lessons