Tractable Hierarchical Control of Autoregressive Language Models

• URL: http://arxiv.org/abs/2607.20483v1
• Date: Mon, 01 Jun 2026 14:57:46 GMT
• Title: Tractable Hierarchical Control of Autoregressive Language Models
• Abstract summary: Constraining the generation of autoregressive large language models (LLMs) is an important component of integrating language models into formal systems.<n>By distilling the LLM to a tractable probabilistic model, its autoregressive generation can be steered and masked to incorporate the probability of satisfying logical constraints.
• Score: 13.930492173862165
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Constraining the generation of autoregressive large language models (LLMs) is an important component of integrating language models into formal systems. In the generation of code and data for tasks like program synthesis, ensuring that language models produce syntactically valid output is a prerequisite for processing such output. These languages (such as SQL or JSON) are often designed as $LR(k)$ context-free grammars. By distilling the LLM to a tractable probabilistic model, its autoregressive generation can be steered and masked to incorporate the probability of satisfying logical constraints, ensuring high quality output that is guaranteed to be valid. This paper demonstrates that the satisfaction of any $LR(k)$ grammar of finite duration can be calculated in polynomial time, an improvement over the exponential time of applying previous methods to such grammars. This result enables efficient constraint and steering of LLM generation towards output that better satisfies formal syntactic constraints.

Related papers

• Lookahead-then-Verify: Reliable Constrained Decoding for Diffusion LLMs under Context-Free Grammars [17.13122301190815]
  We present LAVE, a constrained decoding approach specifically designed for dLLMs.<n>Our approach leverages a key property of dLLMs, namely their ability to predict token distributions for all positions in parallel during each forward pass.<n>Extensive experiments across four widely used dLLMs and three representative benchmarks demonstrate that LAVE consistently outperforms existing baselines and achieves substantial improvements in syntactic correctness, while incurring negligible runtime overhead.
  arXiv  Detail & Related papers  (2026-01-31T08:58:15Z)
• Constrained Decoding of Diffusion LLMs with Context-Free Grammars [1.0923877073891446]
  Large language models (LLMs) have shown promising performance across diverse domains.<n>This paper presents the first constrained decoding method for diffusion models.<n>We show that our method achieves near-perfect syntactic correctness while consistently preserving or improving functional correctness.
  arXiv  Detail & Related papers  (2025-08-13T18:09:09Z)
• Large Language Model Meets Constraint Propagation [42.54350568915404]
  GenCP combines predictions with Constraint Programming (CP) reasoning to generate fluent text.<n>We improve GenCP by integrating Masked Language Models (MLMs) for domain generation, which allows constraint propagation.<n>Our evaluation on COLLIE benchmarks demonstrates that incorporating domain preview via bidirectional calls significantly improves GenCP's performance.
  arXiv  Detail & Related papers  (2025-05-29T21:18:12Z)
• Syntactic and Semantic Control of Large Language Models via Sequential Monte Carlo [90.78001821963008]
  A wide range of LM applications require generating text that conforms to syntactic or semantic constraints.<n>We develop an architecture for controlled LM generation based on sequential Monte Carlo (SMC)<n>Our system builds on the framework of Lew et al. (2023) and integrates with its language model probabilistic programming language.
  arXiv  Detail & Related papers  (2025-04-17T17:49:40Z)
• Type-Constrained Code Generation with Language Models [51.03439021895432]
  We introduce a type-constrained decoding approach that leverages type systems to guide code generation.<n>For this purpose, we develop novel prefix automata and a search over inhabitable types, forming a sound approach to enforce well-typedness on LLM-generated code.<n>Our approach reduces compilation errors by more than half and significantly increases functional correctness in code synthesis, translation, and repair tasks.
  arXiv  Detail & Related papers  (2025-04-12T15:03:00Z)
• Boosting the Capabilities of Compact Models in Low-Data Contexts with Large Language Models and Retrieval-Augmented Generation [2.9921619703037274]
  We propose a retrieval augmented generation (RAG) framework backed by a large language model (LLM) to correct the output of a smaller model for the linguistic task of morphological glossing. We leverage linguistic information to make up for the lack of data and trainable parameters, while allowing for inputs from written descriptive grammars interpreted and distilled through an LLM. We show that a compact, RAG-supported model is highly effective in data-scarce settings, achieving a new state-of-the-art for this task and our target languages.
  arXiv  Detail & Related papers  (2024-10-01T04:20:14Z)
• Using Grammar Masking to Ensure Syntactic Validity in LLM-based Modeling Tasks [0.996023506058745]
  Grammar masking is used to guide large language models toward producing syntactically correct models for a given context-free grammar. We show that grammar masking can dramatically improve the modeling capabilities of several language models.
  arXiv  Detail & Related papers  (2024-07-08T17:19:59Z)
• Which Syntactic Capabilities Are Statistically Learned by Masked Language Models for Code? [51.29970742152668]
  We highlight relying on accuracy-based measurements may lead to an overestimation of models' capabilities. To address these issues, we introduce a technique called SyntaxEval in Syntactic Capabilities.
  arXiv  Detail & Related papers  (2024-01-03T02:44:02Z)
• FiLM: Fill-in Language Models for Any-Order Generation [71.42044325886194]
  Fill-in Language Model (FiLM) is a new language modeling approach that allows for flexible generation at any position without adhering to a specific generation order. During inference, FiLM can seamlessly insert missing phrases, sentences, or paragraphs. FiLM outperforms existing infilling methods that rely on left-to-right language models trained on rearranged text segments.
  arXiv  Detail & Related papers  (2023-10-15T19:37:39Z)
• Large Language Models as General Pattern Machines [64.75501424160748]
  We show that pre-trained large language models (LLMs) are capable of autoregressively completing complex token sequences. Surprisingly, pattern completion proficiency can be partially retained even when the sequences are expressed using tokens randomly sampled from the vocabulary. In this work, we investigate how these zero-shot capabilities may be applied to problems in robotics.
  arXiv  Detail & Related papers  (2023-07-10T17:32:13Z)
• Tractable Control for Autoregressive Language Generation [82.79160918147852]
  We propose to use tractable probabilistic models (TPMs) to impose lexical constraints in autoregressive text generation models. We show that GeLaTo achieves state-of-the-art performance on challenging benchmarks for constrained text generation. Our work opens up new avenues for controlling large language models and also motivates the development of more expressive TPMs.
  arXiv  Detail & Related papers  (2023-04-15T00:19:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.