M7.1 - Speculative Decoding: Draft, Verify, Accept, Reject

M7.1 - Speculative Decoding: Draft, Verify, Accept, Reject

0x00 Historical Introduction And Owner Contract

A decoder-only language model does not produce a sentence in one invocation. It advances a state machine one sampled token at a time. For a request whose committed prefix ends at token $x_t$, one ordinary target-model round does this:

input:
    committed K/V for x_<t
    frontier token x_t

target forward:
    materialize the K/V row for x_t
    read the earlier K/V rows
    produce p(x_(t+1) | x_<=t)

sampling:
    choose x_(t+1)

next round:
    x_(t+1) becomes the new frontier token

The newly sampled token is output state, but it is not yet a target K/V row. Its row is created when that token becomes an input to a later target call. This one-token offset is already important in ordinary decoding; it becomes a correctness boundary when speculation creates provisional branches.

The owner question for M7.1 is:

How can a cheaper process propose several future tokens while the target model still owns the output distribution, positions, random sampling state, and committed K/V history?

Speculative decoding is one answer. It tries to replace several serial target rounds with cheap proposal work plus one wider target verification pass:

draft cheaply
verify with the target model
accept a prefix
reject and correct at the first mismatch
commit only target-valid state

That summary is not yet an algorithm. “Draft and verify” can describe greedy blockwise decoding, exact speculative sampling, heuristic acceptance, or tree verification. Those methods share a systems pattern but not the same probability contract.

0x00A One Output Token Is A State Transition

M5.1 owns the complete serving-state lifecycle. The minimum baseline needed here is that ordinary decode advances several synchronized objects:

The model cannot skip directly to the true target conditional at $t+2$. That distribution depends on which $x_{t+1}$ was actually sampled:

$$p(x_{t+2}\mid x_{\le t}) \neq p(x_{t+2}\mid x_{\le t},x_{t+1})$$

in general. A useful acceleration method must create parallel work without pretending this conditional dependence disappeared.

0x00B Three Pressures Hide Behind “Autoregressive Decode Is Slow”

The serial dependency is only the first pressure.

1. Causal pressure. A target-model decision at one position changes the valid conditional at later positions. Ordinary target rounds therefore lie on a strict dependency chain.
2. Memory-traffic pressure. Decode repeatedly reads model weights and a growing K/V history for relatively few query rows. On common serving regimes, wall time can be limited by moving state rather than by peak arithmetic throughput.
3. Work-shape pressure. At low request concurrency, one query row per request may expose less parallel work than the accelerator can execute efficiently. A wider verification call can improve utilization. At high concurrency, ordinary continuous batching may already supply enough rows, so speculative candidates can displace useful work from other requests.

These pressures imply different solutions. A faster attention kernel can reduce the cost of one round without reducing the number of rounds. Quantization can reduce weight traffic while preserving the serial chain. Batching uses other requests to fill the device. Speculation creates additional positions within one request and attempts to retire several output tokens per target round.

0x00C Speculation Is One Point In The Inference Design Space

M7 studies the last row. It does not replace the other rows. A production system may combine them, and the interactions matter: draft/target quantization changes proposal cost, batching changes the useful speculative depth, and K/V layout changes branch-state overhead.

0x00D A Source-Qualified Lineage Of Changed Contracts

The modern method is easier to understand as a sequence of changed contracts. The dates below are first public arXiv submission dates, not claims that one paper contains every later mechanism or that a submission date alone settles priority.

The rows are related but not interchangeable.

Blockwise parallel decoding establishes the longest-validated-prefix idea: parallel candidate positions can reduce the number of serial iterations even though only a prefix becomes authoritative.

SpecDec makes the drafter/verifier split explicit for sequence-to-sequence generation, but its reported quality contract is tied to its own decoding and evaluation setup. It must not be cited as if it had already supplied the exact target-distribution coupling derived in Sections 0x03-0x04.

The two exact-sampling papers replace greedy agreement with an accept/reject/correction construction between draft distribution $q$ and target distribution $p$. Under that complete construction, the emitted token follows $p$. Exactness belongs to the probability-mass proof, not to the words “target verified” and not to the general draft/verify shape.

Token-tree verification allows several candidate continuations or branches to share a target pass. It adds topology, ancestry masks, position ids, and temporary K/V state. M7.2 owns the Medusa/tree-attention mechanism, while M7.7 compares proposal sources and multi-candidate verifiers.

The terminology used in this sequence must remain precise:

0x00E Why Speculation Can Work

Three observations make the design plausible.

First, future tokens do not have equal difficulty. Formatting, syntax, common phrases, copied code, and locally predictable continuations can be easy for a cheaper proposer even when difficult semantic choices still require the target.

Second, the draft does not need to replace the target. It only needs to generate candidate mass cheaply enough and align often enough that the target retires more than one useful output token per verification round.

Third, a target forward over a proposed continuation can compute the conditionals for several candidate positions in parallel because the candidate tokens are supplied as inputs under a causal mask. The target is not predicting all futures independently; it is evaluating the drafted path. Rejection stops commitment at the first invalid point.

The analogy to CPU speculative execution is useful but incomplete:

similarity:
    perform likely future work before it is known to be commit-safe

difference:
    token generation samples a probability distribution
    exact decoding needs probability-mass correction, not only branch equality
    K/V and RNG state must follow the accepted token history exactly

More drafted tokens are therefore not automatically better. Draft latency, target verification shape, acceptance depth, cache work, batch pressure, and selection overhead all enter the wall-time ledger.

0x00F The State Contract Before The Probability Derivation

A complete speculative round can touch all of the following:

persistent model state:
    target weights and configuration
    draft weights and configuration, if a separate model is used

committed request state:
    output token history
    target K/V through the processed frontier
    sampling parameters and RNG lineage

proposal-side state:
    draft K/V or another proposer state
    candidate tokens and q probabilities

temporary target state:
    verification logits p
    branch K/V rows for drafted candidate inputs
    acceptance uniforms and correction distribution

round result:
    accepted draft-token prefix
    target-governed frontier token
    rejected suffix to discard

An output token and a committed target K/V row are not always created in the same operation. Accepted draft-token rows may be committed from a target verification branch. A correction or bonus token can be emitted from target logits before that token has itself been processed as an input row. Sections 0x04 and 0x06 make this frontier distinction explicit.

0x00G Owner Contract: Consumes, Owns, Defers, And Forbids

M7.1 is not a survey of every speculative method. It freezes the correctness contract that later M7 articles must consume.

The firewall is deliberate:

forbidden substitution in M7.1:
    Medusa head training for the generic draft distribution
    Lookahead pool state for the linear draft-model loop
    EAGLE or DeepSeek MTP training as proof of exact inference
    continuous-batch throughput as proof of one-request distributional correctness
    source-reported speedup as proof of a deployment-independent win

Deferral does not mean deletion. Each deferred mechanism receives its own derivation, tensor/code trace, alternatives, training or runtime integration, paper comparison, and failure contract in the named owner article.

0x01 Claim Status And Scope

0x01A Immutable Speculative-Round Coordinate

The symbols $p$, $q$, “prefix,” and “cache” are meaningful only after their runtime identities are frozen. Define one speculative-round coordinate:

$$\mathcal{M}_{round} = (I_T,I_D,\Omega,\Pi_T,\Pi_D,R,S_0,\Lambda),$$

where:

The target and draft may use different temperature, top-k, or top-p policies. They may even use different tokenizers if an explicit, correct mapping produces a proposal distribution over the same target-token events. What is forbidden is silent ambiguity: raw draft logits cannot stand in for a truncated proposal distribution, and token ids from different vocabularies cannot be compared as if their integers named the same event.

The manifest binds semantics, not only shapes:

target probability row:
    p_i after the declared target processors Pi_T

draft probability row:
    q_i after the declared proposal processors Pi_D
    exactly the distribution that sampled draft token d_i

event:
    one target-token event in Omega after any declared mapping

backend identity:
    model/adapters + dtype/autocast + attention/logit path + software revision

0x01B Two Valid Frontier Layouts, One Mandatory Declaration

Let the conditioning sequence at round start contain $T$ tokens. Let $K_c$ be the number of target-token input rows already committed to K/V. Two layouts can implement the same logical next-token distribution:

This article’s executable fixture uses replay_frontier because it makes the ordinary output/cache one-token offset visible. If the conditioning tokens are $x_0,\ldots,x_t$, then:

