Randomization Beyond Deterministic Adaptivity in Parallel Sampling
Abstract
We study parallel samplers that reveal each coordinate once and draw the coordinates of each batch independently from their exact conditional marginals. Under the same sampling interface and a hard three-round cap, randomization can improve accuracy beyond every deterministic policy that adapts its batches to previously observed values. For an explicit full-support binary family, the optimal deterministic adaptive forward Kullback-Leibler divergence grows linearly with the dimension, while a uniform mixture of four fixed schedules has exponentially small divergence. Only two independent fair bits are needed to select the schedule. We determine the asymptotic additive constant in the deterministic optimum and show that its optimal total variation tends to one quarter. An outward-rounded finite-sum certificate establishes divergence separation at dimension 389. The mechanism combines an irreversible first-batch dependence loss with posterior concentration in the randomized components. A density-coverage lemma describes how their mixture restores the target. A complementary noisy-matching family exhibits a growing round gap for nonadaptive schedules, although uniform random coordinate order still has linear mixture error. These results concern known finite structures and exact conditional marginals.
Related
- Piecewise deterministic sampling for constrained distributions
- Query-Efficient Rejection Sampling for Parallel Masked Diffusion
- Shared Randomness and Parallel Rounds in Permutation Sampling
- Serial Depth of Adaptive Parallel Sampling: Lower Bounds and Schedules for Masked Diffusion Models
- Lower Bounds for Parallel Diffusion Sampling
BibTeX
@misc{li2026randomization,
title = {{Randomization Beyond Deterministic Adaptivity in Parallel Sampling}},
author = {Da Li and Bo Jin and Xiaopeng Wei},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.03335},
eprint = {2610.03335},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.03335},
}
RIS
TY - UNPB
TI - Randomization Beyond Deterministic Adaptivity in Parallel Sampling
AU - Da Li
AU - Bo Jin
AU - Xiaopeng Wei
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2610.03335
UR - https://arxiv.org/abs/2610.03335
AB - We study parallel samplers that reveal each coordinate once and draw the coordinates of each batch independently from their exact conditional marginals. Under the same sampling interface and a hard three-round cap, randomization can improve accuracy beyond every deterministic policy that adapts its batches to previously observed values. For an explicit full-support binary family, the optimal deterministic adaptive forward Kullback-Leibler divergence grows linearly with the dimension, while a uniform mixture of four fixed schedules has exponentially small divergence. Only two independent fair bits are needed to select the schedule. We determine the asymptotic additive constant in the deterministic optimum and show that its optimal total variation tends to one quarter. An outward-rounded finite-sum certificate establishes divergence separation at dimension 389. The mechanism combines an irreversible first-batch dependence loss with posterior concentration in the randomized components. A density-coverage lemma describes how their mixture restores the target. A complementary noisy-matching family exhibits a growing round gap for nonadaptive schedules, although uniform random coordinate order still has linear mixture error. These results concern known finite structures and exact conditional marginals.
ER -