PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Tianyi Wu

arXiv:2610.13924v1cs.LGcs.ITmath.IT

TL;DR

Parallel samplers lose within-round dependence when they draw multiple coordinates independently from frozen exact conditional marginals, raising the question of how schedule-averaged and output-law KL differ in required rounds. The paper analyzes these criteria and proves that, on the balanced slice, their expected round costs differ sharply: Θ_ε((log n)^2) versus (e^−ε + o(1)) log_2 ln n.

  • Problem

    Parallel sampling commits multiple coordinates from frozen exact conditional marginals, and the paper asks how many rounds are needed under schedule-averaged versus output-law KL.

    Source: §1 · p. 1

  • Method

    The paper analyzes mixtures of schedules and causal randomized policies, using a count-state recursion to characterize balanced-slice success under a round cap.

    Source: §1 · p. 2, §3 · p. 6

  • Results

    The balanced-slice expected cost is Θ_ε((log n)^2) under H but (e^−ε + o(1)) log_2 ln n under F.

    Source: §1 · p. 3, §3 · p. 7

  • Takeaways & Limitations

    On the balanced slice, the output-law criterion permits double-logarithmic rounds, while the schedule-averaged criterion retains quadratic-logarithmic order.

    Source: §1 · p. 3, §3 · p. 7

    Small average prediction error alone does not recover the exact-oracle profile rate on the balanced slice.

    Source: §5 · p. 15

Abstract

from arXiv · show

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$ is $\Theta_\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.

1. Introduction

The paper compares schedule-averaged KL with the KL of the schedule-averaged output law for parallel sampling, where rounds discard dependence by drawing coordinates independently from frozen exact conditional marginals. On the balanced slice, the output-law criterion permits logarithmic-in-logarithm round costs, unlike the schedule-averaged criterion’s Θ_ε((log n)^2) order.

1. Introduction

  • In the four-bit example, relabelling leaves H ≈ 0.519 unchanged but lowers F from the fixed schedule’s error to ln(4/3) ≈ 0.288 by spreading valid-string mass equally.Relabelling repairs unequal weighting among valid strings, not the probability of an invalid output.Source: §1 · p. 2, Figure 1 · p. 2
  • The comparison concerns schedules drawn before sampling, with every scheduled round charged and exact conditional marginals frozen at each round’s start.The table summarizes least rounds by design, criterion, and cost; the introduction notes extensions to two additional target classes.Source: §1 · p. 2, Table 1 · p. 3
  • Prior analyses generally bound H or the KL between whole-run laws, whereas Feng et al. (2025, Thm. 4.4) give an Ω(n) F lower bound for random-position masking on a hidden Markov target.The paper positions its balanced-slice result as a randomized-policy round-complexity comparison.Source: §1 · pp. 2–3
  • The balanced-slice output-law cost is (e^−ε + o(1)) log_2 ln n in expected rounds, while the schedule-averaged cost is Θ_ε((log n)^2).The output-law order also holds for the least hard cap up to an additive O_ε(1); the schedule-averaged order follows from prior work.Source: §1 · pp. 2–3

2. Model

The model separates schedules, mixtures, and causal adaptive policies while charging rounds in which independent draws use exact conditional marginals frozen at round start. It distinguishes schedule-averaged divergence, output-law divergence, scheduled mean, executed mean, and hard cap.

2. Model

  • Each round commits a nonempty block of unrevealed coordinates using independent draws from exact conditional marginals frozen at the round’s start.There is no joint draw, lookahead, resampling, or repair, so within-round dependence is ignored.Source: §2 · p. 3
  • On the balanced slice, each block’s number of ones is Bin(b, j/M), moving the count state from (M, j) to (M−b, j−X).The valid target strings have a fixed total count, and the remaining quota determines each unrevealed coordinate’s conditional probability.Source: §2 · pp. 3–4
  • A schedule is an ordered partition into blocks; a finite mixture draws a labelled schedule before sampling, while a causal policy may choose each round’s coordinates from the seed and committed history.Every scheduled round is charged, including rounds after an infeasible prefix; adaptive policies also charge empty and closing rounds.Source: §2 · p. 4
  • For a mixture, H averages KL(p∥q_U) over schedules, whereas F is KL from p to the mixture’s output law; joint convexity gives F ≤ H.The schedule-averaged criterion is not a worst-case bound, and the inequality alone does not establish whether F needs fewer rounds.Source: §2 · p. 4
  • The model distinguishes scheduled mean C(µ), executed mean Eτ, and a hard cap r; a mixture has Eτ = C(µ), while a policy under cap r has Eτ ≤ r.The output divergence splits into leakage outside the target support and shape within it; relabelling removes the shape term on the balanced slice but not leakage.Source: §2 · pp. 4–5

3. The balanced slice: separation and an exact converse

On the balanced slice, output-law divergence is governed by the probability of reaching the valid count state, and an exact count-state recursion characterizes the best success probability under any round cap. This yields a double-logarithmic output-law round cost and a quadratic-log schedule-averaged cost.

The balanced slice: separation and an exact converse

  • The square-root ladder controls accumulated failure probability before a singleton tail, giving an output-law upper bound with O_ε(log log n) rounds.Its rung widths control conditional variances; the final singleton rounds do not fail.Source: §3 · pp. 5–6
  • The recursion is optimal even against policies using the full sampled history, because the next count-state law depends on the policy’s choice only through the block size.An empty round cannot improve the recursion’s success probability.Source: §3 · p. 6
  • The success envelope halves its exponent each round, and summing survival-probability tails gives the expected-round lower bound even when runs can end early.A mixture attains the leading mean-cost coefficient by mixing a near-exact ladder with a cheap one-round schedule that usually fails; failed runs still count.Source: §3 · pp. 6–7
  • For every round cap r, the minimum output divergence over causal randomized policies is exactly −ln G_r(n, k), where G_r is the maximal probability of reaching (0, 0).A maximizing count-state rule attains the value when applied to coordinates in a uniformly random order.Source: §3 · pp. 6–7
  • The least expected cost under F ≤ ε is (e^−ε + o(1)) log_2 ln n, while LH(n, ε) = Θ_ε((log n)^2).The output-law mean lower bound applies to causal randomized policies, and the corresponding double-logarithmic hard cap is attainable.Source: §3 · pp. 5, 7
  • At ε = ln 2 and n = 65536, LH > 26.20 is kernel-checked and a kernel-checked relabelled profile has LF ≤ 11; a searched five-round witness is not shown optimal.The figure’s plotted fixed-schedule and relabelled-profile lengths are upper bounds, not optimality claims, and no rate is fitted.Source: §3 · pp. 7–8, Figure 2 · p. 8

4. Beyond the slice: two extensions

The extensions replace survival-based analysis with lattice geometry for the full-support target and random retention for bounded-weight slices. They preserve the separation between schedule-averaged and output-law costs while addressing settings where relabelling alone cannot control output shape.

4. Beyond the slice: two extensions

  • The balanced-slice relabelling argument does not extend directly: full support has count-shape error, while unequal weights leave residual within-slice shape error.For full support there are no invalid outputs; for weighted slices, survival no longer determines output-law divergence.Source: §4 · p. 8, §4.1 · p. 8, §4.2 · p. 11

4.1. Full support: lattice geometry replaces survival

  • (e^-ε/2+o(1)) log2 log2 n is the sharp scheduled-mean output-law cost for the full-support Beta(1,1)–Bernoulli target.The construction uses rare exact floors, so this is a mean-cost result; the hard-cap constant remains open.Source: §4.1 · pp. 8–10
  • On the full-support target, level grids can grow by squaring for one profile, while randomized bands permit fourth-power growth and a recursive mixture.The mixture controls mass with an ideal comparison law, then uses an exact floor to obtain forward-KL control; dilution supplies the e^-ε factor.Source: §4.1 · pp. 9–10

