Reproduce “Flexible and Efficient Grammar-Constrained Decoding” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Kanghee Park, Timothy Zhou, Loris D'Antoni
Researchers at UCSD developed GREATGRAMMA, an algorithm that improves grammar-constrained decoding for LLMs by efficiently bridging subword tokens with formal grammar terminals. This approach achieves a 17.71x average speedup in offline preprocessing and a 550.57x speedup in online per-token overhead compared to leading baselines, ensuring valid structured outputs from LLMs.
Key insights
- Composing a lexer FST with a detokenizing FST provides an efficient and sound way to bridge the gap between LLM subword tokens and formal grammar terminals.
- By categorizing terminal sequences into 'always-accepted' and 'context-dependent' based on PDA analysis, the online masking process can avoid expensive full PDA traversals for common scenarios.
- The maximal munch principle and 1-lookahead lexing ensure a deterministic and efficient lexer state tracking, crucial for mapping LLM tokens to grammar progress.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.