PaperlayerView exact revision on arXiv

Source-linked AI summary

Conditional Total Correlation and the Serial Depth of Adaptive Parallel Sampling

Chuling Wen, Weijie Liang, Jian Lu

arXiv:2608.25505v1cs.ITcs.CL

TL;DR

The paper asks how many adaptive parallel-sampling rounds are required to approximate a fixed discrete distribution when coordinates selected together are sampled independently. It models this process with exact conditional-marginal queries and proves that forward-KL error equals expected conditional total correlation accumulated across rounds. The resulting theory characterizes serial depth for several dependent distributions and separates it from entropy-based measures, while experiments assess whether teacher-forced pseudo-costs distinguish decoding rules and predict self-sampled output quality.

  • Problem

    Existing entropy, negative-log-likelihood, and fixed-schedule analyses do not determine serial depth for value-adaptive reveal policies targeting a fixed distribution.

  • Method

    The paper analyzes deterministic value-adaptive policies in an exact conditional-marginal oracle model and uses a KL chain rule to track conditional total correlation across reveal rounds.

  • Results

    The exact identity yields logarithmic Bernoulli-walk depth, linear fixed-budget depth for uniform random permutations, and distribution-specific depth laws including squared-logarithmic and square-root regimes.

  • Takeaways & Limitations

    Conditional-dependence structure, rather than entropy or negative log-likelihood alone, determines the information cost and parallelizability of adaptive sampling.

Abstract

from arXiv · show

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.

I. INTRODUCTION

The paper studies the accuracy–parallelism tradeoff when reveal positions adapt to observed values, introducing conditional total correlation as an exact cost of within-round independent sampling. It develops distribution-specific serial-depth results and evaluates whether the cost predicts deployed decoding behavior.

  • Motivation: Value-adaptive reveal positions create random, history-coupled schedules that existing fixed-schedule and target-agnostic oracle analyses do not characterize.Entropy and negative log-likelihood alone cannot determine serial depth because high-entropy distributions may still be independently sampleable in one round.
  • Core contribution: The exact KL–total-correlation identity converts adaptive round complexity into information accounting over the policy tree.The identity applies to random and history-dependent reveal sets and supports both upper and lower bounds on serial depth.
  • Distribution-specific results: Finite-order Markov chains admit zero-error schedules using rounds proportional to Markov order and logarithmic in sequence length.For the Bernoulli walk, hierarchical bisection achieves zero error in O(log n) rounds, whereas contiguous left-to-right schedules require linearly many rounds at fixed accuracy.
  • Distribution-specific results: Uniform random permutations require linearly many expected rounds at every fixed error budget, with hard-cap error characterized by an exact integer-composition problem.The characterization includes fixed-round asymptotics, a finite-blocklength pairs-first phase, and the joint-scaling frontier.
  • Experiments: The study evaluates generic schedules and deployed decoding rules on 542 text sequences and relates teacher-forced pseudo-costs to output quality on 231 held-out prompts.It also tests a model-independent spaced-profile schedule with increasing batch sizes and spatially dispersed reveals.

C. Adaptive reveal model

The adaptive reveal model lets deterministic policies choose unrevealed coordinates from observed histories and samples selected coordinates independently from exact conditional marginals. Its central identity equates forward KL error with accumulated conditional total correlation, while serial depth tracks target-averaged policy-tree rounds.

  • Policy and sampling process: A deterministic adaptive policy maps each revealed state (C, x_C) to a nonempty unrevealed coordinate set.The policy therefore depends on both which coordinates have been revealed and the values observed there.
  • Policy and sampling process: Each selected coordinate is sampled independently from its exact conditional marginal, producing an output law q_π and stopping when all coordinates are revealed.An exact conditional oracle isolates error caused by factorized within-round sampling from model-estimation error.
  • Serial depth: Target-weighted policy-tree depth, sampler-runtime mean, and worst-case depth can differ for value-adaptive policies because q_π may differ from p.For fixed schedules the distinction does not affect the stated upper bounds, while randomized-policy lower bounds remain unresolved.
  • Exact information cost: Theorem 1 states that every policy’s forward KL divergence equals expected conditional total correlation accumulated across reveal rounds.The divergence is zero exactly when every revealed set is conditionally independent given its realized history, almost surely under p.
  • Serial depth: Serial depth is equivalently the minimum expected-round adaptive cover whose accumulated conditional total correlation is at most ε.Sequential revealing gives zero error, and the target-averaged and hard-cap depth quantities are bounded by n.

