One RDNA4 verify pass has slack for about two dozen speculative tokens
Discuss on XYesterday’s post left a bet on the table. Prompt lookup decoding turns a coding agent’s own context into a free draft model: take the last few tokens the model emitted, find where that same n-gram appeared earlier in the context, and propose whatever followed it as a candidate block for the next forward pass to confirm. It works because an agent copies most of its output from the file it just read. But it makes one quiet assumption, and that assumption is where the value leaks out.
When the last n-gram appears in several places, prompt lookup takes the most recent match. In prose that is fine, because text rarely repeats. In code it is a bad bet. A coding agent’s context is full of near-identical lines: the same import written three ways, a variable name that shows up in a dozen call sites, a function signature echoed in its definition, its call, and its test. The most recent match is one of several plausible continuations, and picking it means the engine is guessing which duplicate the model is about to copy, then paying full price when it guesses wrong.
The fix is to stop guessing. You do not have to pick one match if a single forward pass has room to check several of them at once, and on a local card it does. A verification pass on one RX 9070 XT is priced like one decode step, and one decode step has slack for about two dozen candidate tokens before it costs any more. That slack is exactly enough to hedge.
Why a verification pass is priced like one decode step
The reason runs through the last two weeks of posts. A decode step on one RX 9070 XT running Qwen3.5-9B lands about 39.6 tokens per second, roughly 25 milliseconds a token, and almost none of that is arithmetic. It goes to streaming the model’s weights across the bus once and to the fixed overhead of launching the step: the command submission and the barrier between kernels that a single token pays in full.
A verification pass processes several candidate positions at once, but it streams those same weights once and pays that same launch once, for all of them. The only thing that grows with the number of candidates is the matrix work, and decode is not compute bound. So the pass stays flat, near the cost of one token, until the compute for the candidates finally catches up with the time spent streaming the weights. Past that point the pass is doing real extra arithmetic and starts to cost more.
That crossover is a roofline, and it has a number.
Read the flat part first. From one candidate up to about twenty-four, the pass costs roughly what a single decode token costs, because the candidates ride along under the weight stream that was going to happen anyway. The knee is where the compute for the tree grows past the weight-stream time, computed simply as the 25.3 millisecond decode floor divided by the 1.04 milliseconds of compute each candidate adds at the prefill rate. After the knee the curve joins the compute-bound line and the free ride is over.
The box on the right is the whole argument in three numbers. Confirming twenty-four tokens in one pass costs about 25 milliseconds. Generating those same twenty-four tokens one at a time costs twenty-four decode steps, about 606 milliseconds. Same tokens, roughly one twenty-fourth the launches, if you can arrange for the model to actually accept them.
Spend the budget on a tree, not a longer guess
Prompt lookup spends that budget on depth. It proposes one continuation and makes it a bit longer. But a longer single guess only pays when acceptance is high the whole way down, and yesterday’s curve showed that the tail of a long block is where acceptance falls off. Spending all twenty-four tokens on one branch means most of them are speculative continuations of a continuation, and the deeper ones rarely land.
A token tree spends the same budget on breadth. Instead of one block, you propose several candidate continuations that share a prefix and arrange them as a tree, then verify the whole tree in one pass using a tree-structured attention mask so each branch attends only to its own ancestors. SpecInfer introduced this tree-based verification, and Medusa made it mainstream by generating the branches from extra decoding heads on the model itself and confirming them with the same masked pass. The model scores every branch at once and accepts the longest one it agrees with. It is lossless, exactly as prompt lookup is, because a branch is only taken where the model would have produced it anyway.
For prompt lookup the branches are free to find. The context already contains several places the current n-gram appeared, and each one proposes a different continuation. Rather than throwing away all but the most recent, the engine keeps the top few matches and makes each a branch. One of them is usually the line the model is about to copy, and the tree lets a single pass confirm which.
| One verify pass, the ~24-token budget on RX 9070 XT | Candidate tokens | What it covers |
|---|---|---|
| Linear prompt lookup, most recent match, depth 8 | 8 | one continuation, right only if the guess was right |
| Deeper linear block, depth 24 | 24 | one continuation, tail rarely accepted |
| Token tree, 3 matches at depth 8 | 24 | three continuations, one pass picks the right one |
The three rows spend the same forward pass. The first uses a quarter of the budget and bets it all on the most recent match. The second uses the whole budget on depth and wastes most of it on low-acceptance tail tokens. The third uses the whole budget on breadth, so when the model was going to copy the second-most-recent line instead of the last one, the tree already has that branch and confirms it in the pass that would otherwise have been thrown away.
Where the tree earns its keep, and where it does not
The honest limit is the knee. Past roughly two dozen candidate tokens the pass is no longer free, so a tree cannot be both wide and deep on a single card. That rules out the big bushy trees some server-side systems build, and it means the sensible shape here is a handful of branches at modest depth, three or four matches at depth six to eight, not sixteen branches or one branch of length forty. EAGLE-2 makes the same point from the other direction: the acceptance rate of a draft token is context dependent, so a static tree wastes positions, and the win comes from shaping the tree to where acceptance is actually high. For prompt lookup that shaping is cheap, because the number of times an n-gram recurs in the context is a decent proxy for which branches are worth keeping.
There is also bookkeeping the linear version does not have. A tree needs the masked attention, and it needs the KV cache to hold the branches without corrupting the committed context, which means writing candidate keys and values to scratch slots and keeping only the accepted branch. On a card where KV space is the constraint, that scratch has to be small and reused, so the tree budget is bounded by memory as well as by the compute knee. Two dozen tokens is comfortably inside both.
For a swarm the direction is the same as it was for plain prompt lookup, only stronger. Eight agents on one card are bottlenecked on forward passes, because every decode step streams the shared weights, so anything that confirms more accepted tokens per pass is spending the scarce resource better. A tree that accepts the right branch where a linear guess would have missed is a whole re-decode the scheduler never has to run. The extra compute per pass is close to free on a bandwidth-bound card, which is precisely the trade a swarm wants: more arithmetic that was going to waste anyway, in exchange for fewer launches.
What I am building toward
ZINC already keeps every agent’s context resident as KV cache, and yesterday’s plan was to add an n-gram index over each agent’s own token stream. The tree changes what that index returns. Instead of the single most recent match, it returns the top few matches, ranked by how often the n-gram recurs, and the engine assembles them into a small tree that fits inside the two-dozen-token budget. The verification step then needs a tree-structured mask folded into the decode kernel and a scratch region in the KV cache for the branches.
The framing I want to keep is that the budget is the whole point. A local card gives you one nearly-free verification pass per token, and that pass has room for about two dozen candidates. Prompt lookup was leaving most of that room empty by betting on a single match. Filling it with a tree costs nothing the card was not already spending, and it turns the moments a coding agent’s context is ambiguous, several near-identical lines it might copy, from a wrong guess and a re-decode into one pass that quietly picks the right line.