$$T=t+1, \qquad K_c=t, \qquad \operatorname{pos}(x_t)=K_c.$$

For draft tokens $d_1,\ldots,d_K$, the target call receives:

$$V_{in}=[x_t,d_1,\ldots,d_K]$$

at positions $t,\ldots,t+K$. Its two row families are offset:

$$\begin{aligned} \text{logit row }j &\to p(x_{t+j+1}\mid x_{\le t},d_{<j+1}),\\ \text{K/V row }j &\to \operatorname{KV}(V_{in,j},\operatorname{pos}=t+j). \end{aligned}$$

The logit at row j scores the next token; the K/V at row j belongs to the input token. Equal row counts do not mean equal token ownership.

If the first $A$ drafts are accepted and the next output is a correction, the replay layout commits:

$$\Delta K_c=A+1$$

rows: the previously uncached frontier plus the $A$ accepted draft inputs. The correction token is emitted but remains the new uncached frontier. Therefore:

$$T_{after}=T+A+1, \qquad K_{c,after}=K_c+A+1=T_{after}-1.$$

Under retained_frontier, the old frontier is already cached, so the same logical round commits only $A$ new draft rows. The two layouts agree on the post-round conditioning sequence and cache frontier only when their different starting coordinates are respected.

0x01C Worked Immutable Snapshot

Use a synthetic target vocabulary of size 16:

layout                  = replay_frontier
conditioning tokens     = [1, 4, 7, 9, 3, 12]       # T = 6
committed target K/V     = positions [0, 1, 2, 3, 4] # K_c = 5
frontier                 = token 12 at position 5
draft tokens             = [8, 6, 2]                 # K = 3
verification inputs      = [12, 8, 6, 2]
verification positions   = [5, 6, 7, 8]
target logit events       = positions [6, 7, 8, 9]
target K/V delta owns     = input positions [5, 6, 7, 8]

Suppose A = 2, draft token 2 is rejected, and correction token 11 is emitted at position 8:

commit target K/V rows for positions [5, 6, 7]
discard the candidate K/V row for position 8
append output events [8, 6, 11]
leave token 11 as the uncached frontier

after:
    conditioning length = 9
    committed K/V length = 8
    invariant            = K_c_after == T_after - 1

The manifest is serialized canonically and hashed. That digest is provenance, not a synchronization primitive. Any model revision, adapter, token mapping, processor order, RNG stream/counter, layout, prefix token, cache length, or position change creates a different round coordinate and must invalidate a stale proposal/verification result.

0x01D Collision And Mutation Failures

Shape-compatible state can still be semantically incompatible:

The executable fixture in the M7.1 evidence package mutates each field independently and requires a named failure. Loop 2 validates the coordinate; it does not yet claim to reproduce a framework runtime or target distribution.

0x02 Serial Baseline

Fix the round-start conditioning sequence as $c=x_{0:t}$. Ordinary target sampling defines a joint continuation through the chain rule:

$$p(y_{1:m}\mid c) = \prod_{i=1}^{m} p_i(y_i\mid c,y_{<i}).$$

The subscript $i$ names a conditional event, not a separate model head. After $y_i$ is sampled, it becomes part of the conditioning state that defines row $i+1$. This is why the mathematical product can be written at once while the runtime still has a serial state dependency.

For N output tokens, the target-only invocation ledger is:

$$C_{base} = N \cdot C_T,$$

where $C_T$ is the cost of one target decode transition under the frozen model, backend, batch, and cache coordinate. This is an invocation ledger, not the claim that every transition has identical wall time.

0x02A Target Conditionals Are Sequential State Transitions

Write the target state before event $i$ as:

$$S^T_{i-1} = (c,y_{<i},K^T_{i-1},R^T_{i-1},\Pi^T_{i-1}).$$

One ordinary decode transition is:

$$\ell^T_i,K^T_i = F_T(y_{i-1},K^T_{i-1};I_T), \qquad p_i=\Pi_T(\ell^T_i;S^T_{i-1}), \qquad y_i\sim p_i.$$

Here $F_T$ owns model execution and K/V growth, while $\Pi_T$ owns the declared logit processors and normalization. The distinction matters: softmax(raw logits) is not necessarily the user-facing $p_i$ after temperature, masking, top-k, top-p, grammar, or repetition-state processing.

state = target_state(prefix=c)
for i in range(1, m + 1):
    raw_logits, state.kv = target_decode_step(state)
    p_i, state.processor = apply_target_policy(raw_logits, state.processor)
    y_i, state.rng = sample(p_i, state.rng)
    state.output.append(y_i)

The next target call cannot be formed until the sampled event and every stateful processor transition are known. Speculation does not delete this factorization; it evaluates several target conditionals along a proposed path before knowing whether that path will become authoritative output.

0x02B The Draft Samples One Autoregressive Path

Let the draft propose $D_{1:K}=(D_1,\ldots,D_K)$. A causal draft model samples:

$$D_i\sim q_i(\cdot\mid c,D_{<i}),$$

so the probability of the realized path $d_{1:K}$ is:

$$q(d_{1:K}\mid c) = \prod_{i=1}^{K} q_i(d_i\mid c,d_{<i}).$$

Each stored $q_i(d_i)$ must be the probability from the processed distribution that actually sampled $d_i$. Re-running the draft after its adapter, processor state, RNG state, or prefix changed does not reconstruct the same proposal.

draft_prefix = list(c)
draft_tokens = []
proposal_rows = []

for i in range(K):
    raw_q, draft_kv = draft_decode_step(draft_prefix, draft_kv)
    q_i = apply_draft_policy(raw_q, draft_processor_state)
    d_i = sample(q_i, draft_rng)
    draft_tokens.append(d_i)
    proposal_rows.append(q_i)  # post-processed row bound to this sample
    draft_prefix.append(d_i)

The draft is serial in its own smaller state transitions. Its value comes from those transitions being cheaper than target transitions, not from pretending future tokens are conditionally independent.

0x02C The Target Scores The Same Candidate Path In Parallel

Given realized draft path $d_{1:K}$, the target conditionals needed later are:

$$p_i(\cdot) = p(\cdot\mid c,d_{<i}), \qquad i=1,\ldots,K+1.$$

A causal target verification call can materialize these rows together because candidate row $i$ is allowed to see $c,d_{<i}$ but not $d_i$ or later candidate events. This is parallel evaluation of conditionals along one path, not parallel generation of $K$ independent futures.

For K = 3:

The target can return all four probability rows in one verification call, but only rows before the first rejected draft remain conditioned on the eventual authoritative prefix. Later rows are computationally valid for the proposed path and semantically unusable after that path diverges.

This differs from independent horizon heads:

$$\widetilde q_j(\cdot\mid c), \qquad j=1,\ldots,K.$$

Those heads predict several horizon marginals from the same fixed context. In general,

$$\prod_{j=1}^{K}\widetilde q_j(d_j\mid c) \ne \prod_{i=1}^{K}q_i(d_i\mid c,d_{<i}).$$

Medusa-style heads and MTP objectives can still generate useful candidates, but their conversion into a joint proposal and their verification topology belong to M7.2 and M7.4. M7.1’s linear proof assumes one declared autoregressive proposal path.

The next loop will use the row-wise pair $(p_i,q_i)$ to derive one-token maximal coupling. Nothing in this section yet proves that accepting a draft token preserves the target marginal.

0x02D Blockwise Decoding As The Ancestor

Blockwise parallel decoding is the useful historical boundary. It predicts several future positions, verifies them with the target model, and accepts the longest valid prefix. The modern speculative-sampling version generalizes that idea from greedy longest-prefix validation into a sampling rule that can preserve the target distribution.

The distinction:

That is why this article needs both the systems loop and the probability rule. For greedy decoding, longest-prefix validation is already exact: every accepted token equals the target’s argmax under the same prefix, and the target’s own argmax takes the first mismatched position, so the output is the target’s greedy decode (Stern et al., Section 3). The $p/q$ rule below reduces to this check when $p$ puts all of its mass on one token. For sampling, agreement with the target’s greedy choices does not reproduce the target distribution: without the correction rule, “draft and verify” is only a heuristic acceleration pattern.

0x03 Draft And Verify

Let the target model distribution be p and the draft model distribution be q.

The draft model proposes:

$$\hat{x}_{t+1:t+K} \sim q(\cdot \mid x_{\le t})$$

