PaperlayerView exact revision on arXiv

Source-linked AI summary

Randomization Beyond Deterministic Adaptivity in Parallel Sampling

Da Li, Bo Jin, Xiaopeng Wei

arXiv:2610.03335v1cs.ITmath.IT

TL;DR

Parallel samplers can miss joint conditional laws when coordinates within a batch are sampled independently, even with exact marginals. This paper compares deterministic value-adaptive policies with randomized fixed schedules under a hard three-round cap. On an explicit full-support binary family, randomization achieves exponentially small KL where deterministic policies have linear error.

  • Problem

    Independent sampling within parallel batches can miss the joint conditional law, and it is unresolved whether deterministic dependency-based lower bounds extend to randomized policies.

    Source: §I · p. 1

  • Method

    The paper analyzes exact-marginal reveal policies and constructs a uniform mixture of four fixed schedules for a known full-support binary target.

    Source: §I · p. 1, §II · p. 2

  • Results

    Every deterministic value-adaptive three-round policy has linear KL error, while the four-schedule mixture has exponentially small error.

    Source: §I · p. 1

  • Takeaways & Limitations

    The comparison shows that, at fixed depth on this family, randomized schedules can outperform deterministic value-adaptive policies by combining components that cover different selector-conditioned parts of the target.

    Source: §VII · p. 12

    The results concern known finite structures and exact conditional marginals.

    Source: §II · p. 2, §VII · p. 12

Abstract

from arXiv · show

We study parallel samplers that reveal each coordinate once and draw the coordinates of each batch independently from their exact conditional marginals. Under the same sampling interface and a hard three-round cap, randomization can improve accuracy beyond every deterministic policy that adapts its batches to previously observed values. For an explicit full-support binary family, the optimal deterministic adaptive forward Kullback-Leibler divergence grows linearly with the dimension, while a uniform mixture of four fixed schedules has exponentially small divergence. Only two independent fair bits are needed to select the schedule. We determine the asymptotic additive constant in the deterministic optimum and show that its optimal total variation tends to one quarter. An outward-rounded finite-sum certificate establishes divergence separation at dimension 389. The mechanism combines an irreversible first-batch dependence loss with posterior concentration in the randomized components. A density-coverage lemma describes how their mixture restores the target. A complementary noisy-matching family exhibits a growing round gap for nonadaptive schedules, although uniform random coordinate order still has linear mixture error. These results concern known finite structures and exact conditional marginals.

I. INTRODUCTION

Parallel samplers can incur dependence error even with exact conditional marginals, and it is unresolved whether deterministic lower bounds extend to randomized policies. For a known full-support binary family under a hard three-round cap, a four-schedule mixture sharply outperforms every deterministic value-adaptive policy.

I. INTRODUCTION

  • Every deterministic value-adaptive three-round policy has linear KL error on the fixed target family, while a mixture of four fixed three-round schedules has exponentially small error.Both use the same interface: exact one-coordinate marginals at actual histories, independent sampling within each batch, and completion within the cap.Source: §I · p. 1
  • Two fair scheduling bits suffice, and the optimal deterministic-adaptive total variation tends to 1/4; outward rounding certifies KL separation at dimension 389.The deterministic policies’ total-variation lower bound also holds for arbitrary product kernels.Source: §I · p. 2
  • The first batch creates an irreversible dependence loss for deterministic policies, while repeated observations let randomized schedules identify their designated selector and approach its conditional target law.The uniform mixture restores the selector prior.Source: §I · p. 2
  • A complementary noisy-matching family has a growing round gap for nonadaptive schedules, but uniform random coordinate order still has linear mixture error.The main family is exactly sampleable by deterministic adaptivity in four rounds, so its separation is specifically about accuracy at fixed depth.Source: §I · p. 2
  • Prior information-profile methods analyze ordered partitions or random allocations with prescribed batch sizes, whereas these schedules choose sets using the target’s dependence structure.The lower bound covers every deterministic reveal rule under a hard cap, unlike confidence-based decoding work focused on a particular rule.Source: §I · p. 2

II. MODEL AND INFORMATION ACCOUNTING

The model compares deterministic value-adaptive reveal policies with fixed schedules and randomized choices of schedules. Its information accounting decomposes forward KL into dependence costs and kernel mismatch, while the hidden scheduling seed changes the mixture’s divergence criterion.

