The verifier is a coupling, not a judge

Let the target model define the next-token distribution p after the current prefix. Let a cheaper draft model define q over the same token space. The draft samples a token x from q. The task is not to prove that x is true, sensible or equal to an independently sampled target token. It is to decide whether this particular draft draw can stand in for a draw from p.

The acceptance rule is surprisingly small. Accept the proposed token with probability min(1, p(x)/q(x)). When the draft gives a token less mass than the target does, every occurrence can be accepted. When the draft overproduces a token, accept only the fraction needed to reduce its mass to the target level. The ratio is evaluated only for a sampled proposal, so its draft probability is positive; target mass on tokens the draft never proposes reappears through the residual branch.

Accepted proposals contribute probability mass q(x)a(x) = min(p(x), q(x)). That is the overlap between the two distributions at token x. The draft may still under-supply tokens to which the target assigns more probability. The rejection branch must restore precisely that missing mass, not sample from the full target distribution again.

Define the positive residual as (p(x) - q(x))+, meaning the difference when it is positive and zero otherwise. Normalise those deficits into a repair distribution. The total rejection probability is exactly the total missing mass, so the two branches add back to p.

This is a form of maximal coupling. It makes the two draws equal with the largest probability available to any coupling of p and q. The resulting acceptance probability is the total overlap:

TV is total-variation distance. At a fixed prefix, a smaller distance gives a larger maximum acceptance probability. This formalises the useful part of “draft quality”, but it does not yet say whether the drafter is cheap enough or whether the target can score a block efficiently.

A three-token worked example

Suppose the vocabulary is A, B and C. The target assigns probabilities .50, .30 and .20. The draft assigns .60, .10 and .30. A draft proposal of A is accepted with probability .50/.60, or five sixths. B is always accepted because the draft produces too little B. C is accepted with probability .20/.30, or two thirds.

If a rejection occurs, the repair distribution chooses B with probability one. The final output masses become .50 for A, .10 plus .20 for B, and .20 for C. They are exactly the target probabilities.

A tempting alternative keeps the correct acceptance probabilities but, after a rejection, resamples from the whole target distribution. Accepted proposals contribute .50, .10 and .20. The .20 rejection branch then adds .10, .06 and .04, producing final masses .60 for A, .16 for B and .24 for C. It feels conservative because the target is consulted after rejection, yet it is biased. Target mass already represented by accepted proposals is counted again. The residual distribution is not an implementation detail. It is the correction that makes the shortcut exact.

flowchart TD
  A["The hundred-sided die that<br/>should never miss"] --> B["The verifier is a coupling,<br/>not a judge"]
  B --> C["From one coupled draw to a<br/>verified block"]
  C --> D["Exact is not yet fast"]
  D -. "re-test" .-> A
  classDef first fill:#0a1424,stroke:#B96D00,stroke-width:2px,color:#e6f3ff
  classDef step fill:#0a1424,stroke:#3f7da0,stroke-width:1px,color:#e6f3ff
  class A first
  class B,C,D step

From one coupled draw to a verified block

An autoregressive target normally performs one sequential target-model step per committed token. Speculative decoding changes the schedule. The draft model first generates γ candidate tokens autoregressively. Because the entire candidate block is now known, the target can score the conditional distribution at every candidate position in one teacher-forced forward pass. The target is still evaluated at the correct proposed prefixes; those evaluations are merely arranged as parallel tensor work rather than separate serial calls.

Verification then proceeds from left to right. Each token is accepted with the coupling rule using the target and draft distributions at that position. Accepted tokens extend the authoritative prefix. At the first rejection, the verifier draws one repair token from the positive residual and stops. Every later proposal is discarded.

If all γ proposals are accepted, the target pass can supply one additional next-token distribution. Sampling that bonus token means a successful round commits γ + 1 tokens. A failed round commits the accepted prefix plus one repaired token. Either way, at least one target-distributed token is committed.

The first rejection is a causal cut

Consider a draft continuation for a build log: “status green, deploy now, notify team”. The target accepts “status”, rejects “green” and repairs it to “red”. The later draft tokens were generated under the prefix “status green”. They are not proposals for the new prefix “status red”. Keeping “deploy now” because its standalone probability looks high would evaluate the wrong conditional world.

