Admissible LP Bounds for Constrained Infilling in Diffusion Language Models

Language models that write left to right cannot see what they still owe. When a request says "exactly 12 words, the 7th word is 'river', no more than 70 characters," the model commits early tokens blind to whether the remainder can still fit. Masked diffusion language models are generators that start from a canvas of blank placeholders and fill them in any order. They remove that blindness in principle, but they still pick which blank to fill next by local confidence. That choice routinely traps the rest of the sequence. This proposal imports a tool from cost-optimal planning, the linear-programming (LP) lower bound. A planner uses it to prove that a partial plan cannot be completed cheaply, and we use it the same way on a partially filled canvas. At every decoding step we solve a small LP over "which candidate token goes in which blank." If the LP has no solution, the canvas cannot satisfy the counting, positional and keyword constraints, so the branch is pruned with certainty. If it does have a solution, its value bounds the cost of the best completion from below. That bound ranks branches in an A*-style search, picks the next blank to commit, and tells the search when to stop.

The two-sentence version is as follows. Treat each blank on a diffusion canvas as a slot and each candidate token as an action that uses up characters and words. An LP that counts these actions, of the kind used in optimal planning, then gives a cheap, provable test of whether the constraints can still be met and a lower bound on the remaining cost, and the decoder uses these to prune, to order its choices, and to terminate. Constrained generation benchmarks show how much room there is: GPT-4 satisfies only 50.9% of compositional constraints on COLLIE (COLLIE), and failures concentrate on exact counts and late-position requirements.

Core Claim

Operator-counting LPs in planning compute an admissible heuristic, meaning a value guaranteed never to exceed the true remaining cost. They do this by minimizing total action cost subject to linear constraints on how often each action must occur (Heuristics for Cost-Optimal Classical Planning Based on Linear Programming). Their best-known weakness is that they treat a plan as a bag of actions and ignore order. Our central observation is that on a fixed-length diffusion canvas this weakness largely disappears.

Position on a canvas is an index, not a time step that must be inferred. Let $Y_{i,t} \in [0,1]$ be the fractional assignment of candidate token $t$ to slot $i$. Then the word index of slot $i$ is a prefix sum of word-start indicators over slots $j < i$, which is a linear expression. This means "exactly $W$ words," "exactly $C$ characters," "the $k$-th word is X," and "contains keywords A and B" all become linear constraints over the same variables. The resulting LP is

$$\min_{Y} \sum_{i,t} c_{i,t}\, Y_{i,t} \quad \text{s.t.} \quad \sum_t Y_{i,t} = 1,\;\; \sum_{i,t} \ell_t Y_{i,t} = C,\;\; \sum_{i,t} w_t Y_{i,t} = W,\;\; \sum_{i,\, t \in L} Y_{i,t} \ge 1,$$

Here $c_{i,t}$ is the model's negative log-probability for token $t$ at slot $i$ given the current canvas. The quantity $\ell_t$ is the character length of $t$, and $w_t \in \{0,1\}$ marks whether $t$ starts a new word, which in most subword vocabularies means it carries a leading space. $L$ is the set of tokens that realize a required keyword, which plays the role of a landmark (Landmarks for Numeric Planning Problems). Positional constraints add prefix-sum rows of the form $\sum_{j<i,t} w_t Y_{j,t}$. A null token in the style of $S^3$ absorbs unused slots, which makes length variable within the canvas.

We state the guarantee honestly. The feasibility test is exact with respect to the candidate set: an infeasible LP proves that no completion drawn from those candidates satisfies the constraints. The cost bound is admissible only with respect to the frozen per-slot costs at the current canvas. Once a slot is committed, the model rescores the others, and their conditional costs can move in either direction. We therefore claim provable pruning for hard constraints and an admissible bound for a snapshot surrogate cost. We do not claim optimality with respect to the model's true joint likelihood. Experiments will measure how often the snapshot bound is violated after rescoring.

Research Program

The work builds the LP layer on top of open-weight masked diffusion models, namely LLaDA as used in Unveiling the Potential of Diffusion Large Language Model in Controllable Generation and DiffusionGemma (DiffusionGemma Technical Report). The constraints are compiled from COLLIE's constraint grammar (COLLIE).

At each node of the search we take the model's top-$K$ tokens per open slot, with $K$ around 32 plus the null token, and solve the LP. The LP serves three purposes at once. First, if it is infeasible the node is pruned. Second, its value plus the committed cost gives an $f = g + h$ priority for best-first search. Third, its solution and dual prices choose the next slot to commit. A slot whose LP solution is already nearly integral is safe to commit. A slot that carries a large reduced-cost spread is where the constraints bite, and that slot is committed next. This last use is the replacement for the greedy-confidence rule that DiffuSearch showed to be myopic. DiffuSearch fixes it with Monte Carlo rollouts. We fix it with a deterministic bound.

