One-sentence Summary

Harbin Institute of Technology and Du Xiaoman Science Technology Co., Ltd. propose Token Recycling, a training-free speculative decoding method that recycles candidate tokens produced during decoding into an adjacency matrix and constructs draft trees via a BFS-like search validated through tree attention, achieving approximately $2\times$2× speedup across all LLM sizes with under 2MB additional storage and outperforming existing training-free methods by $30\%$30%.

Key Contributions

• Token Recycling is a train-free speculative decoding method that recycles candidate tokens produced during LLM inference to build draft token trees without additional draft models or large external retrieval corpora. It can be integrated with existing LLMs without model-specific training.

• Candidate tokens are stored in an adjacency matrix and retrieved through a breadth-first-search-like procedure to construct a draft tree, which is validated via tree attention while new decoding candidates continuously update the matrix. This produces an adaptive, low-overhead retrieval structure for parallel verification.

• The method requires less than 2 MB of additional storage and achieves approximately 2x inference speedup across LLM sizes, improving over prior train-free speculative decoding methods by 30% and outperforming a widely used training-based method by 25%.

Introduction

Large language models power chatbots, code assistants, and agents, but their token-by-token decoding creates high latency because each step must move large model parameters from memory to accelerator cache. Speculative decoding reduces this cost by guessing draft tokens and verifying them in parallel, using techniques like tree attention to check multiple continuations at once.

Prior work often relies on additional draft models, retrieval from existing corpora, or simple reuse of prior text. These approaches require extra training, large static libraries, slow retrieval, or cannot predict new tokens efficiently. They also discard useful candidate tokens generated during decoding.

The authors propose Token Recycling, a train-free speculative decoding method that reuses these candidate tokens as draft tokens. It stores them in a small adjacency matrix, retrieves a draft tree before each step, verifies it with tree attention, and updates the matrix with new candidates. This yields about 2x speedup, improves previous train-free methods by more than 31%, and needs less than 2 MB of storage.

Method

The authors leverage Token Recycling as a training free and model agnostic speculative decoding framework. It reuses information that has already been produced during LLM forward passes by converting previously generated candidate tokens into future draft tokens. The pipeline contains three coupled modules: adjacency matrix initialization, draft tree retrieval, and verification plus matrix update. Refer to the framework diagram.

The first module stores top k candidate tokens in an adjacency matrix, denoted as $\mathcal{M} \in \mathcal{V}^{|\mathcal{V}|\times k}$M∈V∣V∣×k, where $\mathcal{V}$V is the vocabulary and $k$k is a user defined hyperparameter. Each element $\mathcal{M}[i,j]$M[i,j] indicates that the token $\mathcal{V}_{\mathcal{M}[i,j]}$VM[i,j]​ is the $j$jth candidate token associated with $\mathcal{V}_i$Vi​. This matrix format enables efficient parallel retrieval and parallel updating, which is important for reducing overhead compared with structures such as trie based lookup tables. Instead of starting from an entirely empty matrix, the authors use a hot start strategy by inheriting the existing matrix from prior inference. This keeps commonly observed expressions and patterns available from the beginning, giving the retrieval process a broader initial search space.

The second module constructs a draft tree using a BFS inspired traversal over the adjacency matrix. The root of the tree is the last token of the current content. The algorithm first extracts the top k candidates for this token, then recursively expands each candidate according to a fixed tree structure. The tree is static because the number of children for each node remains constant across decoding steps, which allows preprocessing and supports efficient parallel operations during layer traversal. The tree is imbalanced because nodes with higher probability, which appear earlier in each layer, are assigned more children and can extend deeper. This design directs computational resources toward the most likely continuations while still exploring multiple alternative paths in parallel.

After the draft tree is retrieved, its nodes are arranged into a merged sequence through layer by layer traversal. The merged sequence is fed into the LLM together with the existing prefix and verified with tree attention. Tree attention allows all candidate paths in the merged sequence to be checked in a single forward pass, and the longest correct sequence is selected as the output for that step. Because the matrix stores top k candidates, the verification stage does not need to test only one linear draft continuation. Instead, it can evaluate multiple parallel continuations that were generated by expanding different candidate tokens.