This is why a speculative round accepts a prefix rather than an arbitrary subset. Tree-based methods can preserve several alternative prefixes long enough for parallel verification, but every retained branch still needs a valid conditional history. Wider candidate trees trade more chances of finding a long accepted path against more target computation spent on branches that will be discarded.

The whole decoder needs a commit boundary

Visible tokens are only one part of autoregressive state. A serving engine may also advance a target KV cache, a draft KV cache, grammar state, stop-sequence matching, repetition counters, random-number state, streaming buffers and usage accounting. During speculation, all state derived from an unverified suffix is provisional. Commit means advancing every authoritative state component to the same accepted prefix, not merely appending text to a socket.

Consider a second thought experiment. Two implementations propose the same four-token block and use the same correct acceptance rule. Both accept the first two tokens and reject the third. Implementation A rolls every state component back to the two-token prefix before inserting the repair token. Implementation B removes the rejected text but leaves its repetition counter and grammar automaton one step ahead. The visible prefix is identical, yet the next target distribution can differ because one decoder remembers a token that officially never happened. Only the state-commit rule changed.

The target KV cache needs equally careful treatment. A block-verification pass computes target activations for proposed prefixes. Cache entries corresponding to accepted tokens can become authoritative. Entries after the first rejection cannot, because they encode a counterfactual continuation. The repair token then needs target-consistent state before the next round. Implementations differ in how they stage, slice or recompute these tensors, but the invariant is stable: no rejected branch may influence a later target step.

Streaming makes the boundary observable. Emitting draft text before acceptance can reduce apparent latency, but retraction changes the user contract and may trigger downstream work on text that later disappears. The safer default is to stream only committed tokens. Similar care applies to end-of-sequence tokens and stop strings. A stop condition proposed inside a rejected suffix must not terminate generation, while an accepted stop condition must prevent a bonus token from leaking beyond the baseline contract.

The exact method reaches a hard failure boundary when the engine cannot align target and draft token spaces, apply the same sampling transformation, or roll all consequential state back to the accepted prefix. At that point the system may still implement an approximate accelerator, but it should not claim distribution-preserving substitution. This boundary is operational rather than philosophical: it can be tested with state snapshots, forced rejections and replay.

What exactness does and does not mean

The phrase “lossless decoding” is easy to overread. For stochastic sampling, the defensible claim is distributional: after applying the declared target sampling transformation, the output distribution matches target-only decoding under ideal arithmetic and a correct verifier. It does not promise that two independent runs emit the same text. Independent samples from the same distribution normally differ.

For greedy decoding, the contract is simpler. The draft prefix is retained while its top token agrees with the target’s top token; at the first mismatch, the target token wins. This recovers the same deterministic sequence when the baseline and speculative paths use numerically equivalent target computations. Blockwise parallel decoding established this deterministic precursor before modified rejection sampling extended the idea to stochastic generation.

The target distribution itself may include temperature, top-k, nucleus filtering, repetition penalties, grammar constraints or another logits processor. Exactness is relative to that transformed target distribution. A verifier that computes acceptance from pre-transformation logits while the baseline samples post-transformation probabilities is preserving the wrong object.

Nor does target equivalence imply factual accuracy, safety or good judgement. The method reproduces the target’s errors as faithfully as its strengths. Verified acceleration verifies distributional authority, not semantic truth.

Proposal sources do not confer authority

The proposal can come from a smaller model, an n-gram lookup, extra future-token heads, a feature-level predictor or a tree of candidates. Medusa, EAGLE and SpecInfer explore different points in this design space. Official serving stacks now expose several of them, including n-gram, draft-target, Medusa and EAGLE-style paths.

Those proposal mechanisms change cost, acceptance and operational complexity. They do not by themselves prove exactness. The verifier and sampling path decide that. Some systems deliberately use typicality thresholds or other approximate acceptance rules to gain speed while aiming to retain generation quality. That is a legitimate engineering choice when declared, but it is a different contract from exact target-distribution sampling.

Exact is not yet fast

Speculative decoding replaces serial target calls with extra work: draft generation, target block verification, probability correction, cache management and scheduler coordination. The method wins only when the expected number of committed tokens per round is large enough to amortise that work.

Under a simplifying assumption that each draft token is accepted independently with probability α, a window of γ draft tokens commits the following expected number of tokens, including the repair or bonus token:

