When a neural text generator is forced to satisfy hard rules, such as "the sentence must mention dog, frisbee, catch and throw" or "the recipe must not name ingredients that are not on the list," it often fails. The failure has two possible causes. The decoder may have missed a better sentence that the model itself would have preferred; this is a search error. Or the model may genuinely prefer a bad sentence among all those that obey the rules; this is a model error. Today nobody can tell which is happening, because the standard constrained decoder is a modified beam search. Beam search keeps only the top few partial sentences at each step and can prove nothing about what it discarded. We propose an exact decoder for this setting. It uses branch-and-bound search over a pretrained generator's own log-probabilities. The rules are encoded as an alignment problem: each required concept is matched to exactly one output token. That matching is solved as a small integer linear program (an optimization over yes/no variables with linear constraints), and it is used to prune partial sentences that can no longer satisfy the rules. The decoder either returns the highest-scoring rule-satisfying output or a certificate that no better one exists.
The experiment matters because it resolves a standing tension. Exact search in unconstrained neural translation is known to be harmful: the model's favourite output is often the empty string. Exact search under the explicit coverage constraints of older statistical models, by contrast, measurably helped. Hard coverage constraints make the empty string impossible, so the constrained optimum is a well-posed and non-trivial object. We want to know whether it is good text, or whether the length pathology returns in a new form. Our prediction is that it returns as a "minimal satisfier": the shortest string that strings the required concepts together with as little connecting language as possible.
Core Claim
Our claim has three parts. First, exact decoding of a neural generator under concept-coverage constraints is feasible for short outputs such as CommonGen targets, if two things hold: the search starts from a strong heuristic solution, and each partial sentence is checked against the alignment constraints. Second, with certificates in hand, the gap between constrained neural generation and human quality can be split into a search share and a model share. Third, we expect the model share to dominate, and to show up as a predictable length pathology. If that holds, the field should stop building better constrained beam searches and fix the scoring objective instead. If it does not hold, and exact search substantially improves quality, then constrained heuristics are leaving real quality on the table. Either result is actionable, and neither can be obtained without certificates.
Relation to Prior Work
The search-versus-model question has been answered carefully before, but only for statistical systems with linear, decomposable scores. Four papers in this line made exact search tractable with structure-aware algorithms and then measured how often the standard decoder failed:
- Revisiting Optimal Decoding for Machine Translation IBM Model 4 casts word-based translation as an integer program solved by adding cutting planes on demand. The greedy decoder missed the optimum in 59.9% of French-English sentences, and fixing this gained 0.97 BLEU.
- Exact Decoding of Phrase-Based Translation Models through Lagrangian Relaxation relaxes the "translate every word once" constraint with multipliers. It found that the standard beam decoder erred on 18.1% of sentences, yet fixing these errors did not consistently raise BLEU.
- Exact Decoding of Syntactic Translation Models through Lagrangian Relaxation certified 97.7% of sentences and exposed search errors in 50.5% of them.
- An Exact Dual Decomposition Algorithm for Shallow Semantic Parsing with Constraints enforced logical constraints with zero violations, but its F1 was essentially the same as a large beam (64.43 vs 64.59).
These papers supply our diagnostic methodology and our expectation that certification rates, not just averages, must be reported. Their techniques do not transfer directly, because an autoregressive neural score is not linear in any small set of indicator variables. Integer programming therefore cannot be the whole decoder, only the constraint layer inside one.
Two neural studies motivate and constrain the design:
- On NMT Search Errors and Model Errors: Cat Got Your Tongue? ran exact depth-first search and found the empty string to be the model's optimum for 51.8% of WMT15 English-German sentences, with BLEU collapsing to 2.1.
- He et al. found that beam size 5 already recovers the global optimum for about 70% of sentences, and that exact search costs over 3 BLEU.
These are the negative results we build on. They show that exact search is computationally possible for neural models when the incumbent solution is strong. They also show it is uninformative without constraints, since the empty-string degeneracy swamps everything else. Our contribution is to run the same kind of exact search inside a feasible set that excludes that degeneracy.
The heuristic we test comes from NeuroLogic Decoding. It enforces rules written in conjunctive normal form (an AND of OR-clauses) inside beam search by pruning, grouping hypotheses by which clauses they satisfy, and adding bonuses for newly satisfied clauses. It cut Recipe1M+ hallucinated ingredients from 14.3% to 0.6%. By construction it cannot certify optimality, and it can prune a good hypothesis early if the first tokens earn no clause bonus. We treat it as the incumbent generator and as the method under diagnosis.
The alignment encoding comes from the integer-programming alignment literature:
- The Complexity of Phrase Alignment Problems formulates one-to-one coverage with binary indicator variables.
- Optimal and Syntactically-Informed Decoding for Monolingual Phrase-Based Alignment adds structural side constraints and shows that exact alignment beats simulated annealing in both speed and precision.
- Shekhovtsov is our reference for why bipartite-matching relaxations are typically tight. This matters because it lets the pruning check run as a fast linear program rather than a full integer solve.
The evaluation setting is CommonGen. It reports T5-Large at 31.6% SPICE, a caption-similarity metric, against 63.5% for humans, while coverage of the required concepts is above 95%. That combination already hints that the missing quality is not mainly about satisfying constraints.
Research Program
Let $y$ be an output token sequence and $s(y)=\sum_t \log p(y_t \mid y_{<t}, x)$ its log-probability under a fixed pretrained generator given input $x$. Let $\mathcal{C}(x)$ be the set of rule-satisfying outputs. The object we compute is the constrained optimum:
$$y^\star = \arg\max_{y \in \mathcal{C}(x),\ |y| \le L_{\max}} s(y),$$
where $L_{\max}$ is a generous length cap, twice the longest reference.
Membership in $\mathcal{C}(x)$ is written as an alignment problem. Binary variables $a_{cj}$ indicate that concept $c$, or an allowed inflection of it, is realised by output position $j$. Each concept must be aligned exactly once, each position realises at most one concept, and positions carrying excluded tokens are forbidden:
$$\sum_j a_{cj} = 1 \ \ \forall c, \qquad \sum_c a_{cj} \le 1 \ \ \forall j, \qquad a_{cj}\in\{0,1\}.$$
The search. The decoder is depth-first branch-and-bound over prefixes. Because every log-probability is at most zero, a prefix's score upper-bounds every completion. A prefix is therefore pruned when its score falls below the incumbent, which is the best complete feasible output found so far.
Alignment-based pruning. A prefix is also pruned when the alignment program has no feasible completion. This happens when the concepts not yet placed cannot be matched to the at most $L_{\max}-|y_{<t}|$ remaining positions, or when a disjunctive clause has had all of its alternatives excluded. The check matters because the constrained incumbent scores lower than an unconstrained one, which makes score-based pruning weaker. Feasibility pruning is what we expect to keep the search tractable, and an ablation below tests exactly this.
Incumbents. NeuroLogic with a large beam supplies the initial incumbent. A second source borrows the multiplier idea of Chang and Collins. Per-concept token bonuses $\lambda_c$ are adjusted by subgradient steps until an ordinary beam search produces a satisfier. This is used purely as a heuristic for finding good incumbents. We do not claim it produces a bound, since the relaxed neural problem is not itself solved exactly.
Outputs of the decoder. Each instance ends in one of three states: certified optimal, budget exhausted with the best found, or proven that no feasible output exists within $L_{\max}$. Each certified instance is then labelled. It is a search error if $s(y^\star) > s(y_{\text{NeuroLogic}})$. It is a model error if NeuroLogic's output is already optimal yet scores below the reference on quality. Otherwise it is correct.
Variants of the objective. We repeat the analysis under two alternative scores, length-normalised log-probability and log-probability with a per-token reward. These need a modified bound: a per-step reward $r$ turns the admissible bound into prefix score plus $r$ times the remaining length. The question they answer is whether a simple change of objective moves errors from the model column into the correct column.
Baselines
The naive reference point is plain beam search with the same generator, followed by discarding outputs that violate the rules. It shows how much of any gain comes from constraint handling at all, as opposed to from exact search.
The strongest existing method is NeuroLogic decoding NeuroLogic Decoding. It is the standard heuristic for rule-constrained generation and the method whose failures we are trying to attribute. It will run on the same checkpoints, the same rule sets and the same length cap as our decoder. Its beam width and clause-bonus weight will be tuned on the CommonGen validation split with a tuning budget matched to ours. We report it at its tuned setting and at a beam of 100 or more, so that its best effort is on record. The reference numbers available in the file are T5-Large at 31.6% SPICE on CommonGen and human text at 63.5% CommonGen, plus NeuroLogic's Recipe1M+ hallucination rate of 0.6%. No reported result was found on Lacuna for NeuroLogic's SPICE on CommonGen, so we will produce that number ourselves under our setup.
Beating NeuroLogic is not the only success criterion, because a finding that exact search does not help is also valuable. Exact search counts as beating the heuristic on quality if it improves SPICE by a margin exceeding bootstrap confidence intervals on certified instances. It counts as beating it on diagnosis if it certifies at least roughly 80% of test inputs within a fixed budget, in the spirit of the 90% within-timeout rate of Riedel and Clarke.
Two further baselines run on identical hardware:
- Sampling plus filtering. Draw many samples per input, keep the highest-scoring feasible one, and match wall-clock time to the exact decoder.
- Unconstrained exact search. This reproduces the empty-string phenomenon on our checkpoints, as a calibration check against Stahlberg and Byrne.
The key ablation removes alignment-feasibility pruning and keeps only score-based pruning. If certification rates barely change, the integer-programming layer is decoration and we will say so.
Why not just…?
Why not just increase NeuroLogic's beam and see whether scores improve? This is the most serious alternative, and we run it. A growing beam that finds higher-scoring feasible outputs is evidence of search error, but it gives only a lower bound on the search-error rate. The phrase-based beam decoder still erred on 18.1% of sentences at beam 100 Chang and Collins, and cube pruning at beam 50 erred on 50.5% Rush and Collins. We will report how often the largest beam coincides with the certified optimum. If it coincides on nearly all instances, large beams are an adequate cheap proxy. That would be a useful negative result, and we would recommend the proxy.
Why not just sample many outputs and keep the best-scoring one that obeys the rules? Like beam enlargement, this gives only a lower bound, and it is biased toward outputs that are probable under sampling rather than those that score highest. The matched-compute sampling baseline measures this directly, as the fraction of certified optima that sampling recovers.
Why not just fix the model, for example by adding length normalisation or fine-tuning, and skip diagnosis? If our hypothesis is right, that is exactly the right move. The exact decoder is what tells us so, and it tells us which fix to apply. The objective-variant experiments show whether length normalisation alone removes the minimal-satisfier degeneracy, before anyone pays for retraining.
Why not just hand the whole problem to a commercial integer solver? The autoregressive score is not linear in any tractable set of indicator variables, so it cannot be written as a solver objective. Even for linear problems, structure-aware methods ran 9x faster than CPLEX Das et al..
Proposed Experiments
Primary study. The primary study uses the CommonGen test set with BART-Large and T5-Large fine-tuned generators. Rules are concept inclusion with allowed inflections. We report certification rate within fixed per-input budgets of 10, 60 and 600 seconds, and the search-error and model-error rates on certified inputs. We also report SPICE, BLEU and concept coverage for the exact optimum versus NeuroLogic, and length ratios.
Secondary study. On Recipe1M+ we add exclusion rules that forbid ingredients not on the list, and ask whether NeuroLogic's residual hallucinations are search errors or model preferences.
Decisive check 1: the minimal-satisfier prediction. If certified optima are systematically shorter than both NeuroLogic outputs and references, and score lower on SPICE, the length pathology survives constraints. The prediction fails if certified optima match reference length and quality.
Decisive check 2: the pruning ablation. Certification rates collapsing without alignment pruning would confirm that the matching layer is what makes exact search possible.
Decisive check 3: the objective variants. Re-running the attribution under length-normalised and per-token-reward scores shows whether the model share of the gap is an artefact of the raw log-probability objective or survives a change of objective, and therefore needs retraining.
References
- Revisiting Optimal Decoding for Machine Translation IBM Model 4
- Exact Decoding of Phrase-Based Translation Models through Lagrangian Relaxation
- Exact Decoding of Syntactic Translation Models through Lagrangian Relaxation
- An Exact Dual Decomposition Algorithm for Shallow Semantic Parsing with Constraints
- On NMT Search Errors and Model Errors: Cat Got Your Tongue?
- Empirical Analysis of Beam Search Curse and Search Errors with Model Errors in Neural Machine Translation
- NeuroLogic Decoding: (Un)supervised Neural Text Generation with Predicate Logic Constraints
- The Complexity of Phrase Alignment Problems
- Optimal and Syntactically-Informed Decoding for Monolingual Phrase-Based Alignment
- Maximum Persistency in Energy Minimization
- CommonGen: A Constrained Text Generation Challenge for Generative Commonsense Reasoning