acceptodds
Under review as a conference paper at ICLR 2027

Counterfactual Probing for Parallel Unmasking with Hidden Forest Structure

Abstract

Masked generative models offer parallel token prediction, but accurate parallel sampling must account for dependencies among tokens. When these dependencies are unknown, discovering which tokens can be generated together also requires model evaluations. We study whether both total oracle evaluations and sequential sampling depth can be sublinear in the sequence length \(N\), even after accounting for this discovery cost. We consider discrete distributions with hidden forest structure, accessed through a fixed approximate conditional oracle. Under explicit regularity conditions and uniform Hellinger error bounds on the oracle conditionals, our sampler achieves vanishing expected total-variation error with both masked-state submissions and sequential depth bounded by \(O(N^C)\), for some constant \(0<C<1\). These guarantees hold in a regime where the alphabet size scales polynomially with \(N\). The sampler probes hypothetical reveals to decide which tokens to generate together, sharing masked-state evaluations across many dependence tests. This enables parallel generation without requiring full recovery of the hidden forest. A tunable parameter trades probing cost against irreversible commit rounds. We also prove that, in an explicit accuracy regime, accurate irreversible product-commit sampling requires either at least \(N^c\) counterfactual queries or at least \(N^c\) commit rounds in the worst case, for some constant \(c>0\).

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
parallel sampling, query complexity, discrete diffusion models

Reviews

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

This paper studies the decoding algorithm for masked diffusion models. The paper assumes an underlying target distribution that admits a forest-like structure. They prove that we could achieve approximate sampling using sub-linear (to sequence length) calls to the approximate conditional oracle and decoding. It also provides a lower-bound for the problem. The paper also provides simulated experiment for the advantage of the proposed decoding algorithm.

Critical strengths

This paper studies a relevant problem, proposes a nice formulation, and gives decent results. In particular, it proves that approximately sampling a forest-like distribution is possible in O(N2/3)O(N^{2/3}) (omitting other factors) calls to the oracle and decoding. It also proves that the problem admits a lower bound of O(N1/3)O(N^{1/3}).

Critical weaknesses

The biggest weakness is presentation. Though I have directly worked on relevant subject, it is hard for me to follow some details as well as the motivations. The authors should do a better job explaining relevant concepts, setting up notations, and interpreting the technical results. See more in the question section.

Questions for authors
  1. Can authors provide better motivations for studying a forest-like distribution? A forest-like distribution is not general enough to capture natural language or protein structures. For example, in 'John wants to leave', John is the subject of wants and leave, while leave is a complement of wants, and hence they form a triangle relation instead of a tree-like relation. It could be equally useful if the authors could provide experiments on real-world data, including but not limited to language and protein, rather than just synthetic data.
  2. Can authors provide high level intuitions about the technical contents in section 2.1? Now they are just listing definitions without explanation.
  3. Could the authors provide comparison between the upper bound and lower bound, and provide some interpretations?
  4. Could the authors provide analysis of how existing decoders would perform on the proposed distribution?
1 comment
AuthorsOpenReview ↗

Response to Reviewer V5Vt

We thank the reviewer for the detailed review.

W1 (presentation). The revision clarifies the motivation for hidden forests in the introduction (Q1), adds intuition for the notation and assumptions in Section 2 (Q2), and explains what the bounds establish and leave open (Q3).

Q1 (why forests; real data). We agree that a forest cannot represent the triangle in your example. Our aim is to understand, in a tractable setting, how selected tokens can simplify generation of the rest. This question is motivated in part by SAID [1] and ADLM [2], which use selected tokens or their predictions to reduce uncertainty about the remaining tokens. In a forest, revealing separator tokens makes the remaining components independent, allowing one token per component to be sampled in parallel. With exact conditionals, a known forest permits O(log⁡N)O(\log N) rounds; we study the cost of discovering and exploiting this structure.

Syntax provides complementary structural intuition. Basic dependency parses [3] connect words to their heads, while program syntax trees organize nested expressions and statements. These hierarchies motivate our use of forest factorization as a tractable model of token dependencies.

On real data, we added experiments using frozen CoDA-v0-Instruct [4] on all 90 MBPP validation tasks [5], with one completion per task and setting. Among evaluated settings, some of ours lie on the empirical Pareto frontier for test failure rate versus total model calls and versus sampling time (Fig. 3; Appendix L).

