Reproduce “Efficient Grammar-Constrained Decoding via Parser Stack Classification” 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
Yongmin Li, Yihong Dong, Jia Li, Ge Li
Parser Stack Classification (PSC) is presented as a grammar-constrained decoding method that reduces the computational overhead for ensuring syntactic validity in LLM-generated structured outputs. It achieved up to 700x faster mask computation than previous baselines and improved downstream task performance for code and JSON generation.
Key insights
- The set of (lexer state, parser stack) pairs that accept a given vocabulary token forms a regular language, which can be efficiently represented and processed by a Finite-State Automaton.
- By constructing FSTs for epsilon transitions and individual terminal symbols, the parser's stack stabilization and state transitions for any terminal sequence can be accurately and efficiently simulated.
- Precomputing all possible vocabulary masks and associating them with states in a minimized comprehensive FSA allows online mask computation to be reduced to a simple lookup operation, independent of vocabulary size.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.