acceptodds
Under review as a conference paper at ICLR 2027

Sharp Accuracy Thresholds for Parallel Masked Sampling of Noisy Pairs

Abstract

How accurately must conditional heads be learned to preserve two-round generation of independent noisy pairs? We study masked samplers that select a batch, draw independently from the original heads, and permanently commit the values. For pairs, the critical total population excess-loss budget at fixed depth is for total variation (TV) accuracy . The heads are coherent: they are conditionals of one model, and the budget equals joint KL. Each pair has a fair representative and a mismatch bit; the model allows every positive exchangeable mismatch law independent of the representatives. A deterministic geometric schedule attains the threshold uniformly. A single model gives the converse against fully informed, randomized, value-adaptive policies. With logarithmically vanishing KL and uniformly vanishing head error, some models require expected rounds; a growing-depth upper matches this order for budgets with . The lower obstruction also survives heterogeneous representative biases. Within the fair exchangeable class, target-aware selection of sampled candidates instead yields vanishing TV in three rounds whenever the KL budget vanishes. abstract

Primary area:
learning theory
Keywords:
masked diffusion, learning theory, parallel sampling, lower bounds, conditional sampling

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 4 reviews, above 68% of the others.
Reviewer_WuCjOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper studies questions related to the accuracy of an efficient (parallel) sampling from masked diffusion models (MDM). In particular, the authors ask how large could be the total variation distance from the conditional distribution learned by "heads" of the model to the target one, so that the parallel sampling would still be accurate.

Critical strengths

I cannot identify any strengths of the work. It is written in an obscure, not self-containing way. I had to read the cited works just to get an idea of what the authors intended to do.

Critical weaknesses

The writing prevents to understand what is the problem, contribution and relation to prior works. In particular, the title, the first line of the abstract and the posed question contain "noisy pairs", which is not an established term and requires clarification. There is no explanation for the introduced notation in the background section, what is XX, what is the teacher PnP_n? What is "shallow parallel generation"?

Questions for authors

Could you formulate in your own words what is the problem you want to study, what is the contribution of the paper and how it relates to the previous works?

21 comments
AuthorsOpenReview ↗

【Part 1】 Rebuttal by Authors

We sincerely thank Reviewer WuCj for reviewing our manuscript and for identifying where the terminology, problem statement, and contribution were difficult to follow. We appreciate the opportunity to clarify these points. Your comments have prompted a substantial revision of the opening exposition. Below, we explain the setup directly and respond separately to the terminology questions, the research problem, the contribution, and the relation to prior work.

All page references below refer to the revised manuscript.


W1. The meaning of “noisy pairs” and the clarity of the title and abstract

R1: Thank you for pointing out that this shorthand needed an explanation. The construction is a pair of correlated bits: draw a fair bit AA, then obtain BB by flipping AA with probability 1/41/4. Both bits have fair marginals, but they disagree with probability 1/41/4. Drawing them independently instead makes them disagree with probability 1/21/2. Drawing AA first and then BB conditional on AA gives the exact joint distribution.

The revised title is “How Model Accuracy Limits Parallel Sampling in Masked Diffusion: Sharp Thresholds for Correlated Bit Pairs.” It identifies the field, sampling problem, and target family directly. The revised abstract starts by explaining parallel generation in masked diffusion, then describes the target in plain language. The Introduction gives the explicit two-bit example before introducing the theoretical question.

Manuscript changes: Title and abstract (p. 1); elementary example in Section 1 (p. 1); formal pair construction in Section 2, Eq. (2) (p. 2).

AuthorsOpenReview ↗

【Part 2】 Rebuttal by Authors

W2. The definitions of XX, the target PnP_n, and the conditional heads

R2: XX is the full random vector, and PnP_n is the distribution we want the sampler to generate. Specifically,

$ X=(A_1,B_1,\ldots,A_n,B_n), \qquad B_i=A_i\oplus E_i, $

where all Ai∼Ber⁡(1/2)A_i\sim\operatorname{Ber}(1/2) and Ei∼Ber⁡(1/4)E_i\sim\operatorname{Ber}(1/4) are mutually independent under PnP_n. Thus XX consists of nn independent copies of the pair described above. The main text now calls PnP_n the target distribution. The appendix explains “teacher” as a synonym for this target.

The supplied joint model is denoted by RnR_n. Its conditional prediction, or head, for a missing coordinate ii at visible context xSx_S is

$ q_{R,i}(a\mid x_S) =\Pr_{R_n}(X_i=a\mid X_S=x_S), \qquad a\in{0,1}. $

We call the predictions coherent because all these heads come from the same joint law RnR_n. The revised setup introduces the random vector and both distributions before stating their accuracy and sampling properties.

Manuscript changes: Target vector and law in Section 2, Eq. (2) (p. 2); explicit head formula in Section 2 (pp. 2–3); proof terminology in Appendix A (p. 16).

AuthorsOpenReview ↗

【Part 3】 Rebuttal by Authors

W3. The meaning of “shallow parallel generation”

R3: We mean generating the entire vector within a prescribed budget of KK sampling rounds. In each round, the sampler chooses a set of missing coordinates, draws their values independently from the supplied heads at the context visible at the start of that round, and keeps the generated values fixed. Later rounds may use those values to choose the next batch; its predictions are the original heads evaluated at the updated context.

The planner may know both PnP_n and RnR_n, use private randomness, and adapt to the revealed values. Its choice of positions precedes the new draws. These rules specify the sampling interface and the resource being measured. With the exact target heads, all first bits can be generated in one round and all second bits in another, so the target has an exact two-round sampler.

Manuscript changes: Two-round example in Section 1 (p. 1); formal execution rule in Definition 1, Section 2 (p. 3); an example of position selection using the current predictive distributions in Section 2 (p. 3).

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