4.2. Bounded weights: random retention replaces relabelling

  • (e^-ε+o(1)) log2 ln n is the least expected output-law cost for bounded-weight slices, while the schedule-averaged cost remains Θ((ln n)^2).The bounds hold uniformly for bounded weight ratios and quota fractions bounded away from zero and one.Source: §4.2 · p. 11
  • Bounded-weight upper bounds randomize which coordinates are retained, comparing each executed round with a reference law that completes the kept set exactly.The nested kept-set schedule yields a hard cap of log2 ln n + OΛ,κ0(1 + ε^-2) rounds; growing-n dilution improves the mean without lowering that cap.Source: §4.2 · pp. 12, 14

5. Scope, limits and what the separation shows

The guarantees concern an exact-marginal interface and count rounds rather than computation. The paper does not claim practical speedups or general learned-model guarantees.

5. Scope, limits and what the separation shows

  • The theory assumes exact oracles in one interface; lookahead or joint draws can outperform that class at small n.The reported costs count rounds, not computation.Source: §5 · pp. 14–15
  • No guarantee is claimed beyond the controlled learned-model tests, and those tests provide no population guarantee.The paper also leaves open the full-support hard-cap constant and sharp rates for vanishing tolerances.Source: §5 · p. 15

AI Disclosure

The authors disclose extensive generative-AI assistance across theory, proofs, formalization, experiments, literature review, and manuscript preparation. They describe human review and additional checks within documented scopes.

AI Disclosure

  • Generative-AI tools assisted with theoretical claims, proofs, Lean 4 formalization, experiments, literature review, and manuscript preparation.The authors state that they take responsibility for the final content, including AI-assisted artifacts.Source: AI Disclosure · p. 19

Appendix B, after the proof of (a)

  • Theorem IC2 is summarized as showing that a first-exhaustion identity forces √n rounds.The appendix guide identifies Appendix N as the location of this result.Source: Appendix B · p. 22

Appendix A. Reference material for the main text

Appendix A collects reference tables and notation, including a table that organizes result classes, criteria, costs, and evidence status. Its reference material also highlights that mixing in the one-round schedule reduces the leading scheduled-mean cost by a factor of e^-ε.

Appendix A. Reference material for the main text

  • Appendix A collects the classes-and-costs table, one-round growth table, and notation index.The notation index gives symbol definitions and flags symbols with alternate meanings.Source: Appendix A · p. 22, Table 4 · p. 25
  • Table 2 organizes classes, criteria, and costs, distinguishing scheduled mean, executed mean, hard cap, and per-run length alongside evidence status.It also summarizes finite-regime evidence and scope qualifications for the target classes.Source: Table 2 · p. 23
  • Mixing in the one-round schedule multiplies the leading term of scheduled mean cost by e^-ε, while the mixture also has rare paths of length n.The two profiles have the same path length on every run; the mixture’s cost is its scheduled mean.Source: Appendix A · p. 24

Appendix B. Proofs of Lemma 1 and Theorem 2(a),(b)

The appendix reduces schedule divergence and output-law divergence to success probabilities and count-state dynamics. It proves a logarithmic-squared lower bound for schedule-averaged cost and gives a relabelled ladder construction with double-logarithmic length for output-law error.

Appendix B. Proofs of Lemma 1 and Theorem 2(a),(b)

  • For legal count states, each round’s count update is binomial, and the schedule’s divergence depends only on its block-size profile.Permutation invariance of a uniformly relabelled schedule makes its output law constant on the balanced slice, linking divergence to success probability.Source: Appendix B · pp. 27–28

A pointwise mixture bound

  • At fixed ε, any feasible schedule mixture has scheduled mean cost of order at least (ln n)^2, by averaging divergence bounds and applying Cauchy–Schwarz across rounds.Small per-schedule divergence forces reveal fractions to sum to nearly H_n while their squared fractions remain O(1).Source: A pointwise mixture bound · pp. 28–29
  • The mixture lower bound follows because the per-schedule bounds are affine in divergence and Cauchy–Schwarz relates the averaged reveal fractions to scheduled mean cost.The resulting bound also yields C(µ) ≥ H_n − 2ε.Source: A pointwise mixture bound · p. 29
  • A uniformly relabelled ladder profile reaches output-law divergence at most ε in at most ⌈log2 log2 n⌉ + 8K rounds, with K chosen from the desired failure probability.Its success probability is at least 1 − δ; relabelling makes the output law exchangeable, so divergence is −ln(success).Source: A pointwise mixture bound · pp. 29–30

Appendix C. Proof of the fixed-schedule upper bound in Theorem 2(c)

The appendix bounds the divergence between sampling without replacement and the independent draws of a round, then sums that bound over a fixed schedule. A geometric schedule therefore achieves output KL at most ε with O((ln n)^2/ε) rounds.

Appendix C. Proof of the fixed-schedule upper bound in Theorem 2(c)

  • A block of b coordinates contributes at most b(b − 1)/(2(M − 1)(M − b + 1)) divergence when M coordinates remain.This compares the target’s without-replacement block law with the round’s independent Bernoulli product law.Source: Appendix C · p. 30
  • Choosing α = ε/ln n gives a fixed geometric schedule with KL(p∥qU) < ε and length at most (ln n)(ln n + 2)/ε + 1.The point mass on this schedule has schedule-averaged divergence equal to its output divergence.Source: Appendix C · p. 31
  • For fixed ε, a geometric schedule achieves KL(p∥qU) ≤ ε with length at most (1 + o(1))(ln n)^2/(2ε).The construction uses blocks of size approximately α times the remaining coordinates, followed by singleton rounds.Source: Appendix C · p. 31

Appendix D. Proof of the survival envelope

The appendix proves a survival envelope for the balanced count-state recursion and uses it to bound finite-horizon success and sampler costs. It also identifies the exact optimal output divergence at a round cap and transfers success-threshold results to total variation.

Appendix D. Proof of the survival envelope

  • At legal state (M, j), the survival recursion obeys Gr(M, j) ≤ min{1, Ar(d + 1)^−αr}, with Ar < 36 and αr = 2^−r.Here d is the minority count; the exponent halves at each round in the induction.Source: Appendix D · p. 31, Plan · p. 31

Plan.

  • The survival-envelope proposition is informative only at sufficiently large n, and its statement concerns the recursion itself.The appendix says sampler bounds follow through the tower argument or, for fixed schedules, its elementary special case.Source: Plan · p. 33

Proofs of Lemma 3(b), Theorem 4(a) and Corollary 6(c), with an outline of the rest

  • The exact least output KL at cap r is −ln Gr(n, k), attained by a maximizing count-state policy applied in a uniformly random coordinate order.The recursion bounds success for every causal policy; the attaining policy is complete within r rounds on every seed and word.Source: Proofs of Lemma 3(b), Theorem 4(a) and… · p. 34
  • A valid output completed within s rounds requires the count state to reach (0, 0), whose probability is at most Gs(n, k).Summing the resulting tail lower bounds gives a lower bound on expected executed rounds.Source: Proofs of Lemma 3(b), Theorem 4(a) and… · p. 34
  • The envelope implies least expected executed cost at least e^-ε log2 ln(k + 1) − 2.672 under output KL tolerance ε.The corresponding least expected scheduled mean has the same stated lower bound.Source: Proofs of Lemma 3(b), Theorem 4(a) and… · p. 35

