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

KL Before and After Mixing: A Round-Complexity Separation in Parallel Sampling
Oct 9, 2026Tianyi Wu
Amazon
Lower Bounds for Parallel Diffusion Sampling
Oct 6, 2026Yiwen Kou, Yimeng WangDiffusion Sampling Query Complexity
UCLA
Counterfactual Probing for Parallel Unmasking with Hidden Forest Structure
Sep 29, 2026Ryotaro Kawata, Satoshi Hayakawa, Taiji SuzukiSample Complexity Probabilistic Graphical Models
The University of Tokyo · RIKEN AIP

Oct 9, 2026, cs.LGJ/K move · Enter open · S save

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

Tianyi Wu

Amazon

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

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

Lower Bounds for Parallel Diffusion Sampling

Counterfactual Probing for Parallel Unmasking with Hidden Forest Structure