Following Scala et al., we add redundant constraints that tighten the LP. One example is an implied bound linking character count and word count through minimum and maximum token lengths. Following the cost-partitioning literature, we consider allowing general rather than nonnegative cost shares (From Non-Negative to General Operator Cost Partitioning) when several constraint families are combined. The termination rule is the planner's own: stop when the best complete canvas has cost no greater than the minimum $f$ over open nodes. This rule directly targets the "overthinking" degradation reported for $S^3$ and DiffuSearch.

The LP has at most a few thousand variables per node. Per-node solve time is the main engineering risk. We will warm-start from the parent node's basis, which is the standard trick in planning LP heuristics. We will report wall-clock time, not only node counts.

Baselines

The naive reference point is the diffusion model with its native decoding: confidence-based unmasking (LLaDA's Top-K remasking) with the constraint stated only in the prompt. A second naive point is the same model with $S^3$ scaffolding (Unveiling the Potential of Diffusion Large Language Model in Controllable Generation). On WikiBio, $S^3$ raises schema compliance from 31.2% for LLaDA to 99.4%. That makes it the bar on structural tasks, but it does nothing for numeric counts.

The strongest existing search method for ordering is DiffuSearch's MCTS over slot order (Can I Have Your Order?). It reports an 8.0% average gain over plan-and-infill diffusion and 19.5% absolute on MBPP. However, no reported result was found on Lacuna for DiffuSearch on COLLIE or CommonGen, so we will rerun it. We will give it the constraint checker as its rollout reward, on the same base model, and match it to our method in total model forward passes and in wall-clock time.

The strongest left-to-right competitor is automaton-constrained decoding (Automata-based constraints for language model decoding). For counting constraints we extend it with an exact dynamic program over the product of the constraint counters, applied to an autoregressive model of comparable size. For COLLIE we also cite GPT-4's reported 50.9% average satisfaction as a reference, though not a matched comparison.

Ablations isolate the key ingredient. The first is feasibility-only LP, which prunes but uses confidence for ordering. The second is cost LP without dual-guided slot choice. The third is LP without prefix-sum positional rows, which reproduces the bag-of-actions weakness. The fourth is LP without redundant constraints. All variants share the candidate size $K$ and the forward-pass budget, and any hyperparameters are tuned on a held-out COLLIE split with an equal number of trials.

Beating a baseline means higher constraint satisfaction at matched forward passes. It also requires no worse fluency, judged by perplexity under a separate autoregressive model and by human pairwise ratings.

Why not just…?

Why not just use an exact dynamic program or automaton with counters, decoding left to right? For a single counting constraint this is exact and cheap, and we expect it to beat our LP on, say, "exactly 82 characters" alone. It is a real threat, and we include it as a baseline rather than dismiss it. Two weaknesses remain. The first is the product state space: composed constraints such as character count, word count, several positional words and keywords multiply the number of states, whereas the LP adds rows. The second is that left-to-right decoding remains semantically blind even when it is syntactically valid (Addressing Semantic Blind Spots in Text-to-SQL). The experiment that settles this sweeps the number of composed constraints. If the dynamic program matches us at every level within time limits, our contribution reduces to the ordering component alone, and we will say so.

Why not just sample many outputs and keep one that passes the checker? COLLIE constraints are mechanically checkable, so best-of-$N$ is a strong, simple baseline. It fails exactly when satisfying samples are rare, and composed exact counts are such a case. We run best-of-$N$ at matched forward passes. If it equals our method, the LP is not earning its cost.

Why not just use DiffuSearch's rollouts with a constraint reward? Rollouts estimate value stochastically and cost extra FLOPs. The paper reports 35% more than greedy decoding. They also give no proof that a branch is dead. Our claim is that on hard constraints a deterministic infeasibility test prunes earlier and more cheaply. Matched-compute curves of satisfaction against forward passes will show whether this holds. A hybrid that uses LP pruning inside MCTS is also tested.

Why not just fine-tune with RL on a satisfaction reward? RL on CommonGen raised coverage only to 96.73% and invited absurd concept combinations (Constrained Text Generation with Global Guidance, CommonGen). It also cannot certify satisfaction on unseen constraint combinations. Our method needs no training, though it could be stacked on an RL-tuned model.

Proposed Experiments

The main benchmark is COLLIE's 1,132 instances across 13 constraint structures, with satisfaction rate broken down by constraint type and by constraint position. We predict the largest gains on late-position and multi-count structures, where left-to-right models collapse. CommonGen tests keyword landmarks; we report coverage alongside SPICE, where the best reported model, T5-Large, reaches 31.6% against a human score of 63.5%. WikiBio checks that LP decoding preserves $S^3$-level schema compliance while adding field-length constraints.

There are three decisive checks. The first is whether satisfaction at matched compute beats the counter dynamic program once three or more constraints are composed. The second is whether dual-guided slot ordering beats confidence ordering with pruning held fixed. The third is whether the bound-based stopping rule removes the degradation that otherwise appears as decoding steps increase. Alongside these we report how often the snapshot bound is exceeded after rescoring, which tells us how far admissibility actually transfers to the model's true likelihood.