II. MODEL AND INFORMATION ACCOUNTING

  • A reveal policy exposes each coordinate once, samples a batch independently from exact conditional marginals, and must complete within the hard round cap.A fixed schedule is an ordered partition chosen before sampling; a randomized fixed sampler independently draws that partition and hides the seed from the reported output.Source: §II · p. 2
  • For a deterministic reveal rule, forward KL decomposes into accumulated conditional total correlation plus scalar conditional-KL costs for any inexact kernels.Exact-marginal kernels minimize forward KL for each fixed policy rule.Source: §II · p. 3
  • With exact marginals, the adaptive cost identity makes forward KL equal the expected conditional total correlation along the reveal tree.At each history, the target’s joint batch law is compared with the product of its coordinate marginals.Source: §II · p. 3
  • For a hidden schedule seed, the mixture’s KL reduction from the average component KL is the expected posterior divergence between the prior seed law and its posterior given the output.This posterior divergence can exceed the seed entropy.Source: §II · p. 3

III. A THREE-ROUND SEPARATION FROM DETERMINISTIC ADAPTIVITY

The construction uses a full-support binary target whose selector chooses one of four directions in a repeated nine-coordinate structure. It contrasts deterministic three-round adaptivity with a uniform mixture of four fixed schedules, and also establishes exact deterministic sampling at four rounds.

III. A THREE-ROUND SEPARATION FROM DETERMINISTIC ADAPTIVITY

  • Two independent fair bits select the direction, and the target repeats the nine-coordinate data block conditionally independently given that selector.Each line law is formed by integrating out a hidden fair bit passed through three independent binary symmetric channels.Source: §III · pp. 3–4
  • Theorem 4 compares the optimal deterministic-adaptive three-round sampler with a uniform mixture of four fixed three-round schedules on a full-support binary law.The target repeats conditionally independent data blocks given a two-bit selector that chooses one of four directions.Source: §III · pp. 3–4
  • The theorem’s comparison concerns a hard three-round cap, while a deterministic adaptive policy samples the main family exactly in four rounds.The finite-remainder bound for the asymptotic result is established separately in the proofs.Source: §III · p. 4
  • Table I organizes unavoidable line costs by first-round occupancy, the local costs used in the deterministic lower-bound argument.The passage gives the table’s scope but not its individual entries.Source: Table I · p. 5

A. An irreversible first-batch information loss

The deterministic lower bound arises because the first data batch is fixed before any values are observed. Averaging unavoidable line costs over selector directions yields a minimum at first-round sets of size two, and the construction attains that cost.

A. An irreversible first-batch information loss

  • For R, total correlation is 2a + b, and the inequalities 2b < a < 3b follow without numerical logarithms; the cited passages do not specify a dependence-penalty or first-batch interpretation.Source: A. An irreversible first-batch… · p. 5
  • When a line has no first-round vertices, an unavoidable batch of two or three coordinates costs at least b in conditional total correlation.The minimum is b among the stated possible costs for an untouched line.Source: A. An irreversible first-batch… · p. 5
  • For every first-round data set C, the selector-averaged unavoidable cost is at least γ, with equality precisely when |C| = 2.The line costs apply pathwise even when later choices use observations from other replicas, because conditioning on the selector leaves line factors independent.Source: A. An irreversible first-batch… · p. 5
  • The matching construction reveals one fixed pair per replica initially and attains exact KL r(a + 5b)/4 by completing lines in later rounds.Across the four directions, the first slice has one initial pair and five untouched lines per replica.Source: A. An irreversible first-batch… · p. 6, Figure 1 · p. 6

B. Four fixed schedules

Four fixed schedules are indexed by a selector direction, with each schedule’s first slice independent for its designated selector. Their mixture uses first-slice observations to concentrate the posterior over that selector.

B. Four fixed schedules

  • A uniformly chosen direction selects a schedule whose first slice is independent under its matching selector but contains a correlated pair under any wrong direction.The sets partition the plane, and every line in direction s meets each set once.Source: B. Four fixed schedules · p. 6
  • After the first round, ϑs is the posterior probability that the selector equals s, and each middle-data marginal is at least ϑs times its conditional marginal under Z = s.Under that selector, middle data are independent across lines given the first slice; the final slice is conditionally independent and sampled exactly.Source: B. Four fixed schedules · p. 6
  • The schedule uses 3r, 3r + 2, and 3r scalar draws across its three rounds, while revealing Z first permits exact adaptive sampling in four rounds.Source: B. Four fixed schedules · p. 7

