跳转至

语法对齐解码：保证结构化生成的正确性与概率保真度

文章背景与核心概要

大语言模型（LLM）在生成程序代码、数学公式或结构化标记语言等高结构化输出时，往往难以做到完全可靠。传统的语法约束解码（GCD）虽然能强制输出符合特定语法规则，但它常常会扭曲模型原本的概率分布，导致生成的文本虽然语法正确，但整体质量和可能性较低。

为了解决这一痛点，本文正式引入了“语法对齐解码”（Grammar-Aligned Decoding, GAD）概念，并提出了一种全新的解码算法——ASAp（Adaptive Sampling with Approximate Expected Futures，基于近似期望未来的自适应采样）。ASAp 在严格保证输出语法正确性的同时，能够可证明地匹配在给定语法约束下 LLM 的条件概率分布。在代码生成和结构化 NLP 任务上的实验表明，相比传统 GCD 技术，ASAp 在强制执行语法约束的同时，能够持续产出更高似然度的输出结果。

Grammar-Aligned Decoding

Summary

Large Language Models (LLMs) often struggle to generate highly structured outputs like program code or mathematical formulas reliably. While grammar-constrained decoding (GCD) can guarantee that an LLM's output conforms to a specific grammar, it often distorts the model's native probability distribution. This results in grammatical outputs that have low overall quality and likelihood according to the LLM.

This paper introduces Grammar-Aligned Decoding (GAD) and proposes ASAp (Adaptive Sampling with Approximate Expected Futures), a novel decoding algorithm. ASAp guarantees grammatical correctness while provably matching the conditional probability distribution of the LLM under the given grammar constraint. Evaluation on code generation and structured NLP tasks demonstrates that ASAp consistently produces higher-likelihood outputs than traditional GCD techniques while strictly enforcing grammatical constraints.

Paper Metadata

  • arXiv ID: 2405.21047 [cs.AI]
  • Primary Subject: Artificial Intelligence (cs.AI)
  • Other Subjects: Computation and Language (cs.CL), Machine Learning (cs.LG)
  • Authors: Kanghee Park, Jiayu Wang, Taylor Berg-Kirkpatrick, Nadia Polikarpova, Loris D'Antoni
  • Publication: Accepted to NeurIPS 2024
  • Submitted: 31 May 2024 (v1); Last revised: 2 September 2026 (v4)
  • DOI: 10.48550/arXiv.2405.21047

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.

Access & Resources

External References & Tools