The main result is as follows: suppose that your aim is to generate from a target distribution, under which a sequence of random variables (Ai),i=1,…,n∼Ber(12)(A_i), i=1,\ldots,n \sim Ber(\frac 12) and (Ei),i=1,…,n∼Ber(14)(E_i), {i=1,\ldots,n} \sim Ber(\frac 14) are i.i.d random variables which are mutually independent, and Bi=Ai⊕EiB_i = A_i \oplus E_i. Unfortunately, you instead have access to another law under which the AiA_i continue to remain independent but the joint law of the EiE_i only remains exchangeable, not independent. Your aim is to generate from the original law. However, you are only allowed up to KK rounds, where in each round you can generate some of the unrevealed coordinates, and any such path which decides how to reveal the EiE_i is called a policy.

The authors prove a minimax result concerning this: as the KL divergence threshold reduces and the number of coordinates grow (but the number of rounds is fixed), they show a very clean asymptotic sampling accuracy result in TV distance, demonstrating precisely when generation in KK rounds is possible for fixed KK.

Critical strengths

The result is extremely clean. To obtain minimax optimality at the asymptotic level even in this simple setting is a feat. The mathematics has been verified as correct, and the novelty is fairly high.

Critical weaknesses

The paper needs a very strong rewrite. It is highly, highly unclear what is going on at the very beginning. A number of terms are undefined in the introduction which are fairly technical and require much prior knowledge of the field. Some mathematical terms are also defined well prior to their usage, which is inappropriate.

The assumptions and scope can also be classified as weaknesses; arguably they reduce the informativeness of the models.

These concerns have been addressed significantly enough for my rating to increase

Questions for authors

My questions are as follows.

a) Your task has been done for a binary setup, under exchangeability assumptions, and assuming in fact that the coordinates are i.i.d. I think this kind of setup is too strong for the discussion about its limitations to be deferred completely to the appendix K. Some space is merited for why only this simple case is considered in the main body, even though Appendix K has a number of good results as well.

b) A number of technical terms and mathematical notation are used prior to their definition. For example, "We assume every head is an exact conditional of a common joint law RR. Such a model is coherent: serial conditional sampling generates RR, and small KL(P∥R)KL(P \| R) guarantees proximity to the target PP ." What is head is hasn't been defined, what a "model" is hasn't really been cleared up, and PP and RR come out of nowhere, because so far I don't even know yet that the setup is binary on nn coordinates.

There are a number of such errors in the introduction. �0��0� is introduced as a “conditional head,” without an explicit defining equation. The technical terms “Fresh,” “open,” “birth,” “co-sample,” “pilot,” and “teacher prefix” are introduced almost simultaneously in Section 2, and these come with vey little motivation. In the abstract itself, “Heads,” “coherent,” “exchangeable mismatch law,” and “population excess-loss budget” appear without an accessible explanation. I also think in Sections 3,4, key intuitions are scattered between the theorem statements, specialized constructions, and technical overview. It's disorganized.

c) No elementary example of why independently sampling conditional marginals changes the joint output law is present. This should help motivate the problem strongly.

d) The paper's appendix contains a number of results of which I find little to no mention in the main body. While I agree that they may not be separate subjects, it is worth linking them better to the main body, or avoiding them totally.

Some of these concerns have been addressed, and I will be moving towards a weak accept on this paper.

8 comments
AuthorsOpenReview ↗

【Part 1】 Rebuttal by Authors

We sincerely thank Reviewer fdEx for recognizing the technical achievement of the asymptotic minimax characterization, the clean form of the result, and its novelty. We also appreciate your assessment that the mathematics is correct. Your detailed comments on exposition and scope have been very helpful in improving the manuscript. We have substantially revised the opening, clarified the definitions, and explained the role and limitations of the model assumptions in the main text. Below, we respond separately to the two weaknesses and questions (a)–(d).


All page references below refer to the revised manuscript.

W1. Clarity of the opening and overall exposition

Response: Thank you for explaining where the original presentation was difficult to follow. We have reorganized the exposition to introduce the setting, a simple example, the research question, and the contributions before developing the technical mechanism.

The title now explicitly identifies parallel sampling in masked diffusion and the correlated-bit-pair setting. The abstract first describes the field and sampling problem, then gives a plain-language description of the target and model class. The Introduction illustrates the problem with one binary pair before introducing the supplied joint model and asking how much prediction error a fixed round budget can tolerate.

The contribution paragraph separates the matching fixed-round threshold, the growing-depth consequence, and the effect of target-aware screening. The main results section presents the threshold, an attaining schedule, and a hard model. The technical overview then follows a connected explanation: independent draws amplify a small predictive bias; a generated pilot changes later predictions; the ladder preserves a smaller residual bias; and stopped certificates make the argument uniform over adaptive policies. The upper-bound overview explains the comparison laws and the balance between successive batches.

Manuscript changes: Revised Title and abstract (p. 1) and Introduction, Section 1 (pp. 1–2); organized results in Section 3 (pp. 4–5); connected proof overview in Section 4 (pp. 5–7) and Figure 1 (p. 6).

AuthorsOpenReview ↗

【Part 2】 Rebuttal by Authors

W2. Restrictive assumptions and scope

Response: We agree that the assumptions are important to the interpretation of the result and should be visible in the main text. The sharp matching theorem remains a result for the coherent fair binary class with a positive finite-exchangeable mismatch law. We now explain this scope explicitly and distinguish it from the broader lower-bound extensions.

The simple target provides an exact two-round reference. This lets us quantify the additional execution depth caused by inaccurate predictions while keeping the target's baseline sampling difficulty fixed. The model can introduce dependence between different pairs through its mismatch law. Within this class, the matching theorem determines the accuracy budget required even when each model receives its own fully informed, randomized, adaptive planner.