The independence assumption is a model, not a property of language. Acceptance varies by prefix, token position and request. When α = 1, the expression is interpreted by its limit, γ + 1. The equation remains useful because it exposes diminishing returns. Extending the draft window adds the next term α^γ, which can become small while draft and verification costs continue to rise.

Let B be the measured cost of one baseline target decode step, Dγ the cost of producing a draft block, Vγ the target’s block-verification cost and H all other overhead. A practical first-order speed estimate is:

This form deliberately refuses to assume that verifying five tokens costs exactly the same as decoding one. That approximation can be reasonable for a short block on an under-utilised, memory-bound target, but it can fail under long contexts, wide trees, large batches or compute-saturated hardware. Measure Vγ on the actual engine.

Acceptance is not throughput

A larger draft model usually approximates the target better and can raise acceptance. It also costs more per draft step, occupies more memory, carries another KV cache and can complicate placement. The best drafter is therefore not the one with the highest token acceptance rate. It is the one that maximises committed target-equivalent tokens per unit of constrained resource.

Yan and colleagues measured this conflict directly: across candidate drafters, acceptance rose with model size while throughput could fall because draft latency grew faster than the accepted span. Their resulting shallow, wider draft designs target decode latency and KV-cache cost rather than generic language-model quality. The experiment changes the model-selection question from “which small model is best?” to “which proposal mechanism lies on this target, hardware and workload frontier?”

Thought experiment: one target, two schedulers

Hold the target weights, drafter, prompts, sampling settings and acceptance distribution fixed. Place the same decoder behind two schedulers. Scheduler L serves one interactive request at a time. Each target decode step moves a large model through memory to produce one token, while much of the accelerator's arithmetic capacity remains idle. A short verification block can reuse that expensive weight movement to score several positions, so accepted proposals replace serial calls.

Scheduler H continuously batches enough requests to keep the same accelerator busy. Its baseline step already scores many useful next tokens in parallel. Speculative verification now adds proposed tokens and rejected suffixes to an occupied machine. The mathematical coupling has not changed. The acceptance rate has not changed. Only the opportunity cost of verification has changed, yet the performance verdict can reverse.

This thought experiment isolates why a paper-level speedup cannot be copied into a capacity plan. Acceptance measures local overlap between proposal and target distributions. It says nothing about whether verification consumes otherwise idle bandwidth, displaces useful batched work, crosses a kernel threshold or creates memory pressure that lowers the feasible batch. The same exact algorithm can be an accelerator in a latency-bound queue and a tax in a throughput-bound queue.

Batching changes the bargain

Speculation is most naturally attractive when one target decode step is latency-dominant and leaves accelerator arithmetic under-used. Continuous batching attacks the same under-utilisation by serving more requests together. As batch size grows, target verification processes more tokens across more requests and may become compute-bound. Extra draft and rejected-branch work then competes with useful work rather than filling an idle resource.

A recent production-engine benchmark, Speculative Decoding: Performance or Illusion?, evaluated several methods in vLLM across batch sizes and workloads. It found that gains generally shrank as batches grew, and that verification dominated measured execution time in many configurations. These are bounded results, not a universal law, but they reinforce the correct release test: benchmark the scheduler state and concurrency distribution that will actually be served.

Prompt processing also sits outside the accelerated loop. Speculative decoding mainly reduces decode latency. A workload with long inputs and very short outputs can remain prefill-dominated. Time to first token may be unchanged or slightly worse if the draft path adds setup. End-to-end benefit must weight prefill, queueing and decoding rather than report inter-token latency alone.

Worked scenario: a low-concurrency code assistant

Consider a synthetic code-editing service with a 420 ms prefill and a target decode cost of 20 ms per token at the intended concurrency. A typical response contains 160 new tokens, so target-only decode takes 3.2 seconds and end-to-end model time is 3.62 seconds.

A four-token drafter costs 1 ms per proposed token. The target verifies the block in 21 ms, and scheduling plus acceptance adds 1.5 ms. Offline traces estimate an average per-position acceptance of .78. The simple model gives E[N] = 3.233 committed tokens per round. Each round costs 26.5 ms, or about 8.2 ms per committed token. Estimated decode time falls to roughly 1.31 seconds and total model time to 1.73 seconds, a 2.09× end-to-end improvement.