B. Serial depth is not likelihood

Serial depth is distinct from entropy and likelihood: distributions with identical entropy profiles can have radically different numbers of rounds. For the Bernoulli walk, hierarchical revealing is logarithmic while contiguous left-to-right revealing is linear, even under value adaptivity.

  • Depth versus likelihood: An independent high-entropy distribution can be sampled exactly in one round, so negative log-likelihood alone cannot lower-bound depth for unconstrained factorized-reveal policies.The example has per-token entropy h, total entropy nh, and D0(p) = 1.
  • Depth versus likelihood: Depth is not total dependence; it is the structure of resolvable dependence.A copy chain can have maximal total correlation across coordinates yet require only two rounds because revealing one block makes all remaining conditionals point masses.
  • Structured dependencies: Finite-order Markov chains admit logarithmic-depth hierarchical schedules, and recursive separators of size at most w yield O(w log n) depth bounds.The witnessing schedule for the Markov-chain result uses recursive bisection by m-blocks and does not require value adaptivity.
  • Reveal-order separation: For the Bernoulli walk, an exact hierarchical schedule uses ⌈log2(n+1)⌉ rounds, whereas left-to-right schedules require Ω(n) rounds for constant error budgets.The scan bound contrasts linear-round behavior with zero error under hierarchical revealing.
  • Bernoulli-walk depth: At zero error, D0(pwalk) = Θ(log n), with hierarchical optimality among deterministic value-adaptive policies up to an additive O(log log n).Adaptivity can clear realized degenerate segments for free; the maxrun term accounts for this freedom.
  • Bernoulli-walk depth: Dε(pwalk) = Θ(log n) for every fixed ε, and the hierarchical schedule is optimal up to constant factors at every constant error budget.The fixed-error converse applies to every deterministic value-adaptive policy.

E. Uniform random permutations

Uniform random permutations remain linearly deep at every fixed error budget because every coordinate excludes every other. Their hard-cap tradeoff reduces exactly to optimizing integer batch-size compositions, with decreasing optimal profiles and a characterized joint-scaling frontier.

  • Robust depth: Ω(n) expected rounds are necessary for every fixed error budget ε under deterministic value-adaptive policies.Specifically, Dε(pperm) ≥ n/(1+2ε ln 2).
  • Cost invariance: Position selection and value adaptivity buy nothing under a hard round cap on uniform permutations.Trajectory cost depends only on the batch-size sequence, reducing optimization to integer compositions.
  • Asymptotics: For fixed R, optimal profiles converge to a continuous optimizer, while equal batches are asymptotically worse by a factor ∼(ln R)/4.The optimal remaining-mass rate satisfies 1 − ρR ∼ 2/R as R →∞.
  • Joint scaling: When 3s ≤ n, s size-two batches followed by n − 2s singletons are exactly optimal in the joint regime.The pair-first composition saves s rounds from the all-singleton schedule.
  • Limitations: The joint-scaling frontier is characterized, but equality with target-averaged depth remains open because full-range convexity is unproved.Convexity is established only in the first phase.

F. Balanced binary strings