The extensions show that the lower-bound mechanism also applies to heterogeneous biased endpoints and to finite-alphabet models, including nonexchangeable examples. The fixed-depth exponent for a prescribed non-fair bias law remains unresolved, as does a matching upper bound for the finite-alphabet extension. These limitations are stated alongside the extensions in the main text.

Manuscript changes: Model motivation in “Why study this model?”, Section 2 (p. 3); extensions and their limits in Section 6 (pp. 8–9); “Scope and limitations” in Section 8 (pp. 10–11). Question (a) below gives the specific roles of the assumptions and the corresponding extensions.

AuthorsOpenReview ↗

【Part 3】 Rebuttal by Authors

a. Why focus on this model, and why should its limitations be discussed in the main text?

Response: Thank you for this suggestion. The main text now explains both why the model permits a sharp characterization and how far the lower-bound phenomenon extends beyond it. The assumptions serve the following roles:

  • Independent target pairs provide a known sampling baseline. The two endpoints within each pair are correlated. Independence is across target pairs, which allows exact generation of all first endpoints followed by all second endpoints. This isolates the cost of executing imperfect predictions.
  • Coherence links prediction accuracy to a joint distribution. All supplied heads are conditionals of one model law. Serial sampling reproduces that law, and the population loss equals the target-to-model joint KL divergence.
  • Exchangeability supports the matching upper proof. The model's mismatch law may have arbitrary dependence subject to pair symmetry; it need not be i.i.d. or a mixture of product laws. Symmetry allows the upper proof to group configurations by their total mismatch count and control their conditional predictions.

The main text also introduces two substantive extensions:

  1. Heterogeneous biased endpoints. The lower bound allows arbitrary known biases ai∈(0,1)a_i\in(0,1), which may differ across pairs. Singleton observations can then reveal information about the model's mixture component, so the proof accounts for both the first observation and completion of a pair. The growing-depth separation survives. For a prescribed non-fair bias law, the current fixed-depth upper and lower exponents do not match.

  2. Finite alphabets and nonexchangeable instances. The structural extension allows nonuniform singleton marginals and pair-dependent interactions. It includes explicit three-valued examples and heterogeneous strengths for which both the target and coherent model are nonexchangeable. The lower bound still covers every allowed randomized adaptive policy, under the stated conditions that ensure a uniformly detectable response in either reveal order and bounded score fluctuations. A matching upper bound over this enlarged class remains open.

These extensions retain independence across target pairs. Extending the sharp characterization to targets with dependence between pairs is a further question.

Manuscript changes: Assumption roles in Section 2 (p. 3); biased result in Theorem 6, Section 6 (pp. 8–9) and Appendix E (pp. 23–26); an explicit main-text statement of the nonexchangeable finite-alphabet extension in Section 6 (p. 9), marked in burgundy; structural theorem and examples in Theorem 10, Appendix F (pp. 26–28), with the heterogeneous nonexchangeable instance on p. 28; remaining scope in Section 8 (pp. 10–11).

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

This paper studies how accurately a masked diffusion model must be learned to generate good samples in a small number of parallel rounds (K). To isolate the effect of model error from the difficulty of the target distribution itself, the authors analyze a simple target distribution of n independent noisy binary pairs (A_i, B_i) that can be generated perfectly in K = 2 parallel rounds if the model's single-token prediction heads are exact. They consider "coherent" models where all conditional heads come from a single valid joint distribution R within a total training loss budget KL(P || R) <= B under standard parallel samplers that select a batch of tokens, sample them independently from their heads, and permanently commit the values. The paper's main result is a sharp minimax threshold: to guarantee accurate generation in K >= 2 rounds, the total KL error B must shrink with sequence length n as Theta(n^(-1 / (2(K - 1)))). If B is larger than this threshold, a single adversarial model forces every adaptive, randomized K-round policy to fail completely (TV -> 1), whereas if B is smaller, a simple deterministic geometric batch schedule succeeds uniformly. Consequently, even when a model's total KL loss and per-head errors vanish logarithmically as n -> infinity, parallel sampling can require Theta(log n / log log n) rounds, unless the sampler is allowed to inspect and filter proposed candidate tokens before committing them.

Critical strengths
  • Interesting and somewhat surprising result: Shows that even a coherent model whose total KL loss, joint TV error, and single-token head errors all vanish as sequence length n grows can still require Omega(log n / log log n) parallel rounds (or error budget B << n^(-1 / (2(K - 1))) at fixed depth K) to avoid complete sampling failure.
Critical weaknesses
  • Appendix is too long and paper writeup is too dense.
  • Not particularly sure if the result has any practical value
Questions for authors

Does this still hold for confidence top-k selection or methods that allow for remasking?

5 comments
AuthorsOpenReview ↗

【Part 1】 Rebuttal by Authors

We sincerely thank Reviewer R6xY for recognizing the interesting and surprising separation between vanishing joint KL, joint TV, and individual prediction errors, and the growing number of rounds required for accurate parallel sampling. We also appreciate your positive assessment of the paper's soundness. Your comments have helped us make the presentation more accessible and clarify the implications for sampler design. Below, we respond to both weaknesses and address confidence top-kk selection and remasking separately.

All page references below refer to the revised manuscript.


W1. Length of the appendix and density of the presentation

R1: Thank you for pointing out the difficulty of following the original exposition. We have reorganized the opening around an elementary example, the research question, and the main contributions, and made the proof mechanism easier to follow in the main text.

