Acceptance-Budgeted Context Trees for On-Device Speculative Decoding

Speculative decoding speeds up a large language model by letting a cheap "drafter" guess several upcoming tokens. The large model then checks all of the guesses in one forward pass and keeps the longest correct prefix, so the output is unchanged. On phones, the drafter is usually a small neural network. That network takes RAM and memory bandwidth away from the large model, and on a phone memory, not arithmetic, is the bottleneck. A drafter with no parameters is an alternative: a lookup structure over previously seen text that predicts continuations from the longest matching recent context. This is a variable-order Markov model, meaning a predictor whose memory length adapts to each context. On server GPUs such drafters already give large speedups. Left alone, however, they grow without bound as text arrives, and nobody has checked how they behave on a phone's memory system.

We propose to give the context tree a fixed byte budget on the device. Branches are kept or cut according to how many extra accepted tokens they actually produced when the large model checked them, per byte they occupy. Classical tree pruning instead asks whether a longer context changes the predicted distribution, and existing suffix-automaton drafters do not prune at all. We will validate the method end to end on real smartphones and IoT boards, measuring latency, energy and memory. The claim is that this design makes a memory-hard drafter with fixed, cache-resident memory usage that matches or beats neural drafters on phones. The experiments are also built to catch the failure case, where drafter design turns out not to matter on the device at all.

Core Claim

Classical prediction suffix trees, introduced in The Power of Amnesia, grow a longer context only when it is frequent and changes the next-symbol distribution. That rule is built for predictive accuracy. A drafter has a different goal: it is paid in tokens the target model accepts. Every verification pass tells us, for free, which context node proposed the draft and how many of its tokens survived. We therefore score each node $s$ by

$$ g(s) = \frac{\hat{A}(s) - \hat{A}(\mathrm{parent}(s))}{b(s)}, $$

where $\hat{A}(s)$ is a running average of accepted draft length when $s$ is the deepest matched context, $\hat{A}(\mathrm{parent}(s))$ is the same quantity had we backed off to the shorter parent context, and $b(s)$ is the node's storage in bytes. Nodes with the lowest $g$ are evicted whenever the total exceeds a budget $B$.

The tree is stored in a flat, hash-addressed array. $B$ is chosen so the array fits in last-level cache, which avoids the scattered memory reads that edge-hardware work flags as a hidden cost. The resulting drafter has a fixed memory footprint, needs no gradient updates, and adapts online to the session.

We expect the gain to appear in the regime EdgeLLM identifies. In that regime the target model barely fits in RAM, and every megabyte used by the drafter can force weights back out to flash. EdgeLLM reports that such weight swapping causes 59–224× slowdowns.

Relation to Prior Work

Two server-side systems supply the drafting mechanism we reuse. ANPD builds multi-level n-gram tables on the fly and backs off from order $N$ down to 2. It reports 3.6665× on HumanEval, and reports that accuracy gains plateau at $N=5$. SAM Decoding uses a dynamic suffix automaton plus a static one built from a corpus. It reaches 120.1 tokens/s for Vicuna-7B on an A6000 against about 80 for Prompt Lookup Decoding. Neither bounds its memory, and neither was run off a server GPU. We keep their match-longest-context-and-propose logic but replace unbounded growth with acceptance-budgeted eviction.

Two on-device systems define the competition. EdgeLLM runs a small neural drafter on phones and IoT boards and reports 3.5–4.7× per-token latency reduction on smartphones. It also finds that target verification takes 52.8–76.3% of cycles. OmniDraft adapts a 68M-parameter drafter online and raises GSM8K acceptance from about 10% to over 40%. It pairs the drafter with an n-gram cache of a few megabytes that has no eviction policy. Both keep a neural network in memory. We test whether a parameter-free tree can take its place.

Three papers constrain the design.

  • Compressed suffix trees reach near-minimal memory for unbounded context, but their queries are 1–2 orders of magnitude slower than flat count tables. They also report perplexity plateaus beyond order 5. We therefore reject succinct structures for the online path and expect most useful nodes to be shallow. Deep nodes should survive mainly where text is copied, as in code and summarization.
  • The self-bounded aPST limits depth using prediction-loss margins, keeping average depth near 5.0 versus 7.0 for a standard tree. It is the closest bounding rule to ours, and we use it as an ablation. It bounds depth, not bytes, and it optimizes prediction rather than acceptance.
  • Transformers learn variable-order Markov chains in-context motivates the substitution. A two-layer transformer reaches 0.7569 log-loss against 0.7400 for context-tree weighting, which suggests small neural predictors largely re-implement "match a suffix, then blend counts." That evidence comes from ternary synthetic data, however. Whether it carries over to 32k-token vocabularies is exactly what our comparison with neural drafters tests.

Research Program

We will build the budgeted drafter as a C++ module inside a llama.cpp-style mobile runtime, with the target model 4-bit quantized. The module has three parts.

  • Session tree. A dynamic context tree over the session's prompt and output, with per-node acceptance statistics updated after every verification.
  • Static seed. An optional small tree built offline from task text, subject to the same byte budget.
  • Eviction. A rule that removes the lowest-$g$ nodes when the budget is exceeded, with a minimum-observation threshold so rare nodes are not evicted on noise.