Uniform balanced binary strings provide a fixed-alphabet family with polylogarithmic robust depth under one global exchangeable constraint. Their depth is Θ(log^2 n) for fixed positive error, and fixed schedules match adaptive lower bounds up to constants.

  • Depth rate: Dε(pbal) = Θ(log^2 n) for every fixed ε > 0.The theorem provides matching lower and upper bounds, with constants that may depend on ε.
  • Comparison: The balanced-string family has strictly intermediate depth between the Bernoulli walk, Θ(log n), and permutations, Θ(n).This establishes a fixed-binary-alphabet separation from both comparison families.
  • Scope: The lower bound is truncated because Dε ≤ n, so a bound proportional to (log n)^2/ε cannot hold uniformly as ε ↓ 0.The truncation is necessary near zero error.
  • Proof strategy: An exchangeable urn coupling yields the lower bound, while a fixed fractional-batch schedule supplies the upper bound.The coupling’s complete potential trajectory is independent of the policy.
  • Adaptivity: Exchangeability makes position selection irrelevant asymptotically, and a fixed schedule matches the adaptive lower bound up to constants.This differs from the permutation case in rate but shares its adaptivity-insensitivity.

G. Binary one-hot blocks

Binary one-hot block constructions achieve polynomial robust depth despite using only binary coordinates. Independent blocks produce square-root depth, and rectangular arrays realize every polynomial exponent up to one half.

  • Construction: The construction uses independent blocks, each containing a single uniformly located one-hot 1 among binary coordinates.The latent locations are not themselves revealed coordinates.
  • Square-root depth: Dε(phot) = Θε(√n) along n = m^2 for every ε ≥ 0.The lower bound applies to every deterministic value-adaptive policy, and a matching zero-error schedule is given.
  • Lower-bound mechanism: Adaptive allocation across blocks cannot avoid quadratic information costs for nontrivial within-block batches.A deferred-decision lemma bounds unresolved blocks’ free candidates by one per global round in expectation.
  • Polynomial spectrum: Rectangular one-hot constructions realize every exponent α ∈ (0, 1/2] as Dε(pn) = Θε(n^α).Thus binary coordinate representations support a polynomial depth spectrum through exponent one half.
  • Representation: Serial depth depends on the coordinate representation because the one-hot encoding converts independent categorical locations into binary reveal coordinates.The construction is a reveal-only analogue of group testing with one defective per block.
  • Open directions: Whether any fixed-binary-alphabet family has linear robust depth remains open.The paper also leaves open whether value adaptivity can improve asymptotic rates over non-adaptive schedules on some family.

V. NUMERICAL RESULTS

Numerical checks validate the paper’s theoretical schedules and show that reveal-order effects reverse on natural text. Deployed decoding rules occupy distinct round–cost extremes, while pseudo-cost rankings track self-sampled generation quality, subject to model and numerical qualifications.

  • Finite-blocklength checks: D0 = 1, 2, 2, 2, 2.75, 2.875, 3, 3 for Bernoulli walks with n ≤7 under exhaustive zero-error policy search.Noninteger depths arise from trajectory-dependent degenerate segments that require no additional information cost.
  • Finite-blocklength checks: At n = 240, optimal permutation profiles use only batch sizes one and two throughout the proven region n − R ≤ n/3.For r = R/n ∈ [0.55, 0.75], finite-blocklength hard-cap values differ from the limiting frontier by at most 0.6%.
  • Natural-text measurements: Left-to-right costs 2.7–29× more than random order at equal round counts across all tested natural-text domains.Uniformly random sets of 16 positions cost approximately 0.15–0.20 bits/token, while bisection reaches 0.47 bits/token on WikiText in 9–10 rounds.
  • Batch-size profiles: Increasing, equal, and decreasing batch profiles cost 0.27/0.30/0.46 bits/token at R = 16, reversing the permutation ordering.Decreasing loses to equal on all 542 texts, while increasing beats equal on 77–90% of texts; the advantage weakens toward measurement resolution at R = 16.
  • Deployed decoding rules: At τ = 0.9, threshold decoding clears approximately 1.07 positions per round, whereas confidence top-16 costs 1.650 versus 0.151 bits/token for random-16.Threshold decoding is near-serial; confidence selection is more expensive on every tested text.
  • Qualifications: Pseudo-cost values are teacher-forced model-based measurements, and adaptive-policy absolute costs vary with numerical precision.Fixed-schedule costs move by at most 0.006 bits/token in single precision, while adaptive costs vary by ±0.5 bits/token on average.
  • Self-sampling quality: Teacher-forced pseudo-cost rankings correlate with judge perplexity at Spearman +0.88 across nine policies.Random-16 reaches perplexity 237 versus 1530 for confidence top-16 at 28 rounds and wins on 99% of paired generations.