The revision makes the following changes:

  • An example before the formal setup. The Introduction now introduces a simple example: a fair bit AA and a bit BB obtained by flipping AA with probability 1/41/4. Independently drawing the two fair marginals changes their disagreement probability to 1/21/2, whereas drawing AA and then BB conditional on AA is exact. This explains both the problem with independent parallel draws and the target's two-round baseline before introducing the main theorem.
  • Explicit definitions and a clearer contribution statement. The abstract identifies masked diffusion as the setting, and the Introduction distinguishes the fixed-round accuracy threshold, the growing-depth consequence, and the three-round screening result. The model section explicitly defines the conditional heads and execution rules before stating the minimax result.
  • A connected explanation of the proof. The technical overview follows the progression from a small predictive bias, to a generated pilot, to the ladder and its stopped certificates. Figure 1 (p. 6) illustrates the pair structure and posterior feedback. The upper-bound overview explains the comparison with a target-distributed pilot and how the batch sizes balance the resulting errors.

We have retained the complete proofs and supporting analyses, while adding an appendix contents page and explicit links from the main text. A direct route through the fixed-round result is Sections 2–4 (pp. 2–7), followed by the proofs in Appendices A–D (pp. 16–23). The extensions and numerical analyses are grouped separately, so readers can locate the material relevant to a particular question.

Manuscript changes: Title and abstract (p. 1); Introduction, Section 1 (pp. 1–2); explicit setup in Section 2 (pp. 2–4); proof overview in Section 4 (pp. 5–7) and Figure 1 (p. 6); Appendix contents (pp. 14–15).

AuthorsOpenReview ↗

【Part 2】 Rebuttal by Authors

W2. Practical value of the results

R2: We appreciate the opportunity to clarify this point. The implication for sampler design is that prediction accuracy and confidence-based position ordering alone do not guarantee accurate generation in a few rounds under the stated execution rule. How generated values are retained as context is another consequential design choice.

The target itself admits exact two-round sampling. This lets us isolate the additional depth caused by executing imperfect conditional predictions. Within the coherent fair exchangeable model class, for each fixed K≥2K\ge2 and output-TV tolerance ε∈(0,1)\varepsilon\in(0,1), the fixed-round theorem determines the accuracy budget needed for reliable generation:

$ B^*{n,K}(\varepsilon) =\Theta{K,\varepsilon}!\left(n^{-1/[2(K-1)]}\right). $

The lower bound already allows a planner that knows both the target and model, randomizes, and adapts its batches to previously generated values. Thus, at budgets asymptotically larger than the critical scale, improving position priorities cannot provide a uniform solution throughout the model class. This gives a quantitative constraint on what scheduling alone can achieve.

The screening result identifies an operation that changes this constraint. Retaining candidates with a target-aware calibration rule produces a target-distributed pilot, conditional on enough acceptances, and enables vanishing output error in three rounds on the same hard model sequences. The comparison suggests evaluating the joint output law and the distribution of retained context alongside prediction loss when designing parallel decoders.

The finite-dimensional results provide a complementary check of the execution cost. For each of nine selected coherent models, a feasible four-round policy has smaller TV error than every allowed three-round policy, certified by L3>U4L_3>U_4. For example, at n=16n=16 pairs and total KL budget B=0.10B=0.10, the optimal three- and four-round errors are approximately 0.18320.1832 and 0.17810.1781, respectively. These certify a finite-depth separation for the selected models.

Manuscript changes: Added the paragraph “Implications for sampler design” in Section 1.1 (p. 2), marked in burgundy; connected the interpretation to the certified results in Section 7 (pp. 9–10) and Figure 2 (p. 10); clarified the sampling-interface implications in the new Appendix O (pp. 57–58). The model scope is discussed in Section 8 (pp. 10–11).

AuthorsOpenReview ↗

【Part 3】 Rebuttal by Authors

Q1. Does the lower bound cover confidence top-kk selection?

R3: Thank you for raising this question. Yes, for position selection based on the current predictive distributions before drawing the new values, provided the selected values are independently sampled from the original heads and committed irreversibly. We now distinguish this operation explicitly from filtering already sampled candidates.

  1. Confidence-based position selection. Given the current visible context xSx_S, a policy may rank positions by max⁡aqi(a∣xS)\max_a q_i(a\mid x_S), entropy, or another statistic of the current heads. It may choose the batch size adaptively and randomize its tie-breaking. If it then samples the chosen positions independently from the original heads, keeps those values fixed, and completes within the round budget, it belongs to Definition 1 (p. 3). Our all-policy lower bound therefore covers it under the theorem's model assumptions.

  2. Confidence-based candidate retention. If the decoder first draws candidates x^i\widehat x_i and ranks their realized probabilities qi(x^i∣xS)q_i(\widehat x_i\mid x_S), the retained positions depend on the new values. This uses a larger execution interface. Argmax decisions and temperature transformations also change the original sampling law and require separate treatment.

To make the second case concrete, we added Proposition 16 (p. 57), showing that a specified candidate-confidence filter can fail even when the model and all its heads are exact. Set Rn=PnR_n=P_n and take even nn. First generate all AiA_i. Next propose all BiB_i from their exact heads and retain the n/2n/2 candidates with the highest realized probabilities. Finally, draw the discarded second endpoints afresh from their exact heads. The resulting output law satisfies

$ \operatorname{TV}(P_n,Q_{\mathrm{conf}}) \ge \left[1-e^{-n/8}-e^{-n/64}-e^{-n/128}\right]_+ \longrightarrow 1. $

The mechanism is simple: matching candidates have confidence 3/43/4, while mismatching candidates have confidence 1/41/4. With probability at least 1−e−n/81-e^{-n/8}, the retained half contains no mismatches. Conditional on this event, the final mismatch count has mean n/8n/8, whereas the target mean is n/4n/4. A count test distinguishes the delivered distributions.

This is a counterexample for that particular retention rule. At Rn=PnR_n=P_n, the exact two-round sampler still succeeds. The example shows why confidence-based retention needs its own analysis: preferring individually likely values can bias the retained context even with zero prediction error.

