GrammarRL: Effective Grammar-Constrained Decoding via Reinforcement Learning

Gabriele Tuccio; Antonino Furnari; Aldo Gangemi; Misael Mongiovì

cs.AISep 30, 2026

GrammarRL: Effective Grammar-Constrained Decoding via Reinforcement Learning

Authors: Gabriele Tuccio, Antonino Furnari, Aldo Gangemi, Misael Mongiovì

Organizations: University of Catania · ISTC - National Research Council, Italy · University of Bologna

Abstract

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.

Figures & tables

Figure 1: Illustration of grammar-constrained decoding pitfalls and the GrammarRL solution. Top: The base model assigns most of its probability mass to invalid tokens (e.g., “great”, “huge”). Constrained to a low-probability region where differences are narrowed, a greedy step chooses “real”, leading to the valid but incorrect sequence “real disaster”. Bottom: Unsupervised RL fine-tuning with GrammarRL reshapes the distribution on unlabeled task inputs. The model directly assigns high probability to valid and correct continuations (“major success”), bypassing the need for complex inference-time search.

Panel of Figure 2 — Figure 2: Overview of GrammarRL framework. For each input $x$ , the policy $\pi_{\theta}^{G}$ (LoRA adapters on the frozen model, decoding with the grammar mask) generates $N$ sampled candidates and the top-1 beam-search candidate. The frozen reference model $\pi_{\mathrm{ref}}$ scores every candidate without the grammar mask in two directions: the direct reward measures how probable the candidate is given the input, and the reverse reward measures how well the input can be reconstructed from the candidate. The combined reward defines a leave-one-out advantage that updates the LoRA adapters, with KL regularization toward $\pi_{\mathrm{ref}}$ . At test time, GrammarRL uses only greedy grammar-constrained decoding.

Model	Config	Gloss (BLEU)	WoS (Hier. F1)	CoNLL (F1-micro)
1B	baseline (greedy)	0.342 $\pm$ 0.005	0.384 $\pm$ 0.006	0.435 $\pm$ 0.009
	baseline (beam)	0.390 $\pm$ 0.018	0.385 $\pm$ 0.007	0.590 $\pm$ 0.006
	GrammarRL (reverse only)	0.554 $\pm$ 0.009	0.309 $\pm$ 0.006	0.548 $\pm$ 0.005
	GrammarRL (direct only)	0.456 $\pm$ 0.005	0.288 $\pm$ 0.007	0.597 $\pm$ 0.010
	GrammarRL	0.570 $\pm$ 0.014	0.394 $\pm$ 0.008	0.578 $\pm$ 0.006
	GrammarRL (beam)	0.541 $\pm$ 0.013	0.391 $\pm$ 0.008	0.598 $\pm$ 0.006

Table 1: Results for Llama-3.2-1B-Instruct (1B), Llama-3.2-3B-Instruct (3B), and Llama-3.1-8B-Instruct (8B), with

N{=}3

and

B{=}3

. Baseline denotes the frozen pretrained model under the same grammar constraints, while GrammarRL denotes the model trained with our approach. Reverse-only and direct-only use only the corresponding reward, while GrammarRL combines both with

\lambda{=}0.5

. Rows marked beam use beam search at inference time. Values are mean

\pm

standard deviation over 10 test sets, each generated by randomly sampling the dataset with a different random seed.

Method	Cost	Gloss (BLEU)	WoS (Hier. F1)	CoNLL (F1-micro)
Constrained greedy	$1\times$	0.339 $\pm$ 0.002	0.388 $\pm$ 0.000	0.434 $\pm$ 0.006
Constrained beam ( $B{=}3$ )	${\approx}3\times$	0.380 $\pm$ 0.022	0.386 $\pm$ 0.002	0.586 $\pm$ 0.009
Sample-Rerank ( $\Phi_{\mathrm{exp}}^{\mathrm{rev}}$ )	${\approx}10\times$	0.346 $\pm$ 0.000	0.430 $\pm$ 0.009	0.488 $\pm$ 0.007
Full IS ( $\Phi_{\mathrm{exp}}^{\mathrm{rev}}$ )	${\approx}10\times$	0.302 $\pm$ 0.002	0.442 $\pm$ 0.002	0.511 $\pm$ 0.010
Full SMC ( $\Phi_{\mathrm{exp}}^{\mathrm{task}}$ )	${\approx}10\times$	0.236 $\pm$ 0.004	n/a	0.578 $\pm$ 0.009
GrammarRL ( $\lambda{=}0.5$ )	$1\times$ (+ training)	0.554 $\pm$ 0.008	0.400 $\pm$ 0.010	0.577 $\pm$ 0.009