These numbers are a worked scenario, not a deployment claim. They reveal which measurements carry the conclusion. If verification is 30 ms rather than 21, or acceptance falls on unfamiliar repositories, the gain contracts. If queueing dominates, users may see less improvement than model time suggests. If code edits repeat long prompt spans, a nearly free n-gram drafter may beat the neural drafter even with more variable acceptance.

Negative control: the baseline should win

Now hold the model family constant and move to a high-batch service whose baseline already saturates accelerator compute. Suppose the effective baseline step is 4.5 ms per request, a four-token draft costs .9 ms per token, target verification costs 9.5 ms, overhead costs 1 ms and acceptance is .55. Expected committed tokens are about 2.11, but the speculative round costs 14.1 ms. The estimated speed ratio is only .67. Speculation is slower.

Increasing drafter size may raise acceptance while making the round even more expensive. Widening a candidate tree may find a longer accepted branch while forcing the target to score many doomed tokens. Both changes improve an attractive intermediate metric and worsen the business metric.

A strong evaluation must include a fully optimised target-only decoder as a first-class negative control. It should use the same target weights, quantisation, cache policy, kernel family, scheduler, prompts, output lengths and sampling transform. Compare p50 and p95 latency, throughput at fixed service-level objectives, memory headroom, energy where material, and distributional tests. A speculative prototype beating an unbatched or poorly configured baseline proves little.

stateDiagram-v2
  [*] --> Claim
  state "Independent equality check" as Claim
  state "Distribution coupling" as Test
  state "A three-token worked example" as Revision
  Claim --> Test: expose mechanism
  Test --> Decision: evidence survives
  Test --> Revision: rival survives
  Revision --> Claim: narrow or rebuild
  Decision --> [*]

A verified-acceleration adoption instrument

Speculative decoding should enter an architecture as a replaceable scheduling optimisation around an unchanged target contract. It should not silently redefine model identity. The target version, sampling configuration, logits processors, drafter, verifier, numerical mode and fallback baseline belong in one release manifest.

The following gates turn that principle into a decision. Failing a gate does not condemn speculation forever. It identifies the evidence needed before the shortcut can carry a claim.

Close three ledgers, not one benchmark

The release decision has three independent evidence ledgers. The probability ledger names the target distribution being preserved. It records the target version, tokeniser, temperature, truncation, penalties, grammar constraints and acceptance rule. Its evidence is an analytical correction argument, property tests on known distributions and sampled regression tests on a tractable sequence space. A latency result cannot close this ledger.

The state ledger records what becomes authoritative at commit. It covers target and draft caches, random-number progression, stop conditions, repetition state, streamed output and accounting. Forced-rejection tests should snapshot these fields before and after a repair, then compare the next target distribution with a target-only replay. Distributional mathematics cannot rescue an implementation that lets a rejected suffix alter future state.

The performance ledger measures whether the shortcut is worthwhile under the served workload. It includes a matched target-only baseline, prefill and decode shares, the distribution of accepted prefix lengths, verification scaling by block size, queue depth, concurrency, memory headroom and tail latency. Report the operating envelope rather than one winning point. A configuration may pass at batch one and fail beyond batch eight, or pass for code completion and fail for open-ended dialogue.

Release requires all three ledgers to close at once. A correct but slower implementation should remain an experiment. A faster but biased implementation should be labelled approximate and evaluated under a different quality contract. A fast, exact implementation with broken rollback should remain blocked because its proof no longer describes the running system. This separation prevents a persuasive throughput graph from standing in for probability, state and operational evidence simultaneously.

Exactness tests belong beside performance tests

For greedy decoding, run exact sequence equality over a broad regression corpus, including constraints and stop conditions. For sampling, test the rejection sampler on small known distributions, then compare empirical sequence distributions in a tractable autoregressive world. Property tests should cover support mismatch, zero probabilities, identical distributions, severe draft overconfidence and the first-rejection boundary.

Do not require identical text from two independent stochastic runs. That is the wrong null hypothesis. Compare distributions, or couple random streams in a test designed for pathwise equality. Also monitor target logits across baseline and verification kernels. Official implementations warn that floating-point order, batch shape and nondeterministic operations can create small variations even when the algorithm is correct.

