Locally Repairable Draft Trees for Speculative Decoding

Speculative decoding speeds up large language models by letting a small "drafter" guess several future tokens, which the large "target" model then checks in one parallel pass. The check is all-or-nothing past the first mistake. If the third of eight guessed tokens is wrong, the target swaps in its own third token and throws away guesses four through eight, even when those later guesses would have been fine once the third token was fixed. Distributed storage faced the same shape of problem and solved it with locally repairable codes. These are erasure codes that add small "local" parities over short groups of blocks, so that the common case, a single lost block, is repaired by reading a few neighbours instead of the whole stripe. Rare multi-block failures still fall back to expensive global repair.

We propose to apply that design rule to speculative verification. The draft is extended with cheap "repair branches." Each branch substitutes an alternative token at one position and then reuses the drafter's original continuation, copied for a bounded number of positions $r$ (the locality) rather than redrafted. One target pass can then accept the common case, a single wrong token inside an otherwise good draft, without spending another full draft-and-verify round. Branches need no extra drafter calls, so the only added cost is verifier tokens. The open question is whether the target really does agree with the drafter's old suffix after a one-token fix often enough to justify those tokens. That question is cheap to measure, and the proposal is built around measuring it first.

Core Claim

Single-token mismatches dominate rejections. After such a mismatch, the drafter's later tokens often remain exactly what the target would produce. This is suggested by ReTrace, which recycles hidden states of rejected suffixes through a learned gate and reports that the target token is the drafter's top choice 30.4% of the time and in its top-5 75.2% of the time within rejected suffixes. If both hold, then a draft tree whose extra nodes are reserved for "substitute one token, copy the next $r$" will accept more tokens per verifier pass than a tree of equal size spent on fresh top-$k$ branching.

We also include shifted copies, where the suffix is re-aligned by one position. These handle the drafter inserting or dropping a function word, a failure that storage-style erasure models ignore but text exhibits constantly. The new element is not a finite-field code. It is the allocation principle taken from locally repairable codes: give cheap local redundancy to the frequent single-failure pattern, and leave rare multi-failure patterns to the global fallback, which here means the next round.

Research Program

The work has three parts. The first is a measurement study, run before anything else is built. For each rejection at position $i$, we record whether the target's greedy continuation after its corrected token matches the drafter's copied suffix at offsets $1,\dots,8$. We also record the same for shifted copies at offsets of plus or minus one. This yields a survival curve $s(j)$, the probability that copied token $j$ steps after the fix is still correct. We break it down by task, drafter size and position in the window. This curve decides the whole project.