Manuscript changes: Explicit interface distinction in the new Appendix O.1 (p. 57); complete three-round procedure and Proposition 16 (p. 57) with its proof in Appendix O.2 (pp. 57–58); corresponding pointers in Section 2 (p. 3) and Section 8 (p. 11).

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

This paper studies how accurately conditional models must be learned to support reliable parallel masked sampling with a limited number of generation rounds.

Critical strengths
  1. The paper establishes matching accuracy-budget exponents for fixed-round parallel sampling within its defined oracle class. The converse covers fully informed, randomized, and value-adaptive policies, making the theoretical characterization particularly meaningful.

  2. The paper carefully examines the sampling interface through heterogeneous extensions, certified finite-dimensional experiments, and an analysis showing how target-aware candidate selection changes the depth requirement. These results help explain the mechanisms behind the sampling obstruction.

Critical weaknesses
  1. The sharp threshold applies to noisy-pair targets with coherent conditional heads and exchangeable mismatch laws, under independent sampling and irreversible commitment. The paper explicitly discusses these restrictions and provides some extensions, but the implications for learned models with incoherent heads or samplers using remasking remain uncertain. This limits the immediate applicability of the results.

  2. The finite-dimensional experiments certify execution-depth penalties but do not directly establish the predicted minimax scaling. Appendix G.1 illustrates that one unoptimized parameter choice yields an informative explicit lower bound only at an extremely large dimension. The certified policy optima cover small instances, while the larger-dimensional diagnostics concern selected policies. Thus, the dimensions and constants at which the asymptotic threshold becomes quantitatively useful remain unclear.

Questions for authors

Q1. Section 2 gives a select-before-sample example, and Appendix K analyzes target-aware candidate selection. Beyond these cases, which conclusions might remain valid under approximate head coherence or limited remasking, and which proof steps fundamentally require the current assumptions?

Q2. Could the authors optimize the finite-bound constants or provide additional dimension-dependent bounds that connect the certified small-instance results with the asymptotic exponent? Such results would clarify when the threshold becomes quantitatively informative.

10 comments
AuthorsOpenReview ↗

【Part 1】 Rebuttal by Authors

We sincerely thank Reviewer hiK2 for recognizing the matching accuracy-budget exponents, the breadth of the converse for fully informed randomized adaptive policies, and the analyses that explain the sampling obstruction. We appreciate the questions about scope and finite-dimensional relevance. Below, we respond separately to W1, W2, Q1, and Q2.


[W1] Scope of the sampling guarantee and its extension to approximately coherent heads and charged remasking

R1: We sincerely thank the reviewer for recognizing the matching exponents and the scope of the all-policy converse, and for asking us to clarify what survives beyond exact coherence and irreversible execution. The revision now gives quantitative results for both changes, including matching bounds for a growing total remasking budget. We have collected the new statements, complete proofs, and numerical certificates in a standalone appendix at the end of the paper.

First, the lower bound extends to genuinely interleaved remasking. A policy can erase previously generated values between draw rounds, remember those values, and adapt its subsequent actions to its entire history. Every erased endpoint, including a discarded candidate, is charged to a total budget hh. For every fixed K≥2K\ge2, fixed TV tolerance ε∈(0,1)\varepsilon\in(0,1), and h=o(n)h=o(\sqrt n), we prove $ B^*{n,K,h}(\varepsilon) =\Theta{K,\varepsilon}!\left( \left(\frac{(h+1)^2}{n}\right)^{1/[2(K-1)]} \right). $ The upper bound holds throughout the entire positive finite-exchangeable reference class, and the converse uses one model that defeats every allowed randomized, history-adaptive policy. Thus limited remasking improves the admissible accuracy budget by a precisely quantified amount without eliminating the obstruction. The fixed-tolerance order also holds for an expected erasure budget H=o(n)H=o(\sqrt n). See Appendix P.1 (p. 59) and Appendix P.2 (pp. 59–63).

Second, exact coherence of the supplied predictions is unnecessary. Their distance from a coherent reference can be at most η\eta at every partial context, while the supplied table itself may be incoherent and label-dependent. A new upper bound for the full reference class incurs an additional OK(n η)O_K(\sqrt n\,\eta) error; the hard-witness lower bound has the same stability scale. Consequently, when η=o(n−1/2)\eta=o(n^{-1/2}), these perturbations contribute o(1)o(1) to the error bounds and the coherent accuracy-threshold order remains sharp. We also give a weaker alternative based on local quadratic errors and explicit coverage of the query distributions used in the proof. The reference model is known to the planner, and BB constrains its joint KL; these hypotheses do not follow from an arbitrary average training loss. See Appendix P.3 (pp. 63–65).

Finally, substantial remasking can remove the obstruction. We give an exact two-round reset with expected cost nn erased endpoints. This works even beyond exchangeable mismatch laws, and nn is the sharp worst-case expected cost over the unrestricted reference class, rather than a necessary cost for every model. This supplies a constructive boundary to the lower bound. See Appendix P.4 (pp. 65–66).

The fair independent representatives, iid target mismatches, and frozen independent draw interface remain assumptions of the matching theorem. The full tradeoff for n≲h≪n\sqrt n\lesssim h\ll n remains open. We make these remaining restrictions explicit in Appendix P.6 (p. 69). The precise hypotheses and proof dependencies are detailed in our separate response to Q1.

AuthorsOpenReview ↗

【Part 2】 Rebuttal by Authors

[W2] Finite-dimensional minimax guarantees and the scale at which the obstruction is certified

R2: We thank the reviewer for distinguishing the asymptotic minimax theorem from the evidence supplied by selected-policy experiments. We have added full-class finite minimax intervals and all-policy certificates at moderate dimensions. These address the finite-scale question directly, while keeping the remaining uncertainty about the asymptotic crossover explicit.

1. Certified finite minimax intervals. For three rounds, no erasures, and output-TV tolerance 0.10.1, the new certificates establish