Table 2: Inference-time methods vs. GrammarRL (1B). Cost: generation relative to one greedy pass. Sampling methods use

N{=}10

particles and return the posterior mode. GrammarRL is reported with the default

\lambda{=}0.5

and with the best

\lambda

per task in Table 3 (

0.25

for CoNLL and WoS,

0.75

for Gloss); the latter is selected on the same test seeds and is thus slightly optimistic. Mean

\pm

std over 2 test sets of 2,000 examples; best value per column in bold.

Lambda value	Gloss (BLEU)	WoS (Hier. F1)	CoNLL (F1-micro)
0 (direct only)	0.456 $\pm$ 0.005	0.288 $\pm$ 0.007	0.597 $\pm$ 0.010
0.25	0.541 $\pm$ 0.004	0.407 $\pm$ 0.009	0.625 $\pm$ 0.008
0.5	0.570 $\pm$ 0.014	0.394 $\pm$ 0.008	0.578 $\pm$ 0.006
0.75	0.576 $\pm$ 0.013	0.367 $\pm$ 0.009	0.572 $\pm$ 0.005
1 (reverse only)	0.554 $\pm$ 0.009	0.309 $\pm$ 0.006	0.548 $\pm$ 0.006

Table 3: Ablation on the reward mixing coefficient

\lambda

, with

N{=}3

and

B{=}3

fixed. Experiments use Llama-3.2-1B-Instruct and greedy decoding. Values are mean

\pm

std over 10 sampled test sets.

\lambda{=}0

corresponds to direct-only training and

\lambda{=}1

to reverse-only training. Intermediate mixtures improve over the single-direction objectives, although the best value depends on the task.

Appendix figures & tables11 assets

Supplementary material from the paper’s appendix.

Appendix

		1B		3B		8B
Task	$(N,B)$	$\sigma_{\mathrm{direct}}$	$\sigma_{\mathrm{reverse}}$	$\sigma_{\mathrm{direct}}$	$\sigma_{\mathrm{reverse}}$	$\sigma_{\mathrm{direct}}$	$\sigma_{\mathrm{reverse}}$
Gloss	$(3,3)$	1.1378	0.9731	0.6354	0.5493	0.4564	0.4442
	$(6,3)$	1.0693	1.0001	–	–	–	–
	$(9,3)$	1.1245	1.0229	–	–	–	–
	$(3,5)$	1.1147	0.9125	–	–	–	–
	$(3,10)$	1.1454	0.9453	–	–	–	–

Appendix

Table 4: Reward scaling constants

\sigma_{\mathrm{direct}}

and

\sigma_{\mathrm{reverse}}

per task, rollout composition

(N,B)

(

N

sampled sequences, beam width

B

), and model size, measured on 100 held-out development examples. Rows are grouped by the varied quantity:

N

with

B{=}3

, then

B

with

N{=}3

. Shaded rows correspond to the default composition

(3,3)

used in Table 1 . “–” denotes a combination not used for that model size.

Data
	Gloss	WoS	CoNLL
Training examples	2k	4k	4k
Test sets	$10\times 2000$	$10\times 2000$	$10\times 2000$
Few-shot pairs / hints	20 / 50	1 / —	10 / 80
Optimization
Prompts per step (batch)	4	8	8

Appendix

Table 5: Default training configuration. Learning rate, gradient clipping threshold, and batch size do not depend on the backbone. Values spanning all three columns are shared across tasks. Reward scaling constants are reported in Table 4 .

Task	Few-shot pairs	Dynamic hints per query	Static system content
Gloss	20	50 gloss terms	—
WoS	1	—	label hierarchy (7 parents, 134 children)
CoNLL	10	$4\times 20=80$ entity spans	—

Appendix

Table 6: Composition of the forward prompts. Few-shot demonstrations are selected once, deterministically, without using text from the test sets, and are then reused for every query. Gloss and CoNLL additionally use query-specific hints. The reverse prompt uses the same demonstrations with input and output swapped and contains no retrieved hints.

