Efficient Beam Search for LLMs Using Trie-Based Decoding
Brian J Chan, MaoXun Huang, Jui-Hung Cheng, Chao-Ting Chen, Hen-Hsen Huang · 2025
Read Efficient Beam Search for LLMs Using Trie-Based Decoding by Brian J Chan, MaoXun Huang, Jui-Hung Cheng, Chao-Ting Chen, Hen-Hsen Huang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-00085.txt.
Introduction
Brian Chan, MaoXun Huang, Jui-Hung Cheng, Chao-Ting Chen, and Hen-Hsen Huang speed up a search step in text generation in a 2025 paper. Beam search keeps several draft lines alive at once and grows the best ones. The standard way stores a full memory cache for each draft, which wastes room when drafts share long starts.
Their fix stores shared starts once, in a tree-shaped store, and lets all drafts draw from it. Tests ran on three model types, on news summary and code tasks. Memory fell by four to eight times, and speed rose up to 2.4 times, with no loss in text quality. Tight devices and big fleets both stand to gain.
Catalog record
| CREATOR | Brian J Chan, MaoXun Huang, Jui-Hung Cheng, Chao-Ting Chen, Hen-Hsen Huang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 40 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-00085
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Efficient Beam Search for LLMs Using Trie-Based Decoding Brian J Chan, MaoXun Huang, Jui-Hung Cheng, Chao-Ting Chen, Hen-Hsen Huang Abstract This work presents a novel trie (prefix-tree)-based parallel decoding method that addresses the memory inefficiency of batch-based beam search. By sharing a single KV cache across beams with common prefixes, our approach dramatically reduces memory usage and enables efficient decoding. We evaluated our method across three attention architectures, Multi-Head Attention (Phi-3.5-mini-instruct), Grouped Query Attention (Llama-3.1-8B-Instruct), and Sliding Window Attention (Mistral-Small-24B-Instruct-2501), using CNN/DailyMail for abstractive summarization and HumanEval for code generation. Our experiments demonstrate substantial memory savings (4–8 × \times ) and up to 2.4 × \times faster decoding, without compromising generation quality. These results highlight our method’s suitability for memory-constrained environments and large-scale deployments. 1 Introduction Large language models (LLMs) face significant deployment challenges due to their high memory requirements. For example, the 8-billion-parameter Llama 3.1 model, when deployed in float16 precision, requires approximately 15.7GB of GPU memory solely for its model parameters. Processing an 8k token sequence adds another 2.5GB for the key-value (KV) cache. These constraints make efficient memory utilization a critical factor in optimizing LLM performance. Memory optimization not only reduces hardware requirements but also accelerates inference. Modern GPUs often exhibit faster computation speeds than memory transfer rates, leading to a memory-bound performance bottleneck. Addressing this bottleneck has spurred innovations like Flash Attention ( Dao et al., 2022 ; Dao, 2024 ) , which minimizes memory operations. Efficient memory usage reduces the overhead of transferring data within the GPU, enhancing both speed and scalability. The decoding process plays a pivotal role in the performance and quality of sequence generation in LLMs. Typical decoding strategies fall into three categories: greedy decoding, top- k sampling, and beam search. Greedy decoding selects the most probable token at each step, offering simplicity but often failing to recover from suboptimal decisions. Top- k sampling introduces diversity by choosing the next token from the k most probable options based on their probabilities. While effective for generating varied outputs, top- k sampling is prone to hallucination ( Dziri et al., 2021 ) , limiting its applicability for tasks requiring high factual accuracy, such as programming, math, or retrieval-augmented generation (RAG) ( Lewis et al., 2020 ; Pham and Vo, 2024 ) . Beam search, on the other hand, maintains multiple candidate sequences (beams) at each time step and ultimately selects the one with the highest overall probability. Unlike greedy search, beam search can “look ahead” to identify sequences that may start with lower-probability tokens but lead to better overall outcomes. By keeping multiple hypotheses, beam search can recover from locally suboptimal decisions, often yielding better results than greedy decoding in certain tasks that require high accuracy, like recommendation ( Li et al., 2023 ) and coding. However, its computational cost and memory demands make it less practical for real-world applications, especially at scale. Beam search’s high memory consumption stems from its handling of KV caches. While beam search explores multiple branches originating from a shared prefix, conventional batch-based implementations allocate independent KV caches for each branch, leading to significant memory redundancy, as overlapping tokens across branches are stored multiple times. Such inefficiencies make memory optimization crucial for scalable and cost-effective deployment. Figure 1: With beam width b=3 , the top panel shows multiple explored hypotheses. The middle illustrates conventional beam search, which stores redundant prefixes (e.g., “Once upon a time,”) in separate caches. The bottom shows our trie-based approach, consolidating overlaps into a shared trie to reduce memory while preserving beam width and behavior. Red tokens (e.g., “far”, “a”) indicate pruned branches, and position IDs are reassigned to match conventional beam search. In this paper, we propose a novel trie (prefix tree)-based decoding method that significantly reduces memory usage in beam search by leveraging the hierarchical structure of shared prefixes among branches. Our approach consolidates all branches into a single shared kernel using a trie search strategy. As shown in Figure 1 , this method stores only unique tokens corresponding to shared prefixes, reducing memory consumption by eliminating redundant KV cache entries. For instance, in the illustrated example, our approach requires storing only 12 tokens, compared to the 21 tokens required by conventional batch-based methods. The idea of trie-based decoding introduces two challenges. First, tokens from different beams may inadvertently attend to one another, resulting in corrupted outputs. Second, eliminated tokens may remain in memory, contradicting the goal of efficient memory usage. To address these issues, we adapt the attention mechanism to isolate branch-specific contexts and employ dynamic pruning to remove low-probability branches, ensuring both correctness and memory efficiency. These innovations enable our approach to achieve substantial memory savings while maintaining inference speed, offering a scalable solution for deploying LLMs in resource-constrained settings. We conduct experiments to evaluate our trie-based decoding approach against greedy decoding and conventional batch-based beam search across three attention variants and two datasets, showing the correctness and robustness of our method. The results demonstrate that our method achieves comparable performance to batch-based beam search with the same beam width, while substantially reducing memory usage, particularly for larger beam widths. Our contributions are as follows: 1. We propose a trie-based decoding method that significantly reduces memory usage during beam search by consolidating KV caches among beams with common prefixes, effectively addressing a critical limitation of batch-based beam search. 2. Under dense attention, our approach is theoretically equivalent to conventional beam search while substantially reducing memory overhead. Empirical results across three transformer architectures, Multi-Head, Grouped Query, and Sliding Window Attention, demonstrate that it preserves output quality, with differences from conventional beam search being statistically insignificant. 3. We release our implementation, 1 1 1 https://github.com/brian030128/tridecode offering a scalable and practical decoding alternative. Unlike greedy decoding or top- k sampling, our method retains beam search’s robustness with significantly lower computational overhead, enabling efficient deployment of LLMs. 2 Related Work The evolution of decoding methods for language models in natural language processing (NLP) has been a subject of extensive research, focusing on improving both efficiency and output quality. This section reviews key developments in decoding strategies, including beam search, sampling methods, hybrid approaches, and recent advancements in computational efficiency. The work of Bahdanau et al. (2016) marked a pivotal moment in NLP, introducing the attention mechanism, which allowed models to dynamically focus on relevant parts of the input sequence during generation. This breakthrough significantly improved translation quality, especially for long sentences. Notably, the study employed beam search as its decoding method—a technique that had already gained traction in statistical machine translation. Following this milestone, beam search became the dominant decoding method, as evidenced by its use in prominent works like Vaswani et al. (2017) and Wu et al. (2016) . Beam search’s ability to maintain multiple hypotheses during decoding often resulted in outputs that were more coherent and grammatically accurate, solidifying its popularity in constrained tasks. Comparative analyses of decoding strategies have highlighted the trade-offs between beam search and sampling. Ippolito et al. (2019) showed that while sampling methods generate more diverse outputs, they often compromise coherence and factual accuracy. Similarly, Massarelli et al. (2020) emphasized the susceptibility of sampling to hallucinations, contrasting this with beam search’s strengths in accuracy and faithfulness, albeit at the