acceptodds
Under review as a conference paper at ICLR 2027

Order Stability in Masked Generation: Swap Depth and Selective Repair

Abstract

We develop a quantitative theory of order dependence for positive masked conditional tables. Two structural effects govern reliability. First, along a route with D layers of disjoint adjacent swaps and total source-weighted local Hellinger energy E, the endpoint laws satisfy TV^2 <= 15DE. A matching product-distribution construction makes the depth dependence necessary, although the upper bound allows arbitrary statistical dependence. Second, every fixed order can be exponentially close to an anchor while a content-adaptive order remains a constant distance away, even with all token probabilities in [1/4,3/4]. The same construction gives an exact exponential coverage penalty for independent-mask auditing. We connect local swap audits to anchor-conditional errors and selective repair. For a fixed deterministic policy, replacing selected rows has exactly additive forward-KL benefits. Under a known probability floor, independent anchor replay learns a near-optimal repair budget and certifies its residual error; bounded unresolved-prefix width makes the required conditional evaluations tractable. Bounded-score Chernoff certificates expose the finite audit cost. Exhaustive checks and sample-selected repair experiments demonstrate the structural scalings and nonvacuous certificates. The guarantees measure reliability relative to an anchor; external accuracy requires a separate anchor-quality bound.

Primary area:
generative models
Keywords:
masked generative models, conditional compatibility, decoding order, Hellinger distance, adaptive generation, selective repair, finite-sample certification

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_E34SOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

The general topic of the paper is studying how the order of unmasking affects the output distribution in masked generative models. In practice, because neural networks only approximate consistent conditional distributions, different unmasking trajectories produce distinct joint distributions.

Sections 2-4 (Theorems 2,3,5) relate the squared total variation distance between two fixed decoding orders to the sum of local quantities and the depth. They build to Theorem 5 which Gemini rephrases as: "even if a model is exponentially consistent across all fixed permutations, a content-adaptive decoding policy (like confidence-based unmasking) can deliberately steer itself into rare, inconsistent contexts to incur a constant Ω(1)\Omega(1) total variation discrepancy."

Sections 5 on present more theorems related to "repair" of an adaptive policy toward a trusted, fixed anchor ordering.

Critical strengths

The structural results in the first half of the paper are genuinely nice, clean theoretical contributions. Framing the compounding of local errors through parallel swap-layer depth rather than total swaps is a clever and insightful use of martingale/stopping-time Hellinger chain rules. Theorem 5 is genuinely useful if I understand correctly-- it shows that auditing or regularizing on random masks is insufficient to guarantee safe adaptive decoding.

Critical weaknesses

The primary weakness is readability. Rather than setting proper context, the text jumps immediately into ungrounded vocabulary. For example, the opening sentence introduces "a quantitative theory of order dependence for positive masked conditional tables." Only after processing most of the paper does it become clear that by "conditional tables" we are referring to typical generative neural networks. The abstract goes on to drop terms like "source-weighted local Hellinger energy" as if most readers would know what that is. To me this is essentially disqualifying. It's fine to brainstorm with an AI or use it to polish your text, but this paper is so heavily LLM generated that it loses value as a communicative tool for other humans.

Also I think the paper has been stuffed with theorems for the sake of proving results rather than determining anything necessarily useful. I don't see how the "repair" solution built in the second half of the paper (Sec 5 on) is of any practical value. If you have a fixed anchor order (like left-to-right order), you can already sample directly from the anchor. Why is it interesting that it is possible in principle to "repair" some other permutation toward that reference? And the algorithm to do so requires an exponential number of model evaluations.

The paper would be greatly improved by focusing on Theorem 5 and generally paring it down to the actually useful results, and then putting those results in human-readable context.

Questions for authors

Could you justify the utility of Theorems 6 and 10? Theorem 10's sample complexity scales with a uniform probability floor β\beta that is effectively zero in practice.

If a practitioner already has a trusted, fixed anchor order (like left-to-right) that can sample the reference distribution in nn steps, why would they use an intractable, exponential-time repair algorithm to force an adaptive policy to match it? Or is there some implication of this result that is interesting even if the algorithm is not practical?

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

The paper studies how reveal order affects the output distribution of masked generators. Its main theoretical contributions are a depth–energy stability bound, TV^2 <= 15DE, with a matching depth-dependent construction, and an exponential separation between fixed-order and content-adaptive decoding. It then develops coverage-aware auditing and selective conditional repair relative to an anchor distribution. For a frozen deterministic policy, repair has additive forward-KL benefits, enabling replay-based selection and held-out certification. Validation consists of exhaustive finite-state checks and synthetic sample-selected repair experiments.

Critical strengths
  • The upper bound allows arbitrary statistical dependence, while the lower construction shows that the depth penalty remains necessary even with product endpoint distributions. This makes the result more informative than a bound based only on accumulating individual swap errors.
  • The fixed-versus-adaptive gap holds with all probabilities in [1/4,3/4]. The coverage cost is exact for the specified independent-mask audit. The paper also correctly notes this is not a lower bound for an auditor that chooses masks adaptively.
