Large language models (LLMs) have rapidly become a foundational component of today’s consumer and enterprise applications. However, the need for a fast generation of tokens has remained a persistent challenge, often becoming a bottleneck in emerging applications. For example, the recent trend of inference-time scaling utilizes much longer outputs to perform search and other complex algorithms, while multi-agent and pipelined LLM systems aim to enhance accuracy and reliability, but both often suffer from long response times due to the wait for multiple processing stages. Addressing this need for accelerated token generation is crucial for the continued advancement and widespread adoption of LLM-powered applications.
Existing model-based speculative decoding methods have limitations that hinder their ability to effectively address the challenge of accelerating token generation in LLMs. First, these methods rely heavily on the size and quality of the draft model, which may not always be available, requiring costly training or fine-tuning to create a suitable model. Second, the integration of draft models and LLMs on GPUs can lead to complications and inefficiencies, such as conflicts between the draft model’s memory usage and the LLM’s key-value cache. To address these issues, recent work has explored incorporating additional decoding heads directly within the LLM to perform speculative decoding. However, these approaches still face similar challenges, as the additional heads require fine-tuning for each LLM and consume significant GPU memory. Overcoming these limitations is crucial for developing more robust and efficient techniques to accelerate LLM inference.
Researchers from Snowflake AI Research and Carnegie Mellon University introduce SuffixDecoding, a robust model-free approach that avoids the need for draft models or additional decoding heads. Instead of relying on separate models, SuffixDecoding uitlizes efficient suffix tree indices built upon previous output generations and the current ongoing inference request. The process begins by tokenizing each prompt-response pair using the LLM’s vocabulary, extracting all possible suffixes (subsequences from any position to the end) to construct the suffix tree structure. Each node in the tree represents a token, and the path from the root to any node corresponds to a subsequence that appeared in the training data. This model-free approach eliminates the complications and GPU overhead associated with integrating draft models or additional decoding heads, presenting a more efficient alternative for accelerating LLM inference.
For each new inference request, SuffixDecoding constructs a separate per-request suffix tree from the current prompt tokens. This design is crucial for tasks where the LLM output is expected to reference or reuse content from the input prompt, such as document summarization, question-answering, multi-turn chat conversations, and code editing. The suffix tree maintains frequency counts at each node to track how often different token sequences occur, enabling efficient pattern matching. Given any sequence of recent tokens from the current generation, SuffixDecoding can quickly traverse the tree to find all possible continuations that appeared in the prompt or previous outputs. At each inference step, SuffixDecoding selects the best subtree(s) of continuation tokens based on frequency statistics and empirical probability. These speculated tokens are then passed to the LLM for verification, which is carried out in a single forward pass thanks to a tree attention operator with a topology-aware causal mask.
Similar to prior work like LLMA and Prompt Lookup Decoding, SuffixDecoding is a model-free approach that sources candidate sequences from a reference corpus. However, unlike previous methods that only considered small reference texts such as a handful of snippets or just the current prompt, SuffixDecoding is designed to utilize a much larger-scale corpus, consisting of hundreds or even thousands of previously generated outputs.
By operating on this larger reference corpus, SuffixDecoding can utilize frequency statistics in a more principled fashion to select likely candidate sequences. To enable fast production of these candidate sequences, SuffixDecoding builds a suffix tree over its reference corpus. The root node of the tree represents the beginning of a suffix from any document in the corpus, where a document is an output of a previous inference or the prompt and output of the current ongoing inference. The path from the root to each node represents a subsequence that appears in the reference corpus, and each child node represents a possible token continuation.
SuffixDecoding uses this suffix tree structure to perform efficient pattern matching. Given the prompt plus generated tokens of the current inference, it identifies a pattern sequence and walks the suffix tree to find all possible continuations that appeared in the reference corpus. While this can produce a large set of candidate sequences, SuffixDecoding employs a greedy expansion and scoring procedure to build a smaller, more likely speculation tree, which is then used in the final tree-based speculative decoding step.
The end-to-end experimental results demonstrate the strengths of the SuffixDecoding approach. On the AgenticSQL dataset, which represents a complex, multi-stage LLM pipeline, SuffixDecoding achieves up to 2.9x higher output throughput and up to 3x lower time-per-token (TPOT) latency compared to the SpecInfer baseline. For more open-ended tasks like chat and code generation, SuffixDecoding still delivers strong performance, with up to 1.4x higher throughput and 1.1x lower TPOT latency than SpecInfer.
The evaluation also examines the effectiveness of SuffixDecoding’s speculative decoding capabilities. SuffixDecoding can achieve a significantly higher average number of accepted speculated tokens per verification step compared to the draft-model-based SpecInfer approach. This indicates SuffixDecoding’s model-free suffix tree structure enables more accurate and reliable speculative token generation, maximizing the potential speedup from speculative decoding without the overhead of maintaining a separate draft model.
This work presents SuffixDecoding, a model-free approach to accelerating LLM inference by utilizing suffix trees built from previous outputs. SuffixDecoding achieves competitive speedups against existing model-based speculative decoding methods across diverse workloads while being particularly well-suited for complex, multi-stage LLM pipelines. By scaling the reference corpus rather than relying on draft models, SuffixDecoding demonstrates a robust direction for improving speculative decoding efficiency and unlocking the full potential of large language models in real-world applications.
Check out the Details here. All credit for this research goes to the researchers of this project. Also, don’t forget to follow us on Twitter and join our Telegram Channel and LinkedIn Group. If you like our work, you will love our newsletter.. Don’t Forget to join our 55k+ ML SubReddit.
[FREE AI WEBINAR] Implementing Intelligent Document Processing with GenAI in Financial Services and Real Estate Transactions
Asjad is an intern consultant at Marktechpost. He is persuing B.Tech in mechanical engineering at the Indian Institute of Technology, Kharagpur. Asjad is a Machine learning and deep learning enthusiast who is always researching the applications of machine learning in healthcare.