Task	Instruction	Context	Output format
Forward system prompt
Gloss	Simplify the sentence into basic components. Separate components with a single space; preserve the meaning and structure of the original.	$\langle$ 50 similar gloss terms $\rangle$ (retrieved)	TERM TERM TERM … upper-case content words, space-separated
WoS	Classify the abstract into one parent–child path of the hierarchy. Use labels from the hierarchy only.	$\langle$ label hierarchy $\rangle$ (7 parents, 134 children; static)	{"parent": ..., "child": ...}
CoNLL	Extract named entities from the sentence. Copy the first span of each type verbatim; empty string if absent; emit the JSON object only.	$\langle$ 4 $\times$ 20 similar entity spans $\rangle$ (one line per type, retrieved)	{"person": ..., "organization": ..., "location": ..., "misc": ...}
Reverse system prompt (replaces the forward instruction; no context block)
Gloss	Given the glossed form, reconstruct the original English sentence as it was actually written. Output only that sentence.

Appendix

Table 7: Forward and reverse system instructions (abbreviated). Each forward instruction is composed of a fixed task instruction , a context block (retrieved per query for Gloss and CoNLL, static for WoS), and a required output format . Angle brackets mark slots whose content changes from one query to another. In the reverse prompt, the forward system instruction and its context block are replaced by the inverse instruction shown in the bottom half; the demonstrations are kept, with input and output swapped.

Figure 3: Training and test performance throughout training for Llama-3.2-1B-Instruct with

N{=}3

and

B{=}3

, comparing the GrammarRL direct-only (

\lambda{=}0

), GrammarRL (

\lambda{=}0.5

), and GrammarRL reverse-only (

\lambda{=}1

) objectives. Solid and dashed lines denote test and training performance, respectively. The relatively small train–test gaps throughout training indicate limited overfitting and suggest that the learned reward-driven behavior generalizes beyond the training examples.

Sampled sequences $N$ ( $B{=}3$ )
	Gloss (BLEU)	WoS (Hier. F1)	CoNLL (F1-micro)
3	0.570 $\pm$ 0.014	0.394 $\pm$ 0.008	0.578 $\pm$ 0.006
6	0.584 $\pm$ 0.017	0.403 $\pm$ 0.008	0.577 $\pm$ 0.007
9	0.589 $\pm$ 0.010	0.402 $\pm$ 0.009	0.572 $\pm$ 0.007
Beam width $B$ ( $N{=}3$ )
3	0.570 $\pm$ 0.014	0.394 $\pm$ 0.008	0.578 $\pm$ 0.006

Appendix

Table 8: Ablation on the rollout composition, with

\lambda{=}0.5

fixed (Llama-3.2-1B-Instruct, greedy evaluation). Top: number of sampled sequences

N

with

B{=}3

. Bottom: training-time beam width

B

with

N{=}3

. The shaded row is the default configuration

(N,B){=}(3,3)

, repeated in both blocks. Values are mean

\pm

std over 10 sampled test sets of 2,000 examples. Bold marks the best value in each block.

$\lambda$	THEREFORE-DESC	OFTEN-DESC	THERE-DESC	bare X
0 (direct only)	7	0	33	115
0.25	13	0	46	84
0.5	18	1	67	79
0.75	24	1	90	54
1 (reverse only)	36	1	140	51

Appendix

Table 9: Trap tokens in Gloss predictions as a function of the mixing coefficient

\lambda

(Llama-3.2-1B-Instruct,

N{=}3

B{=}3

). Each entry is the mean number of occurrences over 10 sampled test sets of 2,000 examples. As

\lambda

goes from 0 to 1, THEREFORE-DESC rises monotonically from 7 to 36 and THERE-DESC from 33 to 140, whereas bare X falls monotonically from 115 to 51. OFTEN-DESC is rare for every

\lambda

(at most one occurrence). Bold marks the lowest value in each column.

Figure 4: Sequence likelihood versus correctness on one Gloss test example, chosen for readability (outputs decoded deterministically). Each panel shows one output; panels marked base decode with the frozen model, and beam3 denotes beam search with

B{=}3

. Bars give the probability of each gloss term under the frozen model before the grammar mask, computed as the product of its token probabilities. The header reports the direct and reverse reward terms under the frozen model,

\mathcal{R}_{\mathrm{direct}}

and

