Cacheback: Speculative Decoding With Nothing But Cache

AI summary

Overview

Research area: Efficient LLM inference, specifically speculative decoding and n-gram caching for language models.

Technical level: Intermediate. The paper assumes familiarity with how LLM decoding works and what speculative decoding is, but its central idea is simple enough to follow without deep background in the underlying systems literature.

Scope: The paper introduces and evaluates Cacheback Decoding, a training-free, model-agnostic speculative decoding method that drafts tokens using only Least Recently Used (LRU) cache tables of token n-grams.

What This Paper Is About

Speculative decoding speeds up LLM generation by having a cheap "drafter" guess several upcoming tokens, which the full model then verifies in a single forward pass. Most effective drafters either need training, need a separate smaller model, or need modifications to the target LLM. This paper asks whether a plain LRU cache of recently seen token n-grams, an idea borrowed from 1990s Cache Language Models, can serve as the drafter instead, and shows that it can match or beat far more elaborate training-free, model-agnostic methods.

Key Contributions

1. Cacheback Decoding, a speculative decoding method that generates draft token trees by recursively querying LRU cache tables mapping leader n-grams to follower n-grams, with no auxiliary neural model and no training.
2. A dual-table design combining a dynamic in-decoding cache with an offline frozen table built from frequent n-grams in a large corpus, plus prompt-window initialization, to address the cold-start problem.
3. An open-source implementation integrated into the SpecBench benchmark suite, with frozen cache tables released publicly on Hugging Face.
4. An empirical study on SpecBench with Vicuna 7B, 13B, and 33B models comparing Cacheback against SAM Decoding, PLD, Lookahead Decoding, REST, and Token Recycling, including an analysis of how leader length and follower length settings affect speedup.

Main Findings

• Competitive with far more sophisticated drafters: On SpecBench, Cacheback is on par with SAM Decoding, which is based on suffix automata, and outperforms PLD (brute-force string matching), Lookahead Decoding (parallel Jacobi iteration), REST (database lookup), and Token Recycling (adjacency matrix construction). The abstract describes this as state-of-the-art performance among comparable methods, meaning those that require neither draft model training nor model architecture changes.
• Dual-table initialization is necessary: With the dual-table approach, Cacheback reaches a 1.86x speedup, 2.42 mean accepted tokens (MAT), and 103.71 tokens/s on SpecBench with Vicuna 7B. Without the frozen table it drops to 1.64x, 1.96 MAT, and 91.32 tokens/s. Using only the frozen table is worse still at 1.28x, 1.59 MAT, and 68.11 tokens/s.
• Best configuration is LL = 1 with FL around 3: Cacheback consistently performs best when the leader length is 1 and the follower length is around 3. The authors attribute this to LL = 1 returning more candidate followers with recent occurrences, while FL = 3 best balances the number of drafts against draft length.
• Translation is where Cacheback stands out most: The translation task is hard for every evaluated speculative decoding method, partly because generated words have little token-level relevance to the input context. Cacheback's lead there suggests it can exploit locality in the output text itself, which points to fast domain adaptation and usefulness for low-resource languages where training a draft model is difficult.
• Negligible drafting overhead: Draft generation typically executes in microseconds, so it adds little cost to the decoding loop.
• Constant-time table operations: Lookup, insertion, and eviction are all O(1), implemented with hash maps plus doubly linked lists ordered by recency, and the prototype simply uses Python's OrderedDict. Memory consumption is bounded by O(LL · LC · FL · FC), and with the paper's configuration a fully populated table uses at most a few GiB of DRAM.
• The method is lossless by construction: Because Cacheback follows the standard validate-and-accept framework, and the LLM's forward pass always generates one additional token beyond whatever drafts are accepted, a decoding step yields one token in the worst case and one plus the longest accepted branch length in the best case.

Methodology in Plain English

The authors keep only a table. Each entry pairs a short sequence of tokens (the leader) with the sequences that were seen immediately after it (the followers). At every decoding step, the system takes the last few tokens of the current sequence, looks them up, and gets back candidate continuations. It then grows those continuations into a branching tree of possible drafts by repeatedly looking up the tails of each branch, stopping when the tree reaches a preset size (the total draft length, TDL) or when no branch has any followers left. A chaining-reserved tokens (CRT) parameter controls how much of the tree budget goes to deeper levels rather than a wide first level.

