acceptodds
Under review as a conference paper at ICLR 2027

Decoding under Constraint Uncertainty in Diffusion Language Models

Abstract

Constrained decoding usually assumes a known grammar, schema, or rule set. When constraints must be inferred from positive demonstrations, several hypotheses can explain the same observations, and enforcing one can exclude the correct output. We formalize this setting as hidden-constraint decoding and introduce TACTIC, an execution layer that carries constraint uncertainty into candidate selection. TACTIC converts posterior beliefs or confidence-weighted rules into candidate compatibility and combines it with frozen-model evidence. Factorized and tensor-train representations support independent and correlated constraint components. Our analysis establishes a false-exclusion lower bound for point commitment, posterior support preservation, and conditions for decision stability. Across controlled and real-data tasks, TACTIC improves on matched hard execution under scarce support. On CIDDS structured completion, the gains are 19.4 percentage points with DREAM-7B and 20.8 with LLaDA-8B. These results show how retaining plausible constraints allows model evidence to resolve ambiguity left by demonstrations.

Primary area:
generative models
Keywords:
diffusion language models, constrained decoding, constraint acquisition, uncertainty-aware decoding, structured generation, tensor networks

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_GYmgOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper presents TACTIC, a framework for decoding under constraint uncertainty in diffusion language models. Unlike traditional point commitment, TACTIC preserves acquisition uncertainty during candidate selection to reduce false exclusion. The framework uses posterior-predictive compatibility to measure how likely a candidate is accepted. The authors also use tensor-train factorization to further represent correlated posteriors. It also supports confidence-weighted rules for tasks without joint distribution. The paper provides theoretical analysis of false exclusion, posterior consistency, and decision stability. Experiments on multiple benchmarks show improvements over matched hard constraint execution.

Critical strengths

Pros:

  1. The idea of preserving constraint uncertainty instead of doing point commitment into single constraint hypothesis is simple and potentially useful. Although posterior averaging is not new but applying this into constraint decoding is nice and intuitive. Using Tensor-Train factorization to represent corelatted posterior is fairly interresting.
  2. The experments and ablations are extensive with various benchmarks and two main diffusion language models. The improvements on CIDDS task are substaintial.
Critical weaknesses

Cons:

  1. The paper's title is about diffusion language model, but many experiments do not involve actual iterative diffusion decoding. The dlms are only used for generate candidate score which I believe this could also be done by some standard Auto-regressive models. BFCL is the only one that directly integrates the proposed method into diffusion generation, but its improvement is relatively small.
  2. Each benchmark requires a separately designed constraint hypothesis space and acquisition procedure, which make things hard to generalize. For example, CatSup and GraphColor use posterior-based models, while CIDDS relies on confidence-weighted implication rules. In my opinion, it is unclear how much of the improvement comes from the general framework itself rather than the task-specific constraint design.
Questions for authors
  1. The experiments show that soft compatibility can outperform hard constraint execution, which makes sense to me. However, I am still unclear about the role of diffusion language models in the proposed framework. Could the authors compare against a standard autoregressive language model for candidate scoring like llama-3 or qwen3 models? This would help clarify whether the improvements are related to diffusion decoding.
  2. I am also curious about the generalizability of TACTIC. How easily can TACTIC be extended to other tasks with different types of constraints? Moreover, the idea of soft constraint compatibility seems quite general and does not appear to rely on diffusion language models, could the authors clarify which parts of TACTIC are specifically designed for dlms and which parts can be directly applied to other language models?
  3. Theorem 1 makes sense to me. Though In practice, there could be many possible constraint hypotheses with different posterior probabilities and overlapping accepted sets. Could the authors provide some discussion or empirical analysis of how frequently such conflicts occur in the evaluated tasks, and what the actual false-exclusion rates are?
2 comments

Thank you for your questions about diffusion decoding and generalizability.

1. AR comparison and diffusion generation.

Why diffusion is a substantive setting. Masked dLLMs fill noncontiguous positions and can predict multiple tokens in parallel, so a valid prefix is insufficient to characterize the decoding state. Independent token masks also do not ensure joint validity. This motivates dedicated automaton inference and grammar-based infilling.