\mathcal{R}_{\mathrm{reverse}}

(Section 3.2 ), and sentence-level BLEU;

\star

marks the best value of each quantity.

Figure 5: Empty-field errors and micro-F1 on CoNLL as a function of the mixing coefficient

\lambda

(Llama-3.2-1B-Instruct,

N{=}3

B{=}3

), averaged over 10 sampled test sets of 2,000 examples. (a) Percentage of fields that are non-empty in the gold annotation but left empty in the prediction. (b) Micro-F1. Horizontal lines mark the frozen model with greedy and beam-search decoding. Empty-field errors decrease overall from 23.71% at

\lambda{=}0

to 2.12% at

\lambda{=}1

, whereas micro-F1 peaks at

\lambda{=}0.25

(62.50).

Task	Rule	Violation	Penalty	Check on training gold (500 rows)
CoNLL	Grounding	An entity string is not a verbatim substring of the sentence.	$-3.0$ each	fires on 0
CoNLL	Word boundary	The string occurs in the sentence but only inside longer words.	$-1.5$ each	fires on 0
CoNLL	Duplicate	The same non-empty string is emitted in two different fields.	$-1.0$ per extra field	fires on 0
Gloss	Precision	A completed gloss term is not grounded: after removing the -DESC / -X marker, its lemma matches no source word (suffix stripping and a dictionary lemmatizer) and it is not a closed-class function term (e.g. be, have, not, the ).	$-0.5$ each, at most 5	fires on 14.6% of rows
Gloss	Coverage	A source content word (alphabetic, at least three letters, not a stop word) is not matched by any gloss term. Judged on the complete output only.	$-0.5$ each, at most 5	gold covers $97.3\%$ of content words (shuffled control: $0.9\%$ )
Gloss	Degenerate run	A maximal run of at least three identical adjacent terms (a run of two, as in the gold BE BE , is legitimate).	$-1.0$ per run	fires on 0

Appendix

Table 10: Task-specific potentials.

\log\Phi_{\mathrm{exp}}^{\mathrm{task}}

is the sum of the penalties incurred; all penalties are soft, so a violation lowers a particle’s weight without ever removing it. On training gold, the CoNLL rules fire on none of the 500 rows; for Gloss,

80.2\%

of gold rows incur no penalty, and the mean gold penalty is

-0.17

against

-4.6

for a shuffled control (source of row

i{+}1

paired with the gloss of row

i

), about

27\times

larger, so the potential discriminates without being strict. WoS has no task-specific potential.

Method	What it does	Search at inference	Efficient potential $\Phi_{\mathrm{eff}}$	Expensive potential $\Phi_{\mathrm{exp}}$	Output selection	Cost
Constrained greedy	Mode of the locally renormalized masked policy $\pi^{G}$ equation 1 : one valid token at a time; no look-ahead.	None (single pass).	Grammar as a token mask (Grammar-LLM).	None.	Arg-max token at each step.	$1\times$
Constrained beam ( $B{=}3$ )	Searches for a higher-probability sequence under $\pi^{G}$ ; a mode-seeking approximation of $p_{\theta}(y\mid x,G)$ .	Beam search, 3 hypotheses.	Same mask (Grammar-LLM).	None.	Top-scoring finished beam.	$\approx 3\times$
GrammarRL (ours)	Amortizes sequence-level preferences into the model: LoRA policy trained with RLOO on the label-free bidirectional reward, then decoded greedily.	None at test time (greedy).	Same mask, active in training and testing.	Used only in training: direct $+$ reverse reward from the frozen model equation 6 .	Arg-max token at each step.	$1\times$ (+ one-off training)
Sample-Rerank ( $\Phi_{\mathrm{exp}}^{\mathrm{rev}}$ )	Best-of- $N$ under an external score: $N$ i.i.d. grammar-constrained samples, keep the one with the highest reverse likelihood of the input. No weight correction, no resampling.	$N{=}10$ independent samples.	Grammar mask (proposal).	$\Phi_{\mathrm{exp}}^{\mathrm{rev}}$ (noisy-channel), at completion.	$\arg\max$ of the reverse score among complete samples.	$\approx N\times$ generation $+\,N$ scoring passes
Full IS ( $\Phi_{\mathrm{exp}}^{\mathrm{rev}}$ )	Importance sampling from the grammar-constrained LM towards $p_{\theta}(y\mid x,G)\,\Phi_{\mathrm{exp}}^{\mathrm{rev}}(y)$ ; weights correct the myopia of local masking; no resampling.	$N{=}10$ independent weighted samples.	Grammar mask inside AWRS, with importance weight.	$\Phi_{\mathrm{exp}}^{\mathrm{rev}}$ (noisy-channel), applied once at completion.	Posterior mode: text with the largest total normalized weight.	Same as Sample-Rerank
Full SMC ( $\Phi_{\mathrm{exp}}^{\mathrm{task}}$ )	Sequential Monte Carlo ( Loula et al., 2025 ) : $N$ particles extended in parallel, resampled when the effective sample size drops, steered at every step by a task-specific expensive potential.	$N{=}10$ particles, resampling if $\mathrm{ESS}<N/3$ .	Grammar mask inside AWRS, with importance weight.	$\Phi_{\mathrm{exp}}^{\mathrm{task}}$ (CoNLL, Gloss): grounding, coverage, boundary, repetition; on prefixes and at completion.	Posterior mode over particles.	$\approx N\times$ generation; potential evaluated on CPU

