mlsanityData to 7 Oct 2026

Efficient Beam Search for Large Language Models Using Trie-Based Decoding

arXiv 2502.00085 ↗First posted 31 Jan 2025cs.CLcited by 10

On the map: Efficient LLM inference and serving → KV cache optimization

Abstract (arXiv)

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×) and up to 2.4× faster decoding, without compromising generation quality. These results highlight our method's suitability for memory-constrained environments and large-scale deployments.

Key facts. Cited by 10 papers in the map (data through 7 Oct 2026). Placed in KV cache optimization, one of 12 directions in Efficient LLM inference and serving. Builds on 19 of its 28 references that are in the map. First posted on arXiv 31 Jan 2025.

Builds on

19 of 28 references.

References · 19

  1. 2017Attention Is All You Needcited by 59,932
  2. 2020Retrieval-Augmented Generation for Knowledge-Intensive NLP Taskscited by 9,160
  3. 2021Evaluating Large Language Models Trained on Codecited by 8,053
  4. 2021Measuring Mathematical Problem Solving With the MATH Datasetcited by 5,203
  5. 2014Neural Machine Translation by Jointly Learning to Align and Translatecited by 4,530
  6. 2022FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awarenesscited by 3,611
  7. 2023Let's Verify Step by Stepcited by 3,598
  8. 2023FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioningcited by 2,551
  9. 2019Generating Long Sequences with Sparse Transformerscited by 1,523
  10. 2016Google's Neural Machine Translation System: Bridging the Gap between Human and Machine Translationcited by 1,471
  11. 2024Medusa: Simple LLM Inference Acceleration Framework with Multiple Decoding Headscited by 821
  12. 2016Abstractive Text Summarization Using Sequence-to-Sequence RNNs and Beyondcited by 809
7 more
  1. 2023SpecInfer: Accelerating Generative Large Language Model Serving with Tree-based Speculative Inference and Verificationcited by 359
  2. 2023Accelerating LLM Inference with Staged Speculative Decodingcited by 151
  3. 2021Neural Path Hunter: Reducing Hallucination in Dialogue Systems via Path Groundingcited by 106
  4. 2023GPT4Rec: A Generative Framework for Personalized Recommendation and User Interests Interpretationcited by 101
  5. 2019Comparison of Diverse Decoding Methods from Conditional Language Modelscited by 78
  6. 2019How Decoding Strategies Affect the Verifiability of Generated Textcited by 27
  7. 2024Towards Reliable Medical Question Answering: Techniques and Challenges in Mitigating Hallucinations in Language Modelscited by 15

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 4; 2026: 6.

10 papers.

  1. 2025xLLM Technical Reportcited by 3
  2. 2025Saffron-1: Safety Inference Scalingcited by 1
  3. 2026Efficient Test-Time Inference via Deterministic Exploration of Truncated Decoding Treescited by 1
  4. 2025CoVeR: Conformal Calibration for Versatile and Reliable Autoregressive Next-Token Predictioncited by 0
  5. 2025Democratizing LLM Efficiency: From Hyperscale Optimizations to Universal Deployabilitycited by 0
  6. 2026PRISM: Purified Representation and Integrated Semantic Modeling for Generative Sequential Recommendationcited by 0
  7. 2026Suffix-Constrained Greedy Search Algorithms for Causal Language Modelscited by 0
  8. 2026DocQAC: Adaptive Trie-Guided Decoding for Effective In-Document Query Auto-Completioncited by 0
  9. 2026Regulating Branch Parallelism in LLM Servingcited by 0
  10. 2026Trie Automata for Constrained Decoding over Large Finite Setscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Bifurcated Attention: Accelerating Massively Parallel Decoding with Shared Prefixes in LLMs
  2. 2025Hardware-Efficient Attention for Fast Decoding
  3. 2024DeFT: Decoding with Flash Tree-attention for Efficient Tree-structured LLM Inference
  4. 2026SwiftKV: An Edge-Oriented Attention Algorithm and Multi-Head Accelerator for Fast, Efficient LLM Decoding
  5. 2026Multi-Head Low-Rank Attention
  6. 2024Dynamic-Width Speculative Beam Decoding for Efficient LLM Inference
  7. 2024TriForce: Lossless Acceleration of Long Sequence Generation with Hierarchical Speculative Decoding
  8. 2025PAT: Accelerating LLM Decoding via Prefix-Aware Attention with Resource Efficient Multi-Tile Kernel