Number of pairs nnCertified interval for Bn,3,0∗(0.1)B^*_{n,3,0}(0.1)
8[0.03020, 0.03064][0.03020,\ 0.03064]
12[0.02900, 0.03034][0.02900,\ 0.03034]
16[0.02740, 0.03028][0.02740,\ 0.03028]

The safe endpoint covers every positive exchangeable mismatch law in the stated KL class. We prove support inequalities for the model's first two mismatch moments, cover the entire resulting polygon, and certify a feasible three-round policy on every cell. The independent verifier checks all support inequalities and all 1,9281{,}928, 3,6263{,}626, and 5,4775{,}477 cover leaves, respectively. The failing endpoint comes from one admissible model and a terminal-test Bellman certificate over every allowed action. Thus the two sides have the required minimax quantifiers. The failing models themselves have joint TV below 0.10.1. See Appendix P.5.1, pp. 67–68; Proposition 29 and Table 11.

2. All-policy failure is also certified at moderate dimensions. We prove a count-recursion reduction for nondecreasing tests under explicitly verified head conditions. With joint KL at most 0.10.1, it gives the following downward-rounded lower bounds for every allowed three-round policy:

Number of pairs nnModel joint TV, roundedAll-policy output TV ≥\ge
1280.09620.1145
2560.09760.1153
5120.09900.1103

The exact model TV is below 0.10.1 in all three rows. These are certificates against all allowed randomized adaptive policies, not measurements of selected decoders. The reduction is proved analytically and checked against full recursions; integer rounding is directed throughout. See Appendix P.5.2, p. 68; Proposition 30 and Table 12. The dimension–budget–family grid, corrected 512512-pair input, and verification arithmetic are specified in Appendix P.5.3, p. 69. We evaluated 30 rational models with 90 terminal tests and report representative certificates in the table.

3. What these calculations establish. The finite brackets give a quantitative guarantee for the original minimax problem at specified dimensions. The moderate-dimensional witnesses show an additional execution cost even when the joint model is already within the desired TV tolerance. We agree that neither observation establishes the onset of the asymptotic n−1/4n^{-1/4} exponent. The new witnesses do not make the constants in the original displayed ladder inequality sharp, and the models used in the finite certificates are not asserted to optimize the outer minimax objective.

Manuscript changes. The new core statements, complete proofs, representative certificates, and numerical settings are collected in Appendix P, pp. 59–69, with new material marked in burgundy. The original 58 pages and their references are preserved. Our response to Q2 details the certification methods and the remaining gap between finite-dimensional guarantees and the asymptotic scaling regime.

AuthorsOpenReview ↗

【Part 3】 Rebuttal by Authors

[Q1] What survives approximate coherence and interleaved remasking, and which assumptions enter the proofs?

R3: Thank you for this precise question. We now prove robustness to potentially incoherent supplied heads and a matching accuracy–erasure tradeoff for interleaved remasking. We distinguish these extensions from the large-budget reset, which shows why an unrestricted remasking lower bound cannot hold.

1. Approximate coherence: a full-class upper bound and a stable converse.

Let RR be a positive exchangeable reference model satisfying KL(Pn∥Rn)≤B\mathrm{KL}(P_n\Vert R_n)\le B. Suppose the supplied table q~\widetilde q satisfies

\operatorname{TV}\!\left( \widetilde q_i(\cdot\mid x_O),q_{R,i}(\cdot\mid x_O) \right)\le\eta.$$ **The table $\widetilde q$ need not be compatible with any joint distribution.** It can depend on coordinate labels and all currently visible values. The planner is given $R$ and keeps the reference-designed policy $\pi_R$ fixed when the supplied table is perturbed. Write $K=r+1$. Under the finite parameter conditions stated in the appendix, the new guarantee is $$\operatorname{TV}(P_n,Q_{\widetilde q}^{\pi_R}) \le F_{n,r,c,t}(B) +\left(2+\sqrt{\frac{8r}{3}}\right)\sqrt n\,\eta,$$ where $F_{n,r,c,t}(B)$ is the explicit coherent-reference upper bound, including initialization failure and retained-prefix costs. This estimate holds **uniformly over the full reference class**, without a lower bound on its conditional probabilities. The proof compares the perturbed product batches directly with target product kernels. It does not assume the perturbed output remains exchangeable or claim a general $O(\sqrt n\eta)$ distance between arbitrary coherent and perturbed execution laws. For the hard ladder references, whose heads do have a uniform probability floor, a separate transcript comparison gives $$\operatorname{TV}(Q_{\widetilde q}^{\pi},Q_R^{\pi}) \le \sqrt{\frac{8(2n+h)}3}\,\eta$$ for every allowed policy with at most $h$ erased endpoints. Subtracting this term from the new coherent lower bound proves stability of the converse. Thus **$\eta=o(n^{-1/2})$ preserves both sides of the matching result when $h=o(\sqrt n)$.** The $n^{-1/2}$ perturbation scale is also necessary up to constants: even with reference $R=P$, a supplied table within a larger uniform radius can force output TV to one when $\sqrt n\eta\to\infty$ and $h=o(\sqrt n)$. Here **$B$ is the reference joint-KL budget**, not a joint KL assigned to an incoherent learned table. For perturbations of the ladder witnesses, the original total population loss also satisfies $$D(\widetilde q)\le\frac{64}{7}D(q_R)+\frac{256}{7}n\eta^2, \qquad \eta\le\frac18.$$ Thus $\eta=o(n^{-1/2})$ preserves vanishing population loss whenever the reference-witness loss vanishes. To preserve a population-loss budget of order $B_n$ when $D(q_R)=O(B_n)$, one additionally needs $n\eta_n^2=O(B_n)$. A weaker sufficient condition replaces the uniform radius by local squared errors $L_0,L_1,\ldots,L_r$ under the initialization and target-prefix hybrid query laws: $$\operatorname{TV}(P_n,Q_{\widetilde q}^{\pi_R}) \le F_{n,r,c,t}(B)+\sqrt{2L_0} +\sqrt{\frac83}\sum_{\ell=1}^{r}\sqrt{L_\ell}.$$ An explicit density-ratio coverage condition transfers these errors from a training-query distribution. Class-uniform guarantees require uniform control of those coverage constants; small average training loss alone is insufficient. All statements and proofs are in `Appendix P.3 (pp. 63–65)`.

