Counterfactual Probing for Parallel Unmasking with Hidden Forest Structure

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\).