Following verification, the authors update the adjacency matrix in parallel using the output distributions produced by the model. For each draft token $x_i$xi​ in the verified sequence, the matrix entry is updated according to the most probable next tokens:

This update overwrites the previous candidates for the current token with the newly produced top k candidates. The authors do not add extra conflict resolution logic for duplicated tokens because doing so can reduce overall performance. The update process therefore keeps the retrieval space aligned with the current content and allows the matrix to continuously adapt to the local context. This creates a recycling loop in which candidate tokens become draft tokens, and output distributions generated during standard LLM decoding refresh the matrix for later steps.

Experiment

The experiments evaluate a training-free retrieval-based speculative decoding method on SpecBench and MBPP with Vicuna and Code Llama across scales, benchmarking against Lookahead, PLD, REST, and Medusa. Main results show consistent acceleration and high accepted-token rates across general, code, and context-sensitive tasks, with the method remaining efficient under limited memory. Ablations and analyses validate that tree breadth and depth have trade-offs, adaptive updates and rejected-token feedback improve draft acceptance, initialization patterns generalize, and robustness holds under sampling while added overhead remains small. Comparisons with Eagle indicate strong efficiency, achieving performance close to a training-dependent method with minimal memory footprint.

The compared training-free approach consistently delivers the strongest overall speedup on both SpecBench and MBPP, outperforming prior training-free methods and the tuned Medusa baseline on SpecBench. Its benefit is broadly consistent across task types and model sizes, though PLD can remain competitive on summarization because repeated content favors prior-based matching. The reported MAT and throughput results also indicate low extra decoding overhead. The method gives the best speedups across most SpecBench tasks and on MBPP, where Medusa is absent. Its relative advantage is preserved as model size increases, with the Sum gap to PLD narrowing for larger models. It records the highest MAT while retaining strong token throughput, reflecting efficient self-drafting and short retrieval overhead.

The comparison highlights the tradeoff between additional memory cost and acceleration across speculative decoding methods. TR achieves the highest speed with a much smaller memory overhead than Medusa, while PLD uses no extra memory but trails TR in speed. TR provides the best speed while adding only a small memory overhead. Medusa requires a substantially larger memory footprint than TR and still trails in speed. PLD has zero additional memory cost but does not match TR's acceleration.

Initialization from a prior adjacency matrix substantially improves decoding speed compared with all-zero initialization. Random vocabulary-based initialization performs sharply worse, indicating that irrelevant token noise harms performance. Fixed, shuffled, and inherited matrix settings achieve closely related gains, suggesting that reusable prior patterns are broadly generalizable. A prior adjacency matrix captures common patterns that assist subsequent queries. Random initialization introduces harmful noise and reduces throughput and speedup. Fixed, shuffled, and inherited initialization strategies achieve similar performance, indicating task-agnostic useful patterns.

Updating candidate tokens using all draft tokens produces higher mean accepted tokens than using only accepted tokens. This trend appears on both benchmarks, showing that rejected draft tokens still provide useful information for later decoding. All draft tokens improve mean accepted tokens over accepted-only updates Rejected tokens remain useful for speculative decoding

TR is training-free and self-drafting, yet it slightly outperforms Eagle1 in both throughput and speedup. Compared with Eagle2, TR retains most of the acceleration while using only a tiny fraction of the memory, despite relying on a static tree. TR surpasses Eagle1 without requiring a separately trained draft model. TR approaches Eagle2's speedup with dramatically lower memory use. TR remains effective even when using a static tree rather than dynamic tree construction.

Experiments on SpecBench and MBPP evaluate training-free speculative decoding through end-to-end speedup, memory cost, initialization choices, candidate updates, and comparison with trained Eagle methods. The method delivers the strongest overall speedup and high throughput with only modest memory overhead, outperforming Medusa and approaching trained baselines while remaining robust across task types and model sizes. Prior adjacency initialization and updating candidates with all draft tokens further improve acceptance, showing that reusable token patterns and even rejected drafts carry useful information.