Speculative decoding (Leviathan 2023, Chen 2023) sets the optimal block draft length from one number: the
marginal acceptance rate alpha. The derivation assumes each drafted token is accepted independently with
rate alpha, so accepted runs are capped-geometric and expected tokens per block is
E[k] = (1 - alpha^(g+1))/(1 - alpha). Every serving stack tunes the draft length on that i.i.d. picture.
Token difficulty clusters (boilerplate and copy spans are easy and run together, novel spans are hard and run together), so the accept/reject stream should be autocorrelated and its run lengths over-dispersed relative to geometric. The natural guess is that those long easy runs, which geometric gives almost no mass, should push the optimal draft length up.
The guess is backwards. On real greedy Qwen2.5 spec-decode the stream is autocorrelated and over-dispersed,
but the optimal draft length moves down, and the only real consequence is that the marginal-alpha model
over-predicts how many tokens a block actually yields.
Lossless greedy spec-decode emits exactly the target's raw-argmax greedy continuation y for any draft
length, so at each position t:
a_t = 1 iff argmax(draft | y_<t+1) == argmax(target | y_<t+1) (== y_t+1)
a_t is exact and independent of the draft length. Build y by raw-argmax greedy decoding of the target
(no repetition penalty, no sampling warpers; otherwise y is not the raw-greedy sequence and a_t is
scored against an inconsistent stream), then teacher-force both models on y in one pass each. Gate:
target_argmax_t == y_t+1 holds on 1.000 of positions. A block-walk simulator then computes exact
tokens-advanced and block-count for every draft length from that single pass.
Autocorrelation is measured per stream (own conditional rates p11-p10, then averaged) so it cannot be
faked by pooling prompts of different difficulty. The yield deficit 1 - E_true/E_iid(alpha) at draft
length 8 is split into a cross-prompt heterogeneity part (survives shuffling each stream in place) and a
within-prompt temporal part (removed by that shuffle). Bootstrap 95% CIs over streams.
| corpus | alpha | within-stream autocorr p11-p10 | run-length dispersion D/D_geom | yield deficit total = hetero + temporal (CI) |
|---|---|---|---|---|
| prose (WikiText) | 0.94 | +0.233 [0.19, 0.27] | 16.7x | 0.064 = 0.016 + 0.048 [0.030, 0.063] |
| code | 0.96 | +0.074 [0.03, 0.13] | 5.5x | 0.037 = 0.016 + 0.021 [-0.002, 0.043] |
| json | 0.92 | +0.106 [0.06, 0.14] | 12.2x | 0.071 = 0.008 + 0.063 [0.031, 0.076] |
| math (GSM8K) | 0.93 | +0.047 [0.02, 0.08] | 2.1x | 0.022 = 0.009 + 0.012 [-0.010, 0.026] |
| multilingual | 0.89 | +0.209 [0.16, 0.26] | 24.3x | 0.090 = 0.043 + 0.048 [0.040, 0.067] |
| pooled | 0.93 | +0.155 [0.125, 0.182] | 14.2x | 0.067 = 0.024 + 0.043 [0.033, 0.051] |
Within-stream acceptance is genuinely autocorrelated: the own-mean gap is positive with a CI excluding 0 in every corpus, and pooled +0.155. (Pooling streams into one transition table instead reports +0.183; the gap between the two, 0.028, is Simpson inflation from difficulty differences across prompts, not real temporal structure. This harness reports the per-stream number.)
The optimal draft length is smaller, not larger. The draft-length gap versus the i.i.d. choice is negative
across the whole cost-ratio grid r = c_draft/c_verify in [0.05, 0.6]: the true optimum is 1 to 3 below
the i.i.d. optimum at every r, never above.
Real throughput is tokens / (blocks * c_verify + drafted * c_draft), and tokens/blocks is a
block-weighted average dominated by the hard, clustered, many-block stretches that a single alpha washes
out. So the i.i.d. model over-predicts per-block yield, and the gap widens with the draft length because a
longer block reaches deeper into the hard stretches:
| draft length | E_true / E_iid (pooled, 95% CI) |
|---|---|
| 2 | 0.989 [0.987, 0.992] |
| 4 | 0.972 [0.968, 0.976] |
| 8 | 0.933 [0.925, 0.943] |
| 16 | 0.883 [0.875, 0.894] |
Every CI excludes 1, and the deficit deepens with length, so the true throughput curve peaks earlier than the i.i.d. curve and the optimum shifts down.
Two things, separated by the in-place shuffle. Shuffling each stream preserves its own alpha exactly,
keeping cross-prompt heterogeneity, and destroys only the temporal order. Pooled at draft length 8 the
total 6.7% deficit splits into 2.4% from prompt-to-prompt difficulty differences and 4.3% from within-prompt
temporal clustering, the latter with a CI of [3.3%, 5.1%] that excludes 0. The temporal share is the larger
of the two and is significant in the three high-dispersion corpora (prose, json, multilingual) and not
distinguishable from 0 in the two flat ones (code, math). The marginal alpha, the number serving stacks
tune on, is invariant to the in-place shuffle by construction, so it cannot see either part.
The effect is not specific to the 1.5B target. On the 3B target, prose corpus (single corpus, the full 5-corpus 3B sweep is a stated extension): within-stream autocorrelation +0.187 (CI [0.131, 0.237], excludes 0), run-length dispersion 26.5x, yield deficit at draft length 8 of 8.8% split into 4.1% heterogeneity and 4.7% temporal (CI [0.024, 0.067], excludes 0), and the draft-length optimum is again 0 to 2 below the i.i.d. optimum across the cost-ratio grid, never above. Same direction, same decomposition.
The primary oracle is exact and self-verifying (the substrate gate holds at 1.000, and the block-walk
simulator is checked against the closed-form i.i.d. yield and against synthetic streams with known truth in
16 of the 18 unit tests). As an independent cross-stack check, real greedy llama-speculative on the
quantized q4_k_m models gives per-position acceptance in the same regime as the fp32 HF oracle: 0.865 on a
held-out prose prompt at draft length 1, against the HF oracle's per-prompt range of 0.69 to 0.98 (pooled
0.94). Exact cross-draft-length token identity is not obtainable on this stack: batched verification and
serial decoding compute slightly different target logits, which flip the argmax at near-ties, an effect of
floating-point batching and not of the speculative-decoding algorithm, so the two draft lengths agree for a
prefix and then diverge at the first tie. The losslessness the oracle relies on is the greedy
speculative-decoding guarantee itself; the full accepted-run histogram match on llama.cpp is a stated
extension.
| prediction | outcome | |
|---|---|---|
| P1 | acceptance autocorrelated | holds. Per-stream p11-p10 positive, CI excludes 0, every corpus |
| P2 | run lengths over-dispersed vs geometric | holds. 2.1x to 24x |
| P3 | optimal draft length larger | falsified. It is 1 to 3 smaller, at every cost ratio |
| P4 | a permutation control isolates the cause | holds, once corrected to an in-place shuffle: 4.3% of the 6.7% deficit is temporal, CI excludes 0 |
| P5 | effect scales with autocorrelation across corpora | holds directionally. Temporal deficit significant only in the high-dispersion corpora |
The finding is the negative with a mechanism. The folklore that difficulty clustering lets you raise the
draft length is wrong; over-dispersion instead makes the i.i.d. acceptance-rate formula optimistic about
yield (up to 12% at length 16) and shifts the optimum down. The correct draft length comes from the
empirical run-length yield, not the geometric formula from alpha alone.
- The acceptance bit is exact (argmax on the raw-greedy sequence, gate
target_argmax == y_t+1at 1.000). The block-walk is checked against hand-computed cases and against the closed-form i.i.d.E[k]on synthetic Bernoulli streams (18 unit tests, including the heterogeneous-prompt regime where a pooled autocorrelation statistic would fire falsely and the per-stream one does not). - Autocorrelation and run lengths are computed within each generation, never across a prompt boundary. Every headline number carries a bootstrap 95% CI over streams. The heterogeneity and temporal parts of the deficit are separated by an in-place per-stream shuffle, not a global shuffle (a global shuffle destroys both and cannot attribute the cause).
- Greedy and temperature 0 only; the exact oracle depends on argmax acceptance. Sampling-based spec-decode is out of scope and named as future work. Qwen2.5-0.5B draft, 1.5B target, Apple M4 Pro, no NVIDIA GPU. The draft-length optimum is reported over the cost ratio, so the structural result does not depend on whether this pair nets a raw speedup on this hardware.
./reproduce.sh # extract, analyze, tests
python run_oracle.py <hf_target_id> <tag>
python analyze.py <tag>
MIT.