APPENDIX A PROOF OF THE ADAPTIVE COST IDENTITY

The proof constructs the target and approximate trajectory for every deterministic value-adaptive policy, then compares their likelihoods round by round. The KL divergence becomes the expected conditional total correlation accumulated across reveal rounds, with zero error exactly when every visited round is conditionally independent.

  • Policy trajectory: The adaptive policy’s reveal sets are determined recursively from the observed context, partitioning all coordinates along each trajectory.The construction defines C1 = ∅ and makes each St depend only on the values revealed in Ct.
  • Target law: The target law telescopes across rounds into the product of conditional laws for each reveal set.The chain rule expresses p(x) as the product of p(xSt | xCt) over the trajectory.
  • Approximate law: The approximate law replaces each round’s joint conditional distribution with the product of its conditional marginals.This construction remains valid even if the approximate law assigns mass outside the target support, because it stays positive wherever the target is positive.
  • Identity: KL divergence equals the expected sum of realized conditional total correlations over the adaptive reveal rounds.The tower property converts each realized information density into conditional total correlation given the visited history.
  • Identity: Zero divergence holds exactly when every visited reveal round has zero conditional total correlation almost surely.Nonnegativity of each summand makes the equality condition pointwise over all rounds reached with positive probability.
  • Markov-chain schedule: For order-m Markov chains, revealing central m-blocks across active segments creates conditional independence between segments and therefore zero-cost rounds.The schedule uses m rounds per stage, halves the largest active segment per stage, and finishes after logarithmically many stages.

APPENDIX C PROOFS FOR THE BERNOULLI WALK

The Bernoulli-walk proofs characterize both exact hierarchical sampling and the limits of adaptive zero-error policies. Bridge segments impose dependence unless they are degenerate, yielding logarithmic hierarchical depth but linear depth for contiguous scans at fixed accuracy.

  • Exact hierarchical schedule: ⌈log2(n + 1)⌉ rounds suffice for exact hierarchical sampling of the Bernoulli walk.With m = 1, each round reveals midpoints of all active segments, and the recurrence L(ℓ) = 1 + L(⌈(ℓ−1)/2⌉) gives the exact count.
  • Contiguous scans: Contiguous scans incur a round cost given by summed binomial entropies minus the batch size, because unrevealed increments are jointly fresh but marginal positions have binomial uncertainty.Applying the entropy bound to equal-size profiles gives a logarithmic-in-length lower-bound relation between fixed accuracy and rounds.
  • Bridge structure: Every nondegenerate bridge segment has no determined coordinate and strictly dependent coordinate pairs.Only segments whose endpoint increment sum is 0 or their full length are degenerate and fully determined.
  • Zero-cost policies: Zero-cost reveal sets contain at most one coordinate from each nondegenerate segment, while degenerate segments may be cleared entirely.This follows from conditional-total-correlation monotonicity and the bridge dependence characterization.
  • Policy reduction: Every exact adaptive policy can be reduced to a full-clearing policy that reveals no more rounds on any target trajectory.The reduction absorbs virtual policy rounds that are already revealed and clears currently degenerate segments during real rounds.
  • Lower bound: A zero-error policy’s expected rounds obey a logarithmic lower bound involving the maximum constant run of the realized walk.The per-trajectory bound is R(x) ≥ log2 n − log2(1 + maxrun(x)) − 1, which yields an expected log2 n − log2 log2 n scale.
  • Persistent dependence: Bulk coordinates in long nondegenerate segments retain a uniform positive conditional mutual-information lower bound.For middle-half positions, I(Xu; Xv | xC) ≥ c1; exhaustive computation reports a minimum of 0.085 over bridge parameters.

