Grammar-Aligned Decoding

The document discusses a new constrained decoding algorithm called ASAp, which addresses biases in large language models when meeting specific grammar constraints, and provides comprehensive experimental results, theoretical proofs, and limitations, while also ensuring compliance with ethical guidelines and proper documentation of assets and resources.

Abstract

Large Language Models (LLMs) struggle with reliably generating highly structured outputs, such as program code, mathematical formulas, or well-formed markup. Constrained decoding approaches mitigate this problem by greedily restricting what tokens an LLM can output at each step to guarantee that the output matches a given constraint. Specifically, in grammar-constrained decoding (GCD), the LLM's output must follow a given grammar. In this paper we demonstrate that GCD techniques (and in general constrained decoding techniques) can distort the LLM's distribution, leading to outputs that are grammatical but appear with likelihoods that are not proportional to the ones given by the LLM, and so ultimately are low-quality. We call the problem of aligning sampling with a grammar constraint, grammar-aligned decoding (GAD), and propose adaptive sampling with approximate expected futures (ASAp), a decoding algorithm that guarantees the output to be grammatical while provably producing outputs that match the conditional probability of the LLM's distribution conditioned on the given grammar constraint. Our algorithm uses prior sample outputs to soundly overapproximate the future grammaticality of different output prefixes. Our evaluation on code generation and structured NLP tasks shows how ASAp often produces outputs with higher likelihood (according to the LLM's distribution) than existing GCD techniques, while still enforcing the desired grammatical constraints.

Method

The paper introduces a new algorithm called Adaptive Sampling with Approximate Expected Futures (ASAp) to address biases in large language models when enforcing grammar constraints. This algorithm converges to the desired probability distribution by sampling outputs from the language model conditioned on the outputs being accepted by the grammar, thus improving the likelihood of generated outputs over time while still enforcing the constraints. The method is evaluated on formal program synthesis and constituency parsing tasks, demonstrating improved convergence to the target constrained language model and better respect for the language model while enforcing constraints.

Main Finding

The main finding of the paper is the introduction and formalization of grammar-aligned decoding (GAD), which addresses the issue of structured decoding distorting the language distribution of Large Language Models (LLMs). The paper proposes a new algorithm, ASAp, to iteratively build better approximations to the critical re-weighting term required for GAD, demonstrating its effectiveness in relation to existing grammar-constrained decoding techniques on benchmark code generation tasks. The paper also highlights the limitations of existing constrained decoding approaches and proposes the first converging algorithm to address this problem, providing a significant contribution to the field of language model decoding.

Conclusion

The conclusion of the paper is that the authors have introduced a new analysis of the ideal target for constrained sampling from a Large Language Model (LLM) using a grammar, which they call grammar-aligned decoding (GAD). They proposed a new algorithm for GAD called ASAp, which iteratively builds better approximations to the critical re-weighting term required for GAD: the expected future grammaticality. The authors analyzed the convergence of their proposed algorithm and demonstrated its effectiveness in relation to existing grammar-constrained decoding techniques on a set of benchmark code generation tasks. They also analyzed and evaluated their approach using constraints enforced by a context-free grammar; however, they suggest that extensions of their approach might be applied to more general classes of constraints for LLM decoding.

Keywords

Grammar-Aligned Decoding, Large Language Models, Constrained Decoding, Context-Free Grammar, Language Model Decoding, Neural Information Processing Systems, Code Generation, Constituency Parsing, Hyperparameters, Experimental Details, Open Access, Experimental Reproducibility, NeurIPS Code of Ethics, Broader Impacts, Computational Linguistics, Knowledge Representation, Neural Text Generation, Constrained Beam Search, Model Checkpoints, Experimental Compute Resources, Institutional Review Board, Crowdsourcing, Research Ethics, Data Safeguards, Asset Documentation, Error Bars, Theoretical Proofs, Data and Code Release, Ethical Guidelines, Code Licensing, New Assets Documentation, Knowledge Representation, Lexically Constrained Decoding, Transformer Models, Language Model Bias, Sampling Algorithms, KL Divergence, Expectations, Research Limitations, Research Ethics, Data and Code Release, Asset Documentation, Computational Linguistics, Neural Information Processing Systems, Constituency Parsing, Penn TreeBank Annotation.