Appendix

Table 11: Methods compared with GrammarRL in Table 2 . All use Llama-3.2-1B-Instruct and the same prompts. Efficient potentials

\Phi_{\mathrm{eff}}

are cheap enough to be evaluated on every candidate next token and are folded into the proposal; expensive potentials

\Phi_{\mathrm{exp}}

are evaluated only on the sampled particles and enter through the importance weights.

\Phi_{\mathrm{exp}}^{\mathrm{rev}}(y)=\pi_{\mathrm{ref}}(x\mid\tau(y))

is the reverse likelihood of the input given the candidate (Appendix G.7 ); the task-specific potentials

\Phi_{\mathrm{exp}}^{\mathrm{task}}

are defined in Appendix G.8 . Costs are relative to one greedy pass and refer to generation; reverse scoring adds one forward pass of the frozen model per complete sample. GrammarRL uses the

N{=}3

B{=}3

adapters, with the default

\lambda{=}0.5

and with the best

\lambda

per task (Table 3 ).

Explore similar work

May 31, 2024cs.AI

Grammar-Aligned Decoding

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.

Kanghee Park, Jiayu Wang, Taylor Berg-Kirkpatrick +2

University of Wisconsin-Madison · University of California San Diego

Constrained Decoding Large Language Model Generation Context-Free Grammars Code Generation Grammaticality

Ask PDF

Aug 10, 2026cs.CL

The Parser Already Knows: Lightweight Bias Correction in Constrained Decoding

Grammar Constrained Decoding (GCD) forces Language Models (LMs) to produce syntactically valid outputs by masking out non-conforming tokens at each step. However, rigid masking distorts the model's underlying probability distribution, often biasing generation toward valid but suboptimal outputs. While online sampling restores this distribution, it requires computationally expensive iterative resampling. As a result, existing methods force a compromise between output quality and inference latency. Our key insight is that the internal parser and lexer states inherently maintained during incremental parsing already encode future grammatical validity -- exactly the information required to restore the LM's true distribution. We propose a lightweight, offline-trained logit correction conditioned on this syntactic and lexical state together with candidate next tokens. Because these states are already computed as a necessary part of incremental parsing for masking, extracting them adds negligible overhead while leaving the base LM's weights completely untouched. Across several grammars, this correction substantially closes the gap between the masked distribution and the LM's true distribution, consistently outperforming both masking and online sampling. Even its lightest variant, which relies on the candidate next token alone, still matches or exceeds both baselines: the next token itself carries an implicit lookahead, much like how parsers commonly use a lookahead token to resolve ambiguous decisions. By restoring the probability mass that masking removes, it reconciles the LM's probabilistic integrity with grammar conformance.

Işıl Özgü, Yaoxuan Wu, Guy Van den Broeck +1

University of California, Los Angeles

Constrained Decoding Correction Logit Lens Inference Latency Lightweight

Ask PDF

Aug 6, 2026cs.PL

Learning Context-Free Grammars for Grammar-Constrained Decoding via Declarative Agentic Programming with Guarantees

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.

Kevin Cheang, Geoff Hulette, Rahul Kumar +5

Amazon Web Services · Purdue University

Context-Free Grammars Domain-Specific Language Decoding

Ask PDF