For operational release, preserve a target-only path that can be selected without changing the external generation contract. If the drafter fails to load, acceptance collapses, memory pressure rises or a verifier regression appears, the system should fall back to ordinary decoding rather than improvise a looser acceptance rule.

Choose the proposal mechanism from workload structure

A separate draft model is attractive when a much smaller related model is cheap and well aligned. Distillation can improve alignment without simply scaling the drafter; DistillSpec shows why on-policy data and the choice of divergence depend on task and decoding mode. An n-gram proposer has negligible model cost and can excel when outputs repeat prompt or history spans. Feature-level and multi-head drafters avoid serving an independent full model but require trained auxiliary components and engine support.

Different-tokeniser assistance is possible in current libraries through re-encoding and alignment, but it widens the correctness surface. Hugging Face’s universal assisted decoding uses tokenizer translation and longest-common-subsequence alignment. That convenience should be tested as a separate implementation contract rather than assumed equivalent to shared-tokeniser rejection sampling.

Hardware and serving frameworks matter. TensorRT-LLM, vLLM and SGLang expose different proposal methods, schedulers and kernels. A paper’s speedup is evidence that the mechanism can work under its setup. It is not a transferable service-level objective.

Executable verified-acceleration lab

The companion lab has two jobs. First, it demonstrates that exact residual repair converges to the same sequence distribution as target-only decoding in a small autoregressive world, while a plausible wrong repair remains biased. Second, it makes the wall-clock break-even equation interactive.

The Python programme uses only the standard library and synthetic data. It contains a positive case, the full-target-resampling negative case, the hundred-sided uniform test and assertions. Save it as speculative_decoding_simulator.py and run python3 speculative_decoding_simulator.py. The Monte Carlo comparison uses independent samples, so a small empirical distance remains even when the underlying distributions are equal.

{
  "first_step": {
    "target_p": [0.5, 0.3, 0.2],
    "draft_q": [0.6, 0.1, 0.3],
    "total_variation": 0.20,
    "maximal_coupling_acceptance": 0.80,
    "residual_after_rejection": [0.0, 1.0, 0.0]
  },
  "sequence_distribution_check": {
    "tv_baseline_vs_exact": 0.01170,
    "tv_baseline_vs_wrong": 0.13871
  },
  "identical_uniform_100_faces": {
    "independent_match_rate": 0.00949,
    "coupled_acceptance_rate": 1.0
  },
  "speed_model": {
    "expected_committed_tokens": 3.23310,
    "estimated_speedup": 2.44008
  }
}

"""Speculative decoding simulator for the article
"Speculative Decoding and Verified Acceleration".

Python 3.10+. Standard library only.

The simulator uses a three-token autoregressive world. It compares:
1. ordinary target-model sampling;
2. exact speculative decoding with acceptance/rejection correction; and
3. a deliberately wrong verifier that resamples from the full target
   distribution after rejection instead of the positive residual.

It also checks the identical-uniform case and evaluates a simple
wall-clock break-even model. All distributions and timings are synthetic.
"""

from __future__ import annotations

from collections import Counter
from dataclasses import asdict, dataclass
from itertools import product
import json
import random
from typing import Callable, Iterable, Sequence

Token = str
Distribution = tuple[float, ...]
VOCAB: tuple[Token, ...] = ("A", "B", "C")


def normalise(values: Sequence[float]) -> Distribution:
    if any(value < 0 for value in values):
        raise ValueError("probabilities must be non-negative")
    total = sum(values)
    if total <= 0:
        raise ValueError("probabilities must have positive mass")
    return tuple(value / total for value in values)


def sample_categorical(probabilities: Distribution, rng: random.Random) -> int:
    threshold = rng.random()
    cumulative = 0.0
    for index, probability in enumerate(probabilities):
        cumulative += probability
        if threshold < cumulative:
            return index
    return len(probabilities) - 1  # protects against floating-point tail error


def total_variation(p: Distribution, q: Distribution) -> float:
    return 0.5 * sum(abs(left - right) for left, right in zip(p, q))


def overlap(p: Distribution, q: Distribution) -> float:
    return sum(min(left, right) for left, right in zip(p, q))


