research24 min studyLesson 735 in Engineering

Choose lookahead by committed output per unit cost

Compute accepted-prefix expectations under explicit assumptions and compare draft, verification, and coordination costs without equating target-call reduction with wall-time speedup.

On this page

What you’ll understand

  • Distinguish accepted-prefix length from total accepted positions.
  • Derive a conditional expected output model with its endpoint cases.
  • Compare modeled per-token costs and identify what the model omits.

A longer draft produces more accepted tokens per verification round, yet end-to-end latency becomes worse. The extra proposals consume draft time, target work, and cache space even when many are discarded after an early rejection. Optimize committed output per unit cost rather than acceptance rate or target-call count alone. A compact expectation model is useful for reasoning, provided its acceptance, stopping, and cost assumptions are explicit and its parameters are measured for the actual workload.

Count the accepted prefix and the correction or bonus

Let A be the number of consecutive proposals accepted before the first rejection, capped at draft length γ. A token accepted at a later position is not committed if an earlier proposal failed, because its history is wrong. Thus E[A] is a sum of prefix-survival probabilities, not the sum of all independently reported per-position accepts. Under the simplifying assumption of a common constant conditional acceptance α along the accepted path, Pr(A≥i)=α^i. The real history-dependent process need not have that property, even when its aggregate acceptance average is α.

Ignoring EOS and length caps, the standard round emits A+1 tokens: one residual correction after a rejection, or a bonus target token if every proposal passes. The expected count is 1+α+…+α^γ in the constant-acceptance model. At α=1 it isγ+1, and at α=0 it is one. Handle the α=1 endpoint directly rather than evaluate a closed form with a zero denominator. Early stopping or a different verifier can change the count, so a measured number of output tokens must identify which round and stopping convention was used.