Total variation.

  • For relabelling-invariant output laws, total variation from the balanced target equals one minus the probability of landing on the balanced slice.Thus the hard-cap optimum in total variation is 1 − Gr(n, k), and success thresholds translate using ε = −ln(1 − δ).Source: Total variation · p. 35

E.1. Uniform window in Theorem 4(b)

This section gives round-cap bounds for balanced fixed-count sampling, including a single relabelled profile within a constant factor of the best causal randomized policy, and a logarithmic-in-logarithmic depth lower bound for fixed profiles on the Beta(1,1)–Bernoulli target. Its last-round edge bound constrains only the final round.

E.1. Uniform window in Theorem 4(b)

  • 2^-r ln(k + 1) - ln 36 < -ln G_r(n, k) ≤ 2^-r ln k + ln 48 gives an absolute additive window uniform in r and n.At every hard cap, one uniformly relabelled fixed profile is within a factor 1728 of the best causal randomized adaptive policy in terminal success; this concerns output KL, not operational mean cost.Source: §E.1 · p. 36, Conclusion · p. 37
  • A uniformly relabelled square-root ladder with at most r blocks witnesses the upper bound, but its ln 48 term cannot certify tolerance ε < ln 48.The final block commits all remaining coordinates; the ladder of Theorem 2(b) instead stops bulk rounds at 8Kδ unrevealed coordinates and commits them as singletons, with failure probability at most δ.Source: §E.1 · p. 36

F.1. One relabelled profile: the lower bound

  • log2 ln n − O(1) rounds are necessary for a single relabelled profile to achieve any fixed tolerance on the Beta(1,1)–Bernoulli target.The lower-bound chain limits each successive level to at most quadratic growth in the preceding level.Source: §F.1 · p. 39, Target mass · p. 42

Plan of the lower bound.

  • A gap-set test yields the lower bound by showing that the sampler places much less mass than the target on selected edge intervals, then applying data processing.The proof uses a conditional variance bound and Chebyshev’s inequality; convex-order comparisons control the sampler’s mass near the edge.Source: Target mass · p. 40