Those methods take the constraint as supplied. HCD addresses the next question: what should be executed when a few examples leave that constraint ambiguous? In our BFCL implementation, acquired compatibility enters joint sampling and the constrained marginals used for token commitment. It thus acts during iterative generation. Candidate experiments separately isolate the execution effect.

The contribution is this problem formulation and execution principle; it does not require superiority in every setting. On 100 tuning-disjoint BFCL queries, Soft/Hard/Open reach 54.33/48.67/53.00%. Soft-Hard is +5.67 pp with 95% interval [-1.67, 13.00]; Soft-Open is +1.33 pp with [-4.00, 6.67].

The additional AR experiment tests generality. CIDDS holds demonstrations, rule family and candidates fixed. Hard is dev-retuned using its actual fallback objective:

ScorerRetuned HardTACTIC SoftGain, pp
DREAM53.48%71.47%+17.99
LLaDA55.12%72.85%+17.73
Qwen2.5-Coder-7B-Instruct54.21%70.53%+16.32

The AR gain has a 95% interval of [14.91, 17.73] pp. This supports a broader HCD interface beyond dLLMs.

2. Task design and transfer.

Learning constraints that generalize across arbitrary tasks is a difficult, separate research problem. HCD starts from the uncertainty left by acquisition and asks how to execute it; it does not require one acquisition algorithm to work unchanged everywhere. Within each task, Hard and Soft receive the same demonstrations and use the same rule family and candidates. The controlled gains reported above demonstrate TACTIC’s execution advantage under the same acquisition framework.

Simple CIDDS controls further identify the source of benefit:

DREAM readoutAccuracy
Compatibility only69.70%
Equal-weight rules + model evidence70.61%
Confidence-weighted rules + model evidence71.47%

The last two rows share alpha=0.3. Confidence weighting adds 0.85 pp with 95% interval [0.24, 1.47]; equal weights were not separately retuned. These controls locate the main benefit in graded execution, with a further contribution from confidence weighting in this setting.

Extension is natural at the interface: a task supplies acquired beliefs or weighted rules and a compatibility evaluator; these combine with model evidence through a suitable candidate or decoding interface. The task adapter changes, while the execution principle remains the same. HCD itself is architecture-independent, and the AR control demonstrates this transfer. The current BFCL executor specializes the shared principle to diffusion.

3. Conflict and false exclusion.

The diagnostics confirm that false exclusion occurs in practice. Using plain Hard's feasibility mask, CIDDS yields:

Exclusion eventShare of all records
Gold excluded before fallback20.69%
Gold excluded despite a nonempty feasible set6.31%

Thus, false exclusion is not limited to cases where the feasible set becomes empty.

For posterior hypotheses, a candidate with compatibility Psi has acceptance-disagreement probability 2*Psi*(1-Psi) under two independent posterior draws. This quantifies candidate-level disagreement between plausible constraints.

The separate n=8 GraphColor diagnostic measures the resulting exclusion directly:

Support sizeFactorized-MAP target-exclusion rate
251.7%
421.7%
85.0%

These measurements connect the theoretical risk to observed false exclusion and show how its frequency changes with available support.

Thank you for the additional experiments. The AR comparison and false-exclusion analysis address my earlier questions. I do think preserving constraint uncertainty is a good idea and it can be generalized into both AR model and dlms. My remaining concern is whether soft constraints actaully improve on unconstrained generation in the diffusion decoding settings. On BFCL, the improvment is relatively small so the benefit in the setting emphasized by the paper remains unclear. I therefore maintain my score

Reviewer_q8iHOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The authors study constrained decoding when the constraints are not given explicitly and must instead be inferred from a small number of positive demonstrations. Main observation in the paper is that committing to one inferred constraint can exclude a correct output even when that output remains compatible with other plausible constraints. The proposed method assigns candidates a graded compatibility score and combines this with evidence from a frozen diffusion language model. The paper develops posterior-predictive compatibility for independent and correlated constraint components, with tensor trains representing the latter. It also supports confidence-weighted rules. Experiments compare hard and soft execution across categorical completion, graph colouring, network-record completion, schema validity, and function calling.