The target model verifies the drafted continuation in parallel and produces target probabilities for those proposed positions.

The accept probability for token i is:

$$a_i = \min\left(1, \frac{p_i(\hat{x}_i)}{q_i(\hat{x}_i)}\right)$$

If a token is rejected, sample from the correction distribution:

$$p'_i(x) = \frac{\max(0, p_i(x)-q_i(x))} {\sum_y \max(0, p_i(y)-q_i(y))}$$

This correction is the mathematical reason the method can preserve the target distribution. It is not just “take whatever the draft guessed if it looks good.”

Source: Fast Inference from Transformers via Speculative Decoding, Figure 1. Green tokens are accepted draft suggestions, red tokens are rejections, and blue tokens are target-model corrections. The trace illustrates that accepted-prefix length varies by iteration.

0x03A One Token As A Coupling Problem

Freeze one candidate prefix from Loop 3 and let $p$ and $q$ be normalized distributions over the same discrete event space $\Omega$. The draft first draws $X\sim q$. The output $Y$ must have marginal $p$, while the implementation wants $Y=X$ as often as possible so that the draft work is useful.

This is a coupling problem: construct a joint law for $(X,Y)$ with marginals $q$ and $p$. For a proposed event $x$ with $q(x)>0$, use one uniform draw $U\sim\operatorname{Uniform}[0,1]$ and accept when:

$$U\le a(x), \qquad a(x)=\min\left(1,\frac{p(x)}{q(x)}\right).$$

The probability mass that reaches output event $x$ through the accept branch is:

$$q(x)\min\left(1,\frac{p(x)}{q(x)}\right)=\min(p(x),q(x)).$$

The ratio is not an arbitrary confidence score. It keeps exactly the overlap between target and proposal mass at each event. If $q(x)>p(x)$, only the $p(x)/q(x)$ fraction of proposals for $x$ may be retained. If $q(x)\le p(x)$, every proposed $x$ can be retained because the target needs at least that much mass at $x$.

0x03B Acceptance Is The Shared Mass And Is Maximal

Summing the diagonal accepted mass gives:

$$A_{one} = \Pr[Y=X] = \sum_{x\in\Omega}\min(p(x),q(x)).$$

No coupling can agree more often. For every event, any joint mass on the diagonal satisfies:

$$\Pr[X=x,Y=x]\le p(x) \quad\text{and}\quad \Pr[X=x,Y=x]\le q(x),$$

so it is at most $\min(p(x),q(x))$. The accept rule reaches that upper bound for every $x$ simultaneously. It is therefore a maximal coupling at one position.

The total rejection probability is:

$$Z = 1-\sum_x\min(p(x),q(x)) = \sum_x [p(x)-q(x)]_+,$$

and, because $p$ and $q$ are normalized,

$$Z = \frac{1}{2}\sum_x|p(x)-q(x)| = \operatorname{TV}(p,q).$$

Thus one-position acceptance is exactly $1-\operatorname{TV}(p,q)$. This is a mathematical identity for the frozen probability rows, not a claim that a language-model pair has constant acceptance across positions or requests.

0x03C Rejection Must Emit The Positive Target Residual

Write $[z]_+=\max(0,z)$. Conditional on rejection, the correction sampler uses:

$$p'(x)=\frac{[p(x)-q(x)]_+}{Z}.$$

This is normalized because its numerator sums to $Z$. Proposal events with excess $q$ mass have zero correction probability; the rejection branch fills only target mass that the accepted proposal branch did not already supply.

Multiplying by the probability Z of reaching that branch gives unconditional correction mass [p(x)-q(x)]_+. The two ways to emit x add to:

$$\min(p(x),q(x))+[p(x)-q(x)]_+=p(x).$$

Therefore $Y\sim p$. Sampling the correction directly from $p$, from $q$, or from a threshold-filtered subset would generally double-count some mass and leave other target mass missing.

0x03D Support, Degenerate, And Numerical Cases

The derivation exposes the implementation cases explicitly:

q(x) > 0, p(x) >= q(x):
    accept every drafted x

q(x) > 0, p(x) = 0:
    reject every drafted x

q(x) = 0, p(x) > 0:
    draft never proposes x; correction residual may emit x
    do not evaluate p(x)/q(x) for an event that was not proposed

if p == q:
    Z = 0 and the correction branch is unreachable

in finite precision:
    compute p and q after their declared processors
    clamp tiny negative residuals to zero
    sum in a stable accumulation dtype
    renormalize the residual only when Z is materially positive

Truncation does not invalidate the proof when $p$ and $q$ are the actual normalized, post-processor distributions over the declared event space. It does invalidate the proof if the draft sampled from truncated $q$ while acceptance uses an untruncated or stale denominator.

The upper row of this visual is the one-token proof just derived. Its lower row previews, but does not replace, Loop 5’s conditional-prefix induction.

0x03E Tiny Vocabulary And Coupling Matrix

Use a vocabulary with three tokens:

vocab = [A, B, C]

At one speculative position, suppose the draft sampled A.

The acceptance probability for drafted A is:

min(1, p(A) / q(A)) = min(1, 0.30 / 0.60) = 0.50

If A is rejected, the correction distribution uses the positive part of p-q:

Normalize:

Z = 0.25 + 0.05 = 0.30
p'(B) = 0.25 / 0.30 = 0.833
p'(C) = 0.05 / 0.30 = 0.167

This is not an arbitrary fallback. It compensates for the draft distribution overproducing A relative to the target.

The full coupling matrix makes both marginals auditable. Rows are proposed tokens $X\sim q$; columns are emitted tokens $Y\sim p$:

The diagonal sums to 0.70, which equals $\sum_x\min(p(x),q(x))=1-\operatorname{TV}(p,q)$. The off-diagonal row from proposal A contains the rejected mass redistributed as target residual.

0x03F Prefix Induction: Reuse The One-Token Coupling Only On The Accepted Prefix

The one-token result becomes a sequence result only after its conditioning event is made explicit. Let the committed history before the round be $h_0$, and let the drafter sample a path $D_{1:K}$ autoregressively:

$$q_i(x\mid h_{i-1}) = q\!\left(x\mid h_0,D_{1:i-1}\right).$$

The target verification pass evaluates the matching conditional row:

$$p_i(x\mid h_{i-1}) = p\!\left(x\mid h_0,D_{1:i-1}\right).$$

These rows are comparable at position $i$ only on the event that every earlier draft token was accepted. On that event, the emitted history really is:

$$Y_{1:i-1}=D_{1:i-1},$$

so the target and proposal rows are conditioned on the same prefix. Applying the Loop 4 coupling at that frozen prefix gives:

$$\Pr\!\left(Y_i=x\mid Y_{1:i-1}=y_{1:i-1},\ \text{position }i\text{ is reached}\right) =p_i(x\mid h_0,y_{1:i-1}).$$

The induction is then ordinary chain factorization. If the already emitted prefix has the target joint law through $i-1$, the exact conditional transition at $i$ gives:

$$\begin{aligned} \Pr(Y_{1:i}=y_{1:i}) &= \Pr(Y_{1:i-1}=y_{1:i-1}) \Pr(Y_i=y_i\mid Y_{1:i-1}=y_{1:i-1})\\ &= \prod_{r=1}^{i} p_r(y_r\mid h_0,y_{1:r-1}). \end{aligned}$$

This does not say that the accept decisions are independent, or that one unconditional scalar acceptance rate can be multiplied across arbitrary positions. Each ratio is a conditional object whose prefix exists only if all earlier draft tokens survived.

0x03G First Rejection Is A Semantic Stop, Not Only An Optimization

Suppose drafts D_1..D_{r-1} are accepted and D_r is rejected. Conditional on that rejection, the sampler emits a correction $C_r$ from the normalized positive residual at the reached prefix, not directly from the target conditional. The accept/reject mixture has the target conditional law; the rejection-conditioned correction alone generally does not. The round has produced:

D_1, ..., D_{r-1}, C_r

The precomputed next target row and every later draft row were conditioned on D_r, not on C_r. Unless the two token identities happen to coincide through a separately proved repair path, those suffix rows answer a counterfactual question:

$$p_{r+1}(x\mid h_0,D_{1:r}) \ne p_{r+1}(x\mid h_0,D_{1:r-1},C_r) \quad\text{in general}.$$