C. A sharp total-variation barrier

The section bounds overlap along deterministic reveal trees and uses bad-line counts to control the selector-slice contribution. A selector-first construction gives a total-variation upper bound of 1/4.

C. A sharp total-variation barrier

D. Attaining the selector-entropy offset

A first-round observation supports a maximum-posterior selector estimate that determines the second batch. The resulting policy attains the selector-entropy offset up to an explicit exponentially small bound.

D. Attaining the selector-entropy offset

IV. A FINITE-SCALE SEPARATION

Retaining exact middle-round kernels gives a finite-sum certificate at r = 43, earlier than the simpler bound’s threshold. The finite-scale results also show that the mixture can be worse at r = 1.

IV. A FINITE-SCALE SEPARATION

  • The finite-sum mixture figure is an upper bound rather than a measured mixture KL, with the finite sum and interval computation specified in Section C-A.The two middle decimals are rounded outward.Source: §IV · p. 9
  • At r = 1, mixture KL is 0.22126627770629 . . ., while optimal deterministic adaptive KL lies in [0.0966123125095, 0.0966123125335].Source: §IV · p. 9
  • At r = 1, the 81 combinations of distinct transversal choices give mixture KL between 0.2051962 and 0.2405884; the reported main-construction numerics use (17).The r = 43 certificate does not identify the earliest separation.Source: §IV · p. 9
  • At r = 43, the finite-sum bound certifies divergence separation; the simpler bound 3(3r + 2)βr first falls below rγ − log 4 at r = 135.The marked r = 43 comparison uses outward rounding; other plotted values are floating-point evaluations.Source: §IV · p. 9, Figure 2 · p. 10
  • The finite adaptive optimum is computed over 311 = 177147 partial assignments, with 4017157 second-stage actions and 48650978 action–outcome branches evaluated.Source: §IV · p. 10

V. MIXTURES AND COVERAGE

The section explains how mixtures of fixed schedules can recover a target by covering different selector slices, even when individual components concentrate on one slice. It gives a finite-library characterization of asymptotic mixture error and applies it to the four-schedule construction.

V. MIXTURES AND COVERAGE

  • The density-coverage lemma compares each component with its ideal target reweighted by selector coverage, and describes how mixing components can restore the target.In the main construction, each seed concentrates almost all its mass on one selector slice.Source: §V · p. 10
  • For a fixed finite library with vanishing component error, optimal forward KL tends to the minimum coverage objective; asymptotically exact mixtures exist exactly when the target coverage vector is feasible.The four-schedule library recovers the selector prior with uniform weights, while unequal weights leave an error floor.Source: §V · p. 11
  • For the four schedules, uniform weights recover the selector prior, whereas unequal weights leave a nonzero error floor.This characterization is specific to the four-schedule library; broader posterior-based covers are treated separately.Source: §V · p. 11

VI. A COMPLEMENTARY GROWING-ROUND SEPARATION

A noisy-matching family separates structured randomized mixtures from deterministic nonadaptive schedules over growing round budgets. The section also contrasts this with uniform coordinate allocation and with content-adaptive sampling.

VI. A COMPLEMENTARY GROWING-ROUND SEPARATION

  • The noisy-matching family gives a growing round gap for nonadaptive schedules, while a three-round randomized construction attains fixed accuracy for all sufficiently large n.The construction uses k −1 fair scheduling bits; the supplied theorem statement does not include the full quantitative bound.Source: §VI · pp. 11–12
  • The noisy-matching family has a uniform selector Z over V, with nonzero directions inducing perfect matchings whose edges carry binary-symmetric-channel noise.When Z = 0, the data bits are independent and fair.Source: §VI · p. 11
  • A deterministic content-adaptive policy samples this family exactly in three rounds.The section's growing round lower bound concerns nonadaptive schedules, not content-adaptive ones.Source: §VI · p. 11
  • A common final-data test makes the uniform-order lower bound persist even when schedules mix over batch sizes.The uniform allocation distributes all n + k coordinates across at most T blocks.Source: §VI · p. 11
  • For fixed accuracy, Corollary 9 establishes a round lower bound for deterministic fixed schedules, contrasted with the three-round randomized construction.The bound's expression is not present in the supplied passage.Source: §VI · p. 12