Critical weaknesses

Repair selection needs anchor-conditional evaluation, not just swap scores. The polynomial-query regime assumes fixed alphabet size and width, plus a known probability floor. The authors acknowledge that low-width inference may not be available in large neural models and that the experiments are synthetic. Even so, this limits the practical significance of the repair results.

Questions for authors
  • Is there a concrete masked-generation setting where unresolved-prefix width stays small while the decoding policy still differs meaningfully from anchor order?
Reviewer_zBoFOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
3(+1)
Read review
Paper summary

This paper develops a quantitative theory of order dependence in masked generation. Endpoint discrepancy is bounded by swap-layer depth times local Hellinger energy (TV2≤15DE\mathrm{TV}^2 \le 15DE, with a matching lower construction). The paper also constructs tables in which every fixed order is exponentially close to an anchor while a content-adaptive decoder stays a constant distance away; in this construction, an independent-mask audit requires a 2m2^m density amplification to cover the adaptive replay law. Using anchor replay, the paper shows that replacing selected conditional rows reduces forward KL additively for a frozen deterministic policy, and it gives a finite-sample procedure to select a repair budget and certify the residual error. Validation consists of exact checks and sampled experiments on synthetic binary models; there are no experiments on trained neural models.

Critical strengths
  1. The principal depth-scaling result is paired with a matching lower construction whose endpoint laws are product distributions, so the depth dependence is necessary rather than a proof artifact. A separate example with all conditionals in [1/4,3/4][1/4, 3/4] establishes the fixed–adaptive separation and its exact coverage cost.

  2. Together, these results show that fixed-order guarantees do not generally transfer to content-adaptive decoding, and that independent-mask audits can incur an exponential coverage penalty when decoder-relevant visitation is not controlled; this motivates replay-based auditing. This is a useful message for masked diffusion decoding, and the constants and selected numerical quantities I checked were consistent with the stated formulas.

Critical weaknesses
  1. The theory is not connected to a trained model. The exact evaluator has worst-case row-query cost O(nKw)O(nK^w), so scaling to large vocabularies depends critically on keeping the unresolved-prefix width very small; the paper neither demonstrates such a regime on a trained model nor quantifies the corresponding neural inference cost. The analysis also excludes independently sampled parallel updates and remasking. Repair is evaluated only on 16 five-bit tables with independently randomized conditional rows (mean unrepaired forward KL 3.2273.227). The experiments therefore establish the claimed finite-state behavior, but leave unresolved how large these effects are in trained decoders and whether the procedures are practically useful there.

  2. The matching depth dependence and the bounded-probability separation are the strongest contributions, and the paper correctly credits curl identities and exact compatibility to prior work. I find the additional contribution of the repair pipeline more limited: it combines standard identities and concentration tools under a frozen-policy, exact-conditional interface whose practical reach remains unclear. The reported bounds are also conservative even in synthetic settings:

  • The finite-sample audit certificate (0.5860.586) is ≈15×\approx 15\times the actual TV (0.0380.038), while the population bound alone is ≈3.6×\approx 3.6\times.
  • The observed maximum excess KL (0.007760.00776) is ≈100×\approx 100\times smaller than the worst-case bound of Theorem 10 (≈0.78\approx 0.78).

Whether informative certificates are attainable at feasible cost for trained models is not established.

Questions for authors
  1. Please provide a theorem-level comparison clarifying which depth, adaptive-separation, coverage, and repair results go beyond Kim (2026), and please specify the overlap with the concurrent Anonymous (2026) manuscript. The answer affects my novelty assessment.

  2. Please address the following reporting points: (a) Could you provide a complete per-category breakdown that reproduces the total of 28,842 checks? The categories listed in Appendix N.2 sum to ≈\approx 27,920–28,160. (b) Appendix E.2 explains that 2zˉ+8a2\bar{z} + 8a is a conservative relaxation. Could Fig. 1 also include the tighter 2zˉ+2a2\bar{z} + 2a bound from Eq. (58), so that the gain from numerical Chernoff inversion can be assessed against the sharper closed-form baseline? (c) Could Table 1 report the actual endpoint TV alongside the held-out certificates? (d) Could you quantify the gap between the observed selection regret and the worst-case bound in Theorem 10, and discuss how conservative the sufficient sample budgets in Eq. (29) are?

  3. [Could change my rating; otherwise future work]

    • Can the audit and repair be run on a trained masked diffusion LM in a low-width setting (e.g., short-span infilling, Sudoku, or a small-vocabulary grammar)? If so, please report the swap energies, the gap between fixed-order and confidence-based decoding, and the actual TV versus your certificates.
    • The paper correctly separates anchor consistency from external quality. What practical guidance or diagnostics could support the choice of anchor order, and how sensitive are the repairs to that choice?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.