@inproceedings{chan-etal-2025-efficient,
    title = "Efficient Beam Search for Large Language Models Using Trie-Based Decoding",
    author = "Chan, Brian J  and
      Huang, Mao-xun  and
      Cheng, Jui-Hung  and
      Chen, Chao-Ting  and
      Huang, Hen-Hsen",
    editor = "Christodoulopoulos, Christos  and
      Chakraborty, Tanmoy  and
      Rose, Carolyn  and
      Peng, Violet",
    booktitle = "Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing",
    month = nov,
    year = "2025",
    address = "Suzhou, China",
    publisher = "Association for Computational Linguistics",
    url = "https://preview.aclanthology.org/ingest-emnlp/2025.emnlp-main.748/",
    pages = "14806--14818",
    ISBN = "979-8-89176-332-6",
    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."
}