Therefore the linear speculative round stops at the first rejection. It discards later acceptance uniforms, draft conditionals, target suffix logits, and candidate K/V as output-authoritative state. Continuing to test D_{r+1} against the stale row can remain shape-correct while breaking the target joint.

The rejected position still makes one token of progress because the correction transition itself emits a valid target token. That is why a round emits at least one token even when the first proposal is rejected.

0x03H The All-Accepted Branch Owns One Bonus Target Transition

If every draft token is accepted, the emitted prefix equals the complete draft path. The target row computed after input D_K is therefore conditioned on the actual output history:

$$p_{K+1}(x\mid h_0,D_{1:K}).$$

Sampling one bonus token $B$ from that row is an ordinary target transition:

$$B\sim p_{K+1}(\cdot\mid h_0,D_{1:K}).$$

This yields K+1 output tokens from one target verification call. Sampling the bonus from the drafter, from a stale target row, or after advancing a stateful processor along an uncommitted branch would be a different algorithm. A runtime may defer the bonus sample to the next round without changing the eventual target distribution, but then this round advances only K positions.

The Loop 5 oracle makes this variable-length argument executable. It enumerates all draft paths for a two-token vocabulary and K=3, expands every possible first-rejection correction, and samples the target serially after that round until every branch reaches the common horizon K+1. The resulting fixed-length joint distribution matches ordinary target decoding token for token. The completion step is a proof device: Loop 7, not this section, owns the concrete output/KV/RNG transaction that prepares the next runtime round.

0x04 Loop Pseudocode

while not done:
    draft_tokens, q_probs = draft_model.sample_autoregressive(prefix, K)

    p_probs, p_bonus, branch_cache = target_model.verify(prefix, draft_tokens)

    emitted = []
    accepted_draft_count = 0
    terminal_token_needing_kv = None

    for i, tok in enumerate(draft_tokens):
        ratio = p_probs[i][tok] / q_probs[i][tok]
        if uniform() <= min(1.0, ratio):
            emitted.append(tok)
            accepted_draft_count += 1
        else:
            correction = sample_positive_part(p_probs[i] - q_probs[i])
            emitted.append(correction)
            terminal_token_needing_kv = correction
            break
    else:
        bonus = sample(p_bonus)
        emitted.append(bonus)
        terminal_token_needing_kv = bonus

    commit_output_tokens(emitted)
    commit_verified_prefix_kv(
        branch_cache,
        accepted_draft_count,
        layout=verification_layout,
    )
    discard_rejected_suffix(branch_cache)

    if terminal_token_needing_kv is not None and not request_finished():
        append_target_kv_before_next_decode(terminal_token_needing_kv)

If all K draft tokens are accepted, the canonical algorithm emits one additional target-sampled token from the target distribution at the next position. A runtime may defer that sample to the next iteration and remain distribution-correct, but it gives up one token of progress.

That bonus token matters to both the progress ledger and the cache contract:

all K draft tokens accepted:
    replay_frontier layout:
        commit the frontier row plus K verified draft K/V rows
    retained_frontier layout:
        commit K verified draft K/V rows
    sample one bonus output token from target position K+1

bonus token K/V:
    is not one of the K committed draft rows
    must be produced by a valid later append path before future decode uses it

0x04A Verification Shape

A verification pass is not the same as committing several serial decode steps. The target model evaluates the prefix plus the candidate continuation under causal positions:

input:
    committed prefix tokens
    draft token 1
    draft token 2
    ...
    draft token K

target logits:
    probability for draft token 1 conditioned on prefix
    probability for draft token 2 conditioned on prefix + draft token 1
    ...

The candidate positions must use the same token order, position IDs, attention-mask semantics, tokenizer, sampling parameters, and model state as ordinary target decoding. If any of those differ, the accept/reject math is being applied to the wrong distribution.

The off-by-one alignment is easiest to audit as a tensor table. Assume the committed prefix ends in token x_t, and the draft proposes d_1..d_K:

An implementation may expose the tensors with a different slice convention, but these logical identities cannot change. In particular, logits that score d_i and the K/V row created by input d_i are offset by one model position.

Two layouts are valid, but they must not be mixed:

# Layout A: full prefix K/V and p_1 logits were retained from the prior target step.
draft_logits, draft_kv = target(draft_tokens, past_kv=full_prefix_kv)
p_for_draft = concat(retained_p1, draft_logits[:-1])  # p_1 ... p_K
p_for_bonus = draft_logits[-1]                        # p_{K+1}
kv_for_draft = draft_kv                               # rows d_1 ... d_K

# Layout B: replay x_t because the supplied cache ends before x_t.
verify_inputs = concat(x_t, draft_tokens)
verify_logits, replay_and_draft_kv = target(
    verify_inputs,
    past_kv=prefix_kv_before_x_t,
)
p_for_draft = verify_logits[:-1]       # p_1 ... p_K
p_for_bonus = verify_logits[-1]        # p_{K+1}
kv_for_draft = replay_and_draft_kv[1:] # rows d_1 ... d_K

Replaying x_t while also passing a cache that already contains x_t duplicates the token and shifts every conditional. Tests should assert token identity, logical position, and cache ownership rather than copying slice indices without the cache precondition.

0x04B Source-To-Tensor Verification Contract

The two snippets above are equivalent only after every axis has an owner. For one request, let the round-start output end in x_t, let the target K/V contain either x_<=t or x_<t, and let the draft path be d_1..d_K. A verification call should expose at least this typed interface:

input_ids:       int[token_row]
position_ids:    int[token_row]
request_ids:     int[token_row]
past_kv:         target-cache rows declared by verification_layout
visibility:      bool[query_row, logical_key_row]

target result:
    logits:      work_dtype[token_row, target_vocab]
    new_kv:      storage_dtype[layer, K_or_V, token_row, kv_head, head_dim]

input_ids[j] owns both the K/V row materialized at row j and the logits that score the token at the next logical position. That is the source of the logit/K/V offset; it is not a library-specific accident.

For K=3, the two layouts compile as follows:

The retained layout also carries retained_p_1, produced by the prior valid target call after x_t. The logical extraction is therefore:

def extract_verification(layout, retained_p1, logits, new_kv, K):
    if layout == "retained_frontier":
        assert retained_p1 is not None
        assert logits.shape[0] == K
        p_for_draft = concat_rows(retained_p1, logits[:-1])
        p_for_bonus = logits[-1]
        kv_for_draft = new_kv
        kv_for_replayed_frontier = empty_rows()
    elif layout == "replay_frontier":
        assert retained_p1 is None
        assert logits.shape[0] == K + 1
        p_for_draft = logits[:K]
        p_for_bonus = logits[K]
        kv_for_replayed_frontier = new_kv[:1]
        kv_for_draft = new_kv[1:]
    else:
        raise UnknownVerificationLayout(layout)

    assert p_for_draft.shape == (K, target_vocab)
    assert kv_for_draft.token_rows == K
    return p_for_draft, p_for_bonus, kv_for_replayed_frontier, kv_for_draft

This function only extracts temporary state. Loop 7 decides which rows become authoritative after the accept/reject transaction.

0x04C Absolute Positions And Rectangular Causal Visibility

With a cache, the attention score matrix is generally rectangular: the query rows are only the newly supplied inputs, while the key rows include past K/V plus those new rows. A local lower-triangular matrix over query-row indices is not a complete visibility specification. Define each row by request identity and absolute logical position. Query row u may read key row v exactly when:

$$V_{u,v} = \mathbf 1[\operatorname{request}(u)=\operatorname{request}(v)] \mathbf 1[\operatorname{position}(v)\leq\operatorname{position}(u)].$$

For a prefix at positions 0..2 and drafts at positions 3..5, the retained layout has three query rows but six logical key positions:

                logical key position
query pos       0  1  2  3  4  5
---------------------------------
3 / input d1    1  1  1  1  0  0
4 / input d2    1  1  1  1  1  0
5 / input d3    1  1  1  1  1  1

The replay layout has query positions 2..5 and the same absolute rule. Its first row materializes the previously unprocessed frontier x_t; later rows see it once, not twice. Backend APIs may represent this relation through a rectangular mask, cache positions, sequence lengths, block tables, or kernel metadata. The semantic predicate must remain invariant. In particular, a bare is_causal=True is safe only when that backend’s non-square alignment is known to implement this same relation for the declared cache layout.

0x04D Logit/K/V Offset And Layout Equivalence

