Conditional Total Correlation and the Serial Depth of Adaptive Parallel Sampling

• URL: http://arxiv.org/abs/2608.25505v1
• Date: Wed, 26 Aug 2026 08:16:24 GMT
• Title: Conditional Total Correlation and the Serial Depth of Adaptive Parallel Sampling
• Abstract summary: We show that a pseudo-cost distinguishes deployed decoding rules and that its policy rankings agree closely with the quality of self-sampled outputs.<n> 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.
• Score: 6.705150928866435
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Finite-Probe Total-Variation Certificates for Finite-Basis Drifting Models [1.2072720711193232]
  We describe a frozen measurement system for integrable antisymmetric interactions and absolutely continuous laws in a declared finite density basis.<n>For Gaussian-RBF interactions, a global envelope supports distribution-free and empirical-Bernstein radii without truncation.<n>We characterize random-probe observability by a population Gram matrix, identify rank and symmetry degenera, and prove large-bandwidth collapse toward mean matching.
  arXiv  Detail & Related papers  (2026-08-03T00:00:40Z)
• One-step lowest-variance selection in a Gaussian random-field model motivated by masked diffusion: Total correlation and a square root collision threshold [8.230831152671708]
  Motivated by confidence-guided parallel unmasking in masked discrete diffusion, we study a single selection step in a stylized Gaussian random-field model.<n>Results provide a rigorous confidence-geometry and spatial correlation jointly shape one-step-based selection in masked discrete diffusion.
  arXiv  Detail & Related papers  (2026-07-20T03:56:34Z)
• A Note on Stability for Orthogonalized Matrix Momentum with Client Sampling [7.035974899001363]
  We derive a finite-round upper-tail guarantee from a coupled-neighbor recursion stability and a weighted concentration step.<n>A one-dimensional counterexample shows why a gap, smoothing, or regularity condition is necessary.
  arXiv  Detail & Related papers  (2026-06-01T05:36:26Z)
• SEED: Targeted Data Selection by Weighted Independent Set [76.68391670109433]
  We develop a robust and scalable data selection pipeline dubbed SEED.<n>SEED consistently outperforms state-of-the-art methods on instruction tuning, visual instruction tuning, and semantic segmentation.
  arXiv  Detail & Related papers  (2026-05-15T07:26:54Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  A fundamental and long-standing challenge is their efficient approximation.<n>We develop a linear-space algorithm that requires $P(|hatboldsymbol-boldsymbol|_2geq)leq $ for all commonly used semi-values.<n>Our algorithm allows explicit minimization of the mean square error for each specific utility function.
  arXiv  Detail & Related papers  (2026-04-09T16:38:14Z)
• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  We consider the problem of contextual online RLHF with general preferences.<n>We adopt the Generalized Bilinear Preference Model to capture preferences via low-rank, skew-symmetric matrices.<n>We prove that the dual gap of the greedy policy is bounded by the square of the estimation error.
  arXiv  Detail & Related papers  (2026-02-26T15:27:53Z)
• Analysis of Hessian Scaling for Local and Global Costs in Variational Quantum Algorithm [0.42970700836450487]
  We quantify the entrywise resolvability of the Hessian for Variational Quantum Algorithms.<n>We show two distinct scaling regimes that govern the sample complexity required to resolve Hessian entries against shot noise.
  arXiv  Detail & Related papers  (2026-01-31T15:49:23Z)
• Adaptive Annealed Importance Sampling with Constant Rate Progress [68.8204255655161]
  Annealed Importance Sampling (AIS) synthesizes weighted samples from an intractable distribution. We propose the Constant Rate AIS algorithm and its efficient implementation for $alpha$-divergences.
  arXiv  Detail & Related papers  (2023-06-27T08:15:28Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  This paper considers the problem of online clustering with bandit feedback. It includes a novel stopping rule for sequential testing that circumvents the need to solve any NP-hard weighted clustering problem as its subroutines. We show through extensive simulations on synthetic and real-world datasets that BOC's performance matches the lower boundally, and significantly outperforms a non-adaptive baseline algorithm.
  arXiv  Detail & Related papers  (2022-02-09T06:05:05Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
  arXiv  Detail & Related papers  (2021-05-03T16:36:27Z)
• Consensus-Guided Correspondence Denoising [67.35345850146393]
  We propose to denoise correspondences with a local-to-global consensus learning framework to robustly identify correspondence. A novel "pruning" block is introduced to distill reliable candidates from initial matches according to their consensus scores estimated by dynamic graphs from local to global regions. Our method outperforms state-of-the-arts on robust line fitting, wide-baseline image matching and image localization benchmarks by noticeable margins.
  arXiv  Detail & Related papers  (2021-01-03T09:10:00Z)
• Fused-Lasso Regularized Cholesky Factors of Large Nonstationary Covariance Matrices of Longitudinal Data [0.0]
  smoothness of the subdiagonals of the Cholesky factor of large covariance matrices is closely related to the degrees of nonstationarity of autoregressive models for time series and longitudinal data. We propose an algorithm for sparse estimation of the Cholesky factor which decouple row-wise.
  arXiv  Detail & Related papers  (2020-07-22T02:38:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.