Critical strengths
  • The paper addresses a meaningful problem: constraints inferred from a few positive examples may be too uncertain to enforce as hard restrictions.

  • The distinction between acquisition and execution is useful. A constraint that explains a few positive demonstrations is not necessarily reliable enough to exclude outputs. Carrying that ambiguity into candidate selection is a sensible approach. The controlled comparisons make the consequences of premature commitment concrete, rather than treating uncertainty representation as an end in itself.

  • The empirical evaluation shows substantial gains on CIDDS across two backbones. The ablations and baseline controls strengthen the evidence that graded compatibility improves completion accuracy.

Critical weaknesses
  • The CatSup comparison does not clearly isolate the benefit of retaining uncertainty. In appendix J.1 of the paper states that the hard baseline restricts candidates using observed co-occurrence sets, whereas the soft method uses posterior membership probabilities. The hard baseline is therefore not the MAP constraint obtained from the same acquisition model. With limited demonstrations, restricting outputs to observed combinations can be overly conservative. Some of the improvement may come from this difference in readout rather than posterior averaging itself.

  • Empirical advantage is not consistent across the more practical benchmarks. The CIDDS results are strong, but the evidence on JSON Schema and BFCL is less convincing. On JSON Schema, the recalibrated method slightly exceeds hard commitment at the selected support size but trails it at the other sizes. On BFCL, the recalibrated soft–hard difference has a confidence interval spanning zero, and Open execution performs better than the soft method. These results suggest that retaining uncertainty is useful in some settings, but its advantage depends on calibration and domain coverage. The broader claims should reflect this variation.

  • The theoretical analysis and the strongest empirical result concern different compatibility constructions. The support-preservation, consistency, and stability results are developed for posterior-predictive compatibility. CIDDS instead uses confidence-weighted rule satisfaction, while some controlled experiments use working likelihood approximations. Both constructions fit the proposed framework, but the posterior guarantees do not directly explain the strongest observed gains. The paper would benefit from stating more clearly which conclusions are theoretically supported and which are established empirically.

  • The candidate-selection experiments leave an important part of the decoding problem untested. CatSup and GraphColor enumerate the candidate space, while CIDDS enumerates the vocabulary product for the masked fields. This is useful for isolating the effect of constraint execution, but it assumes that the correct completion is available for selection. The reported gains therefore do not establish how the method behaves when candidate generation misses valid outputs or enumeration becomes infeasible. BFCL provides a more direct generation experiment, but its results offer weaker support for an advantage.

  • The added value of modelling joint constraint dependence is limited in the reported experiments. Table 3 shows that a product of matched marginals reproduces much of the effect of conditioning on the constraint family. Exact joint dependence provides a small improvement in the fixed-cardinality settings, no improvement for the connected family, and a slightly lower point estimate for the degree-sequence family. This does not undermine the main soft-compatibility result, but it makes the practical need for the correlated-posterior machinery less clear.

Questions for authors
  1. Is a CatSup comparison against the MAP constraint under the same acquisition model available? This would help distinguish the benefit of retaining posterior uncertainty from the effect of using a different hard readout.
  2. For the tensor-train study, which decision results can be obtained directly from valid probability cores without dense clipping and renormalisation? Please clarify whether the reported rank and computational costs describe the representation actually used for the repaired distributions.
  3. Could the paper state more explicitly how the evidence is divided between posterior-predictive compatibility and confidence-weighted rules? Both are legitimate parts of the framework, but the strongest real-data result uses the latter, while the main guarantees concern the former.
1 comment

Thank you for your careful feedback on our comparisons and theoretical scope.

1. Same-posterior MAP comparison.

The same-posterior control is now available. It separates hard-readout design from posterior averaging. MAP and Soft share the posterior on 90 held-out rules:

ReadoutAccuracy
Observed-set Hard25.22%
Same-posterior MAP56.79%
TACTIC Soft56.42%
Open56.39%