APPENDIX D PROOFS FOR UNIFORM RANDOM PERMUTATIONS

For uniform random permutations, conditional costs depend only on the number of remaining symbols and the batch size, reducing adaptive scheduling to an integer-composition problem. The proofs establish optimal batch ordering, fixed-round asymptotics, and the joint round-error frontier.

  • State reduction: The cost of a permutation round depends only on M unrevealed coordinates and batch size B, not on selected positions or observed values.Exchangeability makes the conditional law uniform over bijections from remaining positions to unused symbols.
  • Round refinement: Splitting any batch into smaller batches never increases performance cost, so the optimal hard-cap cost En,R decreases strictly with R until sequential revealing.The proof substitutes falling-factorial identities into the one-batch cost g(M,B).
  • Composition reduction: Every adaptive policy is bounded below by the minimum cost of an R-part composition, and a minimizing fixed composition attains that bound.Each trajectory uses at most R rounds, and its composition cost is at least En,R.
  • Optimal ordering: Putting larger batches first never increases cost, yielding nonincreasing optimal compositions.An adjacent-batch exchange changes the cost by a term whose sign follows from the monotonicity of h(u) = ln(1 − u)/u.
  • Fixed-round asymptotics: For fixed R, the normalized permutation cost converges to a continuous recursion whose optimizer has a product-form limiting profile.The recursion is CR = −ρR, and the tail satisfies uR ∼ 2/R.
  • Hard-cap frontier: For s = αn with 3s ≤ n, the hard-cap composition optimum equals the pair-first lower envelope and converges to 1/2 log2(1/(1−2α)).The limiting value crosses error ε at αε = 1 − 2^(-2ε)/2.

APPENDIX E PROOFS FOR BALANCED BINARY STRINGS

Balanced binary strings remain exchangeable after conditioning, so a round’s cost is determined by the remaining length, remaining number of ones, and batch size. Typical-state bounds control adaptive policies and produce squared-logarithmic depth estimates.

  • Exchangeable state: Conditioning on revealed values leaves unrevealed balanced strings uniform over completions with the correct remaining number of ones.The conditional distribution depends only on (M, k), making position selection irrelevant for a round’s cost.
  • Adaptive coupling: Every deterministic adaptive policy can be coupled to one uniform urn sequence of revealed values.At any history, whichever position is selected has probability k/M of revealing a one, so the revealed-value sequence has the uniform balanced-arrangement law.
  • Uniform control: The policy-dependent states form a subsequence of the policy-independent potential trajectory, enabling simultaneous typicality control across all policies.Typicality is established for every relevant remaining count M rather than conditioning on the event that a particular policy visits M.
  • Round-cost analysis: The conditional total correlation of a batch is a sum of mutual informations between each later revealed value and the preceding revealed-value count.Hypergeometric variance and scalar Pinsker bounds convert fluctuations in conditional Bernoulli parameters into round-cost lower bounds.
  • Typical-state bounds: For typical states with M at least logarithmic in n, batch costs admit quadratic lower and upper controls in the batch fraction.The proof tracks a potential combining batch fraction and remaining-size change to relate accumulated cost to the number of rounds.
  • Depth bound: The resulting lower bound yields a two-branch estimate for expected rounds as a function of error ε, with a logarithmic tail from the final M0 = ⌈C2 log2 n⌉ coordinates.The upper bound uses batches Bt = ⌈γMt⌉ until M falls below M0, then singleton reveals.
  • Upper bound: The fixed schedule’s accumulated cost is at most ε after choosing γ proportional to ε/log2 n, with the atypical-event contribution controlled separately.On the good event each non-singleton round is bounded quadratically in γ; the complementary event has probability at most n^-2.