The target distribution that scores d_i is produced before d_i becomes an input row, while KV(d_i) is produced by that input row. Using logical identities rather than raw slices makes the invariant visible:

Both layouts must therefore extract the same logical tuple:

$$\left( [p_1,\ldots,p_K], p_{K+1}, [KV(d_1),\ldots,KV(d_K)] \right).$$

They differ only in whether p_1 and KV(x_t) already exist at round start. The Loop 6 oracle compiles both layouts from the same token trace and rejects off-by-one logit slices, duplicate frontier positions, shifted positions, or a candidate K/V slice that accidentally includes KV(x_t).

0x04E Packed Requests Require Segment-Local Causality

Flattening verification rows from several requests does not create one longer sequence. If request A contributes positions 3..5 and request B contributes positions 8..9, absolute position order alone would incorrectly allow B to read A. The complete predicate needs both terms:

visible = (
    query.request_id == key.request_id
    and key.absolute_position <= query.absolute_position
)

The resulting logical mask is block diagonal by request and causal within each block. Request-local position ids may restart at zero; globally unique packed positions are not required. What is required is that token rows, position ids, request/segment ownership, cache handles, and extracted logits remain aligned through every gather and scatter.

This article owns that visibility contract for a linear speculative path. It does not own page allocation, continuous-batch admission, ragged scheduling, or request migration. Those mechanisms belong to M5 and M7.8, but they must preserve this relation.

0x04F Numerical And Processor Boundary

The verification tensor contract also freezes representation:

Logits processors are not applied once to an undifferentiated K x vocab matrix when they carry state. Each p_i and q_i must be produced at its own logical history under the manifest from Section 0x01. Loop 9 owns framework integration for those processors; Loop 10 tests backend parity. Loop 6 fixes the tensor coordinates they must consume.

0x04G Integrated Gradient-Free Oracle Contract

The previous sections prove separate pieces: one-token coupling, prefix induction, tensor alignment, and transactional publication. A useful implementation test must compose them. The Loop 10 oracle uses a two-token vocabulary, two drafted positions, and a three-token comparison horizon. It executes no training and no autodiff; every result comes from forward probability rows, finite enumeration, random draws, and token-identity state transitions.

Its immutable coordinate includes:

target and draft raw-logit tables by causal prefix
ordered temperature and additive-bias processors
vocabulary order and K = 2
target, proposal, acceptance, and terminal RNG stream identities
retained_frontier and replay_frontier cache layouts
reference and online-softmax probability backends
Monte Carlo seed and sample count

This is a synthetic contract test, not a quality benchmark. The vocabulary is deliberately tiny so every output sequence and state branch can be audited exactly.

0x04H Exact Enumeration Before Sampling

For each draft path $\hat{x}_{1:K}$, the oracle multiplies its processed proposal conditionals, enumerates first rejection at every reachable position, samples correction mass from $[p_i-q_i]_+$, and uses the processed target row for the all-accepted bonus. A short branch is completed with ordinary target transitions to a fixed horizon. The resulting speculative joint is then compared with the direct target chain:

$$P_{target}(x_{1:3}) = p_1(x_1)p_2(x_2\mid x_1)p_3(x_3\mid x_{1:2}).$$

The equality check is over all eight sequences, not only one-token marginals. This catches implementations that accidentally look correct at the first position but use the wrong correction row, continue after rejection, or draw the bonus from q.

for draft_path, q_path_mass in enumerate_draft_paths(K=2):
    for first_rejection in reachable_positions(draft_path):
        branch_mass = q_path_mass * accepted_prefix_mass * rejection_mass
        emit correction from normalize(max(p_i - q_i, 0))
        complete to horizon with ordinary target transitions

    emit all-accepted path + bonus from target row after full draft

assert speculative_joint == target_joint

0x04I Seeded Monte Carlo Is A Secondary Check

Exact enumeration is the correctness oracle. Seeded Monte Carlo is a second implementation path that can expose draw-order and branch-state mistakes. Each sample uses distinct proposal, acceptance, terminal, and ordinary-completion streams. It records:

draft path and proposal draws
reached acceptance draws only
first rejection or all-accepted outcome
correction/bonus draw
ordinary target completion draws
emitted three-token sequence
accepted draft count
published output, K/V identities, frontier, and RNG counters

The empirical joint is required to fall within a declared finite-sample tolerance of the exact target joint. Passing that tolerance does not replace the exact proof: a stochastic test can miss a low-probability bug, while exact enumeration cannot model production floating-point and kernel behavior by itself. They test different failure surfaces.

0x04J Backend, Layout, And State Parity

The oracle evaluates every processed row with two gradient-free probability implementations:

1. a conventional max-shift softmax;
2. an online (m,l) merge over vocabulary blocks.

Both must agree within the declared numerical tolerance before the coupling is evaluated. This is backend arithmetic parity on the fixture, not a claim that arbitrary fused GPU kernels are bitwise identical.

For every sampled branch, retained-frontier and replay-frontier layouts must publish the same logical successor:

$$C_{next}=O_{next}[:-1], \qquad F_{next}=O_{next}[-1].$$

The cache comparison uses token identities, not only lengths. Accepted draft rows may be committed; rejected rows and the correction/bonus frontier may not. Target RNG accounting must equal reached acceptance events plus one terminal draw, while proposal draws remain on their own stream.

Those are local synthetic results, not measured acceptance or latency claims.

0x05 Speedup Ledger

0x05A The Accepted Prefix Is A Random Variable, Not One Rate

Let $A\in\{0,\ldots,K\}$ be the number of accepted draft tokens. Define the survival probability:

$$s_j=\Pr(A\geq j),\qquad s_0=1.$$

The complete accepted-prefix distribution follows from adjacent tails:

$$\Pr(A=a)=s_a-s_{a+1}\quad(0\leq a<K), \qquad \Pr(A=K)=s_K.$$

This representation does not assume independent acceptance. Define the reach-conditioned probability:

$$\alpha_i^{reach} = \Pr(\text{draft }i\text{ is accepted}\mid A\geq i-1).$$

Then the chain rule gives the exact tail:

$$s_j=\prod_{i=1}^{j}\alpha_i^{reach}.$$

Each $\alpha_i^{reach}$ averages only over prefixes that actually reach position $i$. Multiplying acceptance rates estimated over all proposed rows, including unreachable suffixes, estimates a different quantity.

The expected number of accepted draft tokens is:

$$E[A] = \sum_{j=1}^{K} P(\text{first } j \text{ draft tokens accepted})$$

Let alpha_i be the acceptance probability at speculative position i, averaged over prefixes that reach that position. Then:

$$E[A] = \sum_{j=1}^{K}\prod_{i=1}^{j}\alpha_i.$$

Under the simplifying assumption alpha_i = alpha:

$$E[A] = \alpha+\alpha^2+\cdots+\alpha^K = \frac{\alpha(1-\alpha^K)}{1-\alpha}.$$

0x05B Round Progress Includes Correction Or Bonus

Without an EOS or length-limit stop, each speculative iteration makes E[A] + 1 expected output-token progress: either the first rejected position is replaced by one correction token, or all K drafts are accepted and one bonus target token is sampled.

Let $G$ be committed output-token progress in one round. Without a stop event:

$$G=A+1, \qquad E[G]=1+\sum_{j=1}^{K}s_j.$$

Let $H$ be the earliest stopping distance: the first emitted stop token or the remaining output budget, whichever comes first. Take $H=\infty$ if neither limits this round. The request publishes no later tokens:

$$G=\min(A+1,H).$$

This stop-aware form matters near EOS. Counting a target bonus after an accepted EOS, or continuing acceptance tests after a stop automaton terminates the request, inflates both progress and RNG use.

0x05C Separate Draft, Verify, State, And Queue Cost

For batch/workload coordinate $B$, prefix length $L$, and lookahead $K$, write:

$$T_{round}(K,B,L) = T_D(K) +T_V(K,B,L) +T_S(A,K) +T_Q(K,B).$$

For a stationary sequence of rounds, the renewal-reward throughput ledger is:

$$\text{time per committed token} = \frac{E[T_{round}]}{E[G]}.$$

This ratio is not generally $E[T_{round}/G]$. The first is the long-run total time divided by long-run useful tokens; the second weights short-progress rounds differently.

The conceptual speedup condition is:

