Token LabSearch

SYSTEMS / ENGINEERING BRIDGE

Speculative decoding: correctness before speed

Derive acceptance and residual sampling with a two-token example.

Study guide & lesson outlineLEARNING CONTRACT

Understand → implement → investigate

Goal: explain the mechanism in this lesson, reproduce one example and test a failure case. Reading alone does not mark mastery.

Prerequisite route →Related implementation practice →

Mechanism & assumptions

A draft distribution q proposes a token and the target p verifies it. Accept with min(1,p/q); on rejection sample from normalized positive residual (p−q)+. Omitting correction generally changes the output distribution. Actual acceleration depends on draft cost, acceptance, verification batching and workload.

Text / 原始公式
P(X=x and accepted) = q(x) min(1,p(x)/q(x)) = min(p(x),q(x))
r(x) = max(p(x)−q(x),0) / Σy max(p(y)−q(y),0)

Worked example

Let ,0.3], ,0.6]. Accept A always and B with probability 0.5. Accepted mass is [0.4,0.3]; rejection mass 0.3 is reassigned to A, restoring [0.7,0.3]. When there is no rejection and the zero-denominator residual branch is never used.

Implementation exercise

Implement seeded sampling and compare output frequencies with p. Test on some tokens, , and sharply mismatched proposals. Report sampling uncertainty, then benchmark runtime separately.

Deliver code, fixed seeds, raw results and one counterexample. These are experiment specifications, not executed GPU benchmarks.

Does exact distribution mean identical output for a shared seed?

No. Different algorithms consume random numbers differently. Distributional correctness and sequence equality under a seed are distinct tests.

arXiv ↗ · PDF ↗

Original teaching examples; sources checked October 2026. These are foundational mechanisms relevant to engineering, not a claim to cover every latest model.

AI/LM curriculum & checkpoints →Systems index →
MATHEMATICAL REVIEW · 2026-10-26

Assumptions, implementation & acceptance

Conditional acceptance is min(1,p(x)/q(x)) for q(x)>0. Joint proposal-and-acceptance mass is min(p(x),q(x)). Rejection samples normalized positive residual; identical distributions need no residual draw.

Formula conditions, units and worked arithmetic reviewed. The implementation isolates one numerical mechanism; it does not train a policy or control real hardware.

Propose x from draft q → Accept with min(1,p(x)/q(x)) → If rejected: draw positive residual → Accepted + residual mass = target p
Mechanism map: follow the transformations from top to bottom.

Before running: predict a boundary case

Accepted mass is .7, rejection mass .3; adding the residual exactly restores target p.

Hint: isolate the assumption

Keep the baseline input fixed, change one parameter or boundary, and compare both the numerical result and the claimed units. A passing example verifies this fixture only.

Minimal executable example

Save the example and linked modules in one folder. Use Node.js 22 or newer, then run node speculative-correctness.mjs. No third-party runtime dependencies.

const solve=()=>{
const p=[.6,.4],q=[.3,.7];
const accepted=p.map((v,i)=>Math.min(v,q[i]));
const residual=p.map((v,i)=>Math.max(0,v-q[i]));
return [accepted.reduce((a,b)=>a+b),...accepted.map((v,i)=>v+residual[i])];
};
const actual=solve();
const expected=[0.7,0.6,0.4];
if(JSON.stringify(actual)===JSON.stringify(expected)){console.log('PASS',actual)}else{
const a=[actual].flat(), b=[expected].flat();
if(a.length!==b.length||a.some((v,i)=>!Number.isFinite(v)||Math.abs(v-b[i])>1e-10))throw Error('Numerical mismatch');
console.log('PASS within 1e-10',actual);
}
Download this example
Reference output — reveal after predicting
[
  0.7,
  0.6,
  0.4
]

Test and transfer

Accepted mass is .7, rejection mass .3; adding the residual exactly restores target p.

Record input, code version, expected result and observed result in the notebook below. Then construct a counterexample that violates the assumption above and explain why the original conclusion no longer follows.

Download complete kit (.tar.gz) · Complete reference kit and regression checks

Predict, test and keep evidence

Before revealing an answer, predict one result. After the exercise, record the discrepancy and a transfer test. Saved locally across language editions.

Open notebook / export / clear →

The mathematical review scope is recorded per lesson. It does not establish empirical paper reproduction; report suspected errors in your notes. Review scope