APPENDIX F PROOFS FOR BINARY ONE-HOT BLOCKS

The appendix analyzes adaptive search in binary one-hot blocks, deriving a one-round information cost and proving linear lower and upper bounds on expected depth under bounded divergence.

  • One-round cost: A batch of k candidates in an unresolved block with M possible one-locations produces a one-hot conditional law whose parallelism cost is characterized by G(M,k).The selected vector is zero with probability 1−k/M and equals each selected unit vector with probability 1/M.
  • Per-round resolution: Every deterministic adaptive policy leaves at most one free candidate per round for each unresolved block.The proof uses a zero-answer simulation and conditional independence of the block locations.
  • Per-round resolution: A block resolves with probability at most the batch-dependent bound, because batches smaller than M−1 resolve only when they contain the one.For k=M−1 or k=M, resolution is certain.
  • Depth bounds: If divergence is at most ε, the expected number of rounds satisfies d ≥ c m/(1+ε), while a one-candidate-per-round schedule gives D0 ≤ m.The lower bound follows by splitting on whether H=⌈2d⌉ is at most m/8; the upper schedule has zero conditional total correlation in every round.
  • Depth bounds: For blocks of length L and count b, Dε is at least c min{L,b/(1+ε)}, while the zero-cost schedule terminates within L rounds.Choosing L ≍ n^α and b ≍ n^(1−α) yields depth of order n^α for 0 < α ≤ 1/2.

APPENDIX G PROOF OF GENERIC MAXIMAL ZERO-ERROR DEPTH

The appendix proves that, outside a measure-zero set of full-support distributions, conditional independences do not occur at any history. Consequently, zero-error adaptive policies must reveal one coordinate per round.

  • Generic dependence: Conditional independence constraints are polynomial equations in the atoms of the distribution.The equations express Xi ⊥ Xj | XC=xC for each value pair and conditioning assignment.
  • Generic dependence: A perturbation of the uniform distribution violates every such conditional-independence relation through a non-unit cross-ratio.The construction pδ(x) ∝ 1 + δ 1[xi=a0]1[xj=b0] makes the conditional pair law nonproduct.
  • Zero-error depth: For any full-support distribution outside the exceptional null set, zero divergence forces every reveal set to have size one.A reveal set containing at least two coordinates would imply pairwise conditional independence, contradicting generic dependence.
  • Zero-error depth: Generic full-support distributions therefore have R(x)=n and expected zero-error depth n under every admissible zero-divergence policy.The conclusion holds for every target x because every atom has positive probability.

APPENDIX H ENTROPY OF BERNOULLI SUMS

The appendix establishes local central-limit and entropy estimates for sums of independent Bernoulli variables, with explicit error bounds depending on the variance.

  • Local approximation: For a Bernoulli sum with variance σ^2≥2, its point probabilities uniformly approximate a discrete Gaussian with error at most CL/σ^2.The result is presented as a self-contained local central limit theorem with an absolute constant CL.
  • Local approximation: The characteristic-function proof controls the Gaussian approximation on small frequencies and bounds the remaining frequency ranges using variance-dependent decay.Taylor expansion gives a cubic remainder near zero, while separate ranges contribute exponentially or quadratically decaying terms.
  • Entropy estimate: The entropy of every Bernoulli-sum law with variance σ^2≥2 is within δ(σ) of the corresponding Gaussian entropy, with δ(σ)→0.The appendix permits δ(σ)=C(1+ln σ)σ^−1/3.
  • Entropy estimate: The entropy proof obtains the deficit by restricting to a central window, applying the local approximation there, and controlling the tails with Bernstein bounds.The tail probability and truncated second moment are bounded explicitly in terms of σ.
  • Entropy estimate: Across hypergeometric marginals, the numerical entropy deficit is much smaller, approximately 0.06/σ^2.This numerical observation is stated after absorbing an additional variance-dependent term into δ.
Loading 2608.25505v1…