acceptodds
Under review as a conference paper at ICLR 2027

Near-Linear Adaptivity Gaps in Parallel Masked Generation

Abstract

Masked generators reduce decoding depth by filling several positions at once, but each round must decide both what values to generate and which positions to fill together. Existing work shows that adapting this choice can help, but leaves open whether the generated values themselves are necessary for fast and accurate generation. We prove that they are, even when the full target distribution is known and every per-position prediction is exact. On a four-symbol target family where every pair of positions is independent, a decoder that uses earlier values samples exactly in three rounds, whereas every randomized schedule that ignores them needs nearly linear depth to attain a fixed small error. We further prove that any short, accurate decoder must make its batch choices reflect the information revealed by those values. In contrast, for uniform sampling without replacement, generated values cannot improve the optimal schedule. These results identify generated values as a necessary scheduling resource, rather than merely a useful signal, and show when this necessity disappears.

Primary area:
learning theory
Keywords:
masked generative models, adaptive parallel decoding, adaptivity gaps, constrained sampling, information-theoretic lower bounds, higher-order dependence

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_ssYbOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper explains why parallel decoding in masked generation models can be hard without looking at already generated values. The authors construct a toy four-symbol target in which every pair of positions is independent. A decoder that uses generated values can sample this target exactly in three rounds, but a decoder that ignores them needs at least omega(L/log L) rounds to keep the error small. However, for uniform sampling without replacement, generated values do not help.

Critical strengths
  1. Fig. 1 is easy to interpret, and the idea is clear.
  2. The main idea, that a fixed schedule cannot use information revealed during generation, is intuitive, and the construction combines known tools such as secret sharing, orthogonal arrays, and hidden hypermatchings.
Critical weaknesses

Weaknesses are mainly about visualization, clear explanation, and practicality. Details are explained in the questions.

Questions for authors
  1. Fig. 2’s format is hard to understand. (c) and (f) use the same caption “four scales” but it is shown differently in each plot: in (c) the four lines are the four sizes, while in (f) the sizes are on the x-axis and the four lines are leakage levels instead. “Naïve split”, “Naïve fail”, “Naïve witnesses” are not clearly distinguished, and “Naïve fail”, “Naïve witnesses” seem to refer to the same 4,296 cases. These terms are confusing.
  2. Even if this “ambiguity in next token prediction” happens in this toy example, is there a guarantee that real data has similar scenario? Lack of practical experiment (no trained model or real data is used) is the key weakness of the paper.
  3. The three-round decoder does not just look at generated values. It uses them to compute the hidden grouping with the full route table. Is the generated values itself necessary, or knowing the hidden structure is necessary?
  4. Is adaptive decoder explanation in Appendix F (e.g., confidence-based) actually faster than value-oblivious decoders on this example?
  5. Constants in page 6 and Lemma A.1,2 (1/9, 1/18, five ties) come from loose bounds, while the experiments show losses of about 0.5. Can the bound be tightened? Also, the theorem certifies error floor of 5.4%, and 5% threshold is arbitrarily chosen. What about larger tolerance decoder? At least the calculations and numbers should be tightened and generalized. The number that is guaranteed from the theorem is not strong enough.
  6. What if we do remasking such as ReMDM (Wang et al., 2025) or PRISM (Kim et al., 2026) or LLaDA 2.1 (Bie et al., 2026)? If the decoder can circumvent by remasking, this might not be a problem.
  7. The novelty compared with known adaptive vs. non-adaptive separations is unclear. What is technically new beyond applying this idea to masked generation?

(Wang et al., 2025) G. Wang, Y. Schiff, S. S. Sahoo, and V. Kuleshov. Remasking Discrete Diffusion Models with Inference-Time Scaling. NeurIPS, 2025. arXiv:2503.00307. (Kim et al., 2026) J. Kim, S. Kim, T. Lee, D. Z. Pan, H. Kim, S. Kakade, and S. Chen. Fine-Tuning Masked Diffusion for Provable Self-Correction. ICML, 2026. arXiv:2510.01384. (Bie et al., 2026) T. Bie, et al. LLaDA2.1: Speeding Up Text Diffusion via Token Editing. arXiv:2602.08676, 2026.

Reviewer_99RZOpenReview ↗
Rating
3(+1)
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates whether access to previously generated values is necessary for reducing the depth of parallel masked generation. The authors fix the target distribution and exact per-position conditional predictions, and vary only whether the scheduler can use generated values to select subsequent batches.

The main result constructs a family of pairwise-independent distributions over an alphabet of at most four symbols for which a content-adaptive policy samples exactly in three rounds, whereas every randomized value-oblivious schedule requires Ω(L/log⁡L)\Omega(L/\log L) rounds to achieve a fixed small total variation error. The paper further quantifies how much information about the hidden dependency structure must be reflected in scheduling actions and studies robustness to support-preserving prediction errors.

As a contrasting case, the authors show that predetermined batch sizes are optimal for uniform sampling without replacement and characterize the associated round–error tradeoff. Validation includes theoretical proofs, small-scale exact enumeration, rank checks for the redundant-tag construction, and scheduling experiments on randomly sampled hypermatchings.

Critical strengths

1. The central separation isolates a meaningful and nontrivial resource for parallel generation.