The second part is tree design. A tree is the spine (the drafter's linear guess) plus a set of repair branches. Each branch is specified by a substitution position, an alternative token drawn from the drafter's top-$k$ at that position, a shift, and a copy length $r$. Given the measured spine acceptance rates and $s(j)$, the expected accepted length of a tree is a sum over root-to-leaf paths. Maximizing it under a verifier-token budget $B$ is a small knapsack-style problem, which we solve by dynamic programming offline per task category.

The locally-repairable-code lens fixes the structure of this search and tells us what to look for. The analogue of locality is how long $r$ should be before copied tokens stop paying for themselves. The analogue of local distance is whether two-substitution branches ever beat one-substitution branches. The analogue of overlapping repair groups is whether branches at nearby positions should share copied suffixes. The last point echoes the overlap structure studied by Cai et al.. That paper bounds code distance when repair sets must intersect. We borrow only the question, not the algebra, since its constructions need large fields and say nothing about language.

The third part is exactness. Verification uses tree-structured checking with topology-aware attention masks, as in SpecInfer, which organizes top-$k$ draft expansions into a tree and checks them in one pass. For greedy decoding this is exact by construction. For sampling, copied tokens have no valid drafter probability under the new prefix, so we treat each as a point-mass proposal. Such a token is accepted with probability equal to its target probability $p(x)$. On rejection we sample from the residual $\max(0, p - \delta_x)$, normalized. This keeps the output distribution identical to the target's. We will verify this empirically by comparing token-frequency statistics against plain sampling.

Baselines

The naive reference is plain autoregressive decoding with the target model. A second simple reference is linear speculative decoding with the same drafter and the same window, which isolates what any tree adds.

The strongest existing competitors are tree and graph speculative decoding. SpecInfer branches on drafter top-$k$ and reports 1.5–2.8× speedup over vLLM and HuggingFace TGI and 96–97% token verification success. Graph-Structured Speculative Decoding merges the more than 70% redundant subsequences of such trees into a graph and reports 1.96× speedup on GSM8K with LLaMA-2-70B. The latter is the number to beat on math. These methods are the right competitors because they spend the same resource we do, extra verifier tokens per pass, but spend it on freshly drafted alternatives rather than repaired copies. We run them at matched verifier-token budget $B$, with the same drafter and target, on the same prompts and hardware. Tree shapes for SpecInfer and the graph method get the same tuning budget we give our dynamic program. Beating them means higher accepted tokens per verifier pass at equal $B$ and higher wall-clock speedup, with fewer drafter calls per accepted token.

For learned recycling we compare to ReTrace, which reports a 6.97% gain in acceptance length and 5.34% end-to-end speedup over its DFlash backbone. Because ReTrace needs a trained gate on a specific drafter, we report it where we can reproduce its setting. We also test whether our trees compose with it.

For verification-rule improvements we cite Block Verification, which replaces token-by-token acceptance with an optimal joint rule for linear drafts and reports 5–8% wall-clock gains. It is orthogonal to our work. It also explicitly leaves trees open, so we treat it as a ceiling-raiser on the spine rather than a competitor.

The key ablation replaces our repair branches with the same number of nodes placed as ordinary top-$k$ alternatives followed by fresh drafter continuations. This isolates whether suffix reuse, rather than mere tree width, is responsible for any gain. A second ablation removes shifted copies.

Why not just…?

Why not just reuse the rejected suffix as next round's draft? This is the most serious threat. It costs no extra verifier tokens: after a rejection, feed the corrected token plus the old suffix to the next verification round. If survival $s(j)$ is high, this captures most of the benefit. What it does not capture is the saved round, since each round is one full memory-bound pass of the target. Our method wins only if the expected tokens gained in the current pass outweigh the verifier tokens added. No reported result was found on Lacuna for this suffix-reuse baseline, so we implement it ourselves and report it head to head at every budget. If it matches us at small $B$, we will say so and recommend it.

Why not just a wider SpecInfer-style tree? Top-$k$ branching already covers "the drafter picked the second-best token." It covers it only at the branch point, though: each branch needs its own drafted continuation, which costs drafter compute and, in SpecInfer's design, deeper trees. The 70% redundancy measured by Graph-Structured Speculative Decoding hints that those continuations often coincide with the spine anyway. Our matched-budget ablation tests exactly this. If fresh branches win, the reuse premise is wrong.

Why not just stop drafting when the drafter is uncertain? Hierarchical Speculative Decoding with Dynamic Window truncates drafts on high entropy and reports 2.91–3.13× on MT-Bench. The same paper reports only modest gains on GSM8K and HumanEval, where drafter confidence is poorly calibrated. Truncation also discards the post-error tokens that we aim to keep. We will combine truncation with repair branches and report whether repair adds anything on top of truncation on math and code, where truncation is known to be weakest.

Proposed Experiments

We use the Vicuna-v1.3 and Llama-2-chat families as targets, with small and medium drafters, so that results line up with the cited papers. Benchmarks are Spec-Bench, GSM8K, HumanEval, MT-Bench and XSum. Metrics are mean accepted tokens per target pass, wall-clock speedup over autoregressive decoding at batch sizes 1 and 8, verifier tokens per pass, and drafter calls per accepted token.

The decisive first check is the survival curve. If copied-token survival one step after a single-token correction falls below roughly the marginal spine acceptance rate at the same depth, repair branches cannot beat fresh branches, and we stop and report the negative result. The second check is the matched-budget comparison against SpecInfer trees and the graph method on GSM8K. The goal there is to exceed 1.96× on LLaMA-2-70B, or to match it with clearly fewer drafter calls. The third check is the head-to-head against next-round suffix reuse across budgets, which tells us whether in-pass repair is worth its tokens. The fourth confirms that stochastic outputs are distributionally identical to plain sampling. Finally, we report how optimal $r$ and the share of shifted branches vary by task. This shows whether code and math, where drafters fail most, have the short, local error structure that the locally-repairable-code analogy predicts.