Q2 (intuition for Section 2.1). The revision adds intuition alongside the definitions.

  • Forest and residual forest. Generating selected tokens first can simplify sampling the rest: on the chain 11--22--33, conditioning on X2X_2 makes the endpoints independent, allowing parallel sampling. More generally, conditioning on committed tokens leaves independent residual components.
  • Directed response and UEN. Fix the token values outside i,ji,j. The directed response is the largest TV change in jj's exact conditional as ii's token varies; it is zero for a nonedge. To ensure edges represent detectable conditional dependence, UEN requires a response of at least ω\omega in both directions, for every assignment to the other positions.
  • RF and RT. Zipf's law [6] motivates RF's bound on the number of frequent tokens. RT requires swapping two rare tokens to have correspondingly small effects on another position's conditional distribution. It rules out large responses hidden solely in distinctions between extremely rare tokens.
  • Uniform oracle accuracy (Section 2.2). Probes evaluate hypothetical states, so we require accuracy there as well. This controls oracle error in the edge tests and is stronger than average prediction accuracy.

Q3 (upper vs. lower bound). At fixed accuracy, Theorem 3.1 gives Q=O~(d2N1/(3s))Q=\tilde O(d^2N^{1/(3s)}) probes and R=O~(N/d)R=\tilde O(N/d) commit rounds. Here s>1s>1 is the rank-frequency exponent and dd the degree cutoff. In QQ, N1/(3s)N^{1/(3s)} bounds the number of token values tested per position, and d2d^2 covers screening up to degree dd; N/dN/d in RR covers singleton peeling. QQ's bound grows with dd and RR's falls; balancing them gives O~(N2/3+1/(9s))\tilde O(N^{2/3+1/(9s)}) total submissions.

Theorem 3.2 requires Q=Ω(N1/(3s))Q=\Omega(N^{1/(3s)}) or R=Ω(N1/3)R=\Omega(N^{1/3}) in the worst case. It uses an adversarial approximate oracle satisfying our accuracy assumption to hide informative tokens among Θ(N1/(3s))\Theta(N^{1/(3s)}) candidates. Thus the vocabulary-search factor agrees, but the lower bound does not show that our extra screening and peeling costs are necessary. We suspect these costs can be reduced, but making the hidden graph harder to infer may also strengthen the lower bound. The bounds do not match, and the optimal total cost remains open.

Q4 (existing decoders on hidden forests). As a representative example, consider entropy-based decoders [7,8]. Even conditionally independent positions can have high marginal entropy, making entropy budgets conservative. Larger batches, however, risk sampling dependent positions independently. We conjecture that this tradeoff can limit their efficiency on hidden forests. Our probes instead seek to identify dependencies and exploit conditional independence.

We added fixed-count and entropy-bounded decoder comparisons on four exact-oracle forest families (Fig. 3; Appendix K). Among tested settings, some of ours lie on the empirical TV–query Pareto frontier in all four families, and the TV–time frontier in three (excluding binary trees).

[1] Li et al. (2026), SAID, arXiv:2606.04974.

[2] Rout et al. (2025), ADLM, arXiv:2505.18456.

[3] de Marneffe et al. (2021), Universal Dependencies, CL 47(2):255–308.

[4] Chen et al. (2025), CoDA, arXiv:2510.03270.

[5] Austin et al. (2021), MBPP, arXiv:2108.07732.

[6] Zipf (1949), Human Behavior and the Principle of Least Effort.

[7] Ben-Hamu et al. (2025), arXiv:2505.24857.

[8] Cai & Li (2026), arXiv:2603.22248.

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

This paper seeks to address an important problem in masked diffusion language models (MDLM): when sampling a text sequence, we desire to generate samples from the joint distribution, but instead we factorize it across positions. The authors seek to propose a method to instead generate from the true joint distribution in o(n) evaluations of the neural network.