Comments on the paper

4 comments
AuthorsOpenReview ↗

【Part 1】General Response

We sincerely thank all four reviewers for their time, careful reading, and constructive feedback. We appreciate the recognition of the minimax characterization and the breadth of the converse, together with the requests for clearer exposition, a better account of the assumptions, and more informative finite-dimensional guarantees. Below, we summarize the main concerns and the corresponding revisions and additional results.

All locations refer to the revised manuscript. Substantive changes are marked in burgundy.

1. Clarity of the problem, definitions, and proof organization (Reviewers WuCj, fdEx, and R6xY)

Concern: The organization of the paper.

Response: We have reorganized the opening around the setting, an elementary example, the research question, and the contributions. The Introduction first explains a correlated binary pair: independently drawing its fair marginals changes its disagreement probability from 1/41/4 to 1/21/2, while sequential conditional sampling is exact. Section 2 then defines the target vector and law, the joint model, each conditional head, the loss normalization, and the execution rule. Section 3 separates the theorem from its attaining schedule and hard model; Section 4 develops the pilot, posterior ladder, stopped certificates, and upper-bound comparison in sequence. Figure 1 illustrates the mechanism.

We have also added appendix navigation and explicit main-text pointers. Readers can follow the fixed-round argument through Sections 2–4, pp. 2–7, then its proofs in Appendices A–D, pp. 16–23; the extensions and numerical analyses are grouped separately. The additional results are consolidated in Appendix P, pp. 59–69.

Locations: Title, abstract, and Section 1, pp. 1–2; Section 2, pp. 2–4, including Definition 1 on p. 3; Sections 3–4, pp. 4–7; Figure 1, p. 6; Appendix contents, pp. 14–15.

2. The contribution, its relation to prior work, and its significance for sampler design (Reviewers WuCj and R6xY)

Concern: The research problem, contribution, relationship to prior work, and practical meaning needed a clearer explanation.

Response: The contribution is a sharp population-accuracy requirement for parallel sampling near a target with a known two-round sampler. For each fixed K≥2K\ge2 and output-TV tolerance, Theorem 2 identifies the critical joint-KL budget as order n−1/[2(K−1)]n^{-1/[2(K-1)]}. One geometric schedule gives the uniform upper guarantee; one hard model sequence defeats every allowed fully informed, randomized, value-adaptive policy above the critical scale. The known easy target isolates the extra depth caused by executing imperfect predictions.

This gives a quantitative constraint on what position ordering alone can guarantee. Target-aware screening, using known target probabilities, shows how calibrating retained context can change the depth requirement. We explain these implications in the Introduction and distinguish our known-target accuracy-radius question from unknown-target query lower bounds and deterministic-policy analyses under output KL. Direct quantitative guarantees for trained language models remain outside the established scope.

Locations: Section 1.1, p. 2; Theorem 2, p. 4; Corollary 5, p. 8; Section 8, pp. 10–11; Appendix K.1, Theorem 12, pp. 48–49; Appendix M.1–M.2, pp. 51–52.

AuthorsOpenReview ↗

【Part 2】General Response

3. Structural assumptions and approximately coherent learned predictions (Reviewers fdEx and hiK2)

Concern: The binary, coherence, and exchangeability assumptions restrict applicability; their roles and the implications for incoherent learned heads needed to be explained.

Response: The main text now explains why the simple target permits a sharp characterization and identifies what the assumptions supply. Independence is across target pairs; the two endpoints within each pair are correlated. The reference model's mismatch law can have arbitrary dependence consistent with finite exchangeability. Section 6 also presents heterogeneous-bias and finite-alphabet lower-bound extensions, including nonexchangeable examples, with their remaining matching-bound limitations stated explicitly.

The additional analysis allows the supplied heads themselves to be incoherent and label-dependent. If they are uniformly within TV η\eta of the heads of a known coherent reference in the stated class, the full-class upper bound gains only OK(nη)O_K(\sqrt n\eta); the hard-witness converse is stable at the same scale. For the irreversible interface, the n−1/2n^{-1/2} perturbation scale is also necessary up to constants, even with the reference equal to the target. We also give a sufficient condition based on local squared errors and explicit query coverage. The joint-KL budget constrains the reference law; these hypotheses make precise what is required beyond an average training-error claim.

Locations: Model motivation in Section 2, p. 3; extensions in Section 6, pp. 8–9 and Appendices E–F, pp. 23–28; robustness and coverage in Appendix P.3, pp. 63–65, Theorems 24 and 26 and Proposition 25; scope in Section 8, pp. 10–11 and Appendix P.6, p. 69.

4. Confidence top-kk selection and remasking (Reviewers R6xY and hiK2)

Concern: Do the conclusions survive confidence-based selection or revision of previously generated values?

Response: Confidence-based position selection before drawing is covered by the original policy class, when followed by independent draws from the unmodified heads and irreversible commitment. Ranking already realized candidates uses a different interface. We make this distinction explicit and give a counterexample for one specified candidate-confidence retention rule even with exact heads. Target-aware calibrated screening has a separate three-round guarantee.

