LLM Decoding Without Changing Output Bytes

Thesis

Autoregressive generation is serial by construction: each byte waits for the one before it. That serialization is the dominant latency cost of running a language model interactively, and it is especially punishing for a byte-level model, which emits four times as many steps per character as a subword model. The good news is that a family of techniques, speculative decoding and multi-token prediction, attacks this latency without touching output quality. Done correctly, the bytes that come out are identical to what the slow path would have produced. This article reports what we measured when we ported that family to Veritate's byte-level models, and why byte-level decoding turns out to have enough internal agreement for the techniques to work.

The Public Frame

Speculative decoding (Leviathan et al., 2023; Chen et al., 2023) uses a small fast drafter to propose several tokens at once and the full model to verify them in a single parallel pass, accepting the run of correct guesses and falling back to normal decoding at the first mismatch. Because the full model does the verifying, the output is provably the same as standard decoding. Medusa (Cai et al., 2024) attaches extra prediction heads to the model itself so it can draft several tokens ahead with no separate drafter, and EAGLE (Li et al., 2024) drafts at the feature level with a small extra decoder layer. These methods are now standard in production inference stacks. The open question for us was whether byte-level prediction is internally consistent enough for any of them to pay off, since the whole approach lives or dies on the acceptance rate.

Is There Enough Agreement at Byte Level?

We measured this directly before building anything. Sampling eight continuations per position on real text from our byte-level 85M, 56.2 percent of positions showed unanimous agreement on the most likely byte and 74 percent showed a majority of at least six of eight. On genuinely low-entropy positions (under half a bit), mean agreement was 7.95 out of 8. This matches the published acceptance ceilings for speculative methods, which sit in the 60-to-80 percent range, and it tells us the byte stream is locally predictable enough for draft-and-verify to have real headroom. The heavy-tailed entropy structure described elsewhere in this series is the reason: most bytes are nearly determined, so a cheap drafter is right most of the time.

What We Built and Measured

The cheapest lever, the key-value cache, gives a 19-times speedup at a 512-byte context, byte-exact, simply by not recomputing past positions. On top of that we trained a four-byte multi-token-prediction head; it improved training-time cross-entropy slightly while adding 2.76 percent to parameters, and at decode time it doubles as a drafter.