@inproceedings{anandakumar-etal-2026-flashtrie,
title = "{F}lash{T}rie: A {GPU}-Accelerated Constrained Beam Search for Generative Retrieval",
author = "Anandakumar, Dakshitha B and
Mukkara, Anurag and
Hu, Wenxiang and
Mohankumar, Akash Kumar and
Chen, Jiusheng and
Lou, Qiang and
Jiao, Jian and
Ye, Ting",
editor = "Atanasova, Pepa and
Haffari, Gholamreza and
Wang, Minghan",
booktitle = "Proceedings of the 2026 Conference on Empirical Methods in Natural Language Processing: Industry Track",
month = oct,
year = "2026",
address = "Budapest, Hungary",
publisher = "Association for Computational Linguistics",
url = "https://aclanthology.org/2026.emnlp-industry.157/",
pages = "2662--2683",
ISBN = "979-8-89176-460-6",
abstract = "Constrained decoding is essential in generative retrieval, where document identifiers generated directly from a query must exactly match a predefined library of valid IDs. At scale, decoding is often constrained using a trie with beam search but most implementations run on CPU. Limited parallelism then makes trie traversal and candidate validation a serving bottleneck as beam width grows.\par We present FlashTrie, which addresses this limitation by optimizing constrained beam search on GPUs. It introduces an integer-aware succinct trie layout that uses bit compression to reduce memory footprint while keeping the full index in GPU high-bandwidth memory reducing memory stalls, and a cooperative CUDA kernel that performs beam expansion, validation, and pruning entirely on-device without per-step host orchestration. GPU-native parallel primitives further replace CPU-style irregular lookup and heap maintenance, improving warp utilization and reducing divergence.\par Together, these designs significantly reduce decoding latency and increase throughput while preserving retrieval quality. On a library of 800M keywords with beam widths up to 1000, FlashTrie reduces trie-search latency to under 2 ms mean latency, achieving up to $24\times$ speedup over a highly optimized multi-threaded CPU baseline. These improvements enable FlashTrie to scale beam sizes by up to $5\times$ in latency-critical applications such as sponsored search. In a large-scale online A/B experiment on a commercial search engine, it delivers a statistically significant $+0.71\%$ revenue lift, enabling real-time constrained decoding at a scale previously impractical within our production serving budget"
}<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="anandakumar-etal-2026-flashtrie">
<titleInfo>
<title>FlashTrie: A GPU-Accelerated Constrained Beam Search for Generative Retrieval</title>
</titleInfo>
<name type="personal">
<namePart type="given">Dakshitha</namePart>
<namePart type="given">B</namePart>
<namePart type="family">Anandakumar</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Anurag</namePart>
<namePart type="family">Mukkara</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Wenxiang</namePart>
<namePart type="family">Hu</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Akash</namePart>
<namePart type="given">Kumar</namePart>
<namePart type="family">Mohankumar</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Jiusheng</namePart>
<namePart type="family">Chen</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Qiang</namePart>
<namePart type="family">Lou</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Jian</namePart>
<namePart type="family">Jiao</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Ting</namePart>
<namePart type="family">Ye</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<originInfo>
<dateIssued>2026-10</dateIssued>
</originInfo>
<typeOfResource>text</typeOfResource>
<relatedItem type="host">
<titleInfo>
<title>Proceedings of the 2026 Conference on Empirical Methods in Natural Language Processing: Industry Track</title>
</titleInfo>
<name type="personal">
<namePart type="given">Pepa</namePart>
<namePart type="family">Atanasova</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Gholamreza</namePart>
<namePart type="family">Haffari</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Minghan</namePart>
<namePart type="family">Wang</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<originInfo>
<publisher>Association for Computational Linguistics</publisher>
<place>
<placeTerm type="text">Budapest, Hungary</placeTerm>
</place>
</originInfo>
<genre authority="marcgt">conference publication</genre>
<identifier type="isbn">979-8-89176-460-6</identifier>
</relatedItem>
<abstract>Constrained decoding is essential in generative retrieval, where document identifiers generated directly from a query must exactly match a predefined library of valid IDs. At scale, decoding is often constrained using a trie with beam search but most implementations run on CPU. Limited parallelism then makes trie traversal and candidate validation a serving bottleneck as beam width grows.\par We present FlashTrie, which addresses this limitation by optimizing constrained beam search on GPUs. It introduces an integer-aware succinct trie layout that uses bit compression to reduce memory footprint while keeping the full index in GPU high-bandwidth memory reducing memory stalls, and a cooperative CUDA kernel that performs beam expansion, validation, and pruning entirely on-device without per-step host orchestration. GPU-native parallel primitives further replace CPU-style irregular lookup and heap maintenance, improving warp utilization and reducing divergence.\par Together, these designs significantly reduce decoding latency and increase throughput while preserving retrieval quality. On a library of 800M keywords with beam widths up to 1000, FlashTrie reduces trie-search latency to under 2 ms mean latency, achieving up to 24\times speedup over a highly optimized multi-threaded CPU baseline. These improvements enable FlashTrie to scale beam sizes by up to 5\times in latency-critical applications such as sponsored search. In a large-scale online A/B experiment on a commercial search engine, it delivers a statistically significant +0.71% revenue lift, enabling real-time constrained decoding at a scale previously impractical within our production serving budget</abstract>
<identifier type="citekey">anandakumar-etal-2026-flashtrie</identifier>
<location>
<url>https://aclanthology.org/2026.emnlp-industry.157/</url>
</location>
<part>
<date>2026-10</date>
<extent unit="page">
<start>2662</start>
<end>2683</end>
</extent>
</part>
</mods>
</modsCollection>
%0 Conference Proceedings
%T FlashTrie: A GPU-Accelerated Constrained Beam Search for Generative Retrieval
%A Anandakumar, Dakshitha B.
%A Mukkara, Anurag
%A Hu, Wenxiang
%A Mohankumar, Akash Kumar
%A Chen, Jiusheng
%A Lou, Qiang
%A Jiao, Jian
%A Ye, Ting
%Y Atanasova, Pepa
%Y Haffari, Gholamreza
%Y Wang, Minghan
%S Proceedings of the 2026 Conference on Empirical Methods in Natural Language Processing: Industry Track
%D 2026
%8 October
%I Association for Computational Linguistics
%C Budapest, Hungary
%@ 979-8-89176-460-6
%F anandakumar-etal-2026-flashtrie
%X Constrained decoding is essential in generative retrieval, where document identifiers generated directly from a query must exactly match a predefined library of valid IDs. At scale, decoding is often constrained using a trie with beam search but most implementations run on CPU. Limited parallelism then makes trie traversal and candidate validation a serving bottleneck as beam width grows.\par We present FlashTrie, which addresses this limitation by optimizing constrained beam search on GPUs. It introduces an integer-aware succinct trie layout that uses bit compression to reduce memory footprint while keeping the full index in GPU high-bandwidth memory reducing memory stalls, and a cooperative CUDA kernel that performs beam expansion, validation, and pruning entirely on-device without per-step host orchestration. GPU-native parallel primitives further replace CPU-style irregular lookup and heap maintenance, improving warp utilization and reducing divergence.\par Together, these designs significantly reduce decoding latency and increase throughput while preserving retrieval quality. On a library of 800M keywords with beam widths up to 1000, FlashTrie reduces trie-search latency to under 2 ms mean latency, achieving up to 24\times speedup over a highly optimized multi-threaded CPU baseline. These improvements enable FlashTrie to scale beam sizes by up to 5\times in latency-critical applications such as sponsored search. In a large-scale online A/B experiment on a commercial search engine, it delivers a statistically significant +0.71% revenue lift, enabling real-time constrained decoding at a scale previously impractical within our production serving budget
%U https://aclanthology.org/2026.emnlp-industry.157/
%P 2662-2683
Markdown (Informal)
[FlashTrie: A GPU-Accelerated Constrained Beam Search for Generative Retrieval](https://aclanthology.org/2026.emnlp-industry.157/) (Anandakumar et al., EMNLP 2026)
ACL
- Dakshitha B Anandakumar, Anurag Mukkara, Wenxiang Hu, Akash Kumar Mohankumar, Jiusheng Chen, Qiang Lou, Jian Jiao, and Ting Ye. 2026. FlashTrie: A GPU-Accelerated Constrained Beam Search for Generative Retrieval. In Proceedings of the 2026 Conference on Empirical Methods in Natural Language Processing: Industry Track, pages 2662–2683, Budapest, Hungary. Association for Computational Linguistics.