To achieve this, the authors first assume a hidden "forest" structure that models discrete dependencies and admit O(log n) queries to the neural network. They find there is a sampler with total variation error at most epsilon using O(N^{2/3 + 1/9s} network evaluations. They then provide experiments to support this claim.

Critical strengths

The paper identifies an important problem in masked diffusion language models: how to sample from the joint distribution in parallel. They propose a meaningful approach to this problem!

Critical weaknesses
  1. The introduction is confusing because it does not clearly explain what forests are. More broadly, how do the authors justify using the assumption of forest structure for language?
  2. No experiments are performed on standard masked diffusion language models. These can be performed on small-scale (MDLM [1]) or large-scale (Llada 8B [2]) model sizes.
  3. The math is written in quite a dense way

[1] Simple and Effective Masked Diffusion Language Models by Sahoo et al. [2] Large Language Diffusion Models by Nie et al.

Questions for authors
  1. Can you please explain how we can justify using the forest assumption for language data?
  2. Is it possible to include an experiment on standard MDLM models ? This would greatly strengthen the paper.
3 comments
AuthorsOpenReview ↗

Response to Reviewer AWTT

We thank the reviewer for the comments.

W1 and Q1 (forest assumption and motivation). The revised introduction explains our aim: to understand, in a tractable setting, how selected tokens can simplify generation of the rest. This question is motivated in part by SAID [1] and ADLM [2], which use selected tokens or their predictions to reduce uncertainty about the remaining tokens.

For this purpose, we study distributions that factorize over a hidden forest on token positions. Revealing separator tokens makes the remaining components independent, allowing one token per component to be sampled in parallel. With exact conditionals, a known forest permits O(log⁡N)O(\log N) rounds; we study the cost of discovering and exploiting this structure.

Syntax provides complementary structural intuition. Basic dependency parses [3] connect words to their heads, while program syntax trees organize nested expressions and statements. These hierarchies motivate our use of forest factorization as a tractable model of token dependencies.

W2 and Q2 (experiments on standard masked diffusion models). We added experiments using the publicly available CoDA-v0-Instruct 1.7B masked diffusion model [4] on all 90 MBPP validation tasks [5], with model weights frozen throughout. We compare a practical implementation of our method with CoDA’s released entropy, confidence, margin, and Origin samplers, generating one completion per task and setting.

We measure test failure rate as the fraction of generated programs that do not pass all tests for their task. To compare accuracy and cost, Figure 3 plots this rate against total model calls QtotQ_{\mathrm{tot}}, including preprocessing and counterfactual probes, and sampling time, including model inference and controller computation. Among the evaluated settings, some configurations of our method lie on the empirical Pareto frontier in both plots. Appendix L provides the experimental protocol and all 33 settings.

W3 (dense mathematics). Section 2 now explains the directed response and the roles of the assumptions in words, and includes a three-token example illustrating conditional independence. In Section 4.2, we simplified the voting notation and now describe the probing and voting procedure before analyzing why it works. Section 4.3 now explains the rationale for peeling before introducing its selection rule.

[1] Li et al. (2026), SAID, arXiv:2606.04974.

[2] Rout et al. (2025), ADLM, arXiv:2505.18456.

[3] de Marneffe et al. (2021), Universal Dependencies, CL 47(2):255–308.

[4] Chen et al. (2025), CoDA, arXiv:2510.03270.

[5] Austin et al. (2021), MBPP, arXiv:2108.07732.

I thank the authors for their response. The revised motivation (separator tokens splitting the remaining dependencies into independent components) and the added intuition in Section 2 make the paper easier to follow, and the CoDA experiments on MBPP are a welcome step toward real masked diffusion models. That said, the forest assumption remains a heuristic for natural language, and with one completion on each of 90 tasks the CoDA results are fairly noisy; more samples or a larger benchmark would make the Pareto claims more convincing. I maintain my score.

Thank you for your response and helpful feedback. We are glad that the revisions made the paper easier to follow.

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

The paper studies sampling from distributions with an unknown dependency forest. Under its response and oracle-accuracy assumptions, it achieves o(N)o(N) total submissions at fixed output accuracy, including dependency discovery. The algorithm combines shared counterfactual tests, vertex removal based on neighbor reports, and centroid sampling. A lower bound requires polynomially many probes or commit rounds for irreversible product-commit samplers under seed-averaged error. Experiments use four synthetic forest families with exact oracles.

Critical strengths
  1. The algorithm pays for discovering safe batches while handling arbitrary vertex degrees. Its key step uses correct reports from low-degree vertices to identify a small set to sample singly, despite unreliable high-degree reports. Repeating this step enables recovery and parallel sampling of the remaining forest. The path example with constant dependence per edge and total correlation Θ(N)\Theta(N) shows that the guarantee handles substantial token dependence.
  2. The lower-bound analysis tracks hidden matching information as probes and sampled values change later decisions. Handling this adaptivity is a substantive technical contribution. The hard instances satisfy the same Hellinger assumptions as the upper bound, showing that an accurate sampler must spend polynomially many probes or commit rounds in the worst case.
Critical weaknesses
  1. The paper does not establish that the query savings can be obtained with a trained masked model. The TV result requires squared Hellinger error at most ε2/(8N)\varepsilon^2/(8N) at every query, including unlikely hypothetical fillings. Edges must remain detectable under every complete boundary, and rare tokens must have similar responses. These conditions enable discovery in arbitrary draft contexts but do not follow from average prediction accuracy. A submission returns any requested set of full probability vectors for one unit of cost, with local computation uncharged. The exact-oracle experiments leave prediction-error sensitivity and runtime savings untested.

  2. The lower bound does not determine the best achievable total query cost. At fixed accuracy and s=2s=2, the upper bound is O~(N13/18)\widetilde O(N^{13/18}), while Theorem 3.2 requires Q=Ω(N1/6)Q=\Omega(N^{1/6}) or R=Ω(N1/3)R=\Omega(N^{1/3}). The resulting total-cost lower bound is only Ω(N1/6)\Omega(N^{1/6}). The proof uses an approximate oracle that hides nontrigger responses and averages TV errors before mixing decision seeds. It does not establish the same obstacle for exact oracles or for the TV error of the mixed output. The paper states these distinctions correctly, leaving the optimal cost unresolved.

  3. The tuned experimental settings do not inherit the theorem's accuracy guarantee. Appendix K.3 permits targets and parameters outside its sufficient conditions. Structural checks support zero batch discrepancy on all 120 evaluated executions, but do not bound the chance of an unsafe batch on a new execution. For fixed seed ww, the exact path statistic in Eq. (228) averages to DKL(P^w∥P)D_{\mathrm{KL}}(\widehat P_w\|P), whereas the KL theorem bounds DKL(P∥P^w)D_{\mathrm{KL}}(P\|\widehat P_w). Either direction can support a TV bound. No bound is reported that converts the observed path values into an output-accuracy guarantee for the tuned sampler.

Questions for authors
  1. What accuracy statement applies to the frozen settings in Figure 3 beyond the evaluated trajectories? Is there an argument covering all executions, or an estimate of unsafe-batch probability and its contribution to output error?
  2. Does the upper-bound construction need to interleave discovery and sampling? Since the assumptions hold for every boundary, could discovery temporarily fix removed vertices to draft values, then sample those vertices and the remaining forest after discovery finishes? This would help clarify which parts of the adaptive upper-bound analysis are essential.
3 comments
AuthorsOpenReview ↗

Response to Reviewer YXxF

We thank the reviewer for the detailed review.

W1 (assumptions; trained models; computational cost). The revised Section 2.1 explains how the assumptions support discovery under hypothetical fillings. UEN requires a detectable edge response under every complete boundary. RF bounds the number of frequent tokens, while RT controls response differences among tail tokens, allowing one tail representative. Section 2.2 states the uniform oracle-accuracy requirement, including counterfactual states, and distinguishes it from average prediction accuracy.

Our theoretical resource metric counts masked-state submissions; returned probabilities and local computation are not charged separately (Section 2.2). We therefore also report sampling time, including oracle/model evaluations and controller computation, in Appendices K.5 and L. On synthetic forests, some of our settings lie on the empirical TV–time Pareto frontier for matching, path, and growing stars, but not binary trees.

To examine sensitivity to oracle error, we added experiments with controlled per-row TV perturbations on original and weak-edge forests, using the common 20 pairs of target instances and decision-rule seeds (Appendix K.6). For comparison on a trained model, we evaluated a practical implementation using frozen CoDA-v0-Instruct [1] on all 90 MBPP validation tasks [2], with one completion per task and setting. Among evaluated settings, some of ours lie on the empirical Pareto frontier for test failure rate versus total model calls and versus sampling time (Fig. 3; Appendix L).

W2 (gap; approximate oracle; seed-averaged risk). At fixed accuracy, Theorem 3.2 shows that either the probe budget or the commit-round budget must grow polynomially with NN in the worst case. Its vocabulary-search factor N1/(3s)N^{1/(3s)} also appears in the upper bound, but the lower bound does not establish that the additional screening and peeling costs are necessary. The bounds do not match, and the optimal total cost remains open (Section 3.2).

The lower-bound construction uses an adversarial approximate oracle satisfying our accuracy assumption, and the result concerns seed-averaged TV risk. Establishing an analogous lower bound for exact oracles remains open.

W3 and Q1 (accuracy of the frozen settings). The settings in the original Fig. 3 (now Fig. 8) are empirically tuned and do not inherit the theorem’s guarantee. We have added an evaluation of the frozen settings at N=16384N=16384 on 20 fresh pairs of target instances and decision-rule seeds per forest family. A batch is structurally unsafe if it contains multiple vertices from the same connected component of the remaining target forest. At least one such batch occurred in 1/20 runs for matching and 0/20 for each of the other three forest families (Appendix K.3.2).

The unsafe-batch counts describe the sampling decisions. To quantify error in the output distribution itself, we also estimate TV directly from density ratios and forward KL using exact target samples (Appendix K.2). Appendix K.5 reports these estimates over the common 20 pairs in the error–cost comparisons. Regarding the KL direction, for a fixed target and decision-rule seed, the expectation of the exact path statistic KK in Eq. (226) is the reverse KL DKL(P^w∥P)D_{\mathrm{KL}}(\hat P_w\Vert P), distinct from the theorem’s forward KL.

Q2 (is interleaving necessary?). We expect that interleaving with sampling is not essential under our boundary-uniform assumptions. The key adaptivity in our construction lies within discovery: each successful screen identifies low-degree neighborhoods, these reports determine which vertices to remove from the residual forest (peel), and subsequent screens operate on the resulting residual set. On successful screens, this process progressively shrinks the high-degree core until the remaining forest can be recovered (Section 4.3). Thus later probes depend on earlier screening results, even if all sampling is deferred.

The low-degree recovery guarantee, valid under every fixed boundary (Lemma E.6), suggests that discovery could use temporary draft values for peeled vertices, with sampling deferred until discovery is complete. One would then sample the peeled vertices singly and the remaining forest in centroid layers, using fresh rows conditioned on the actual sampled values. We expect the same asymptotic resource bounds and accuracy guarantees to hold, although we have not separately formalized this variant.

[1] Chen et al. (2025), CoDA, arXiv:2510.03270.

[2] Austin et al. (2021), MBPP, arXiv:2108.07732.

Thank you for the detailed response. The clarifications in Section 3.2 and additional experiments in Appendices K-L address my main concerns.
The strong assumptions and the gap between the upper and lower bounds remain limitations, but the revised paper makes the scope clearer. I will maintain my original score.

Thank you for your time and constructive feedback. Your comments have helped us improve the paper.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Comment by the Authors

We thank the reviewers for their feedback. We summarize the main revisions and clarifications below.

1. Motivation and presentation. (V5Vt: W1, Q1–Q2; YXxF: W1; AWTT: W1, Q1, W3)

We study how revealing selected tokens can simplify generation of the rest. This question is motivated in part by SAID [1] and ADLM [2], which use selected tokens or their predictions to reduce uncertainty about the remaining tokens. We analyze this idea in a hidden forest model. In this model, revealing selected tokens can split the remaining dependency structure into independent components. With exact conditionals, we can then sample one token per component in parallel.

The revised introduction now makes this connection explicit. To help readers follow the analysis, Section 2 adds intuition for the assumptions. Section 4 explains the algorithm’s steps and why they work.

2. Experiments on code generation and synthetic forests. (V5Vt: Q1, Q4; YXxF: W1, W3, Q1; AWTT: W2, Q2)

To clarify the practical implications, we evaluated a practical implementation of our method using CoDA-v0-Instruct [3], a 1.7B-parameter masked diffusion model for code generation. With its weights frozen, we generated one completion per setting for each of the 90 Python coding tasks in the MBPP validation set [4]. We compared against CoDA’s baseline samplers.

We examined how test failure rate (the fraction of programs failing their tests) trades off against two costs (total model calls and sampling time). Calls count every model evaluation, and sampling time includes both inference and controller computation. Among the tested settings, some configurations of our method are Pareto-optimal in both comparisons (Fig. 3; Appendix L).

We also extended experiments on synthetic forests to estimate error in the output distribution, test sensitivity to oracle perturbations, and compare query and runtime costs (Appendix K).

3. Interpretation of the theoretical results. (V5Vt: Q3; YXxF: W2)

We revised Section 3 to explain the roles of probing and commit rounds more clearly and to make explicit that the tightness of the bounds remains open.

At fixed accuracy and under our assumptions, both total oracle calls and sequential depth of our algorithm are sublinear in sequence length NN. These bounds include the cost of dependency discovery. The proposed algorithm trades dependency discovery (probing) cost against sampling (commit-round) cost by choosing an integer degree cutoff: increasing it raises the probing bound and lowers the commit-round bound.

The lower bound uses an adversarial approximate oracle within our irreversible sampling framework. At fixed accuracy, either probing or sampling (commit rounds) requires at least polynomially many oracle calls in the worst case as sequence length NN grows. Whether our total-cost bound is optimal remains open.

[1] Li et al. (2026), SAID, arXiv:2606.04974.

[2] Rout et al. (2025), ADLM, NeurIPS 2025, arXiv:2505.18456.

[3] Chen et al. (2025), CoDA, arXiv:2510.03270.

[4] Austin et al. (2021), MBPP, arXiv:2108.07732

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.