Search papers, labs, and topics across Lattice.
This paper introduces PSC, a novel grammar-constrained decoding method that significantly reduces the computational overhead associated with ensuring syntactic validity in outputs generated by large language models (LLMs). By utilizing a single classifier to combine acceptance conditions for all vocabulary tokens, PSC achieves a time complexity that is independent of vocabulary size, enabling mask computation up to 700 times faster than existing methods. The results indicate that PSC can enhance LLM throughput to levels comparable to unconstrained decoding, making it a practical solution for generating structured outputs like code and JSON efficiently.
PSC achieves up to 700x faster grammar-constrained decoding, making LLMs as efficient as unconstrained decoding for structured output generation.
LLMs are widely used to generate structured output like source code or JSON. Grammar-constrained decoding (GCD) can guarantee the syntactic validity of the generated output, by masking out tokens that violate rules specified by a context-free grammar. However, the online computational overhead of existing GCD methods, with latency typically scaling linearly with vocabulary size, limits the throughput of LLMs, especially for models with large vocabularies. To address this issue, we propose PSC, a novel grammar-constrained decoding method. By combining acceptance conditions of all vocabulary tokens into a single classifier of the parser stack during preprocessing, PSC can compute the complete vocabulary mask by checking the parser stack exactly once per decoding step, with time complexity independent of the vocabulary size. Experiments show that PSC computes masks up to 700$\times$ faster than baselines on complex programming language grammars, and up to 30$\times$ faster for schema-conformant JSON; end-to-end LLM throughput with PSC approaches that of unconstrained decoding. We analyze the preprocessing overhead for preprocessing providers and decoding users, and provide a break-even point analysis to help users decide whether to do preprocessing by themselves.
