Conditional Total Correlation and the Serial Depth of Adaptive Parallel Sampling

Chuling Wen; Weijie Liang; Jian Lu

cs.ITAug 26, 2026

Conditional Total Correlation and the Serial Depth of Adaptive Parallel Sampling

Authors: Chuling Wen, Weijie Liang, Jian Lu

Organizations: Shenzhen Key Laboratory of Advanced Machine Learning and Applications, School of Mathematical Sciences, Shenzhen University, Shenzhen 518060, China · National Center for Applied Mathematics Shenzhen (NCAMS), Shenzhen 518055, China

Abstract

Motivated by parallel decoding in masked diffusion models, we study adaptive parallel sampling of discrete vectors: in each round, a deterministic policy selects unrevealed coordinates on the basis of the values observed so far, and the selected coordinates are sampled independently from their exact conditional marginals. Approximation error is measured by forward Kullback-Leibler divergence, and serial depth is the minimum target-averaged number of rounds meeting a prescribed error budget. Our central result is an exact identity: the divergence of every policy equals the expected conditional total correlation accumulated over its reveal rounds, so conditional total correlation is the exact information cost of within-round parallelism. The identity yields zero-error schedules for finite-order Markov chains with round complexity proportional to the Markov order and logarithmic in sequence length, a matching logarithmic characterization of the Bernoulli walk at every fixed error budget, and a linear-versus-logarithmic separation between left-to-right and hierarchical reveal orders. Uniform random permutations require linearly many expected rounds at every fixed budget; their hard-cap round-error tradeoff is an exact integer-composition problem whose fixed-round asymptotics and joint-scaling frontier we determine. Uniform balanced binary strings have depth of order squared logarithm, and binary one-hot blocks have square-root depth, with rectangular versions realizing every polynomial exponent up to one half. These results separate serial depth from entropy and negative log-likelihood, and establish conditional-dependence structure as a fundamental determinant of parallelizability. Experiments with a masked diffusion language model show that the pseudo-cost distinguishes deployed decoding rules and that its policy rankings agree closely with the quality of self-sampled outputs.

Figures & tables

distribution	depth	source
independent	$D_{0}=1$	Example 1
copy chain	$D_{0}=2$	Example 2
order- $m$ Markov	$D_{0}\leq m(\lceil\log_{2}(n/m)\rceil+1)$	Theorem 2
Bernoulli walk	$D_{\varepsilon}=\Theta(\log n)$ for every fixed $\varepsilon\geq 0$	Theorems 3 (i), 4 , 5
affine subspaces	$D_{0}\leq 2$	Remark 10
balanced binary ( $\|V\|{=}2$ )	$D_{\varepsilon}=\Theta(\log^{2}n)$ for fixed $\varepsilon>0$	Theorem 11

TABLE I: Depth guarantees established in this paper.

Fig. 1: The hard-cap round–error tradeoff for uniform random permutations at

n=240

. The dots are the exact values

\mathcal{E}_{n,R}

from the dynamic program in Proposition 1 . The solid curve is the pair-first schedule, which equals

\mathcal{E}_{n,R}

for

n-R\leq n/3

by Theorem 9 . The dashed and dotted curves are the two lower bounds for target-averaged depth from Proposition 3 and Theorem 6 . The vertical line marks the proven endpoint

R/n=2/3

of the pair-first phase.

	left-to-right			random		bisect	greedy min-ent
domain	$B{=}4$	$B{=}16$	$B{=}64$	$16$	$64$		$16$	$64$
code	$0.81{\pm}0.10$	$1.45{\pm}0.16$	$2.48{\pm}0.19$	$\mathbf{0.18{\pm}0.02}$	$0.90{\pm}0.07$	$0.93{\pm}0.11$	$0.67{\pm}0.07$	$1.24{\pm}0.07$
math	$1.58{\pm}0.04$	$3.01{\pm}0.12$	$3.89{\pm}0.16$	$\mathbf{0.15{\pm}0.01}$	$0.77{\pm}0.05$	$1.04{\pm}0.04$	$1.21{\pm}0.12$	$1.64{\pm}0.09$
prose	$2.23{\pm}0.08$	$3.84{\pm}0.17$	$4.54{\pm}0.18$	$\mathbf{0.20{\pm}0.02}$	$0.94{\pm}0.02$	$1.12{\pm}0.18$	$1.63{\pm}0.16$	$1.91{\pm}0.17$
struct	$0.89{\pm}0.20$	$1.63{\pm}0.29$	$2.60{\pm}0.29$	$\mathbf{0.17{\pm}0.02}$	$0.76{\pm}0.04$	$1.11{\pm}0.23$	$0.66{\pm}0.10$	$1.23{\pm}0.13$
wiki	$2.30{\pm}0.01$	$4.34{\pm}0.01$	$5.34{\pm}0.02$	$\mathbf{0.15{\pm}0.00}$	$0.62{\pm}0.00$	$\mathbf{0.47{\pm}0.01}$	$1.95{\pm}0.02$	$2.30{\pm}0.03$