$$S \approx \frac{E[A]+1} {1 + C_{draft}/C_T + C_{verify\_overhead}/C_T}$$

This is not a benchmark formula. It is a pressure ledger.

A more implementation-facing wall-time expression is:

$$T_{iteration}(K) = T_{draft}(K) + T_{target\_verify}(K) + T_{state}(K),$$ $$\text{time/token} \approx \frac{T_{iteration}(K)}{E[A]+1}.$$

T_state includes candidate packing, probability extraction, accept/reject work, cache compaction, and scheduler bookkeeping. Target verification can perform more arithmetic than one ordinary decode step while taking less wall time than K serial weight-streaming steps; speculative decoding trades serial model invocations for parallel work, not for zero work.

0x05D Recovering The Primary-Paper Closed Form

Leviathan et al. analyze a simplified coordinate: constant $\alpha_i^{reach}=\alpha$, K serial draft calls each costing a fraction $c$ of one target call, one target verification call with normalized cost 1, and negligible extra state cost. Then:

$$E[G] = 1+\alpha+\cdots+\alpha^K = \frac{1-\alpha^{K+1}}{1-\alpha},$$

and the idealized speedup is:

$$S_{paper}(K,\alpha,c) = \frac{1-\alpha^{K+1}} {(1-\alpha)(1+Kc)}.$$

For $\alpha=1$, use the continuous limit $E[G]=K+1$. This closed form is valuable because it exposes the tradeoff, but its denominator does not include shape-dependent verification overhead, cache compaction, queueing, or a target pass whose latency grows with K. Those terms must be restored before using it as a deployment prediction.

Source: Fast Inference from Transformers via Speculative Decoding, Figure 5. The wall-time trace makes the cost condition visible: additional draft calls reduce target-model serial steps only when draft cost and acceptance jointly beat the baseline.

0x05E Sensitivity: Why One Mean Acceptance Rate Is Insufficient

Two systems can have the same mean token-level acceptance but different useful progress. Early-position acceptance has multiplicative leverage because every later candidate requires the earlier prefix to survive. For K=4:

front-loaded reach acceptance: [0.95, 0.90, 0.60, 0.40]
back-loaded reach acceptance:  [0.40, 0.60, 0.90, 0.95]

same arithmetic mean, different survival tails and E[G]

The measurements needed for diagnosis are therefore:

Pr(A = a) for a = 0..K
Pr(A >= j) for j = 1..K
alpha_j^reach by position, domain, sampling policy, and prefix bucket
T_D, T_V, T_S, T_Q by K and live batch shape
temporary verification rows and bytes per committed token

Speculation helps when:

draft is cheap
draft is aligned with target
verification pass is efficient
accepted length is often greater than one

Speculation hurts when:

draft is expensive
acceptance is low
verification shape is inefficient
serving batches become harder to schedule

Draft length is therefore a control policy, not a fixed law:

Worked speedup ledger:

The denominator is normalized so one target decode step costs 1. The point is not the exact value; it is that increasing draft length does not matter if accepted progress or draft cost goes the wrong way.

0x05F Temporary-State And Batch Sensitivity

The target call materializes K candidate K/V rows in the retained layout and K+1 new rows in the replay layout, although the replayed frontier row was unavoidable ordinary decode work. Only A candidate rows survive. A useful waste ledger is:

$$E[\text{discarded draft K/V rows}]=K-E[A].$$

Temporary K/V bytes, probability buffers, masks, and graph workspaces scale with proposed or verified rows, while persistent cache growth scales with accepted rows. At high live batch, those temporary rows can reduce the number of requests admitted to the target step. Thus a K that minimizes latency for one isolated request can reduce aggregate goodput.

The Loop 8 oracle evaluates several nonuniform acceptance profiles over K=1..8 with explicit draft, verification-shape, state, and batch-pressure terms. It selects an interior optimum when one exists and rejects fixtures that use unreachable suffix rates, omit the correction/bonus progress token, or hide a negative cost. M7.8 owns the real scheduler controller; this section provides the one-request and work-surface quantities that controller must measure.

0x06 KV Commit And Rollback

M5’s KV lesson applies directly.

Speculative candidates are not committed history until accepted. The authoritative frontier token is different: under replay_frontier it was already emitted before the round and its target K/V row must be committed from the verification call even when the first draft is rejected.

main KV:
    prefix that the request has really emitted

branch KV:
    target verification state for candidate positions

commit:
    accepted prefix only

discard:
    rejected suffix and unchosen branches

Count published tokens, not only accepted proposals. Let $A_{\mathrm{emit}}$ be the number of accepted draft tokens actually emitted after EOS/length-limit truncation. Then emitted-output growth is:

$$\Delta T_{output} = A_{\mathrm{emit}} + \mathbf{1}_{\{\text{correction or bonus emitted}\}}$$

The indicator is one for either an emitted correction after rejection or an emitted bonus after full acceptance. Under the immediate-terminal convention used here, a round without stopping has A_emit = A and emits exactly one of these tokens, so output grows by A + 1. A bonus deferred to a later round is not counted in the current round.

Apply stopping before publication. If EOS or the remaining output budget is reached inside the accepted prefix, truncate that prefix and omit the later correction/bonus. If the correction or bonus itself is EOS or reaches the length cap, count it once and finish. Zero remaining budget dispatches no round. A stopped request must not resume merely to materialize a cache frontier.

full acceptance, no stop:
    proposals = [d_1, d_2, d_3]
    output append = [d_1, d_2, d_3, bonus b]
    A_emit = 3; terminal emitted = 1; output growth = 4
    new accepted target KV rows = 3; bonus KV remains pending

length cap after d_3:
    output append = [d_1, d_2, d_3]
    A_emit = 3; terminal emitted = 0; output growth = 3

EOS at d_2:
    output append = [d_1, d_2=EOS]
    A_emit = 2; terminal emitted = 0; output growth = 2

Replaying the previously emitted frontier can add one more target K/V row, but never another new output token. Thus the no-stop full-acceptance example adds three target rows in retained_frontier, or four in replay_frontier, while both layouts emit the same four new tokens. These target-row counts do not describe draft-model K/V; that separate ledger is owned by M7.8.

That is not the same as branch-cache K/V growth. The target verification pass produced branch K/V for the proposed draft tokens. If token i is rejected and the correction token differs from the rejected draft token, the correction token’s K/V row is not safely available from that rejected branch row.

Safe K/V rule:

commit from verification branch:
    replay_frontier:
        the authoritative frontier row
        accepted draft-token K/V rows
    retained_frontier:
        accepted draft-token K/V rows only

discard:
    rejected draft-token K/V row
    every later draft-token K/V row

correction or bonus token:
    emitted as output now, if not suppressed by stopping
    not supplied by an accepted draft-token K/V row
    if decoding continues, receives its own target K/V row through a valid append path

A runtime that commits rejected branch K/V has corrupted the request state. A runtime that treats a correction token as if it owned the rejected draft token’s K/V row has the same bug.

Toy state trace:

draft length K = 4
target accepts first A = 2 draft tokens
third token rejected
correction token emitted

output tokens emitted:
    accepted draft token 1
    accepted draft token 2
    correction token

branch K/V committed from verification in replay_frontier layout:
    previously uncached authoritative frontier token
    accepted draft token 1
    accepted draft token 2

correction-token K/V:
    not taken from rejected draft token 3
    computed by a later target append/verification path

discard:
    candidate token 3 branch state
    candidate token 4 branch state

The rejected suffix may have been useful for verification work, but it is not request history.

0x06A One Round Is A Transaction, Not A Sequence Of In-Place Appends

The target verification call creates enough temporary data to describe several possible outcomes. None of those outcomes should mutate the authoritative request while acceptance is still being decided. Freeze a round-start snapshot S_0, build a staged transaction txn, and publish one successor S_1:

ROUND_READY
    authoritative output, K/V, frontier, position, processors, RNG counters
        |
        v
VERIFIED_TEMPORARY
    drafts, q rows, p rows, branch K/V, acceptance uniforms
        |
        v
DECIDED
    accepted count A, terminal kind, emitted suffix, rows to commit/discard
        |
        v
STAGED
    complete successor state assembled off to the side
        |
        +---- validation/failure ----> ABORTED -> S_0 remains authoritative
        |
        v
PUBLISHED
    one generation/version fence makes S_1 authoritative

Publication must move one coherent state vector:

