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 dependencies are unknown, finding safe batches also costs model evaluations. We study whether total evaluations, including discovery, can be sublinear in sequence length N; sublinear sequential depth then follows. We consider discrete distributions with hidden forest structure, accessed through a fixed approximate conditional oracle. Under explicit regularity conditions and uniform Hellinger error bounds, for any fixed target accuracy ε∈(0,1/8] and sufficiently large N, our sampler achieves seed-averaged total-variation error at most ε, with total masked-state submissions and sequential depth both bounded by Õ(NC ε−a) for constants 0<C<1 and a>0. These guarantees use polynomial vocabulary size and an edge-response lower bound set by N and ε. The sampler shares evaluations of hypothetical reveals across dependence tests to identify safe parallel batches without requiring full recovery of the hidden forest. A tunable parameter trades probing cost against irreversible commit rounds. In the same class, any admissible irreversible product-commit sampler attaining the same seed-averaged accuracy requires Ω(Nc εb) counterfactual submissions or commit rounds in the worst case, for constants c,b>0.
Related
- Steer-to-Detect: Probing Hidden Representations for Detection of LLM-Generated Texts
- Dynamics of Hidden Learning Structure
- Structure-Informed Bayesian Inference of Anomalous Transport and Hidden Molecular Trapping in Amorphous Media
- Denoising Is Stein: Moment Access and a Resource Hierarchy for Learning Hidden Structure in Diffusion Models
- The data geometry of masking diffusion: Certified-optimal schedules via unmasking growth complexity
BibTeX
@misc{kawata2026counterfactual,
title = {{Counterfactual Probing for Parallel Unmasking with Hidden Forest Structure}},
author = {Ryotaro Kawata and Satoshi Hayakawa and Taiji Suzuki},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.37841},
eprint = {2609.37841},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.37841},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Counterfactual Probing for Parallel Unmasking with Hidden Forest Structure
AU - Ryotaro Kawata
AU - Satoshi Hayakawa
AU - Taiji Suzuki
PY - 2026
DA - 2026/10/04
PB - arXiv
DO - 10.48550/arxiv.2609.37841
UR - https://arxiv.org/abs/2609.37841
AB - Masked generative models offer parallel token prediction, but accurate parallel sampling must account for dependencies among tokens. When dependencies are unknown, finding safe batches also costs model evaluations. We study whether total evaluations, including discovery, can be sublinear in sequence length N; sublinear sequential depth then follows. We consider discrete distributions with hidden forest structure, accessed through a fixed approximate conditional oracle. Under explicit regularity conditions and uniform Hellinger error bounds, for any fixed target accuracy ε∈(0,1/8] and sufficiently large N, our sampler achieves seed-averaged total-variation error at most ε, with total masked-state submissions and sequential depth both bounded by Õ(N^C ε^−a) for constants 0<C<1 and a>0. These guarantees use polynomial vocabulary size and an edge-response lower bound set by N and ε. The sampler shares evaluations of hypothetical reveals across dependence tests to identify safe parallel batches without requiring full recovery of the hidden forest. A tunable parameter trades probing cost against irreversible commit rounds. In the same class, any admissible irreversible product-commit sampler attaining the same seed-averaged accuracy requires Ω(N^c ε^b) counterfactual submissions or commit rounds in the worst case, for constants c,b>0.
ER -