Abstract
As a crucial method in prompt engineering, In-Context Learning (ICL) enhances the generalization and knowledge utilization capabilities of Large Language Models (LLMs) (Dong et al., 2024). However, the lengthy retrieved contexts and limited token throughput in autoregressive models significantly constrain reasoning speed. To address this challenge, we propose N-Gram Trie Speculative Decoding, a novel approach that leverages the overlap between context and model output. This method constructs an n-gram trie from the context to generate drafts, accelerating token generation for LLMs. We evaluate our approach on summarization, Retrieval-Augmented Generation (RAG), and context-based Question Answering (QA) tasks. Experimental results on Vicuna-7B, Llama2-7B-Chat, and Llama3-8B-Instruct demonstrate substantial speed improvements without compromising accuracy. Compared with various strong baselines, our method achieves the highest mean speedup, showcasing its effectiveness and efficiency.
Introduction
In-Context Learning (ICL) has become the backbone of modern AI applications such as Retrieval-Augmented Generation (RAG) and long-document summarization. However, these applications suffer from a significant "speed tax." Because LLMs generate text autoregressively—one token at a time—processing long retrieved contexts is computationally expensive and slow.
Existing solutions like standard Speculative Decoding typically require a secondary, smaller "draft model," which introduces memory overhead and requires complex training. Other methods, such as Lookahead Decoding, are often limited to repetitive patterns. This paper identifies a specific opportunity: in ICL, the model’s output often overlaps significantly with the provided context. By exploiting this overlap, we can accelerate generation without the need for additional models or training.
Methodology
We introduce N-Gram Trie Speculative Decoding, a plug-and-play framework that operates in three main phases:
- N-Gram Trie Construction: Before generation begins, the system scans the input context using a sliding window to create an N-gram trie. This trie stores the dependencies between sequences (prefixes) and the tokens that follow them (suffixes).
- Drafting via Trie: During inference, the system monitors the tokens generated by the LLM. If a sequence matches a prefix in the trie, the trie "speculates" the next several tokens as a draft.
- Tree Attention Verification: Instead of checking guesses sequentially, the system utilizes "Tree Attention." This allows the target LLM to verify multiple potential paths from the trie simultaneously in a single forward pass. If the guesses are correct, the model jumps forward multiple tokens; otherwise, it reverts to standard generation.
Crucially, building the trie is highly efficient, taking approximately 10ms, which is negligible compared to the generation time saved. To maintain a manageable draft tree, the system employs frequency-based pruning to prioritize the most likely sequence continuations.
Experimental Evaluation
The approach was evaluated across several benchmarks, including Spec-Bench (Summarization and RAG), TriviaQA, and Hagrid (context-based QA). We tested the method using popular open-source models: Vicuna-7B, Llama2-7B-Chat, and Llama3-8B-Instruct.
Key Results
The method consistently outperformed strong baselines such as Medusa, REST, and Lookahead Decoding:
- Vicuna-7B: Achieved a 2.27x mean speedup.
- Llama2-7B-Chat: Achieved a 2.10x mean speedup.
- Llama3-8B-Instruct: Achieved a 1.56x mean speedup.
- Peak Performance: In specific RAG tasks using Llama2, the speedup reached as high as 3.62x.
Because the target LLM always verifies the drafts, the output quality remains identical to standard decoding, ensuring zero loss in accuracy.
Discussion and Conclusion
N-Gram Trie Speculative Decoding demonstrates that for tasks like RAG or QA, the context itself can act as a highly accurate, zero-cost draft model. While the speedup is directly tied to the degree of overlap between the input context and the model's output, the method provides robust gains even in the presence of noisy or irrelevant information.
Future work will explore more sophisticated frequency-weighting schemes and context-aware candidate selection to further improve the acceptance rate of speculated tokens in creative or less-repetitive tasks.
Reference: Chen, J., et al. (2025). Faster In-Context Learning for LLMs via N-Gram Trie Speculative Decoding. Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing (EMNLP).
Summary updated