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

arXiv:2610.13924v1 Announce Type: new Abstract: 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 E_U D_{KL}(p|q_U) with the output-law divergence D_{KL}(p|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/2 ones, the least expected number of rounds at a fixed tolerance arepsilon>0 is Theta_arepsilon((log n)^2) under the first criterion but (e^{-arepsilon}+o(1))log_2ln 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^{-arepsilon}/2+o(1))log_2log_2n, attained with rare n-round runs. Prior work implies the order of the schedule-averaged cost on the balanced target and its O_arepsilon((log n)^2) upper bounds on both extensions.

Source: arXiv cs.LG | 2026-10-12