We will then run the same drafter at budgets from 64 KB to 64 MB on two device classes: a recent Android smartphone and an ARM IoT board. For each configuration we record:

  • per-token latency and throughput;
  • mean accepted draft length;
  • the fraction of wall time spent in the drafter;
  • peak resident memory, page-fault counts and last-level cache misses from hardware counters;
  • energy from an external power monitor.

The analysis question is how accepted length per byte behaves as $B$ shrinks, and whether the acceptance-driven score keeps the curve flat longer than frequency-based or distribution-based pruning.

Baselines

The do-nothing reference is plain autoregressive decoding of the same quantized target on the same device. All speedups are reported relative to it, measured in the same session with the same prompts.

The strongest existing model-free drafter is SAM Decoding, run unchanged on the device, both with and without its static automaton. Its reported figure is 120.1 tokens/s for Vicuna-7B on an A6000, against about 80 for Prompt Lookup Decoding (SAM Decoding). ANPD, whose reported HumanEval speedup is 3.6665× (ANPD), is run alongside it. No reported result for either method on phone or IoT hardware was found on Lacuna, so the paper numbers are not comparable and we will measure both ourselves. Beating them means matching their accepted length at under a tenth of their memory, or giving lower wall-clock latency in the memory-pressure regime.

The strongest on-device method is a neural drafter in the EdgeLLM style, which reports 3.5–4.7× per-token latency reduction on smartphones (EdgeLLM). OmniDraft's online-adapted 68M drafter reports 1.5–2.0× wall-clock and over 40% GSM8K acceptance (OmniDraft). Where their code is unavailable we will reimplement a 68M drafter with the same tree verification. Every method gets the same target, the same quantization, the same draft length (capped at 8, where ANPD reports diminishing returns) and the same total RAM cap. Beating these means lower per-token latency or energy at equal output. A tie at much lower memory is also a meaningful result.

Two ablations isolate the key ingredient. Both keep the identical flat layout and budget $B$ and change only the eviction score: first, a frequency threshold combined with a divergence-from-parent test, as in The Power of Amnesia; second, aPST-style margin bounding. A fourth comparison, a fixed-order 5-gram cache with least-recently-used eviction, is described under the next section. If acceptance-driven scoring does not beat these at small budgets, the central claim fails.

Why not just…?

Why not just run SAM Decoding unchanged on the phone? This is a real threat. If memory is not binding and verification dominates (52.8–76.3% of cycles in EdgeLLM), then the drafter's size and cache behavior may be irrelevant, and unbounded SAM would simply win. Our budget sweep and drafter-time measurements settle this directly. We expect SAM to be fine for short sessions with 7B targets, and to lose in long sessions and with 13B targets near the RAM ceiling, where its growth pushes out target weights. If that loss does not appear, we will report that model-free drafters transfer to phones as-is, which is still a new validation result.

Why not just use a fixed-order n-gram cache with least-recently-used eviction? It is simpler, has predictable memory access, and ANPD's plateau at $N=5$ suggests deep contexts rarely matter. We include it at identical budgets. Our prediction is that it wastes bytes on common short contexts that the target model would have accepted anyway. It should also drop the rare long copy contexts that produce long accepted runs on HumanEval and CNN/DM. If it matches our method, the variable-order ingredient is unnecessary and we will say so.

Why not just keep a small neural drafter? EdgeLLM and OmniDraft show that neural drafters work on phones and adapt well. The question is cost at equal memory. A 68M drafter at 4 bits still occupies tens of megabytes and competes for bandwidth. OmniDraft's online variant also needs on-device gradient updates. The equal-RAM-cap comparison, together with the energy measurements, decides this. A neural drafter could still win on open-ended dialogue with little repetition, and we will report results per task rather than averaged.

Why not just bound depth as the aPST does? Depth bounds do not control bytes, since a wide shallow tree can still be large. Loss margins also reward predictive accuracy rather than accepted tokens. The eviction-score ablation tests exactly this difference.

Proposed Experiments

Tasks are Spec-Bench, HumanEval, GSM8K, CNN/DM and XSum, plus EdgeLLM's WMT14 and Wikitext settings for continuity with the on-device literature. Targets are Vicuna-7B and LLaMA-2-7B, with LLaMA-2-13B as the memory-wall case. We run fixed-length sessions of 2k tokens and long sessions of 50k tokens so that growth under unbounded baselines becomes visible.

Three results are decisive, and each can falsify part of the proposal.

  • Accepted length per byte. The first result is the curve of accepted length against budget $B$, for acceptance scoring versus the frequency, divergence, margin and least-recently-used scores. The claim needs acceptance scoring to hold within 10% of unbounded-SAM acceptance at budgets at least ten times smaller.
  • Memory-pressure regime. The second is wall-clock latency and energy for 13B on the phone under a fixed RAM cap, with page faults logged. The claim needs the budgeted tree to beat both unbounded SAM and the neural drafter there.
  • Does drafter design matter at all? The third is the drafter's share of wall time and its cache-miss rate across devices. If that share stays below a few percent and memory never binds, the contribution reduces to measurement: model-free drafters work on phones unchanged. We will state that as the finding instead of claiming a new method.