The full LLM then checks all the drafted branches at once using tree attention, an attention mask that lets each token attend only to its ancestors in the tree. Branches are accepted from the root down until a mismatch. At the end of the step, a sliding window over the accepted tokens is inserted back into the cache, evicting the least recently used entries when capacity is exceeded.

Two caches work together. The dynamic one learns from the current generation and is seeded with the prompt before decoding begins. The frozen one is built offline by sampling 1% of the OpenWebText dataset, taking the most frequent leaders of length LL and, for each, the most frequent followers of length FL. The dynamic table is queried first, then the frozen table to extend the tree further. The frozen table never absorbs new entries.

Experiments ran on a desktop machine with an AMD Ryzen 5965WX CPU and four NVIDIA RTX 4090 GPUs, using one, two, and four GPUs for Vicuna 7B, 13B, and 33B respectively. Cacheback was configured with LL = 1, LC = 2^20, FL = 3, FC = 128, TDL = 96, and CRT = 16, chosen empirically. The authors modified SpecBench in two ways for fairness: stateful methods (SAM Decoding, Token Recycling, and Cacheback) have their state reset before each test case, and the static automaton from the SAM repository was built and included when running SAM. They also fixed the SpecBench implementations of REST and Token Recycling so they run with multiple GPUs. Lookahead Decoding could not be run with multiple GPUs in the current testing framework.

Why This Matters

Impact on research. The paper revives a 1990s idea, the Cache Language Model, and redirects it from improving modeling quality to accelerating inference. It is a data point that minimalist, training-free heuristics can compete with elaborate systems, which challenges the assumption that better speculative decoding requires learned drafters or architectural changes. Because Cacheback produces drafts as a tree, it is structurally compatible with other speculative decoding methods, so their predictions could be inserted as extra branches, in the same spirit as the reported combination of SAM decoding and EAGLE.

Real-world applications.

• LLM serving and chat systems, where Cacheback can be dropped into an existing inference framework as a plug-and-play component with no model retraining or architecture modification.
• Code generation and IDE assistants. The paper notes that programming languages exhibit locality just as natural languages do, making coding copilots a natural fit.
• Translation and low-resource language generation, where training a dedicated draft model is impractical. The paper specifically highlights Cacheback's lead on the translation task.
• Domain-specialized generation, because the method's inherited CLM strengths let it adapt quickly to a specific domain through the cache rather than through weight updates.

Industry relevance. The requirements are modest: standard library data structures, CPU-side memory on the order of a few GiB for a fully populated table, and microsecond-scale drafting overhead. That makes adoption unusually low-friction for production inference stacks that cannot afford to train or ship an additional draft model per target LLM, and it applies uniformly across any model because the approach is model-agnostic.

Future Directions

• Dynamic cache scaling and automatic parameter tuning. The authors report that Cacheback is sensitive to configuration parameters, that optimal values likely vary across tasks, language models, and hardware, and that a theoretical analysis of these parameters is still lacking.
• Studying frozen-table corpora. How the choice of corpus for initializing the frozen table affects performance is explicitly left unstudied.
• Broadening the evaluation. The current results are limited to the SpecBench dataset, and performance variation across different GPU architectures and LLM models remains unexplored.
• Custom GPU kernels. The authors note that a custom kernel may improve Cacheback's performance and leave this as a future direction.
• Combining with other speculative decoding methods. Since Cacheback organizes drafts as a tree, other methods' predicted drafts could be added as extra branches for further speedup.

Target Audience

Researchers and engineers working on LLM inference efficiency, speculative decoding, and serving infrastructure will get the most from this paper. It is also relevant to practitioners who need a plug-and-play acceleration method that works with any model and requires no training or architecture changes, and to readers interested in how classical n-gram and cache-based NLP techniques can be repurposed for modern large models.

Authors’ abstract

We present Cacheback Decoding, a training-free and model-agnostic speculative decoding method that exploits the locality in language to accelerate Large Language Model (LLM) inference. Cacheback leverages only Least Recently Used (LRU) cache tables of token n-grams to generate draft sequences. Cacheback achieves state-of-the-art performance among comparable methods despite its minimalist design, and its simplicity allows easy integration into existing systems. Cacheback also shows potential for fast adaptation to new domains.