KL Before and After Mixing: A Round-Complexity Separation in Parallel Sampling

A parallel sampler can choose at random which coordinates to generate together. For a target $p$ and the output law $q_U$ of a schedule $U$ drawn afresh for each output, we compare the schedule-averaged divergence ${\mathbb{E}}_U{D}_{\mathrm{K}\mathrm{L}}(p\mathrm{\parallel }{q}_U)$ with the output-law divergence $D_{\mathrm{K}\mathrm{L}}(p\mathrm{\parallel }{\mathbb{E}}_U{q}_U)$, in nats. Rounds commit independent draws from exact conditional marginals frozen at the round’s start, each output’s schedule is drawn before sampling from a finite mixture of schedules, and every scheduled round is charged. For the uniform distribution on binary strings of even length $n$ with $n\mathrm{/}2$ ones, the least expected number of rounds at a fixed tolerance $\epsilon >0$ is ${\mathrm{\Theta }}_{\epsilon }((\log n{)}^2)$ under the first criterion but $(e^{-\epsilon }+o(1)){\log }_2\ln n$ under the second, and the double-logarithmic order is attainable with the same round count on every run. For this target, a count-state recursion gives the exact least output divergence at every round cap over all causal randomized policies. The separation extends to weighted fixed-count targets with bounded weight ratios and quota fractions bounded away from zero and one, without permutation symmetry, and to the full-support Beta$(1,1)$–Bernoulli target, where the sharp expected cost under the output-law criterion is $(e^{-\epsilon }\mathrm{/}2+o(1)){\log }_2{\log }_{2}n$, attained with rare $n$-round runs. Prior work implies the order of the schedule-averaged cost on the balanced target and its $O_{\epsilon }((\log n{)}^2)$ upper bounds on both extensions.