E[Nout]=∑i=0γαi={1−αγ+11−α,0≤α<1,γ+1,α=1.\mathbb{E}[N_{\mathrm{out}}]=\sum_{i=0}^{\gamma}\alpha^i=\begin{cases}\dfrac{1-\alpha^{\gamma+1}}{1-\alpha},&0\leq\alpha<1,\\\gamma+1,&\alpha=1.\end{cases}
γ is a positive integer, N_out=A+1, and the constant conditional acceptance model excludes EOS and output caps. The expectation is in committed tokens per round; it is not a binomial count of all positions and is not guaranteed by a pooled acceptance average.↔ Scroll wide equations horizontally.

Charge for the entire round

A simple sequential round budget includes γ draft steps, one target verification pass at that block length, and coordination or sampling overhead. Divide that cost by the expected committed count only under a sustained repeated-round model with suitable stable averages. A target pass scoring a long block can take more time than one ordinary decode step, and memory pressure or synchronization can add costs. If phases overlap, use the actual critical-path model instead of adding them blindly. State whether prefill, compilation, tokenizer work, and request queueing are included in the reported interval.

Compare against the same target decoding workload, hardware, batch conditions, and output contract. A two-times reduction in target invocations does not imply a two-times speedup when the draft or verification kernel is expensive. Conversely, extra arithmetic can help a memory-bound workload if it amortizes weight access effectively. Sweep a bounded range of γ values while measuring accepted-prefix distributions, stage times, peak memory, and latency tails. A higher acceptance rate with a slower draft can lose to a less accurate but much cheaper proposal mechanism.

Ctoken≈γTd+Tv(γ)+ToE[Nout]C_{\mathrm{token}}\approx\frac{\gamma T_d+T_v(\gamma)+T_o}{\mathbb{E}[N_{\mathrm{out}}]}
T_d is draft-step time, T_v the γ-dependent target verification time, and T_o other sequential round overhead, all in the same time unit. The approximation assumes this cost decomposition and sustained compatible round averages; output counts and stopping effects must match the expectation model.↔ Scroll wide equations horizontally.

Model adaptation as a measured policy

Acceptance varies across prompt type, context length, decoding temperature, and position within a response. Dynamic lookahead can use recent evidence to choose γ, but its changing cost and selection policy must be evaluated on held-out or representative traces. Avoid substituting one global α into every latency percentile or assuming a longer proposal always adds useful work. Include EOS-heavy short requests and low-acceptance domains. Pinned backends can implement confidence-based proposal stopping without changing verification, but their precise schedule and overhead remain implementation details to measure, not a universal optimum.

The probability lab shows why a binomial count is another quantity. Reset, set both lab p=0.8 and n=3, predict its mean and all-three bar, then inspect. Its mean is 2.4 successes and its all-three probability 0.512. Under the separate independent-prefix toy model, E[A] is 0.8+0.64+0.512=1.952, not 2.4, because success after a prior failure is unusable. The instrument does not model prefix stopping or round cost. Use its exact independent bars to compare those definitions, then calculate the committed-prefix expectation explicitly.

Compute a fictional sustained-round cost

Assumeγ=3, constant conditional acceptanceα=0.8, no EOS or length cap, draft time 0.5 ms per proposal, target verification 4 ms per round, and other sequential overhead 0.5 ms. An ordinary target decode step takes 4 ms in this fictional comparison.

  1. Expected committed output is 1+0.8+0.64+0.512=2.952 tokens per round, including correction or bonus.

  2. The stated sequential round cost is 3×0.5+4+0.5=6 ms. Divide to obtain 6/2.952≈2.03252 ms per committed token in the sustained model.

  3. The modeled speed ratio is 4/2.03252≈1.968 times. This depends on the fixed verification cost and acceptance assumptions; actual queueing, γ-dependent kernels, memory, or stopping may change it.

The result

The invented model predicts about 1.968-times throughput improvement for the stated long-run round conditions, not a measured backend speedup or a per-request tail guarantee.

Explore the model

Interactive lab

Interactive lab · probability

A success count is not an accepted-prefix length

Reset, set both p=0.8 and n=3, predict, then inspect. The exact binomial count has mean 2.4 and all-three mass 0.512. Separately calculate prefix expectation 0.8+0.64+0.512=1.952 under the stated conditional-acceptance model. This instrument does not stop at first failure or measure decoding cost.

A success count is not an accepted-prefix lengthThese are exact binomial probabilities for independent trials with one fixed success probability. Playback tours the distribution; it does not resample outcomes. Current readings: Mean · np: 5; Variance · np(1−p): 2.5; Total probability: 1. All parameters are adjustable with the labeled controls below.03581000.070.150.220.3Successes kP(X = k)k = 0 · P = 9.77e-4
Exact probabilityHighlighted outcomeMean np
Mean · np
5
Variance · np(1−p)
2.5
Total probability
1
t = 0 s

These are exact binomial probabilities for independent trials with one fixed success probability. Playback tours the distribution; it does not resample outcomes. Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.

Look forOnly consecutive verified proposals are reusable along one draft path. Round cost and committed output require the correct prefix model.

Check your understanding

Why can the binomial mean γα overestimate the expected committed draft-prefix length?

Try it yourself

Assumeγ=2 and constant conditional acceptanceα=0.5 with no stopping. Draft steps cost 1 ms each, verification 4 ms, and other overhead zero. Compute expected output and modeled cost per token.

Take a moment to make a prediction or work it out on paper. Open a hint when you need one.

Give me a hint

Include the correction or bonus token in 1+α+α².

Compare with the solution

Expected output is 1+0.5+0.25=1.75 tokens. Round cost is 2×1+4=6 ms, giving 6/1.75≈3.42857 ms per token. Against a 4 ms baseline, the modeled ratio is about 1.16667 times under these assumptions.

Take it with you

  • Model consecutive accepted prefixes rather than all successful positions.
  • Charge draft, verification, overhead, memory, and stopping effects appropriately.
  • Tune lookahead against measured committed output and actual latency objectives.

Read further

Original sources and deeper explanations to follow at your own pace.

Optional progress, saved in this browser when available. Revisit any lesson at any time.

Lesson not marked complete.