The observed-set loss illustrates why execution matters. Soft-MAP is -0.375 pp with a 95% rule-cluster interval of [-1.64, 0.96], so no further gain over MAP is established here. HCD makes this distinction explicit, without assuming every decision must improve. CIDDS separately establishes gains under matched acquisition.

2. Calibration and practical benchmarks.

Our central contribution is HCD: formalizing decoding when the constraint itself remains uncertain, and identifying how acquisition and execution interact. Its value is not contingent on winning every benchmark.

The experiments test this formulation under different decision regimes. Frozen development-selected thresholds on 771 held-out JSON schemas and a tuning-disjoint 100-query BFCL generation subset give:

Benchmark / metricHardSoftOpen
JSON Schema / balanced accuracy84.12%84.30%--
BFCL / official accuracy48.67%54.33%53.00%

Soft has higher JSON Schema point estimates at all five support budgets, with an average gain of +0.18 pp. BFCL Soft-Hard is +5.67 pp with 95% interval [-1.67, 13.00]; Soft-Open is +1.33 pp with [-4.00, 6.67].

These results do not imply uniform superiority. JSON Schema's nominal 95% intervals exclude zero only at the two smallest budgets, and one shared threshold did not improve the original threshold; BFCL's intervals include zero. Alongside CIDDS, these findings show why calibration and candidate coverage belong in the HCD formulation. They delimit the method's advantage without removing the problem-level contribution.

3. Theory and empirical compatibility.

TACTIC separates the execution interface from the construction of compatibility. Posterior-predictive compatibility provides support-preservation, consistency and stability guarantees under the stated probabilistic assumptions. Confidence-weighted rules test the same interface empirically; PP guarantees are not transferred to them. CatSup and GraphColor use working likelihoods, and consistency requires correct specification and identifiability.

The CIDDS finding stands on its controlled comparison: after Hard is retuned using the actual fallback objective, Soft still gains 17.99/17.73 pp on DREAM/LLaDA. Compatibility alone reaches 69.70%, showing that graded rule execution supplies most of the benefit. These are distinct, explicit roles for theory and experiment.

4. Finite candidate coverage.

Enumeration fixes candidate availability so that execution can be tested in isolation. We separately measured finite generation with four candidates per query on a 20-query BFCL diagnostic, without adding gold answers:

Generation armOfficial recall@4Heuristic final accuracy
Open60%60%
Hard70%65%
Soft70%70%

Correct answers are absent from 30-40% of these pools. This makes candidate coverage an observed limitation, rather than an assumed guarantee.

5. Dependence and valid TT cores.

Direct inference from valid cores is now verified. Nonnegative count-state cores for fixed K=4/8 have bond dimensions 5/9, zero measured compatibility error, and identical winners to exact DP on all 720 queries. No dense posterior or clipping is needed on this path.

Table 3 measures the separate question of accuracy gains from dependence. Matched marginals recover much of the benefit, so TT is an optional representation rather than a universal accuracy requirement.

In the earlier TT-SVD experiment, clipping repairs the contracted candidate-compatibility vector, not the posterior. Its TV concerns that vector, and chi denotes the truncation cap, not a repaired-posterior rank. The reported timings exclude dense construction. The direct-core result resolves valid execution in the tested fixed-cardinality setting without relying on that repair.

Reviewer_v9UMOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes TACTIC, which combines constraint compatibility inferred from a small number of valid examples with language model prediction scores to address decoding under unknown constraints in diffusion language models. Experiments show that the method outperforms hard enforcement of learned constraints on some tasks.

Critical strengths

None

Critical weaknesses

The methodological novelty of this paper is rather limited. Its core posterior-predictive compatibility (Eq. 4) is mathematically equivalent to the existing Bayesian hypothesis averaging [1] (Eq. 1), and learning unknown constraints from positive examples has also been studied in prior work [2]. Eq. 5 follows directly from the assumptions of independence and decomposability, while Eq. 7 applies existing tensor train techniques [3]. Combining model probabilities with auxiliary probabilistic guidance signals during decoding also has precedents in ARMs, such as FUDGE [4]. As for the dLLM part, the BFCL decoding implementation largely follows the finite-automaton-based constrained decoding method in [5], with the main additions being soft penalties and weighted transitions for unseen enum values. The other experiments mainly involve candidate re-ranking or validity classification and do not rely on decoding mechanisms specific to dLLMs. Therefore, the technical contribution of this paper seems to lie mainly in combining and adapting existing methods, rather than introducing new algorithms. The paper also does not sufficiently explain why this problem needs to be studied specifically for dLLMs.