def residual_distribution(p: Distribution, q: Distribution) -> Distribution:
    residual = tuple(max(0.0, left - right) for left, right in zip(p, q))
    if sum(residual) == 0:
        # This branch is unreachable after a genuine rejection when p == q.
        return p
    return normalise(residual)


def target_distribution(prefix: tuple[Token, ...]) -> Distribution:
    """Synthetic target model p(. | prefix)."""
    if not prefix:
        return (0.50, 0.30, 0.20)
    last = prefix[-1]
    if last == "A":
        return (0.20, 0.55, 0.25)
    if last == "B":
        return (0.15, 0.25, 0.60)
    return (0.65, 0.20, 0.15)


def draft_distribution(prefix: tuple[Token, ...]) -> Distribution:
    """Cheaper but imperfect draft model q(. | prefix)."""
    if not prefix:
        return (0.60, 0.10, 0.30)
    last = prefix[-1]
    if last == "A":
        return (0.30, 0.50, 0.20)
    if last == "B":
        return (0.25, 0.20, 0.55)
    return (0.55, 0.30, 0.15)


def baseline_generate(length: int, rng: random.Random) -> tuple[Token, ...]:
    prefix: list[Token] = []
    while len(prefix) < length:
        p = target_distribution(tuple(prefix))
        prefix.append(VOCAB[sample_categorical(p, rng)])
    return tuple(prefix)


@dataclass(frozen=True)
class DecodeStats:
    target_calls: int
    drafted_tokens: int
    accepted_draft_tokens: int
    rejected_draft_tokens: int


def speculative_generate(
    length: int,
    gamma: int,
    rng: random.Random,
    *,
    exact_residual: bool = True,
) -> tuple[tuple[Token, ...], DecodeStats]:
    """Generate from the target using a draft-and-verify loop.

    The implementation is sequential Python, but target distributions for a
    proposed block are logically the values a transformer can score together
    in one verification pass.
    """
    if length < 1 or gamma < 1:
        raise ValueError("length and gamma must be positive")

    committed: list[Token] = []
    target_calls = drafted = accepted = rejected = 0

    while len(committed) < length:
        remaining = length - len(committed)
        block_size = min(gamma, remaining)

        proposals: list[Token] = []
        draft_probs: list[Distribution] = []
        draft_prefix = list(committed)

        for _ in range(block_size):
            q = draft_distribution(tuple(draft_prefix))
            token_index = sample_categorical(q, rng)
            token = VOCAB[token_index]
            proposals.append(token)
            draft_probs.append(q)
            draft_prefix.append(token)
            drafted += 1

        # One target verification call scores all proposed positions.
        target_calls += 1
        all_accepted = True

        for token, q in zip(proposals, draft_probs):
            p = target_distribution(tuple(committed))
            token_index = VOCAB.index(token)
            acceptance_probability = min(1.0, p[token_index] / q[token_index])

            if rng.random() < acceptance_probability:
                committed.append(token)
                accepted += 1
                if len(committed) == length:
                    break
                continue

            rejected += 1
            all_accepted = False
            repair = residual_distribution(p, q) if exact_residual else p
            committed.append(VOCAB[sample_categorical(repair, rng)])
            break  # later proposals were conditioned on the now-invalid prefix

        if (
            all_accepted
            and len(committed) < length
            and len(proposals) == block_size
        ):
            # The target pass can also provide the next-position distribution.
            p_bonus = target_distribution(tuple(committed))
            committed.append(VOCAB[sample_categorical(p_bonus, rng)])

    return tuple(committed[:length]), DecodeStats(
        target_calls=target_calls,
        drafted_tokens=drafted,
        accepted_draft_tokens=accepted,
        rejected_draft_tokens=rejected,
    )


def empirical_distribution(
    generator: Callable[[random.Random], tuple[Token, ...]],
    trials: int,
    seed: int,
) -> dict[str, float]:
    rng = random.Random(seed)
    counts = Counter("".join(generator(rng)) for _ in range(trials))
    return {"".join(key): counts["".join(key)] / trials for key in product(VOCAB, repeat=4)}


def dictionary_tv(left: dict[str, float], right: dict[str, float]) -> float:
    keys = set(left) | set(right)
    return 0.5 * sum(abs(left.get(key, 0.0) - right.get(key, 0.0)) for key in keys)