Both policy classes have access to the same target distribution and exact conditional predictions; only their use of generated values for batch selection differs. The lower bound covers arbitrary randomized value-oblivious schedules rather than a particular fixed ordering. The constant alphabet and unconditional pairwise independence further show that the separation cannot be attributed to a single large symbol or obvious pairwise dependence. This provides a compelling theoretical demonstration that hidden higher-order dependencies can determine parallel sampling depth.

2. The four-symbol construction and action-information bounds provide substantive technical content.

Splitting the hidden structure across ordinary coordinates allows schedules to interleave tag and payload observations, which makes the lower bound considerably less immediate. The redundant tags and pre-crossing guard address this difficulty. The action-cover bounds additionally explain that a fast policy need not recover the entire hidden route, but its batch choices must reflect enough information about that route. This strengthens the contribution beyond a qualitative example of an adaptivity advantage.

Critical weaknesses

1. The uniform-permutation analysis needs a clearer account of its incremental contribution relative to recent work.

The recent preprint by Wen, Liang, and Lu, Conditional Total Correlation and the Serial Depth of Adaptive Parallel Sampling, already establishes optimality of non-adaptive schedules under a hard round cap for uniform permutations, a dynamic program over batch sizes, and asymptotic characterizations in both fixed-round and linear-round regimes. Section 5 and Appendices H–I of the present paper overlap substantially with these results, but the manuscript does not currently provide a comparison. Related paper, Section IV-E

The treatment of general uniform injections q≥nq\ge n, randomized policies, the TV metric, and the limiting profiles of all exact optimal schedules may provide additional contributions, which should be explained individually. Since this is a preprint released close to the submission deadline, I do not regard its omission alone as grounds for rejection. However, until the relationship is clarified, I cannot credit the entire uniform-permutation analysis as an independently novel contribution. This concern does not undermine the central separation result in Section 4.

2. The comparison of six schedules provides limited additional evidence.

Section 6 and Appendix E compare round-robin, contiguous-block, and four randomly permuted schedules. For the tested parameters, they have identical numbers of groups assigned to each round and differ only in the assignment of group labels. Because the experimental routes are uniformly random perfect 3-uniform hypermatchings, relabeling vertices preserves the route distribution. Consequently, these schedules have identically distributed terminal-tie counts and safety probabilities.

Questions for authors

1. Clarification of the contribution. Please compare Proposition 5.1 and Theorems 5.2–5.3 individually with the corresponding results in the recent work mentioned above. Which conclusions follow from the existing permutation optimization problem and relationships between error metrics, and which require new proofs? In particular, what is added by randomized policies, q>nq>n, and convergence of optimal schedule profiles?

2. Clarification of the existing experiments. Under uniformly random hypermatchings, are the six balanced schedules indeed related by vertex relabeling and therefore identical in their population-level performance? If so, please explain what additional evidence their comparison provides and clarify whether the figures characterize the typical behavior of balanced configurations or the performance of schedules optimized for a fixed, known route table. Existing results involving different batch-size profiles or optimization for a fixed route table would strengthen my assessment of the experimental section.

Reviewer_rMBqOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The context of this paper is masked generators, models that generate text by progressively unmasking tokens and can act non-autoregressively. A typical example are text diffusion models.

The paper derives a number o mathematical results that allow to claim properties of such models, to some extent. These mathematical claims arise from a number of assumptions including

  • considering only two families of specifically crafted distributions. These distributions do not reflect the natural distribution of language and are more toy-like, but are crafted to reflect worst case scenarios

  • considering only parametrizations that predict each token independently of all others given a partially masked sequence i.e. they do not model joint distributions. This is the standard text diffusion setting.

  • considering perfect knowledge of the distribution per token and thus only exploring the effect of choosing which group positions to unmask at each time step

Given this conditions, the paper produces some interesting results such as

  • under certain distributions, a schedule fixed in advance will need far more rounds of generation than one that "reacts" to generates values. They also provide concrete results for a specific 4-symbol distribution

  • batch choices of any fast, accurate decoder must carry information about the hidden structure

  • it is possible to survive small prediction errors as long as we never put mass on impossible values

However, its is not straightforward to deduce how far reaching these results are and the paper could make a better work of clarifying this.

Critical strengths
  • The paper addresses a very active area of research such as masked generators, with implications for e.g. discrete diffusion and speculative decoding

  • It provides theoretical results that back intuitions about how these models can not predict the optimal actions ahead of time.

  • To the best of my knowledge results are correct and detailed.

Critical weaknesses
  • The paper is sometimes hard to follow. In particular it proves a number of results for specific distribution and model assumptions, but its hard to deduce from there what the real implications are for e.g. Diffusion models

  • It seems to me the chosen distributions only prove worst cases and they are very far away from real language. It would be interesting to see something closer to real world cases, even if just empirical.

Minor notes:

  • The "On a four-symbol target family where every pair of positions is independent" sounds as if this applies to all such distributions, it does not seem so.

  • Softmax always puts mass on impossible values

Questions for authors

"From Bits to Rounds: Parallel Decoding with Exploration for Diffusion Language Models" (arXiv:2511.21103, Nov 2025), seems related to Theorem 4.5 and Corollary 4.6.

The concept of "value-aware vs. value-oblivious" also appears in the "adaptivity-gap" literature i.e. Gupta, Nagarajan & Singla (arXiv:1608.00673) and the hard target resembles Boolean Hidden Matching (Gavinsky et al., arXiv:quant-ph/0611209).

Please indicate if you see any overlap with your work

Note also the contemporaneous Wen, Liang & Lu (arXiv:2608.25505)

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.