Controlling the output of Large Language Models (LLMs) through context-sensitive constraints has emerged as a promising approach to overcome the limitations of Context-Free Grammars (CFGs) in guaranteeing generation validity. However, such constraints typically require manual specification -- a significant barrier demanding specialized expertise. We introduce a framework that automatically learns context-sensitive constraints from LLM interactions through a two-phase process: syntactic exploration to gather diverse outputs for constraint learning, followed by constraint exploitation to enforce these learned rules during generation. Experiments demonstrate that our method enables even small LLMs (1B parameters) to learn and generate with perfect constraint adherence, outperforming larger counterparts and state-of-the-art reasoning models. This work represents the first integration of context-sensitive grammar learning with LLM generation, eliminating manual specification while maintaining generation validity.
Figures & tables
Figure 1: Two-phase methodology for learning context-sensitive constraints. Phase 1: An LLM pθ samples diverse sequences using generator g from a CFG -masked distribution ( q_{C_{\text{\lx@glossaries@gls@link{acronym}{cfg}{{{}}{\color[rgb]{0,0,0}CFG}} }}} ). Tokens such as bc are CFG -valid but context-sensitively invalid, leading to oracle rejection ( V ) and red masking in \hat{\mathcal{C}}_{\text{\lx@glossaries@gls@link{acronym}{asg}{{{}}{\color[rgb]{0,0,0}ASG}} }} . Valid tokens appear green, invalid tokens red. Labeled examples form dataset E for the ASG learner to construct G^ . Phase 2: The LLM uses the learned ASG -constrained distribution ( qC^GASG ), disallowing tokens that may lead to violations (red), while valid tokens remain accessible (green), ensuring all outputs satisfy the target grammar (✓). The gear in Phase 2 illustrates all constraints have been learned (100%), so nothing new is learned (note: this is for visualization purposes only).
Model
G
Accuracy
anbncn
anbncm
GPT 4.1
-
63.3%
76.7%
o1
-
86.7%
96.7%
o3 mini
-
63.3%
86.7%
o4 mini
-
90.0%
93.3%
DeepSeek-R1
-
80.0%
86.7%
Table 1: Accuracy results for anbncn and anbncm with different LLMs (Model) and grammar constraints ( G ).
Appendix figures & tables3 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 2: The learned ASG for anbncn using our approach. This grammar utilizes ASP constraints (in bold and surrounded by {} ) to enforce the context-sensitive condition that all three symbol sequences maintain equal length.
Model
G
Accuracy
anbncn
anbncm
GPT 4.1
-
63.3%
76.7%
o1
-
86.7%
96.7%
o3 mini
-
63.3%
86.7%
o4 mini
-
90.0%
93.3%
DeepSeek-R1
-
80.0%
86.7%
Appendix
Table 2: Accuracy results for anbncn and anbncm with different LLMs (Model), including Llama 3.2 3B and 3.1 8B, and grammar constraints ( G ).
Figure 3: Prompt template for the a n b n c n language generation task. The system instruction defines the formal language requirements, followed by example interactions demonstrating expected inputs and outputs.
Large language models (LLMs) are powerful tools that have found applications beyond human-machine interfaces and chatbots. Beside free-form generation, there has been an interest in constrained generation, a setting where LLMs are constrained to generate well-formed outputs with respect to the language defined by a formal grammar. Although appealing, this setting may be over restrictive for downstream applications. For example, many LLM tasks require the model to reason freely before generating its final response in a specific format. In this work, we introduce suffix-constrained generation, a constrained generation setting in which only the end of the response is constrained by a grammar, a scenario that is not supported by existing constrained generation methods. We introduce several suffix-constrained generation algorithms that are based on greedy search. We experiment on several datasets, and show that our approach allows to guarantee suffix constraints without having a negative impact on results, and even improving them in many settings.
Language models (LMs) are increasingly used to interact with external services via programs written in domain-specific languages (DSLs). Unfortunately, since DSLs are often low-resource and esoteric, LMs frequently produce syntactically invalid programs in these languages. Grammar-constrained decoding can eliminate such failures, but requires syntactic constraints. These are usually in the form of a context-free grammar for the target language, an artifact that is hard to come by for third-party DSLs. In this work, we define an agent, called Autogrammar, that automatically learns context-free grammars from documentation and execution data. Autogrammar is formalized as a Kripke structure whose nondeterministic choices are resolved by a language model, enabling declarative control of agent behavior via linear temporal logic constraints. We evaluate four versions of Autogrammar on three DSLs (i.e., Amazon CloudWatch Logs Insights, Dynatrace Query Language, and Datadog Search Syntax) and find that it generates grammars that achieve near perfect precision on unseen data; that temporal restrictions reduce execution time by 3.8x without incurring statistically-significant loss in precision; that execution data is crucial while documentation is dispensable; and that grammar-constrained decoding using Autogrammar-generated grammars significantly improves end-to-end LM performance on eight out of ten real tasks, matching or exceeding the performance of a professionally-maintained grammar. In comparison, the context-free grammars generated by existing LM baselines and a state-of-the-art formal technique perform significantly worse over the same evaluation.
Grammar-constrained generation guarantees syntactic validity, but can substantially degrade semantic quality when the model's preferred outputs are poorly aligned with the imposed grammar. This trade-off is particularly severe when the prompt is underspecified or the model has limited instruction-following ability. Beam search can partially mitigate these failures by exploring multiple valid sequences, but its computational cost grows with beam width, while sequence-level probability is only an imperfect proxy for semantic quality. We introduce GrammarRL, a label-free reinforcement learning method that adapts language models to grammar constraints without requiring annotated data. GrammarRL optimizes the model using two complementary self-supervised rewards derived from its own likelihoods: a direct reward, measuring how likely the constrained output is given the input, and a reverse reward, measuring how well the input can be reconstructed from the generated output. We optimize these rewards with a Reinforce Leave-One-Out (RLOO) objective over groups of grammar-constrained rollouts, augmented with the top-1 beam-search hypothesis and regularized towards a frozen base model. We evaluate GrammarRL on sign language gloss translation, hierarchical text classification, and named entity recognition using Llama models ranging from 1B to 8B parameters. GrammarRL consistently outperforms constrained greedy decoding, with an average improvement of 9.8 points and gains of up to 22.8 BLEU. It matches or outperforms beam search on two of the three tasks while preserving greedy-decoding inference cost. Ablations further show that the two rewards are complementary: either reward alone can underperform the untrained baseline, whereas their combination consistently improves upon it.