$$S= (O,C,F,P,G,R,V),$$

where O is emitted output, C committed target K/V, F the optional unprocessed output frontier, P position/length state, G grammar and other stateful processors, R RNG stream counters, and V the request generation. Publishing only O and repairing the rest later creates an externally visible state that no serial target execution could have produced.

0x06B Zero, Partial, And Full Acceptance Produce Different Suffixes

Let A be the number of accepted draft tokens before the first rejection. Ignoring an earlier stop token, exactly one of these terminal paths occurs:

The common postcondition for an unfinished request is:

authoritative output = tokens represented by committed K/V + exactly one frontier token

For a finished request, retaining a K/V row for the final stop token is a storage policy, not a prerequisite for future generation. The output and stop decision must still be published atomically.

0x06C Layout-Specific Rows, Layout-Independent Successor

The physical row slices differ, but both layouts must publish the same logical successor. The following fragment assumes no stop has truncated the accepted prefix and one correction/bonus is actually emitted; stopped outcomes must use the publication rule above instead. Let accepted = branch_kv.draft_rows[:A]:

def stage_kv_successor(start, branch_kv, A, layout):
    if layout == "retained_frontier":
        assert start.frontier is None
        assert start.cache_tokens == start.output_tokens
        base = start.cache_tokens
    elif layout == "replay_frontier":
        assert start.frontier == start.output_tokens[-1]
        assert start.cache_tokens == start.output_tokens[:-1]
        assert branch_kv.frontier_row.token == start.frontier
        base = start.cache_tokens + [branch_kv.frontier_row.token]
    else:
        raise UnknownVerificationLayout(layout)

    staged_cache = base + branch_kv.draft_tokens[:A]
    staged_output = start.output_tokens + draft_tokens[:A] + [terminal_token]

    assert staged_cache == staged_output[:-1]
    return staged_cache, staged_output, terminal_token

The assertion is stronger than a length check. It compares token identities: a same-shaped K/V row generated from the rejected token cannot represent a correction token. The correction or bonus remains F, the unprocessed frontier. Before a later target call can condition beyond it, that call must materialize KV(F) at the next absolute position.

The replayed KV(x_t) is not speculative. It represents output that was already authoritative before the round, so it is committed even when A=0. Conversely, KV(d_(A+1)) is discarded even though the target computed it, because that draft was rejected.

0x06D RNG And Stateful Processors Follow Reached Events

Use separately identified draft and target-side streams. A canonical target-side draw schedule for a linear K-draft round is:

The proposal model owns the draws that sampled d_1..d_K from q. The target transaction owns acceptance uniforms and the correction/bonus sample. A runtime may reserve counter ranges in advance, but its manifest must define which counters become the successor state. A retry of the same unpublished transaction must not silently allocate a new set of target-side random choices.

Stateful processors advance over the published token sequence, not over every verified candidate:

processor_state = clone(start.processor_state)
for token in draft_tokens[:A]:
    processor_state.advance(token)
processor_state.advance(terminal_token)

That order matters for grammars, repetition/frequency penalties, stop-string automata, and watermark state. The precomputed processor state after rejected d_(A+1)..d_K is discarded. The successor RNG counters and processor state are staged alongside output and K/V, then published under the same generation fence.

0x06E Failure Injection, Retry, And Idempotent Publication

A useful transaction record is explicit enough to audit without reading cache bytes:

@dataclass(frozen=True)
class SpeculativeCommit:
    request_id: str
    round_id: str
    expected_generation: int
    layout: str
    accepted_draft_count: int
    terminal_kind: Literal["correction", "bonus", "stop"]
    emitted_token_ids: tuple[int, ...]
    committed_kv_token_ids: tuple[int, ...]
    discarded_kv_token_ids: tuple[int, ...]
    rng_before: tuple[int, ...]
    rng_after: tuple[int, ...]
    processor_before_hash: str
    processor_after_hash: str

Build and validate this record against S_0; then use a compare-and-swap on expected_generation to publish S_1. The following injected failures must leave the authoritative state byte-for-byte or semantically unchanged:

after target verification
after acceptance decision
after staging K/V rows
after staging output and processor state
immediately before generation-fenced publication

If failure happens after publication, recovery is not rollback to S_0; it is idempotent acknowledgement of the already published round_id. Publishing the same transaction twice must fail or return the same successor without appending tokens twice. Loop 7’s oracle executes these failure points for both frontier layouts and proves that their published logical successors agree.

0x06F Sampling State Invariants

Exact speculative sampling is only exact for the distribution it actually verifies. The runtime state must match the target decode state:

same prefix tokens
same position IDs
same attention mask
same tokenizer and chat serialization
same target model weights and adapters
target probabilities p after the target's intended sampling processors
actual proposal probabilities q after the draft's proposal processors
p_i and q_i conditioned on the same candidate prefix at position i
same stateful target constraints at the same logical output position

The target and draft do not need the same temperature, top-p, or top-k transformation. Exactness requires p to be the distribution the user intends to sample from and q to be the actual distribution that generated the proposal. The acceptance ratio must use those two post-processed distributions. Reusing raw draft logits after sampling from a truncated q, or advancing a grammar/repetition-penalty state along rejected tokens, breaks the proof.

Stateful processors need branch semantics just like KV:

candidate-local:
    grammar state
    repetition/frequency counters
    stop-sequence automaton
    RNG draws used for proposal and acceptance

commit:
    accepted prefix state only

repair/advance:
    correction or bonus token through the target output-state path

Acceptance logging should include:

draft_token
q_prob
p_prob
accept_ratio = min(1, p_prob / q_prob)
uniform_sample
accepted_or_rejected
correction_distribution_id
committed_token_count

Without that log, debugging a low-acceptance deployment becomes guesswork: the issue could be draft quality, position mismatch, sampling mismatch, or a KV commit bug.

0x06G Draft Sources And Runtime Integration

The exact accept/reject contract does not require q to be one particular kind of model:

Serving integration must account for two independently shaped workloads:

draft workload:
    K serial cheap steps, or one head/module/tree proposal step

target workload:
    one verification sequence/tree with K or more temporary positions

A continuous-batching scheduler can group target verification rows by compatible shape, but a request with low acceptance may consume many temporary tokens while committing one output token. Useful telemetry therefore includes:

accepted_draft_tokens / proposed_draft_tokens
committed_output_tokens / target_verification_positions
draft_time, verify_time, state_repair_time
temporary_KV_bytes, committed_KV_bytes
TPOT and throughput with speculation enabled and disabled

The right comparison is the end-to-end serving objective under the same traffic, not isolated draft-model latency.

0x06H Version-Pinned Transformers Integration Coordinate

The probability and state contracts above are framework-independent. A framework trace is still useful, but only after its version is frozen. The concrete coordinate used here is Hugging Face Transformers commit b317ff31cd2491c2d4fc05d25fa06f35c527bcf6, committed on 2026-08-03. The evidence package records whole-file hashes for generation/utils.py and generation/candidate_generator.py; line links below are observations of that snapshot, not promises about every Transformers release.

At that coordinate, generate() selects assisted decoding and constructs a CandidateGenerator. The dispatch distinguishes a smaller assistant, prompt lookup, MTP, early exit, same-tokenizer assistance, and two different-tokenizer paths. The public assisted-decoding guide describes these user-facing choices; the pinned generator dispatch reveals which implementation owns each one.

The snapshot also imposes a narrower admission contract than the abstract algorithm:

These restrictions are Externally verified for the pinned source only. They are not inherent limitations of speculative decoding.

0x06I Candidate Generator To Target Verification Call Trace

The pinned _assisted_decoding loop realizes the logical round in seven concrete steps:

1. candidate_generator.get_candidates(input_ids)
       -> candidate_input_ids [1, T + K]
       -> candidate_logits    [1, K, |V_target|] or None

2. prepare target attention mask, token types, positions, and cache view

3. target forward(candidate_input_ids)
       -> new_logits [1, K + 1, |V_target|]
       -> temporary target K/V covering candidate input rows

4. apply target logits processors separately at logical prefixes
       prefix_i = candidate_input_ids[:, :T + i]

5. select accepted draft prefix plus one correction/bonus token

6. append selected output tokens, then crop unused target K/V rows

7. update proposal strategy and target generation kwargs

Step 3 requests K+1 target rows because the final row supplies the all-accepted bonus distribution. Step 4 matters just as much as the target forward: the raw model logits are converted into the processed target rows actually owned by the decoding policy. The source promotes the verification slice to float32 before these manipulations.