We have further extended the theory to charged erasures interleaved with generation. Every discarded endpoint is charged, including repeated deletions; policies can remember erased values and adapt to their entire history. For fixed K≥2K\ge2, fixed tolerance ε∈(0,1)\varepsilon\in(0,1), and total erasure budgets h=o(n)h=o(\sqrt n), we prove

=\Theta_{K,\varepsilon}\left( \left(\frac{(h+1)^2}{n}\right)^{1/[2(K-1)]} \right).$$ The upper bound covers the whole positive finite-exchangeable reference class; the converse covers all allowed randomized adaptive policies. The fixed-tolerance order also extends to an expected erasure budget $H=o(\sqrt n)$. At the large-budget endpoint, an exact two-round reset works for arbitrary positive mismatch laws independent of the fair representatives, with expected cost $n$ and pathwise cost at most $2n$ erased endpoints. The expected cost is worst-case optimal for exact sampling over that unrestricted class. These results strengthen the remasking discussion in our earlier responses. **Locations:** Confidence-selection distinction and counterexample in `Appendix O, pp. 57–58, Proposition 16`; screening in `Appendix K.1, pp. 48–49`; interleaved-erasure interface and matching bounds in `Appendices P.1–P.2, pp. 59–63, Theorem 17`; reset and resource bounds in `Appendix P.4, pp. 65–66, Theorem 27 and Proposition 28`.
AuthorsOpenReview ↗

【Part 3】General Response

5. Finite-dimensional usefulness and evidence beyond selected schedules (hiK2; practical relevance raised by R6xY)

Concern: Small-instance depth gaps and larger-dimensional selected-policy diagnostics did not establish when the minimax threshold becomes quantitatively informative.

Response: The new calculations include two-sided certificates for the actual three-round critical budget, with no erasures and output-TV tolerance 0.10.1:

Number of pairsCertified critical KL-budget interval
8[0.03020, 0.03064]
12[0.02900, 0.03034]
16[0.02740, 0.03028]

The safe endpoint gives a guarantee throughout the model class via a complete moment cover. The failing endpoint uses an admissible model and a terminal-test certificate against every allowed policy. We prove a scalable recursion, with hypotheses checked for each witness, and certify three-round output-TV lower bounds of 0.11450.1145, 0.11530.1153, and 0.11030.1103 at 128128, 256256, and 512512 pairs, respectively. Each corresponding model has joint TV below 0.10.1 and joint KL at most 0.10.1. These are bounds against every allowed three-round policy. The appendix specifies rational inputs, directed rounding, error bounds, and independent checks; the study comprises 30 models and 90 tested thresholds.

The results give finite minimax guarantees and certify an additional execution cost at hundreds of pairs. They leave the onset of the asymptotic exponent and optimal crossover constants unresolved.

Locations: Existing depth certificates in Section 7, pp. 9–10; full-class budget intervals in Appendix P.5.1, pp. 67–68, Proposition 29 and Table 11; moderate-dimensional certificates in Appendix P.5.2, p. 68, Proposition 30 and Table 12; inputs and verification in Appendix P.5.3, p. 69.

Remaining scope. The matching results retain the stated reference and target assumptions. The intermediate erasure regime n≲h≪n\sqrt n\lesssim h\ll n, general nonexchangeable or dependent-target matching results, and guarantees from ordinary average training loss without coverage remain open. These boundaries are explicit in Appendix P.6, p. 69.

We sincerely appreciate the reviewers' feedback and the opportunity to strengthen the paper. We hope that the revised presentation and additional results address the concerns above, and would be grateful for any further questions or suggestions.

Best regards,

The authors of Submission19157

AuthorsOpenReview ↗

General Response: Revisions to the Paper’s Structure

Dear Reviewers,

We sincerely thank all reviewers for your time and feedback on the presentation of our paper. Your comments prompted us to substantially revise the exposition throughout the main text and reorganize the supporting appendices to make the complete argument clearer and easier to follow. Below, we summarize these revisions. All locations refer to the current manuscript.

  • A problem-first opening and clearer definitions. The title, abstract, and Introduction now explain the masked-diffusion setting, introduce an elementary two-bit example, and state the research question and contributions before the technical development. The model section introduces the target, supplied model, conditional predictions, loss normalization, and execution rule in sequence. See Title, abstract, and Section 1 (pp. 1–2) and Section 2 (pp. 2–4).

  • A clearer progression from results to proof ideas. The main-result section presents the sharp threshold, the attaining schedule, and the hard model in order. The technical overview then develops the lower- and upper-bound arguments separately, explaining how generated values affect later predictions and how the batch sizes are chosen. The mechanism is illustrated in Figure 1 (p. 6). See Sections 3–4 (pp. 4–7).

  • Consequences and assumptions explained alongside the results. We clarify the growing-depth and expected-round consequences, explain the changes needed for biased endpoints, and describe the finite-alphabet extensions together with their remaining matching-bound limitations. See Sections 5–6 (pp. 7–9).

  • Clearer interpretation of numerical evidence and scope. The numerical discussion distinguishes certified depth separations from diagnostics for selected policies. The discussion explains the sampler-design implications, the relationship to prior work, and the model’s assumptions and limitations. See Sections 7–8 (pp. 9–11).

  • Better navigation of the supporting material. We added appendix contents on pp. 14–15 and explicit main-text pointers to the complete proofs and supplementary studies. The fixed-round proofs are grouped in Appendices A–D (pp. 16–23); confidence selection and remasking are discussed together in Appendix O (pp. 57–58); the additional robustness and finite-dimensional analyses are consolidated in Appendix P (pp. 59–69).

These revisions address the structure and readability of the full manuscript, including the later sections and supporting analyses. Selected substantive revisions are marked in burgundy.

We are grateful to all reviewers for helping us improve the manuscript. We hope these changes make the results, their interpretation, and the supporting arguments easier to assess, and we would sincerely welcome any further questions or suggestions.

Best regards,
The authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.