def identical_uniform_check(trials: int, seed: int) -> dict[str, float]:
    """Compare independent token matching with maximal-coupling acceptance."""
    rng = random.Random(seed)
    faces = 100
    independent_matches = 0
    coupled_accepts = 0

    for _ in range(trials):
        draft = rng.randrange(faces)
        target = rng.randrange(faces)
        independent_matches += int(draft == target)

        # p == q, so min(1, p(x)/q(x)) == 1 for every proposal.
        coupled_accepts += 1

    return {
        "independent_match_rate": independent_matches / trials,
        "coupled_acceptance_rate": coupled_accepts / trials,
    }


def expected_committed_tokens(alpha: float, gamma: int) -> float:
    if not 0 <= alpha <= 1:
        raise ValueError("alpha must be between zero and one")
    return sum(alpha**step for step in range(gamma + 1))


def estimated_speedup(
    alpha: float,
    gamma: int,
    target_single_ms: float,
    draft_token_ms: float,
    verify_block_ms: float,
    overhead_ms: float,
) -> float:
    committed = expected_committed_tokens(alpha, gamma)
    speculative_round_ms = gamma * draft_token_ms + verify_block_ms + overhead_ms
    return target_single_ms * committed / speculative_round_ms


def main() -> None:
    trials = 150_000
    length = 4
    gamma = 3

    baseline = empirical_distribution(
        lambda rng: baseline_generate(length, rng), trials, seed=8301
    )
    exact = empirical_distribution(
        lambda rng: speculative_generate(length, gamma, rng, exact_residual=True)[0],
        trials,
        seed=8302,
    )
    wrong = empirical_distribution(
        lambda rng: speculative_generate(length, gamma, rng, exact_residual=False)[0],
        trials,
        seed=8303,
    )

    first_p = target_distribution(())
    first_q = draft_distribution(())
    alpha = overlap(first_p, first_q)

    uniform = identical_uniform_check(100_000, seed=8304)
    result = {
        "assumptions": {
            "vocabulary": VOCAB,
            "sequence_length": length,
            "draft_window_gamma": gamma,
            "trials_per_decoder": trials,
            "all_probabilities_and_timings": "synthetic",
        },
        "first_step": {
            "target_p": first_p,
            "draft_q": first_q,
            "total_variation": total_variation(first_p, first_q),
            "maximal_coupling_acceptance": alpha,
            "residual_after_rejection": residual_distribution(first_p, first_q),
        },
        "sequence_distribution_check": {
            "tv_baseline_vs_exact": dictionary_tv(baseline, exact),
            "tv_baseline_vs_wrong": dictionary_tv(baseline, wrong),
        },
        "identical_uniform_100_faces": uniform,
        "speed_model": {
            "alpha": 0.78,
            "gamma": 4,
            "expected_committed_tokens": expected_committed_tokens(0.78, 4),
            "estimated_speedup": estimated_speedup(
                alpha=0.78,
                gamma=4,
                target_single_ms=20.0,
                draft_token_ms=1.0,
                verify_block_ms=21.0,
                overhead_ms=1.5,
            ),
        },
    }

    # Positive case: exact speculative decoding should converge to baseline.
    assert result["sequence_distribution_check"]["tv_baseline_vs_exact"] < 0.02
    # Negative case: the tempting full-p repair should remain detectably biased.
    assert result["sequence_distribution_check"]["tv_baseline_vs_wrong"] > 0.025
    # When p == q, maximal coupling accepts every proposal.
    assert uniform["coupled_acceptance_rate"] == 1.0
    # Independent equality wastes almost all identical-distribution proposals.
    assert 0.007 < uniform["independent_match_rate"] < 0.013

    print(json.dumps(result, indent=2))


if __name__ == "__main__":
    main()

Compact glossary

Target model

The authoritative autoregressive model whose declared decoding distribution must be preserved.

Draft model

A cheaper proposal mechanism. It may be a model, lookup, trained head or other predictor.

Acceptance

The probabilistic decision to reuse a draft token while retaining the target marginal distribution.

Residual

The normalised positive mass (p-q)+ used to repair the first rejected proposal.

Draft window γ

The maximum number of proposed tokens in one chain before target verification.

Accepted prefix

The consecutive proposals retained before the first rejection. Later proposals are discarded.