Cache cropping exposes the same frontier invariant derived in Loop 7. With m accepted drafts out of K, the snapshot crops K-m rows from the target result. The accepted draft-token rows remain cached; the correction or bonus token has been emitted but is still the next uncached frontier. When all K drafts are accepted, the source explicitly notes that the bonus token is not yet in cache, so a negative crop must not occur.

0x06J Processed Probability Rows And Stateful Sampling

For exact sampling, p_i and q_i are not arbitrary model softmaxes. They must be the distributions that actually generated and verify draft event \hat{x}_i after temperature, masking, penalties, grammar constraints, and every other transform owned by the decoding policy:

$$q_i = \operatorname{softmax}\!\left(\mathcal{P}_q(\ell_i^q;H_i)\right), \qquad p_i = \operatorname{softmax}\!\left(\mathcal{P}_p(\ell_i^p;H_i)\right).$$

Here H_i is the same published history plus the already accepted/proposed prefix relevant to row i. The pinned same-tokenizer candidate generator passes the configured logits processors into the assistant’s generate() call and returns its generated score rows; the target loop reapplies its processors one candidate position at a time before _speculative_sampling converts both tensors to probabilities. The latter then computes the ratio and positive residual in the shared vocabulary. See the pinned AssistedCandidateGenerator and _speculative_sampling.

That source trace supports prefix-derived processors. It does not prove that an arbitrary custom processor with hidden mutable state can be replayed safely across speculative branches. Such a processor needs one of two stronger contracts:

pure replay:
    processor output is a deterministic function of published prefix + row prefix

transactional state:
    speculative updates are staged per row and only reached events are published

Proposal RNG, acceptance RNG, and target correction/bonus RNG must likewise remain distinguishable. The assistant’s confidence threshold decides when to stop proposing; it is not the acceptance probability and must never replace min(1,p/q). A heuristic num_assistant_tokens update changes future work allocation, not the current round’s target law.

0x06K Same-Tokenizer And Universal Tokenizer Contracts

With a shared tokenizer and vocabulary, draft ID v names the same event for both models, so p_i(v)/q_i(v) is well-typed. A different tokenizer destroys that assumption: one assistant token can map to part of a target token, several target tokens, or a context-dependent segmentation. Equal integer IDs are irrelevant.

The pinned implementation exposes two distinct solutions:

1. Different-tokenizer greedy assistance. AssistedCandidateGeneratorDifferentTokenizers decodes a lookbehind window to text, re-encodes it, and finds an aligned token subsequence before target-prefix validation. It returns no proposal-logit tensor, so the stochastic p/q rule is not invoked.
2. Different-tokenizer sampling. UniversalSpeculativeDecodingGenerator translates both candidate IDs and candidate logits into the target event space before returning them to _speculative_sampling.

The general type rule is:

ratio_allowed(p, q) only if:
    p.event_space == q.event_space
    candidate_identity is expressed in that event space
    processor semantics refer to the same published history

Re-encoding plus longest-common-subsequence alignment is an implementation choice, not a mathematical identity between tokenizers. Lookbehind lengths therefore belong to the versioned runtime coordinate. A tokenizer-normalization mismatch, lossy decode/re-encode, unmapped special token, or stale alignment window is an admission failure, not something the acceptance ratio can repair.

0x06L Cache Crop, Stop, And Unsupported Mode Boundary

The implementation trace closes four operational distinctions:

The source rejects static, hybrid, and sliding-window target cache classes at this coordinate because assisted decoding calls a crop-able dynamic-cache interface. It also rejects batches larger than one. Those checks are valuable evidence of what this implementation can execute, but they must not be generalized into claims that speculative serving cannot batch or use specialized cache layouts. M7.8 owns those broader runtime designs.

A release should pin and test this entire coordinate:

framework commit and model revisions
candidate-generator class
target and assistant tokenizer revisions
vocabulary mapping or lookbehind settings
logits processor list and configuration
sampling mode and RNG streams
cache implementation and crop behavior
draft-length schedule and confidence threshold

Changing any item can change proposal cost, acceptance, or state transitions even when the public generate() call looks unchanged.

0x07 Failure Lab

0x07A Failure Classes Are Executable Contracts

The table below is not an anecdotal checklist. Its rows are keyed in the Loop 11 failure-test matrix to a concrete oracle mutation, sensitivity profile, source-scope assertion, or versioned admission test. Shape-compatible failures are especially important: a shifted logit row, stale processor state, or wrong-token K/V row can pass ordinary tensor-shape checks while changing the target law.

0x07B Source, Visual, And Link Closure

The publication package audits the article as a graph rather than trusting the reference list by inspection:

External reachability is time-scoped. A passing URL check does not verify the technical claim behind the URL; claim scope remains the job of source_manifest.json. Conversely, a later transient URL failure does not invalidate a hash-pinned local source observation, but it does block a fresh publication audit until the reference is repaired or archived.

0x08 Boundary To The Rest Of M7

M7.1 owns the exact draft-model contract.

M7.2:
    Medusa same-model heads and tree attention

M7.3:
    Lookahead Jacobi/n-gram generation

M7.4:
    multi-token prediction objectives and shared-trunk gradients

M7.5-M7.6:
    EAGLE-family feature drafting and DeepSeek MTP modules

M7.7:
    draft-source alternatives, dependent heads, multi-candidate exactness,
    and hardware-aware tree topology

M7.8:
    continuous-batch scheduling, dynamic K, evaluation, release, and rollback

All of them must still answer the same two questions:

what proposed tokens were accepted?
which K/V became committed history?

0x09 Publish Gate

0x09A Final Formula And Symbol Registry

The final audit treats the mathematics as an ordered program, not as isolated typesetting. The evidence package extracts every display equation in article order, records its owning heading and normalized LaTeX, and hashes the result. There are 59 display-formula blocks at this publication coordinate. A change in their count, order, section owner, or normalized content therefore requires an intentional registry update.

The registry does not pretend that notation is global merely because the same letter appears twice. It freezes the scopes that matter to the derivation:

Inline notation remains checked through section markers and browser rendering; the display registry is the exact article-wide formula stream. Synthetic oracles validate the probability, tensor, state, and cost identities they can execute. They do not turn source-reported throughput into local measurement.

0x09B Cross-Article Ownership Proof

M7.1 must be deep without absorbing the articles that consume its sampler. The final boundary manifest resolves each route to source Markdown and checks an exact owner heading in that source:

This is a dependency graph, not a summary hierarchy. M5.1 supplies state semantics below this article; M7.2 and M7.7 change the proposal graph above it; M7.8 schedules and evaluates many such rounds around it. None of those changes licenses replacing M7.1’s exact one-draft coupling with a shape-compatible heuristic.

0x09C Evidence Coordinate And Residual Limits

The final package closes four different claims independently:

formula closure:
    59 ordered display blocks + symbol registry + executable arithmetic oracles

source closure:
    1 hash-pinned A30 source + 5 primary papers + 5 official implementation entries

render closure:
    22 registered image routes + desktop/mobile MathJax, link, image, and overflow checks

boundary closure:
    M5.1, M7.2, M7.7, and M7.8 source paths + owner headings + local routes

The remaining limitation is explicit: this repository has not run a target and assistant model to produce hardware latency, measured acceptance, or serving goodput for M7.1. Exact synthetic enumeration proves the declared probability and state contracts on finite fixtures. Deployment performance remains a versioned measurement owned by M7.8.

0xFF Reference

• Transformer Series A30 - Decoding Speculation
• M5.1 - Autoregressive Serving State
• M7.2 - Medusa Tree Verification
• M7.7 - Draft Sources and Hardware-Aware Trees
• M7.8 - Speculative Serving
• Fast Inference from Transformers via Speculative Decoding
• Blockwise Parallel Decoding for Deep Autoregressive Models
• Speculative Decoding: Exploiting Speculative Execution for Accelerating Seq2seq Generation
• Accelerating Large Language Model Decoding with Speculative Sampling
• SpecInfer: Accelerating Generative Large Language Model Serving with Tree-based Speculative Inference and Verification
• Transformers assisted decoding guide
• Transformers text-generation configuration
• Pinned Transformers assisted-decoding source
• Pinned Transformers candidate-generator source
• vLLM speculative decoding documentation