[1] Generalization, similarity, and Bayesian inference

[2] What Are the Rules? Discovering Constraints from Data

[3] TENSOR-TRAIN DECOMPOSITION

[4] FUDGE: Controlled Text Generation With Future Discriminators

[5] Constrained Decoding for Diffusion Language Models via Efficient Inference over Finite Automata

Questions for authors

The authors need to clearly state the substantive technical contributions over the related works mentioned in the Weaknesses, beyond simply combining them. They also need to justify why this method needs to be specifically designed for dLLMs.

1 comment

Thank you for your comments on our contribution and its relation to prior work.

1. The contribution starts from a new problem formulation.

TACTIC is motivated by a practical gap: constraints are often inferred from a few valid examples, yet conventional execution treats the inferred constraint as certain. Several constraints can explain the same examples while disagreeing on a new output. Committing to one can therefore exclude a valid answer before the language model can resolve the ambiguity.

We formalize this setting as hidden-constraint decoding, HCD. It changes the question from enforcing a supplied constraint to deciding how uncertain acquired constraints should influence generation. This is the new paradigm our paper develops. Assessing five familiar ingredients separately misses that problem-level contribution: they form a coherent acquisition-execution interface, rather than an arbitrary collection of components.

2. Each technical component serves that problem.

Positive-example acquisition [2] supplies hypotheses; HCD studies their downstream execution while ambiguity remains. Bayesian averaging [1] provides posterior compatibility, independence gives its factorization, and TT [3] represents dependence when needed. The contribution is their connection to false-exclusion risk, support preservation and decision stability under stated assumptions. FUDGE [4] uses an attribute predictor; our guidance expresses uncertainty about acquired constraints. The automaton machinery in [5] supplies an executor; TACTIC changes how uncertain enum restrictions enter it. We credit these foundations without claiming to reinvent them.

This distinction is operational: point acquisition followed by hard execution discards alternatives before query evidence is applied; TACTIC carries compatibility into the decision. Posterior guarantees apply to the probabilistic construction, while confidence-weighted rules provide an empirical extension. TT is optional: nonnegative fixed-cardinality cores match exact inference on all 720 tested decisions without dense posterior construction or clipping.

3. Controlled results demonstrate the value of the interface.

CIDDS uses the same demonstrations, rule family and candidates for Hard and Soft. Hard is retuned on development data using its actual fallback objective. Accuracy is:

ScorerRetuned HardTACTIC SoftGain, pp
DREAM53.48%71.47%+17.99
LLaDA55.12%72.85%+17.73
Qwen2.5-Coder-7B-Instruct54.21%70.53%+16.32

These gains cannot be explained by giving Soft extra task information. Compatibility alone reaches 69.70%, identifying graded execution as the main source of improvement. The AR gain has a 95% interval of [14.91, 17.73] pp, supporting transfer across scorers.

4. Why begin with diffusion language models?

This starting point follows the gap already identified in Sections 1 and 7. DINGO handles regular-expression constraints, Muendler et al. address CFG-constrained infilling, and Dang and Ermon [5] provide joint sampling under automaton constraints. These works develop executors for constrained dLLM generation, with the formal constraint supplied. HCD asks how execution should proceed when a task constraint must instead be inferred from a few valid examples and several hypotheses remain plausible.

Masked dLLMs resolve noncontiguous positions and can predict several tokens together. In our BFCL executor, acquired compatibility shapes joint samples and the constrained marginal entropies used to choose token commitments, as specified in Appendix J.1. This makes uncertainty about the acquired constraint part of iterative generation, while using the existing automaton inference machinery.

We therefore begin with dLLMs to study the acquisition-execution gap within this concrete constrained-generation setting. The formulation is broader than the starting architecture, as the AR transfer result above demonstrates.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.