TABLE II: Realized generation cost in bits per token (mean

\pm

standard error over texts). In each domain, boldface marks the lowest cost; the additional boldface bisection entry on WikiText is the lowest cost among schedules using at most ten rounds.

Fig. 2: Batch-size profiles at equal round budget on natural text (542 texts, 3 seeds, paired positions). The cost ordering increasing

<

equal

<

decreasing is the reverse of the provably optimal order on random permutations (Theorem 8 ); its equal-versus-decreasing half holds for every text, seed and

R

, while increasing

<

equal holds at

R{=}4,8

and weakens to the measurement resolution at

R{=}16

(see text).

rule	rounds	bits/token
threshold $\tau{=}0.99$	$493.1$	$0.0005{\pm}0.0002$
block-32 threshold $\tau{=}0.99$	$493.7$	$0.0004{\pm}0.0001$
threshold $\tau{=}0.9$	$478.2$	$0.0070{\pm}0.0007$
block-32 threshold $\tau{=}0.9$	$479.6$	$0.0059{\pm}0.0006$
confidence top-16	$31.6$	$1.650{\pm}0.019$
greedy min-entropy 16	$31.6$	$1.897{\pm}0.023$

TABLE III: Deployed decoding rules versus reference schedules (pooled over 542 texts; mean

\pm

standard error). Reference rows repeat Section V-B schedules at matched round counts.

Fig. 3: Deployed decoding rules and reference schedules in the round–cost plane (pooled means over 542 texts, logarithmic round axis). The deployed rules occupy two extremes — near-serial threshold rules and expensive confidence rules — while the reference schedules provide measured intermediate tradeoff points.

policy	rounds	judge PPL	rep-4
threshold $\tau{=}0.9$	$431.9$	$120.6{\pm}4.9$	$0.068$
bisection	$9.0$	$192.2{\pm}5.9$	$0.019$
spaced profile $R{=}16$	$16.0$	$201.7{\pm}6.9$	$0.023$
random 16	$28.0$	$236.9{\pm}7.5$	$0.016$
increasing profile $R{=}16$	$16.0$	$276.2{\pm}8.5$	$0.018$
increasing profile $R{=}8$	$8.0$	$391.6{\pm}11.3$	$0.012$

TABLE IV: Self-sampling generation quality (231 prompts

\times

3 seeds, paired; arithmetic mean of per-sequence judge perplexity on the generated span, with standard errors clustered by prompt; rep-4 is the

4

-gram repetition rate).

Explore similar work

Oct 9, 2026cs.LG

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{KL}}(p\|q_U)

with the output-law divergence

D_{\mathrm{KL}}(p\|\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/2

ones, the least expected number of rounds at a fixed tolerance

\varepsilon>0

Θ_\varepsilon((\log n)^2)

under the first criterion but

(e^{-\varepsilon}+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^{-\varepsilon}/2+o(1))\log_2\log_2n

, attained with rare

n

-round runs. Prior work implies the order of the schedule-averaged cost on the balanced target and its

O_\varepsilon((\log n)^2)

upper bounds on both extensions.

Tianyi Wu

Amazon

Topic pending

Ask PDF

Oct 6, 2026cs.DS

Lower Bounds for Parallel Diffusion Sampling

Standard diffusion samplers generate samples through repeated evaluations of a learned score function. Parallel sampling methods seek to accelerate generation by trading additional evaluations for fewer sequential rounds. This raises the question of how much sequential dependence is unavoidable, even when many score queries can be made simultaneously. We establish the first polynomial parallel-round lower bounds for diffusion sampling with approximate scores. Specifically, we prove (1) a

\widetildeΩ(d^{1/3})

-round lower bound for sampling smooth, near-isotropic Gaussian mixtures in

R^d

, and (2) an

Ω(d)

-round lower bound for uniform sampling from anisotropic axis-aligned boxes contained in the unit ball. Both bounds hold for arbitrary randomized algorithms making polynomially many queries per round at arbitrary locations and noise levels, with inverse-polynomial score error and constant total variation accuracy. The linear bound is tight for our box family. Our constructions use fixed approximate score oracles that enforce sequential access to hidden information while satisfying the accuracy guarantee at every noise level.

Yiwen Kou, Yimeng Wang

UCLA

Diffusion Sampling Query Complexity

Ask PDF

Sep 29, 2026cs.LG

Counterfactual Probing for Parallel Unmasking with Hidden Forest Structure

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

\varepsilon\in(0,1/8]

and sufficiently large

N

, our sampler achieves seed-averaged total-variation error at most

\varepsilon

, with total masked-state submissions and sequential depth both bounded by

\widetilde{O}(N^C \varepsilon^{-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

\varepsilon

. 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 \varepsilon^b)

counterfactual submissions or commit rounds in the worst case, for constants

c,b>0

Ryotaro Kawata, Satoshi Hayakawa, Taiji Suzuki

The University of Tokyo · RIKEN AIP

Sample Complexity Probabilistic Graphical Models Generative Modeling Parallel Decoding

Ask PDF