Proposition L (last-round edge bound, all policies).

  • In the final round, W is at least a count that stochastically dominates Bin(n−˜m, 1/(2+˜m)); the bound follows by taking expectations and applying data processing to {W ≤ j}.The argument uses that kl(a∥·) is decreasing on [0, a].Source: Proposition L (last-round edge bound,… · p. 43

F.3. One relabelled profile: the matching upper bound

This section develops round-cost bounds and constructions for schedule-averaged and output-law KL criteria on balanced fixed-count and Beta(1,1)–Bernoulli targets, including finite mixtures and a single relabelled profile. It also treats lower bounds for broader policy classes and identifies adaptive-policy questions that remain open.

F.3. One relabelled profile: the matching upper bound

  • RPROF_F(n, ε) = log2 log2 n + Oε(1) for fixed ε > 0, matching the lower bound up to Oε(1).The result is for one profile, one predrawn uniform relabelling, the exact oracle, forward KL, and the target with α = β = 1; the finite bound has an astronomical constant, and no matching bound is claimed for adaptive schedules or other α, β.Source: §F.3 · p. 43, Schedule · p. 49

Plan of the upper bound.

  • The proof bounds output KL by one-round log-likelihood terms, then replaces later-round posterior pullbacks with count laws at a cost controlled by envelope variation and Kolmogorov distances.Geometrically growing schedule levels make the later-round distance sum O(1/c), so the replacement costs O(1/c).Source: Plan of the upper bound · p. 43

Lemma U1 (pointwise Jensen chain).

  • A pointwise Jensen chain bounds terminal log-likelihood by accumulated one-round terms averaged under posterior kernels pulled back from the target.The posterior kernels are monotone because the round kernel is totally positive of order two, and they do not increase function variation.Source: Lemma U1 (pointwise Jensen chain) · pp. 44–45

Lemma U5 (edge pointwise bounds).

  • For edge and intermediate states, one-round log-likelihood ratios admit explicit bounds: at the edge d(y) ≤ 2r, while the other bound depends on r/χ(y) and ln(16χ(y)/r).These bounds apply under the conditions stated in Lemma U5, including c ≥ 8r + 4.Source: Lemma U5 (edge pointwise bounds) · p. 45

Pointwise bound.

  • In the bulk, a local-limit lower bound on the one-round output probability is obtained by summing binomial mass over a window of integer states around χ(y) − 1.The window argument yields a bound of the form 1 − 72r/σ for the ratio of the one-round law to the uniform output law.Source: Lemma U5 (edge pointwise bounds) · pp. 45–46, Pointwise bound · p. 46

Summation.

  • The one-round Kolmogorov distance is strictly below 1, and the envelope’s variation and mean bounds make its contribution summable across the schedule.The envelope variation is at most 4r + ln(16Ξ) + 1; the mean bound combines κ log r, √κ, and 1/c terms.Source: Summation · pp. 46, 48

Schedule.

  • The schedule uses ε-dependent design slots and geometrically growing levels; its round count is at most log2 log2 n + 8cε.If the final growth step would be too small, it merges the last step into a final round; the construction ensures F ≤ ε.Source: Schedule · pp. 48–49

F.4. The schedule-averaged criterion

  • The next subsection defines the schedule-averaged criterion for finite predrawn mixtures of full labelled schedules, using expected schedule length and expected conditional KL.It denotes the least expected length among mixtures whose expected schedule-averaged KL is at most ε by LH(n, ε).Source: §F.4 · p. 49
  • For the balanced fixed-count target, the schedule-averaged criterion requires Θε((ln n)^2) rounds at fixed ε > 0, while zero divergence requires n rounds.A labelled profile committing b = min{n + 2 − c, max(1, ⌊αHc⌋)} coordinates at level c gives divergence below ε with at most min{n, 2 + (3Tn + 2)/αH} rounds.Source: §F.4 · p. 49

F.5. Mixtures: the common lower bound

  • A single test set of thin neighborhoods around reduced fractions with small denominators supplies a lower-bound argument shared by every mixture component.Profile-dependent gap sets alone do not provide a lower bound because atoms of one component can fill another component’s gaps.Source: §F.5 · p. 50

Part (c).

  • For components capped at R rounds, the common-test-set divergence lower bound is at least n^(3/(4R−1)−η′) for every η′ > 0 and all sufficiently large n.For R = 2, the stated lower bound is n^(1/5−η′).Source: The obstruction · p. 51

Part (a).

  • Every finite predrawn mixture with output divergence at most ε must put positive weight on components longer than R0(n), yielding a cost lower bound of 1 + R0(n)ηn when ηn > 0.The proof compares target and mixture mass outside the common test set, then uses that every component with at most R0(n) rounds has a forced jump.Source: The obstruction · p. 51, Part (a) · p. 53

The obstruction.

  • For every ε ≥ 0, finite predrawn mixtures with output divergence at most ε require a hard cap of at least (1/2 − o(1)) log2 log2 n rounds.The common-test-set argument forces some mixture weight onto components longer than R0(n); Theorem 15 also gives a liminf cost coefficient e^-ε/2 and a limsup coefficient e^-ε.Source: The obstruction · p. 51, Part (a) · p. 53

F.6. Mixtures: the fourth-power construction and the exact constant

  • The recursive mixture achieves output divergence at most ε with cost at most 2 log2 log2(n + 2) + Oε(1), and dilution gives a leading coefficient e^-ε.The construction uses singleton rounds below a tolerance-dependent cutoff, then recursively samples a prefix and commits the remaining coordinates together; rare exact-sampling floor schedules repair the count law.Source: §F.6 · pp. 54–55

Construction.

  • The recursive profile law draws a prefix size from a band, recurses on the prefix, and commits the rest in one round, with an n^-2 chance of an exact-sampling all-singleton schedule.Uniformly relabelling the blocks makes the count-law divergence equal the output-law divergence; the floor contributes at most one expected round along a branch.Source: §F.6 · p. 54, Construction · p. 55

Lemma Z1 (translation smoothing).

  • For Y distributed as Bin(b, θ), translating Y by an integer v changes its law in total variation by at most |v|/(2√((b + 1)θ(1 − θ))).This translation-smoothing bound is used within the construction’s randomized lattice-band argument.Source: §F.6 · p. 54, Lemma Z1 (translation smoothing) · p. 55

Lemma Z6 (common-mass lift).

  • (e^-ε/2 + o(1)) log2 log2 n is the least expected cost under the output-law criterion for every fixed ε > 0.The finite-mixture construction also gives LF(n, ε) ≤ 1/2 log2 log2(n + 2) + K⋆(ε) for ε ∈ (0, 1].Source: Lemma Z6 (common-mass lift) · p. 58

Error induction.

  • For every n ≥ 1, the recursion gives C(µn) ≤ log4 ln(n + 2) + Nε0 + 2, while averaging yields Dn ≤ ε0, that is, F(µn) ≤ ε0 by count reduction.At nonbase size n > Nε0, y := ln N ≥ Yε0 ≥ 1024 and cmin(n) = ⌈e^y/4y^8⌉, with y/4 ≤ ln cmin(n) ≤ y/2 and 4cmin(n) ≤ N.Source: Scales · p. 58, Error induction · pp. 59–60

Part (a).

  • Every almost-surely completing adaptive policy meeting the KL tolerance has Pr(τ+ > R0(n)) ≥ ηn and expected executed rounds at least 1 + R0(n) max(ηn, 0).The proof tests the adaptive output law and partitions by the first jump, an event decided before that round’s draws.Source: §F.7 · p. 61, Part (a) · p. 62

Parts (b) and (c).

  • Causal adaptive policies have the same sharp expected-cost asymptotic, lim inf Lad_F(n, ε)/log2 log2 n ≥ e^-ε/2 and lim Lad_F(n, ε)/log2 log2 n = e^-ε/2 for ε > 0.The matching upper bound follows from inclusion of finite predrawn mixtures among causal policies and Corollary 18.Source: §F.7 · p. 61, Parts (b) and (c) · p. 62
  • For fixed ε > 0, the least hard cap for causal policies lies between (1/2 − o(1)) log2 log2 n and log2 log2 n + Oε(1), leaving its sharp constant open.The lower bound follows from the adaptive tail result; the upper bound uses one uniformly relabelled profile.Source: Parts (b) and (c) · p. 62

F.8. Separation and scope

  • For 0 < ε ≤ 1, finite mixtures have LF(n, ε) ≤ log2 log2 n + 8cε, and their cost ratio to schedule-averaged cost is at most (1 + o(1))(24e^ε/ε)(ln n)^2/log2 log2 n for large n.Source: §F.8 · p. 63
  • Θ_ε((ln n)^2) rounds are needed for F ≤ ε under the best fixed labelled schedule, versus log2 log2 n + O_ε(1) for one relabelled profile.The relabelled-profile bound is Corollary 13; the comparison does not imply a lower bound on F from a lower bound on H, since F ≤ H.Source: §F.8 · p. 63
  • The separation is qualitative at practical n: the cited constants are astronomical, and the asymptotic constructions’ least expected round counts are far below their lengths at the sizes of Table 6.The ratio statement is two-sided for finite predrawn mixtures because Theorem 15 bounds LF; no adaptive-policy lower rate for H is claimed.Source: §F.8 · p. 63

Scope.

  • The deterministic-grid arguments for one relabelled profile do not bound mixtures, whose components can fill one another’s gaps, or value-adaptive policies.For profiles (2, n − 2) and (6, n − 6) at n = 5000, the gap-set ratio ρG changes from 1.7 · 10−18 under one profile to 0.94 under their equal mixture; the arguments also do not extend to α, β ≠ 1.Source: Scope · pp. 63–64
  • At fixed R, the computed gain from mixing profiles grows with n: at R = 2 it rises from 0.7% at n = 64 to 27.9% at n = 1024.At R = 3, it rises from 0.04% at n = 64 to 7.7% at n = 512; these single-profile arguments therefore give no lower bound on the mean-length quantity LF.Source: Scope · p. 63
  • For finite predrawn mixtures, LF has order Θ_ε(log log n) and LF(n, ε) / log2 log2 n → e−ε/2; adaptive policies have the sharp expected-executed-rounds constant.Theorem 19 also gives adaptive hard-cap order Θ_ε(log log n), between (1/2 − o(1)) log2 log2 n and log2 log2 n + O_ε(1); the sharp hard-cap constant and adaptive H remain open.Source: Scope · p. 64

Appendix G. Two-group survival envelope

Appendix G analyzes survival for a two-group tilted fixed-weight target under causal randomized policies, deriving an envelope for lower bounds on round costs and a count-state recursion whose optimum is attained by a deterministic count policy. It does not establish matching KL upper bounds for this target.

Link

  • Theorem 21 bounds Gλ_r(s) by a negative power of V(s) + 1, with constants independent of λ, group sizes, and state.The bound's content depends on V(s), which can be o(1) even as n grows; it therefore does not imply a λ-uniform doubly-logarithmic lower bound.Source: Appendix G · p. 64, Link · p. 66

Appendix G. Two-group survival envelope

  • The envelope yields lower bounds on the least hard cap, mean cost, and expected executed rounds, but the appendix proves no matching upper bound.The survival bound implies an output-KL lower bound through KL(pλ∥Q) ≥ −ln Q(Sk).Source: Appendix G · p. 64

Prefixes and states.

  • A legal prefix is summarized by s = (mA, mB, j), the free-coordinate counts in each group and the residual quota; illegal states have no completion in Sk.A legal state has 0 ≤ j ≤ mA + mB and positive target mass.Source: Prefixes and states · p. 64

Interface.

  • Each round commits a batch using fresh, conditionally independent Bernoulli draws at the current exact conditional marginals; values at illegal prefixes may be drawn arbitrarily.The auxiliary randomness is independent of the seed and earlier auxiliary randomness.Source: Interface · pp. 64–65

Policies.

  • A causal randomized policy draws its seed before sampling and chooses each batch from that seed and prior committed values; its hard cap requires all coordinates committed within r rounds almost surely.A full schedule is an ordered partition into nonempty blocks, and a schedule mixture is drawn before any bits.Source: Policies · p. 65

Count kernel.

  • For batch composition (bA, bB), committed counts are independent binomials with the groups' exact marginals, and the child state subtracts those counts from the residual quota.The child is alive exactly when its state is legal.Source: Count kernel · p. 65

Link

  • For every causal randomized policy, success within r rounds is bounded by Gλ_r(root), and a deterministic count policy attains that bound.At λ = 1, the recursion reduces to the balanced G_r(M, j) recursion.Source: Link · p. 65

Plan of the lemmas.

  • The proof combines a one-step estimate with Cauchy–Schwarz halving; the target's free coordinates are generally dependent, while the sampler's batch draws are conditionally independent.The one-step argument uses variance bounds for child states, and the conditional law at each legal prefix retains the tilted fixed-quota form.Source: Plan of the lemmas · p. 66, Lemma TG0 (conditional law) · p. 66

Lemma TG0 (conditional law)

  • For every round cap, the supremal success probability over causal randomized policies equals G^λ_r(root), and a deterministic seedless policy attains it.The attaining policy chooses a maximizing batch at each legal state and completes all coordinates within the cap on every path.Source: Lemma TG0 (conditional law) · pp. 70–71

Markov split

  • A split at round r bounds mean schedule cost using each schedule’s survival probability, while KL(pλ∥Q) ≤ ε requires Q(Sk) ≥ e^−ε.The argument separates schedules with length at most r from longer schedules and averages the resulting componentwise bound.Source: Markov split · p. 72, Asymptotics · p. 72

Asymptotics

  • Under either stated condition on Vroot, log2 ln Vroot = log2 ln n + o(1), giving R^F_λ(ε) ≥ log2 log2 n − O_ε(1) and expected-cost lower bounds of (e^−ε − o(1))·log2 ln n.The conditions are dist(k, D) ≥ δn, or λ in a fixed compact subset of (0, ∞) with interior limiting group and quota proportions; the expected-cost bound extends to every causal policy, with −O(1) in place of −o(1)·log2 ln n.Source: Asymptotics · p. 73
  • For nA = nB = k = N and λ = N^−4 or N^4, Vroot → 0 and one exact-marginal round has KL → 0, so no λ-uniform doubly-logarithmic lower bound holds.The passage reports one-round KL values 0.229, 0.080, 0.0255, 0.0077, 0.0023, and 0.00065 at N = 4, 8, 16, 32, 64, and 128; these high-precision results are not interval-certified.Source: Asymptotics · pp. 73–74

Numerical checks (not used in the proofs)

  • Finite checks found no violations in the reported informative tests, but several small-size envelope checks are vacuous and the numerical evidence does not replace the proof.Tests included exact labelled enumeration of deterministic policies for n ≤ 8 and checks of selected inequalities and states at larger sizes.Source: Numerical checks (not used in the… · pp. 74–75

Lower bounds only

  • The appendix proves lower bounds only: survival-optimum attainment is not a KL upper bound, and the analysis does not control the between-group shape term.Matching weighted-target upper bounds are established elsewhere only under bounded weight ratio and quota fractions bounded away from zero and one; this appendix does not address the H side.Source: Lower bounds only · p. 75

Loose constants

  • At λ = 1 and the balanced root, the envelope is below 1 only for n > 1,679,612 at r = 2 and n > 7.4·10^16 for r ≥ 3; finite certificates should use the exact DP.The bounds are loose, and the stated policy classes exclude repair or restart and samplers outside the exact-marginal interface.Source: Loose constants · p. 76

Appendix H. Proof of Theorem 8 (bounded weights)

This section proves lower bounds and gives schedule constructions for output-law KL round complexity on bounded-weight fixed-count targets. It establishes double-logarithmic round bounds for hard caps and expected executed rounds under the stated hypotheses.

Appendix H. Proof of Theorem 8 (bounded weights)

  • The theorem’s assembly extends lower bounds to any bounded weights with an interior quota, while the explicit two-weight bounds cover arbitrary group splits, including an empty group.The appendix also treats edge cases and more weight values; its schedule-mixture construction reaches the hard-length order up to an additive constant.Source: Appendix H · pp. 76–77

Informativeness.

  • 1+max{8(ln n+1), 16Λ^3(ln n+1)^2/ε} rounds suffice for schedule-averaged KL, using one fixed schedule for any bounded weights and quota.The construction takes blocks of size max(1, floor(αM)) from the current free set; the theorem’s matching general-weight upper bounds are supplied by Appendix I.Source: Appendix H · pp. 76–77, Informativeness · p. 81

Appendix H. Proof of Theorem 8 (bounded weights)

  • (e^-ε+o(1)) log2 ln n is the least expected cost under the output-law criterion for bounded weights, and a schedule mixture attains it with every component of length log2 ln n + O(1).The lower bound applies to every causal policy; the stated construction is given for two weight values or a group of at least ρn equal weights.Source: Appendix H · pp. 76–77

Lemma W1 (ratios and floors).

Lemma W5 (entropy decrement at deterministic labelled sets).

  • The entropy-decrement lower bound uses fixed labelled coordinate sets; choosing the free set adaptively from observed values can substantially reduce the decrement.The appendix illustrates this limitation with finite examples, while retaining its stated lower bound for fixed sets.Source: Lemma W5 (entropy decrement at… · p. 80

6.1 Construction.

  • The output-law construction reserves the larger weight group while committing the smaller group, then uses a randomized ladder on the reservoir to control residual-quota failure.The chain rule separates the divergence into the committed-group term and the expected negative log success probability; the construction bounds each contribution.Source: Informativeness · p. 82, §6.1 · p. 82

6.6 The relabelled ladder is uniform on each residual slice (FB): an exact identity.

  • The two-weight construction controls output KL by bounding the Stage A divergence and making the relabelled ladder uniform on each residual slice.The schedule is predrawn, and uniformly relabelling B makes its conditional law constant on each fixed-count slice; this matches the target’s uniform conditional law there.Source: §6.6 · p. 84, §8 · p. 87

Lemma (one-block atom).

  • For every legal quota, the ladder succeeds with probability at least 1/(M + 1), making atypical-quota conditional KL at most ln(M + 1).The atypical quota mass is O(1/M) by Chebyshev, so its contribution is O(ln M/M); the construction needs no extra mixture component for atypical quotas.Source: Lemma (one-block atom) · p. 84, §8 · p. 87

Remark (more weight values: a homogeneous group suffices).

  • A homogeneous group of size at least ρn suffices for bounded-weight targets to attain F = (e^-ε + o(1)) log2 ln n and common length log2 ln n + Oε,Λ,κ0,ρ(1).This includes any fixed number q of weight values; a largest weight class has ρ ≥1/q.Source: Remark (more weight values: a… · p. 86
  • Without a homogeneous group, the appendix gives F ≤ ε mixtures with at most log2 ln n + OΛ,κ0(1 + ε^-2) rounds per component or scheduled mean (e^-ε + o(1)) log2 ln n.These existence-only mixtures may use components of different lengths, so they do not establish a common-length bound.Source: Remark (more weight values: a… · p. 87

8. Why survival alone is not enough.

  • Survival probability alone does not bound output KL: at (nA, nB, k) = (3, 3, 3), λ = 2, and r = 3, −ln Gλ3 = 0.05518 while F*3 = 0.05881.The construction controls the between-orbit law and the law on each residual slice, leaving only the expected negative log ladder success probability.Source: §8 · p. 87

Hard-length analogue of Corollary 5.

  • The least common component length for the two-weight construction is log2 ln n + Oε,Λ,κ0(1), while fixed labelled schedules require Θε,Λ,κ0((ln n)^2) rounds.The relabelled schedule mixture runs every component to its full length, so its mean cost equals its hard cap.Source: Hard-length analogue of Corollary 5 · p. 88
  • The least expected cost under output KL is (e^-ε + o(1)) log2 ln n for two-weight targets.The upper bound mixes the construction at tolerance ν with a one-round schedule; the lower bound applies uniformly over λ, the split, and k.Source: Hard-length analogue of Corollary 5 · p. 88
  • For arbitrary weights with ratio at most Λ, the bounded-weight envelope gives an adaptive converse without assuming a homogeneous group.The stated envelope applies to every causal randomized policy with fresh exact-marginal draws.Source: Remark (more weight values: a… · p. 87, Hard-length analogue of Corollary 5 · p. 89
  • The least hard cap is log2 ln n + O(1), and the least expected executed rounds are (e^-ε + o(1)) log2 ln n.Uniform lower bounds are R_w^F(n, ε) ≥ log2 ln n − 1 − log2(ε + ln KΛ) and Eτ ≥ e^-ε log2 ln n − e^-ε − c(KΛ); the stated schedule mixtures attain these orders under the cited hypotheses. Without a homogeneous group, Appendix I gives the same orders, with an existence-only upper hard-cap constant; these results do not concern adaptive selection, and KΛ grows with Λ.Source: Hard-length analogue of Corollary 5 · p. 89

Inputs.

  • Residual arrays with weight ratio at most Λ yield uniform bounds on coordinate marginals and variances, including vi ≥ V/(ΛM) and V ≥ d/(2Λ).The proof uses these bounds over residual arrays rather than assuming counts are a sufficient state.Source: Hard-length analogue of Corollary 5 · p. 89, Inputs · p. 90

Base.

  • For a legal state with minority quota d ≥ 1, the one-step bound is E[(d′ + 1)^-1/2; child legal] ≤ 12Λ(d + 1)^-1/4.The proof handles small batches with a Chebyshev bound and large batches with an atom bound; it then iterates the estimate, including the final large batch.Source: Base · p. 90

Appendix I. Reservoir-free upper bound for bounded weights

Appendix I develops reservoir-free upper bounds for bounded-weight fixed-quota targets using finite kept-set schedules and reference-law, concentration, typicality, and density-ratio analyses to support hard-cap and scheduled-mean guarantees. It also characterizes round-cost and output-law frontiers through count-state recursions and terminal-vector hulls, including predrawn-mixture brackets and a leakage–shape decomposition, while noting that the stated TGR7 brackets are estimates rather than certified bounds.

0. Statement Hypotheses.

  • For n ≥ 4m0, the mixture has hard cap at most log2 ln n + 8A^2 + 5 rounds; below that threshold it uses the exact sampler.Here m0 = ⌈4A^2⌉.Source: §0 · pp. 91–92
  • At fixed tolerance ε, choosing A = max(A0, C*/ε) gives F ≤ ε and hard cap log2 ln n + OΛ,κ0(1 + ε^-2), uniformly over weight arrays and quotas.The schedule law depends only on n and A, not on the weights.Source: §0 · p. 92
  • Mixing U(An) with the one-block schedule yields scheduled mean (e^-ε + o(1)) log2 ln n and hard cap log2 ln n + O(√log log n).An = max(A0, (log log n)^1/4), with εn = C*/An → 0.Source: §0 · p. 92

Scope and notation of the proof.

  • The bound applies to positive weighted fixed-quota targets without a homogeneous reservoir; it does not establish a full-support extension or a common schedule length.The proof bounds output divergence level by level, using kept-set averaging to compare rounds with a reference law.Source: Appendix I · p. 91, Scope and notation of the proof · p. 92

1. Weighted slices and elementary probability tools

  • Weighted-slice pairwise covariance bounds support a sub-Gaussian linear-statistics lemma for positive weights, without using a full negative-association theorem.The covariance result also holds under further feasible conditioning.Source: §1.1 · p. 93, §1.2 · pp. 94–95

2.2 Uniform lattice Edgeworth estimate

  • A uniform lattice estimate yields exact marginals within O(V^-1) of the logistic tilt at an interior parent.The estimate is uniform over arrays whose Bernoulli probabilities stay bounded away from zero and one.Source: §2.2 · p. 97

2.4 The normalizer and its full change of variables

  • For interior quotas, the normalizer is within O(√(log m/m)) of one, and it remains finite and positive even at endpoint quotas for nonempty coordinate sets.The stated approximation is restricted to interior quotas; finiteness and positivity also hold at quotas zero and m.Source: §2.4 · p. 98

3. Exact identities, one-step error, and target-law and execution-law tails

  • The reference law matches the sampler’s first step, then completes the kept coordinates; exact parent-marginal centering gives E_p D_X(u)=0.The reference construction is used for analysis, with target-law and execution-law bounds distinguished in the comparison.Source: §3 · p. 100, §3.1 · p. 101

3.1 Reference law and exact identities, including the empty child

  • The exact identities yield S1(u) ≥ −C fN u^2/V and S1(u) ≤ C N/V^2 + C fN u^2/V; the relevant nonconstant numerator is O(|u|+N^-1).Source: §3.1 · p. 103

3.3 Bulk normalization

  • The bulk normalization gives a lower bound with factor 1−C/V multiplying a Gaussian expectation.The passage states this bound after identifying the normalized Gaussian integral up to O(V^-1).Source: §3.3 · p. 103

3.4 The tilted subset law and the all-point lower bound

  • Under the tilted subset law, the child is non-interior with probability at most 4e^(-cfN), controlling both its size and its quota fraction.The event covers |C| outside [fN/2, 2fN] or |x_C|/|C| outside [κ/2, 1−κ/2].Source: §3.4 · p. 104

3.5 One-step KL and the likelihood-ratio second moment

  • The likelihood-ratio second-moment bound is uniform in dimension, the coordinate array, and f in the stated regime; establishing it requires integration, not a target-law tail bound alone.The proof integrates the one-step estimate under p.Source: §3.5 · p. 105

3.6 Execution-law non-interiority and the exact kept-set mean cancellation

  • Execution-law non-interiority, including empty and infeasible children, has probability at most 2e^(-c fN), with c=κ^2/32 available.The analysis also uses exact kept-set mean cancellation rather than replacing the coordinate-marginal sum with ρ|C|.Source: §3.6 · pp. 105–106
  • The non-interior event is handled alongside interior-child deviation bounds to establish concentration for the kept-set statistics.The union bound counts the non-interior event just once.Source: §3.6 · p. 106

3.7 Finite typical family, exact coefficient centering, and bulk/tail control

  • A finite family of centered linear statistics defines typical states, while the integral outside the bulk is bounded by Ce^{-c''ℓ²}.The family supports bulk and tail control; the centering preserves statistics on the slice.Source: §3.7 · pp. 106–107

3.8 The non-interior contribution and two-sided density ratios

  • On typical outputs, the density ratios are bounded on both sides near one, and separate target-law and execution-law mass bounds control the excluded outputs.The bounds use two-sided estimates for ψ and separately account for non-interior contributions.Source: §3.8 · p. 108

4.1 Integer sizes and their two-sided growth

  • Geometrically growing nominal sizes yield R ≤ log2 log n + 3 levels with a kept set, and the per-level errors are summable.A terminal level follows the kept-set levels.Source: §4.1 · p. 109

4.2 A finite law on full labelled schedules, sampled before any bits

  • The sampler draws a finite distribution over full labelled schedules before any bits, with every run costing at most log2 log n + 8A² + 5 rounds.The guarantee requires A ≥ A0; A0 is existence-only, so the parameter for a given ε is not explicit.Source: §4.2 · p. 110

4.3 Suffix kernels and good states: actual sizes versus nominal sizes

  • Suffix kernels obey a first-block recursion, and at the last level every good state has an exact suffix sampler.Good states keep actual size near nominal and density away from the endpoints, allowing the one-step results to apply.Source: §4.3 · pp. 110–111

4.4 Conditional probability of leaving the good set

  • The conditional probability of leaving the good set is bounded by combining size failures with density failures on the size-good event.The bound applies to the pre-completion state and therefore to both the suffix kernel and the reference law.Source: §4.4 · p. 111

4.5 Jensen composition with signed continuation log ratios

  • Two-sided control of ψ on typical states keeps the signed continuation-log-ratio excess in the recursion to a small factor 2ηt.The argument retains the good event and controls discarded events using separate target-law and execution-law masses.Source: §4.5 · p. 112
  • Sub-probability continuation laws use the cemetery extension, rather than a conditional-on-survival ratio for W.The composition argument needs no omitted multiplicative constant before its first term because 1 − ηt ≤ 1.Source: §4.5 · p. 113

4.7 Summation and a fully constant-tracked scalar recursion By (4.5),(4.23),(4.27), X

  • The scalar recursion establishes item 3 of Theorem A uniformly over A ≥ A0, admissible dimensions, quotas, and bounded-ratio arrays.The exact singleton branch covers all small dimensions.Source: §4.7 · p. 114

4.8 Survival and within-slice shape

  • The first-exit bounds control survival, while the within-slice shape term is F + log Q(Sk) ≤ F.The same bound is used for both shape and survival.Source: §4.8 · p. 115

4.9 Fixed error, small n, and the diagonal scheduled-mean coefficient

  • For fixed ε > 0, choosing A = max(A0, C∗/ε) gives the stated upper bound via (4.8), (4.30), and the exact branch.The admissible dimensions satisfy n ≥ 2, so the exact small-n branch fits the additive-constant expression without using log log 1.Source: §4.9 · p. 115
  • Eτμ′n = (e−ε + o(1)) log2 log n, and every causal policy with output KL at most ε has Eτ ≥ e−ε log2 log n − e−ε − c(KΛ).The construction also has hard cap log2 log n + O(√log log n); the matching lower bound makes e−ε the least leading coefficient.Source: §4.9 · p. 116
  • The diagonal construction has EτU(An) = log2 log n + o(log log n) and Eτμ′n = (e−ε + o(1)) log2 log n.These equalities describe the constructed family; its component schedules are charged in full.Source: §4.9 · pp. 115–116

5. Constants and a noncircular choice order

  • A single sufficiently large finite A0 can satisfy the stated uniform requirements, but no numerical value of A0 or finite-size constant is derived.The requirements are uniform in d ≥ 0 and their finite maximum is independent of n.Source: §5 · p. 117

Setting.

  • The extended count state tracks the committed A-group ones, and its policy-independent controlled kernel supports a backward recursion over legal and absorbing illegal states.Deterministic Markov count policies choose group compositions; their convex hull gives terminal vectors for randomized policies under the hard round cap.Source: Setting · p. 120, TGR0 (conditional law) · p. 122

Reported quantities and the lemmas behind them.

TGR0 (conditional law).

  • The output-law divergence is leakage, −ln s(q), plus between-orbit shape, KL(P∥q/s(q)); the optimal terminal vector is unique and positive.The shape term is a KL divergence.Source: TGR0 (conditional law) · p. 122

Lemma TGR6 (predrawn frontier).

  • At a fixed round cap, the predrawn frontier minimizes Φ over the convex hull of terminal vectors from schedules of at most r nonzero compositions.An optimal policy may need to adapt to the committed A-count uA; tested uA-independent tables are worse at nA = nB = k = 3, r = 3, λ ∈ {2, 4}.Source: Lemma TGR6 (predrawn frontier) · pp. 122, 125

Lemma TGR6 (predrawn frontier)

  • The order √g cannot be improved for brackets of this form as a function of (P, q̂, g) on a convex set.The example is an abstract segment, not a realised conv V_r.Source: Lemma TGR6 (predrawn frontier) · p. 126
  • Along the example direction, Φ rises as Θ(t²) while s moves by −t.The segment uses P = (1/5, 2/5) in direction (1, −2), where q* is the minimiser and the directional derivative is 0.Source: Lemma TGR6 (predrawn frontier) · p. 126
  • The TGR7 brackets use g = max(Frank–Wolfe gap, 0) + 10⁻¹³ and are estimates, not certified bounds.Grid Z, used for some exhibit rows, is defined in Appendix K.Source: Lemma TGR6 (predrawn frontier) · p. 126

Appendix K. Finite exhibits: details and evidence classes

Appendix K documents how finite exhibits were computed and validated, then reports finite comparisons across balanced-slice, two-group, and full-support targets. Its predictions have explicit discovery and held-out scopes, and several numerical findings remain uncertified or limited to tested grids.

Appendix K. Finite exhibits: details and evidence classes

  • A six-coordinate witness shows a block-composition rule chosen from committed counts beats every predrawn mixture by a factor of at least 2.35.The witness uses (nA, nB, k, λ) = (3, 3, 3, 4) and r = 3; its output-KL value is kernel-checked.Source: Appendix K · p. 127
  • At ε = 0.1, the least cap is 10 versus 5 rounds at n = 24, λ = 1, for deterministic versus output-law criteria.For n ≤ 16, the reported ranges are 5–8 rounds for the path certificate and 4–5 for the output law.Source: Appendix K · p. 128

Frozen predictions and phases of the cells.

  • Eight two-group predictions were frozen before held-out cells were computed; five passed and three failed, each narrowing its stated claim.The 72 cells included 25 discovery cells and 36 held-out cells; the held-out set comprised equal splits at n ∈ {20, 24} and four unequal or off-centre targets.Source: Frozen predictions and phases of the… · p. 128

Scoring scopes.

  • Two-length linear programs bound mean costs; at n = 2048, the computed LH/LF ratio is about 3.8, not a rate or monotone trend.The reported finite ratio is about 1.3 at n = 16.Source: Scoring scopes · p. 130
  • For Beta(1, 1), the proved mixture rate is (e^-ε/2 + o(1)) log2 log2 n, while finite profiles are non-decreasing and reversal can sharply worsen F.For n ∈ {8, 16, 32, 64} and r ≤ 6, reversed optimal profiles have 4.2–148 times their F; mixing profiles or adapting block sizes gains at most 3%.Source: Scoring scopes · p. 130
  • The tested growth-exponent predictions for other Beta priors failed, and Table 6 is not interval-certified except for its LF bounds at n ≤ 2^10.The cited passage says no rate is claimed for priors other than Beta(1, 1), the only case proved in Appendix F.Source: Scoring scopes · pp. 129, 132

Appendix L. Reproducibility

Appendix L records the software, licenses, and compute used for proofs and finite computations. It also evaluates proved balanced-slice bounds, which separate the two criteria beyond stated sizes.

Software, licenses and compute.

  • The formal proofs use Lean 4 and Mathlib, while numerical scripts use Arb and standard scientific Python libraries; no external data or pretrained models are used.All data are synthetic draws from the stated targets; learned heads used about 25 H100 jobhours, while kernel checks and other finite computations used CPUs.Source: Software, licenses and compute · p. 132
  • At ε = ln 2, the proved LF upper bound is below the proved LH lower bound for every even n ≥ 2^15; at ε = 0.1, this holds for every even n ≥ 2^13.The thresholds are kernel-checked; the two formulas first cross at even n = 19,286 and n = 4,788, respectively.Source: Software, licenses and compute · p. 134

Appendix M. Controlled learned-conditional test

This appendix reports controlled tests of oracle-derived schedule choices under learned conditionals and documents limits on what the tests establish, including limits on the sampler and cost model. It also presents results and checks on imperfect conditionals, relabelled outputs, and bounded-weight and full-support targets, while distinguishing prior results from the paper’s fixed-target randomized optimum.

Appendix M. Controlled learned-conditional test

  • The tests are sample-level, not population guarantees: six clusters per target yield a one-sided 95% lower bound of only 0.61, and they establish no robustness theorem under learned error.The learned-head tests used small masked transformers on known targets, not language models; the restricted interface is not recommended for practice.Source: Appendix M · pp. 135, 138, 140
  • On screened learned-head pairs, TERM met its regret threshold in 342/342; PATH and the head’s own H choice retained at least half of PATH’s oracle loss in 180/180.The fixed-order relabelling gain held in 1386/1386 eligible triples, while the quota value-adaptive rule was within 0.005 nats of TERM in 242/252 pairs.Source: Appendix M · pp. 137, 140
  • The two-group survival rule beat the group-blind terminal profile by at least half its oracle gain in 36/36 pairs at r = 3, 4, with median gain 0.045 nats; a fourth test used the wrong comparator.The rule was the best menu law in 36/36 pairs; the r = 2 comparison as written failed by construction.Source: Appendix M · pp. 138, 140
  • Frozen variance-matching predictions passed every tested cell across four held-out Beta–Bernoulli targets, with the lowest cell at 17/18 heads.For Beta(4, 4), regret was at most 0.005 in 18/18 heads in every tested cell; some n = 16, r = 3, 4 cells were not tested.Source: Appendix M · pp. 138, 140
  • The plug-in rule matched the frozen rule’s profile in 5,559/5,760 rows, while direct validation improved on TERM by more than 0.005 nats in only 3/486 pairs.The authors claim no decision value for the frozen rule over either comparator on the tested targets.Source: Appendix M · p. 139

Extended menu (main test).

  • On the extended menu, TERM regret exceeded 0.005 nats in 14/486 pairs, but every cell mean stayed below 0.005; the largest pairwise regret was 0.0080.The value-adaptive optimum beat TERM in 11 of those 14 pairs; without it, regret exceeded 0.005 in 3/486 pairs.Source: Extended menu (main test) · p. 141

Appendix N. Imperfect conditionals

  • Appendix N studies relabelled singleton schedules under heads that are exact at forced states, defining masked-prediction excess and output-law divergence for possibly imperfect conditionals.Its scope includes general heads and label-invariant count-state heads on fixed-count targets that need not be balanced.Source: Appendix N · p. 141

Proposition IC1 (imperfect conditionals on relabelled singletons).

  • For relabelled singletons, output divergence satisfies F(Q̂) ≤ nA(ĥ), with equality for coherent heads; label-invariant count-state heads have F(Q̂) = 0.Over heads exact at forced states, the supremum of F(Q̂) subject to A(ĥ) ≤ a is na; under a small nonconstant logit perturbation, F(Q̂)/(nA(ĥ)) tends to ρ_n, which tends to 1.Source: Appendix N · p. 141, Proposition IC1 (imperfect… · p. 142

The choice of divergence.

  • At n = 4096, the fixed labelled ladder has TV 0.673, while its relabelled mixture has TV 0.015; randomized-side results also hold in total variation.Validity probability is linear in the schedule mixture, so relabelling leaves it unchanged; the shape-error comparison therefore is not specific to KL.Source: The choice of divergence · p. 145

Symmetry in the leakage-only reduction.

  • For permutations, every fixed schedule has zero shape error on valid strings, so randomizing schedules cannot improve the least hard cap; a fixed schedule also attains the adaptive optimum.The fixed-schedule restriction to valid strings is constant, and the result extends to causal adaptive policies for this oracle.Source: Symmetry in the leakage-only reduction · pp. 145–146

Two groups: survival is not enough.

  • On two-group tilts, survival does not control the between-orbit divergence: a kernel-checked case has Gλ_r = 1 but F*_r = 5.0 · 10−4.Across 24 targets, the computed D_r/F*_r ranges are 1.3–1.9, 1.8–3.0, and 2.6–9.2 at r = 2, 3, and 4, respectively.Source: Two groups: survival is not enough · p. 146

Imperfect conditionals.

  • For imperfect heads, relabelled singletons satisfy F ≤nA, coherent heads attain equality, and a label-invariant count-state head has F = 0.For small label-dependent tilts, F/(nA) tends to ρ_n ∈[163/192, 1].Source: Imperfect conditionals · p. 146
  • A →0 while the best fixed relabelled profile needs Θ(√n) rounds for F ≤ln 2, whereas a count-adaptive policy achieves it within ⌈log2 n⌉+1 rounds.The adaptive bound is an achieved pathwise cap, not the least cap; this example shows aggregate A alone does not control fixed-profile length uniformly in n.Source: Proposition IC1 (imperfect… · pp. 143–144, Imperfect conditionals · p. 146

Sampling the mixtures.

  • Mixture-description and selection costs are excluded, and the support may grow with n; the stated upper-bound constructions sample mixtures without listing their supports.The exact oracle marginal computation cost is not analyzed, and charging extra for describing or sampling mixtures could only raise costs.Source: Sampling the mixtures · pp. 146–147

Restart.

  • Restarting until validity removes quota leakage but not fixed-schedule shape error; for the diluted ladder mixture, expected rounds per valid output are (1 + o(1))L.Thus the factor e−ε is a one-output criterion, not a per-valid-sample saving.Source: Restart · p. 147

Appendix P. Further related work

  • On the balanced slice, the paper gives the randomized optimum for both hard-cap and expected executed rounds, extending prior work that left expected-round budgets open.Li et al. (2026) listed expected round budgets as an open question; the paper’s Theorem 4 and Corollary 6 give the randomized optimum for both criteria.Source: Appendix P · p. 151

Appendix Q. Kernel-checked declarations

  • The Lean companion rebuilds from source without `sorry`, and its theorem declarations report only propext, Classical.choice, and Quot.sound as axioms.A separate certificate package is also rebuilt in two stages with identical axiom reports; the appendix cautions that kernel checking certifies formal statements, not their agreement with the printed results.Source: Appendix Q · p. 151

kernel-checked declarations

  • The formalization identifies printed randomized processes with the policy class, preserving output laws, completion probabilities, caps, and executed means.The appendix also maps main results to ordinary proofs, declarations, and clauses not kernel-checked; it notes that the output law after r rounds under an almost-sure cap is the terminal law.Source: Appendix Q · p. 152
  • IC1 covers the relabelled-singleton setting with a bound, coherence and supremum result, a zero-value case with a counterexample, and a limiting family with its rate.The setting requires relabelled singletons to remain in V; the passage identifies these as IC1(a)–(c).Source: kernel-checked declarations · p. 162
  • IC2 states a bound with a limiting result, a formula with upper and lower profile bounds and a Θ result, and a further result in part (iii).The passage identifies these as IC2(i)–(iii), without giving their formulas or quantitative values.Source: kernel-checked declarations · p. 162
  • For relabelled outputs, the chain rule gives two identities and characterizes infinite KL divergence; averaging over a proper subgroup need not suffice.The infinite-divergence condition is that the output law assigns zero mass to an orbit of the support.Source: kernel-checked declarations · p. 162
  • (e−ε + o(1)) log2 ln n is the least mean for predrawn mixtures and the least expected executed-round cost for causal policies on bounded-weight targets.Mixtures from Corollaries A′ and A′′ attain these orders.Source: kernel-checked declarations · p. 166
  • (1/2 − o(1)) log2 log2 n is a lower bound on the least hard cap for both finite predrawn mixtures and causal policies under the full-support criterion.The finite-mixture bound follows from Theorem 15(a); the causal-policy bound is derived from Theorem 19(a).Source: kernel-checked declarations · pp. 168–169
  • Every full-support construction branch has fewer than 1 + log4 ln(n + 2) nonbase recursive calls.The nonbase calls form a nested chain, and every component of the recursion’s law comes from such a branch.Source: kernel-checked declarations · p. 169
  • An exact sampler exists for the full-support setting, contrasting with the one-interface-round method for n ≥ 2.The declarations identify both the exact sampler and its contrast with one interface round.Source: kernel-checked declarations · p. 169
Loading 2610.13924v1…