{"id":"arxiv/2610.22238","url":"https://arxiv.org/abs/2610.22238","tags":["cs.LG","math.PR","stat.ML"],"score":0,"title":"Query-Efficient Rejection Sampling for Parallel Masked Diffusion","domain":"cs.LG","source":"arxiv","authors":["Shiyuan Zhang","Xuheng Li","Qiwei Di","Quanquan Gu"],"reviews":0,"subject":"cs.LG","summary":"Masked diffusion models (MDMs) accelerate generation by unmasking multiple tokens in parallel, but sampling these tokens independently ignores their correlations and biases the output. Anari et al. (2026) corrected this bias with rejection sampling, decomposing the log acceptance probability into a sum of token-level terms, but the evaluation requires one score query per unmasked token. We propose the Single-Increment Rejection Sampler (SIRS), which provides an estimate of the log acceptance probability from a single randomly sampled increment at the cost of one query. SIRS then converts a…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-15","reactions":{}}