VII. DISCUSSION

The discussion distinguishes the fixed-depth accuracy separation from the nonadaptive round separation and explains how mixtures cover target mass across selector slices. The appendices give coverage bounds, posterior-based cover conditions, and dual certificates.

VII. DISCUSSION

  • On the nine-point family, an irreversible first-batch loss limits deterministic three-round accuracy, while randomized schedules approach selector-conditioned laws whose mixture recovers the target.On the matching family, the growing round lower bound applies to nonadaptive partitions; observing the selector removes that obstruction.Source: §VII · p. 12
  • The constructions use known finite structures and exact marginals; balanced covers, their discovery from estimated conditionals, and expected-round budgets remain open questions.A pointwise perturbation bound separates oracle error from density deficit.Source: §VII · p. 12

APPENDIX A COVERAGE BOUNDS AND MIXTURE OPTIMIZATION

  • For an uncovered selector slice of mass νz, forward KL is at least νz log(1/ε) − log 2 when its mixture probability is at most ε, and is infinite when ε = 0.Corollary 10 characterizes asymptotic exactness in KL or TV for a fixed finite library.Source: Appendix A · p. 12

A. Posterior-based covers

  • Posterior-based covers assume shared one-coordinate marginals and at least one good candidate in each revealed-selector fiber; distinct full-support laws have affinity strictly below one.Under these conditions, Proposition 11 applies the density-coverage lemma.Source: A. Posterior-based covers · p. 13

B. Dual certificates

  • When every selector row is covered, the mixture optimization has a finite convex optimum with a dual representation, and a selector-only test lower-bounds every library mixture.Coverage vectors need at most rank(M) columns, but this does not establish finite-r sampler optimization or template discovery.Source: B. Dual certificates · p. 13

APPENDIX B PROOFS FOR THE MATCHING FAMILY

These proofs bound matching loss under reveal schedules and certify the adaptive and mixture calculations. They also specify a sufficient condition for combining density coverage with predictor accuracy.

APPENDIX B PROOFS FOR THE MATCHING FAMILY

  • A fixed schedule incurs Iη for each same-round matching edge, while cross-round edges incur no factorization loss.The permutation-exposure martingale bounds deviations in the number of same-round edges.Source: Appendix B · p. 14, A. Uniform random order · p. 15
  • For nontrivial selectors, half the eligible normals are crossing schedules, and the crossing candidate’s posterior is (1 + Λ)^−1 before the last round completes its matching exactly.Each schedule uses three actual histories.Source: Appendix B · p. 14

A. Uniform random order

  • Every nonzero matching has at least n/(8T) same-round edges except on a schedule set of probability at most (n−1)e−n/(192T^2).The bound is independent of the block-size profile.Source: A. Uniform random order · p. 15

A. The finite-sum upper bound

  • At r = 43, the mixture upper bound is 2.71196872075260781480999681773394853516183 and the deterministic lower bound is 2.7680350773111076634832933261617088629238.The bounds use 42-digit directed decimal arithmetic with outward rounding.Source: A. The finite-sum upper bound · p. 16

B. Exact laws and adaptive dynamic programming

  • The adaptive calculation includes all reveal sets and observed values, so its recurrence retains fully value-dependent continuations.The partial assignment and remaining round budget determine the conditional target and possible continuations.Source: B. Exact laws and adaptive dynamic… · p. 17

C. Certified logarithms

  • The logarithm certificate uses N = 40 and rounds required integer logarithms outward to the grid 10^-12Z.Power-of-two range reduction encloses positive rational logarithms.Source: C. Certified logarithms · p. 17

D. An integer recurrence covering every adaptive action

  • The exact three-round numerator interval is 1582896128156416–1582896128548768, with common denominator 16384000000000000.The 311 states distinguish both the revealed coordinate set and its values, including value-dependent choices and selector/data interleavings.Source: D. An integer recurrence covering… · p. 18

A. A sufficient pointwise predictor condition

  • A density-cover deficit and predictor deficit can be added, but exponential accuracy requires the predictor deficit B to be correspondingly small.Full support alone gives no quantitative lower bound on approximate probabilities, and an absolute marginal-error bound does not imply the condition.Source: A. A sufficient pointwise predictor… · p. 18

Related papers

Loading 2610.03335v1…