PaperlayerView exact revision on arXiv

Source-linked AI summary

Leveraged Learning: entropy cleared per bit received

Daniel Chernowitz

arXiv:2609.08054v3cond-mat.stat-mechcs.ITmath.IT

TL;DR

The paper asks how learning from answers can be described beyond finite examples and in the thermodynamic limit. It develops a degree-based simplicity prior that retains information across scales. The supplied passages characterize when learning continues into the bulk and specify boundaries on the macroscopic profile result.

  • Problem

    The paper seeks general learning curves in the thermodynamic limit, using the asked fraction of the question table as time rather than examples per parameter.

    Source: §4 · p. 24

  • Method

    The construction grades Boolean maps by polynomial degree and allocates macroscopic weight across degree classes to preserve information at macroscopic times.

    Source: §5 · p. 35, §5.2 · p. 40

  • Results

    A nondegenerate extensive limit requires learning to continue into the bulk rather than settle within a boundary around t = 0.

    Source: §4.2.2 · p. 33

  • Takeaways & Limitations

    Degree-class weighting avoids constructions that resolve the class label in o(Q) bits and then leave a constant bulk learning rate.

    Source: §5 · p. 35, §5.2 · p. 40

    The pointwise profile convergence excludes step discontinuities, while degenerate zero-entropy laws and singular endpoint behavior require separate treatment.

    Source: §5.4 · p. 48

Abstract

from arXiv · show

An expository essay containing some new results. A learner holds a prior belief over Boolean maps that answer a finite set of $Q$ questions, and receives answers one by one. Each answer carries surprisal and can clear predictive uncertainty about both the question asked and questions still unasked. We quantify this effect by the leverage: table entropy cleared per bit of surprisal received. Taking expectations over the truth prior and the question order, define the aggregate leverage as the ratio of expected uncertainty cleared to expected surprisal received. It equals one for independent answers and can exceed one for correlated answers. At finite size, this ratio is determined exactly by a single sequence: the mean entropy $G_\ell$ of the answers to $\ell$ questions. As the number of input bits grows at fixed asked fraction $t=\ell/Q$, a limiting increment profile $\gamma(t)$ determines the macroscopic learning curve. With $\eta_0$ the limiting initial entropy per question, the leverage becomes $L(t)= \frac{\eta_0-(1-t)\gamma(t)} {\int_0^t\gamma(x),dx}$. For exchangeable priors, de Finetti's representation gives a constant bulk profile $\gamma(t)$: deduction is confined to a boundary layer at $t=0$, and the leverage is forced to a hyperbolic form, as surprisal grows linearly. By contrast, we construct a simplicity prior with nontrivial bulk learning by grading Boolean maps by their polynomial degree over $\mathbb{F}_2$ and allocating weight across degree classes through a CDF $F$. Reed-Muller capacity then yields $\gamma(t)=1-F(t)$. This realizes any nonincreasing profile taking values in $[0,1]$, together with the corresponding macroscopic leverage curve.

1 A thought experiment

The essay models learning as improved ability to answer questions about an unknown Boolean map. Its examples show how prior beliefs can make one answer resolve uncertainty about other questions, and introduce leverage to measure this effect.

1 A thought experiment

  • Werner learns an unknown Boolean map by receiving its answers to questions, with candidate maps representing possible truths.The thought experiment begins with maps from one bit to one bit.Source: §1 · p. 5

1.1 An unintelligent learner

  • Under a uniform prior, each answer is initially a fair coin, and eliminating inconsistent maps updates Werner’s beliefs without distinguishing the two survivors after the first answer.After ψ(0) = 1, NOT and constant 1 remain; a second answer identifies the truth.Source: §1.1 · pp. 5–7

1.2 Intelligent priors

  • A prior that rules out constant maps lets one answer determine both outputs, clearing 2 bits of table uncertainty for 1 bit of surprisal.The prior makes the answers perfectly anticorrelated, so Werner finishes after one question.Source: §1.2 · p. 8

1.2.1 A one-parameter world

  • When constant maps have prior probability p, the first answer clears 2 − h2(p) bits, and leverage varies with p as the second question’s expected information declines toward the nonconstant-map case.The one-parameter prior spreads weight evenly within the constant and nonconstant classes; at p = 1/2, L1 = L2 = 1.Source: §1.2.1 · pp. 8, 10, 11

2 The general case

The general framework represents a learner’s beliefs as probabilities over maps and tracks prediction uncertainty across questions. It separates uncertainty about individual answers from dependence among them, then uses expected entropy changes and surprisal to characterize the value of questions and cumulative learning.

2.1 The answer matrix and the update rule

  • A prior over maps induces an answer matrix whose columns give answer probabilities; observing an answer eliminates inconsistent maps and renormalizes the surviving weights.The survivors depend on which questions were asked, not their order.Source: §2.1 · pp. 13–14

2.2 Entropy bookkeeping

  • The table entropy sums marginal answer entropies, while the map entropy is their joint entropy; their nonnegative gap is total correlation, the dependence invisible in individual columns.The gap vanishes exactly when the prior is a product over questions.Source: §2.2 · p. 15

2.2.1 What a question is worth

  • Expected table improvement beyond the asked column’s surprisal is the expected gain on other questions, drawn from correlations; the forecasts depend on joint answer laws as well as the answer matrix.Two priors with the same answer matrix can forecast different improvements.Source: §2.2.1 · pp. 16–17
  • In the guiding example, asking q = 11 clears 0.748 bits at a realized surprisal cost of 1.269 bits, below the forecast, while later questions more than repay the gap.The full run clears 2.925 bits for 2.231 bits of surprisal.Source: §2.2.1 · p. 17

2.3 Leverage

  • Cumulative leverage is table entropy destroyed per bit of surprisal received; 1 is the uniform-prior baseline, and expected leverage above 1 represents deduction.The aggregate definition removes run-level windfalls by taking expectations.Source: §2.3 · p. 17

3 Expectations

Averaging over the truth and a uniformly ordered set of questions yields exact laws for expected learning and aggregate leverage. The mean block-entropy sequence determines the learning curve, while correlations shape how surprisal and predictive uncertainty change across rounds.

3.1 Two exact laws

  • The expected learning curve is the discrete derivative of the mean block-entropy sequence, which determines aggregate leverage exactly at every size and for every prior.Expected surprisal is G_ℓ, and the remaining table entropy is Q−ℓ copies of one increment.Source: §3.1 · pp. 19–20
  • Aggregate leverage is at least one, need not be monotone, and reaches its completion ratio at ℓ=Q; deduction has already saturated at ℓ=Q−1.The completion ratio is L_Q = H(M(0))/H(p) = 1 + C_0/H(p).Source: §3.1 · p. 20
  • Any product prior over answers has aggregate leverage L_ℓ=1 when its denominator is positive, because observing one answer cannot improve prediction of another.This holds even when the prior's answer columns are biased.Source: §3.1 · p. 20

3.2 The total predictive gain

  • Through round ℓ, expected leverage depends only on correlators supported on at most ℓ+1 questions, so deeper correlator shells are not yet distinguishable.A prior with one nondegenerate answer copied to every question has L_ℓ=Q for every ℓ.Source: §3.2 · p. 22
  • Under uniformly random question order, mean block-entropy increments decrease with ℓ, so later answers carry less expected surprisal.The averaged sequence G_k/k is also nonincreasing.Source: §3.2 · p. 22
  • The expected aggregate leverage in the guiding example peaks at ℓ=2 and finishes at 2.925/2.707 = 1.081.The realized run reached 1.311; expected remaining, received, and deduced entropy sum to the initial table entropy, with correlation-store withdrawal saturating at 0.218 by ℓ=3.Source: §3.2 · p. 23

4 The thermodynamic limit

The thermodynamic limit tracks learning as a function of the fraction of questions queried, with the macroscopic learning curve determined by a limiting answer-entropy profile and initial entropy kept separate for learning compressed into a boundary layer at zero. A precise leverage limit requires positive bulk learning and convergence assumptions, and profile convergence need not be unique across priors.

4 The thermodynamic limit

  • The thermodynamic limit holds the prior mass p and asked fraction t > 0 fixed as n grows, so it captures learning over a nonzero fraction of the run.Learning completed in O(1), O(log Q), or more generally o(Q) questions is compressed into the boundary layer at t = 0.Source: §4 · p. 24

4.1 A toy example: the spike prior

  • The spike prior places distinguished mass on one map and spreads the rest uniformly over all others, retaining full support while allowing Bayesian conditioning to stay within a tractable family.Confirming answers produce a sharper spike on a smaller map space; refuting answers cull the distinguished map and leave equal weights among survivors.Source: §4.1 · p. 24

4.1.1 The two-state renormalization flow

  • The spike posterior follows a two-state flow: confirmations sharpen the spike, while any refutation enters a uniform class that remains uniform under later conditioning.After all Q questions, the spike survives only when the truth map is the distinguished map; at the uniform prior, both posterior branches are uniform on their surviving map spaces.Source: §4.1 · p. 24, §4.1.1 · pp. 25–26

4.1.2 The fixed-p thermodynamic limit leverage

  • For the fixed-p spike prior, the limiting leverage is hyperbolic: the initial deduction is compressed at t = 0, while only the refuted class, of probability 1 − p, pays m bits per later answer.Finite curves approach the limit from below, with the gap closing last near t = 0.Source: §4.1.2 · pp. 28–29

4.1.3 Exchangeable answers and de Finetti’s theorem

  • For exchangeable priors, de Finetti’s theorem [18, 19] represents symmetric dependence as a mixture of answer laws, and the limiting increment profile is flat, forcing hyperbolic leverage.The answer law is learned within o(Q) questions; afterward, answers are independent conditional on that law and have constant expected surprisal.Source: §4.1.3 · pp. 29–31

4.2 Thermodynamic-limit calculus

  • Symmetry reduces the average over k-question subsets to a sum over prior-invariant orbits; the fully permutation-invariant spike prior has one orbit per size, collapsing G_k to one term.This reduction also supports moderate-n numerical results for less symmetrical priors.Source: §4.2 · p. 31

4.2.1 The finite sequence from which the limit is taken

  • The finite sequence G_n,k of mean block entropies has increments equal to mean conditional entropy of a fresh answer, and these increments form a deterministic nonincreasing staircase.For binary linear codes, the corresponding EXIT-function area law gives the code rate.Source: §4.2.1 · pp. 31–32
  • At finite size, the sequence covers 0 ≤ ℓ < Q, with zero remaining entropy at ℓ = Q.Source: §4.2.1 · p. 32

4.2.2 A precise macroscopic-limit statement

  • The initial marginal entropy η0 must remain separate from γ(0+), since learning completed in o(Q) questions creates a boundary layer invisible in the bulk profile.The gap η0 − γ(0+) measures that boundary-layer learning.Source: §4.2.2 · pp. 32–33
  • The macroscopic limit assumes fixed answer width, convergent initial entropy, almost-everywhere profile convergence, and positive area under γ.Positive area is the nondegenerate extensivity condition: learning continues into the bulk rather than settling within a boundary layer at t = 0.Source: §4.2.2 · p. 33
  • The limiting leverage is L(t) = [η0 − (1−t)γ(t)]/g(t), where γ(t) is the next-answer entropy and g(t) is its cumulative area.The numerator is what was knowable initially minus what remains in unasked questions; the denominator is the surprisal received so far.Source: §4.2.2 · p. 33
  • Monotonicity and boundedness ensure convergent subsequences but not a unique profile, so uniqueness requires a coherent prior construction or profile convergence as a hypothesis.A family may alternate between two constructions as n varies.Source: §4.2.2 · p. 34

5 Polynomial degree as complexity prior

This section develops polynomial degree over F2 as a tractable simplicity prior for nonconstant bulk learning, deriving its learning curve from Reed–Muller entropy increments and showing how the rate distribution realizes any nonincreasing profile in [0, 1]. Toy statistics also show that population can outperform simplicity in aggregate while the per-map ordering remains unchanged.

5 Polynomial degree as complexity prior

  • Degree-based priors avoid the circuit-complexity approach’s limitations and sustain information stores that do not settle until macroscopic learning times.A single-temperature weighting concentrates on a thin shell; allocating a shared quota to each degree keeps every shell and map at positive weight in the thermodynamic limit.Source: §5 · p. 35

5.1 Polynomials over F2, and the butterfly

  • Over F2, each Boolean map has a unique polynomial representation, and its degree is the largest monomial size with a nonzero coefficient.The truth-table-to-coefficient transform is the XOR-butterfly, which is its own inverse and can be computed efficiently via its tensor-product structure.Source: §5.1 · pp. 36–37

5.2 Complexity classes and the sampling rule

  • The prior preserves positive weight for every map while strictly decreasing map probability with degree, making it a full-support Occam prior.Each shell receives macroscopic weight by construction, counteracting the severe scarcity of lower-degree maps without ruling out any degree in the thermodynamic limit.Source: §5.2 · p. 40
  • The sampling rule draws a rate R from CDF F, selects the degree class whose rate gap contains R, then samples a map uniformly within that class.Thus F determines aggregate weight across shells, while uniform sampling within a class gives each allowed monomial coefficient a fair-coin draw.Source: §5.2 · p. 40

5.3 Three terms for the leverage average

  • The exact finite leverage law is organized into three terms, including prior table entropy Q G_n,1, and each term reduces to a statement about F.Source: §5.3 · p. 42

5.3.1 The table entropy

  • At every finite n, every answer is a fair bit and the initial answer distribution is fully uniform, so the prior’s content is entirely correlational.This holds in every degree class, without taking a limit or referring to F.Source: §5.3.1 · p. 42
  • Each map within a degree class is equally weighted, and the constant monomial pairs maps into complementary halves, giving every question marginal answer probability 1/2 and initial table entropy Q.Source: §5.3.1 · p. 43

5.3.2 The received entropy

  • Within a degree class, entropy equals the rank of the asked-column submatrix; finite dependencies smear the transition, but Reed–Muller capacity yields a limiting step at the class rate.The class label costs a vanishing fraction of the run, and averaging the per-class limits gives mean entropy increment min(t, R).Source: §5.3.2 · pp. 43–45

5.3.3 The increment

  • The limiting fresh-answer entropy profile is γ(t) = 1 − F(t), since a class contributes a full bit until exhausted and none afterward.The contribution of uncertainty about the class label to the increment vanishes as n grows.Source: §5.3.3 · p. 46

5.4 The macroscopic curve

  • The macroscopic leverage curve follows from γ(t) = 1 − F(t), and any nonincreasing profile in [0, 1] can be realized by choosing F(x) = 1 − γ(x).At continuity points, the curve converges where its denominator is positive; under the stated endpoint conditions, L_F(0) = 1 + F′(0) and L_F(1) = 1/E_F[R].Source: §5.4 · p. 48

5.5 Toy statistics: min and max draws

  • For r uniform draws, keeping the minimum yields constant leverage r + 1, while keeping the maximum produces leverage rising from 1 to (r + 1)/r.The minimum concentrates prior weight on low-rate classes; the maximum shifts weight toward high-rate classes and delays deductions.Source: §5.5 · p. 50
  • Population can beat simplicity in aggregate, while the per-map ordering never wavers.The white bars represent the budgets w_d; their slight difference reflects leakage into a degree from higher classes.Source: §5.5 · p. 51

6 Discussion and Next Steps

The discussion extends the framework to stochastic answers and misspecified priors, sketches how to design learning curves, and proposes measuring leverage in real learners.

6.1 Stochastic truth maps

  • Under stochastic answers, chain rule (43) and the received-entropy law persist, but remaining-entropy accounting must include asked columns when predicting fresh responses.Answers no longer pin down the truth, so the profile remains positive rather than finishing at zero.Source: §6.1 · p. 52
  • With soft likelihoods, surprisal and belief movement diverge, so pricing answers by surprisal preserves the telescoping identity while pricing belief movement measures what the learner absorbed.These are distinct denominator choices and therefore different leverage theories.Source: §6.1 · p. 52

6.2 A prior that is wrong

  • A wrong prior adds D(πq∥M·,q) to expected surprisal; the discussion assumes full support to avoid zero believed probability and undefined updates under elimination.The cumulative excess surprisal is the relative entropy between the joint laws, but the numerator's relation to divergence remains open.Source: §6.2 · p. 52

6.3 Designing a curve, shell by shell

  • A demanded leverage sequence recursively fixes the block-entropy sequence, but each new correlation shell must admit a completion to a valid prior.The inverse Walsh transform recovers the prior once all correlators are specified; partial shell constraints alone need not guarantee nonnegative probabilities.Source: §6.3 · p. 53
  • Correlators in deeper shells affect learning later because a correlator touching r questions has macroscopic inclusion probability t^r, suppressing its profile contribution by a power of t.The approach would require thermodynamic limits for the correlators themselves.Source: §6.3 · p. 53

6.4 Measuring leverage in a real learner

  • A real-learner protocol can measure answer surprisal and predictive-entropy drops across sequential questions or training updates, but the question universe must be exhaustible to study macroscopic learning.Otherwise t = ℓ/Q stays in the boundary layer near zero.Source: §6.4 · p. 53

Appendices

The appendices provide supporting derivations, examples, constructions, extensions, and reference material for the essay.

Appendices

  • Appendices A–E develop correlator and elimination tools, examples, and prior constructions; F–H treat question choice and circuit-complexity priors; I–J collect symbols and scripts.Appendix B walks through all four questions, while Appendix C computes every block entropy from a single tensor sweep.Source: Appendices · p. 54

A Correlators

The correlator appendix transforms a prior into a ledger indexed by question subsets, where updates redistribute correlation structure and reveal how answered questions affect future predictions.

A Correlators

  • For m = 1, the Walsh–Hadamard transform maps the belief over truth tables to correlators indexed by question subsets, and the complete ledger determines the prior.Rows encode subsets, with the row index serving as the subset mask.Source: A Correlators · p. 56
  • Shell 1 records question biases, while shell 2 captures pair agreement that the answer matrix cannot distinguish; higher shells encode subtler joint structure.A product prior factorizes its correlators, whereas correlated knowledge appears in non-factorizing correlators.Source: A Correlators · p. 56
  • Each answer update combines every correlator with its partner differing by the asked question, then renormalizes by the updated normalization coordinate.The observation mask has only two nonzero ledger entries for m = 1.Source: A Correlators · p. 57
  • The asked question's bias saturates to certainty, while shifts in unasked columns track covariance with the asked question; product priors have no such transfer.The example's negative pair correlator indicates slightly more disagreement between questions 11 and 10, while the other pairs lean toward agreement.Source: A Correlators · pp. 57–58
  • Updates move structure one shell down toward the answer matrix, as correlations stored jointly with the asked question become lower-order predictions.The discussion describes higher shells as increasingly conditional knowledge.Source: A Correlators · pp. 58, 60
  • After all four questions are answered in the walkthrough, the ledger becomes the correlator transform of a point mass on the surviving map.The XOR toggles commute, so the answer order does not affect the final ledger.Source: A Correlators · p. 60

A.1 General m

For multiple-bit answers, the correlator ledger extends from individual question sites to blocks of answer bits, with updates combining all correlators linked to the asked block.

A.1 General m

  • With m output bits, each question contributes m sites, and correlators are indexed by subsets of those mQ sites.The answer matrix is recovered from the correlators supported on one question's block.Source: §A.1 · pp. 60–61
  • An answer update combines each correlator with its A partners, one for each subset of sites toggled within the asked question's block, then renormalizes.For m = 1, these formulas reduce to the earlier two-term update.Source: §A.1 · p. 61
  • In the sparse m = 2 example, the asked site saturates to −1, while a foreign-site correlator changes from −0.060 to +0.200.The update groups four correlators into a jointly averaged clique.Source: §A.1 · p. 62

B Playing the guiding example

The guiding example shows how a prior can make learning uneven: an early answer can cost more surprisal than the uncertainty it clears, while later answers exploit correlations. Across a complete run, the prior clears more table entropy than the surprisal received.

B Playing the guiding example

  • Question 1 costs 1.269 bits of surprisal but clears only 0.748 bits of table entropy, yielding L1 = 0.589.The realized answer is the less informative branch, so this round is anti-leverage despite correlations helping on average.Source: B Playing the guiding example · p. 64
  • Question 2 clears 1.113 bits for 0.604 received, but cumulative leverage remains just below one at L2 = 0.993.The favored answer and a 0.055-bit drop in the correlation store contribute to the gain.Source: B Playing the guiding example · p. 65
  • Question 3 clears 0.801 bits for 0.292 received, raising cumulative leverage to L3 = 1.229 as the correlation store reaches zero.With no correlations left, the final question can only be observed, not leveraged.Source: B Playing the guiding example · pp. 66–67
  • 2.925 bits of table entropy are cleared for 2.231 bits of surprisal received over four questions, giving L4 = 1.311.The cumulative stack first falls below its initial-entropy baseline after question 2, when genuine deduction overtakes the early loss.Source: B Playing the guiding example · p. 67

C Block entropies by elimination

  • A tensor of map-survival rules reuses elimination sums to calculate block entropies without assuming symmetry or independence of the prior.The method sums surviving prior weights across question sets and answer strings.Source: C Block entropies by elimination · p. 68

C.1 Map survival under binary answers

The block entropies can be computed by encoding which maps survive each set of answer restrictions, then aggregating entropy contributions by block size. The construction extends to larger answer alphabets and can be pruned when only early block entropies are needed.

C.1 Map survival under binary answers

  • A local rule keeps maps answering 0, keeps maps answering 1, or leaves either answer unrestricted; tensoring these rules yields each surviving prior weight.The wildcard marks an unasked question and does not claim that its answer cannot be deduced.Source: §C.1 · pp. 68–69
  • The shared tensor sweep and entropy accumulation take order 3^Q work, versus order 4^Q for scanning the prior separately for each question set.Reusing sums of surviving weights gives about a hundredfold savings at (4, 1) and fortyfold at (3, 2), while the calculation remains exponential in Q.Source: §C.1 · p. 71

C.2 General answer alphabet

  • For a fixed answer alphabet of size A, the complete construction and entropy accumulation take order (A + 1)^Q work, versus order (2A)^Q for separate scans.The all-answers rule remains the wildcard: it excludes no maps.Source: §C.2 · pp. 71–72

C.3 Stopping at ℓand the cost of another Gk

  • Pruning the sweep at ℓ produces the requested G0 through Gℓ, but does not make Gℓ+1 free because discarded branches must also be computed.The scalar values G0 through Gℓ alone generally do not determine the next value.Source: §C.3 · pp. 72–73

D Block priors and the Bernstein profile language

Exchangeable priors are mixtures of independent answer draws and have a flat interior learning profile, whereas fixed-size independent blocks let local answer dependencies shape that profile. For bounded block types with convergent population shares, the limiting profile is an average of within-block conditional entropies.

D Block priors and the Bernstein profile language

  • Every projectively consistent exchangeable prior is generated by drawing an answer law and then answering questions independently from it.The construction has full support wherever the mixing distribution does and yields a closed-form thermodynamic limit.Source: D Block priors and the Bernstein… · p. 74
  • Exchangeable priors have a flat interior profile and a hyperbolic leverage curve; a profile changing throughout 0 < t < 1 requires structure tied to groups or question addresses.A convergent frequency law can still produce a flat profile even for an exchangeable prior that is not a mixture of independent draws.Source: D Block priors and the Bernstein… · p. 74

D.1 Independent blocks of questions

  • A block’s entropy profile records joint answer uncertainty after observing j locations, and its successive differences give the uncertainty in a fresh answer.For two fair answers, independent bits have increments (1, 1), while a copied fair bit has increments (1, 0).Source: §D.1 · p. 75
  • For independent blocks from a fixed finite set of bounded types, the limiting profile averages each type’s mean conditional entropy according to its share of questions.The share of each type is assumed to converge as the table grows.Source: §D.1 · pp. 74–75

D.2 Block laws and their map priors

Independent block laws generate map priors and their leverage curves from within-block entropy profiles. The profile language constrains leverage behavior, while finite-size examples show how different block structures produce distinct learning curves.

D.2 Block laws and their map priors

  • Clique blocks of two questions support four maps in the example, and learning either answer settles its partner, giving L ≡ 2.The map weights are products of the two blocks’ answer probabilities.Source: §D.2 · p. 77

D.3 Bernstein polynomials as a profile language

  • Block entropy increments are nonincreasing, so the macroscopic profile is nonincreasing, although leverage itself need not be.Mixtures of common-length MDS blocks approximate continuous nonincreasing profiles when the answer alphabet can grow; this is not completeness at fixed answer width.Source: §D.3 · p. 78

D.4 Leverage curves at finite n

  • The finite curves match their macroscopic limits: clique blocks have L ≡ 4, parity-block deductions arrive late, and the mixed MDS example peaks at 1.645 near t ≃ 0.72 versus 1.6 at completion.The comparison uses exact finite-n leverage rather than simulation.Source: §D.4 · pp. 78–79, Figure 8 · p. 79

E.1 One question, branch by branch

  • For the spike prior’s first question, the expected leverage can remain well above one even when the refuting branch’s leverage falls below the uniform baseline and eventually below zero.Aggregate leverage divides expected entropy reduction by expected surprisal, rather than averaging the branch leverage ratios.Source: Figure 10 · p. 81, §E.1 · p. 81

E.2 The extraction ratio

The extraction ratio measures the share of dependency information released by an answer, while leverage measures released dependency information per received bit. The exact one-question ratio has stated finite-size trends, and the theorem for spike-plus-uniform priors does not automatically extend to broader hedges.

E.2 The extraction ratio

  • The total correlation C = H(M(0)) − G_Q is dependency information hidden by separate answer marginals; leverage above one measures released dependency information per received bit.R1 is the share of the whole dependency stock extracted, whereas leverage uses received surprisal as its denominator.Source: §E.2 · p. 81
  • At (n, m) = (2, 1), the exact one-question extraction ratio is 12/17 ≃ 0.706, versus 0.75 for the large-N approximation.The two values share a thermodynamic limit.Source: §E.2 · p. 81
  • In Figure 11, growing n drives the exact one-question ratio toward 1/2 as p → 1−, while growing m lifts it toward one.The figure plots the ratio only for 1/N < p < 1.Source: Figure 11 · p. 82
  • The theorem covers the spike-plus-uniform family; extending it to broader uninformative hedges requires a separate extremal argument, since full support alone is insufficient.Source: §E.2 · p. 82

E.3 The sharp-prior limit and the order of limits

The sharp-prior analysis takes p toward one with n and m fixed, where leverage is a limiting ratio rather than a value at the delta prior. The order of limits matters, and joint scalings yield a crossover between the two endpoint regimes.

E.3 The sharp-prior limit and the order of limits

  • For fixed finite Q, as p → 1−, the one-question leverage tends to Q − (Q − 1)2^-m.This limit is taken after setting ε = 1 − p and cancelling the common ε log2(1/ε) factor.Source: §E.3 · p. 82
  • The coefficient 1 − 2^-m is the fraction of hypotheses eliminated by one answer, but it is not literally the fraction of every prediction column settled.At p = 1, leverage itself is 0/0; the finite value is the ratio as p approaches one.Source: §E.3 · p. 82
  • In the sharp-prior curve normalized by Q, an O(1) boundary layer is squeezed toward t = 0, leaving a plateau at 1 − u; tightening the prior lifts the curve only logarithmically.The plateau is approached pointwise in t but not uniformly.Source: Figure 12 · p. 83, §E.3 · p. 83
  • For 0 < t < 1 under the joint scaling, G1 ∼ (1 − u)ε_n^λQ, G_ℓ ∼ ε_nQ(λ + mt), and G_ℓ+1 − G_ℓ ∼ ε_nm.Substitution gives a crossover family whose endpoints recover the two familiar orders of limits; at t = 1 the completion formula gives the same value.Source: §E.3 · p. 83

F Choosing the questions

Question selection can vary in lookahead and adaptivity, and adaptive questioning can outperform fixed orders when answers guide what to ask next. The paper also introduces a simplicity-based Gibbs prior as an illustration.

F Choosing the questions

  • The four protocols combine one-step or ℓ-step lookahead with a fixed question order or one chosen contingently from answers.Source: F Choosing the questions · p. 84, Table 8 · p. 84
  • For the guiding prior, contingent greedy outperforms the uniform order and matches the contingent ℓ-optimum at every horizon, but the authors caution this is prior-specific.The exact dynamic program has reachable-posterior states—81 in the guiding example—and is astronomical beyond it; optimal decision trees are NP-complete in general.Source: F Choosing the questions · p. 84
  • Adaptive questioning can strictly improve on every fixed set of the same size because an answer can indicate which question will be useful next.Source: F Choosing the questions · p. 84
  • In the n = 2, m = 1 example, two adaptive questions identify the map completely, while the best fixed pair leaves an expected 1/2 bit unresolved.The adaptive second question distinguishes the surviving pair; no single fixed pair splits both possible pairs.Source: F Choosing the questions · p. 85

G The Gibbs complexity prior

  • The Gibbs-prior appendix illustrates the principle that simpler explanations are likelier, using circuit complexity as a quantitative simplicity measure.The essay says its main body does not depend on this illustration.Source: G The Gibbs complexity prior · p. 86

G.1 AIG complexity

The appendix constructs Gibbs priors from circuit complexity, visible truth-table descriptors, and coupling fields, then tracks how uncertainty, received surprisal, and inferred information partition the initial table entropy.

G.1 AIG complexity

  • AIG complexity counts the fewest two-input AND nodes in a feed-forward circuit with complemented edges; constants, input wires, and inversion cost zero.For multiple outputs, the metric is the size of one joint circuit, with gates shared.Source: §G.1 · p. 86
  • The footprint combines input support and number of distinct outputs, while the bias counts truth-table ones minus zeros and breaks output-negation symmetry.Source: §G.1 · p. 86

G.2 The ensemble

  • Occam spreads belief mainly across six gate-free maps, whereas the Pragmatist puts 0.90 of its mass on the two constants, biased toward TRUE.If the map is non-constant, renormalization scales the Pragmatist’s interior mass up.Source: §G.1 · p. 87

G.1 AIG complexity

  • At (4, 1), shell counts grow faster than e^-X decays through X = 3, so Occam places most faith in maps with X_j ∈ {2, 3}.The ten gate-free maps contrast with 320 maps at the X = 10 ceiling; the analogous mass-growth threshold at (3, 2) is X = 2.Source: §G.1 · pp. 87–88

G.2 The ensemble

  • The Gibbs prior assigns each map weight proportional to e^-E_j, with energy linear in complexity, footprint, and bias; positive couplings suppress their corresponding descriptor values.The Pragmatist uses a negative bias coupling to favor 1-heavy tables and break output-negation symmetry.Source: §G.2 · pp. 88–89, Table 9 · p. 88

G.3 The layered entropy books

  • In expectation, table-entropy loss equals received surprisal plus withdrawal from the correlation store, and these three quantities sum to the starting table entropy at every ℓ.The displayed panels use one row per system size on a shared vertical scale and one column per prior.Source: §G.3 · p. 89

G.4 Trajectories

Across three system sizes, the trajectories show that leverage depends on the prior and question schedule; deep correlations can produce an interior hump, and the information-optimal schedule need not maximize leverage.

G.4 Trajectories

  • The figures average question order and plot the ℓ-optimal schedule only through its target horizon; all schedules agree at ℓ=1, and full-length curves share the endpoint H(M(0))/H(p).The contingent twin reproduces the fixed optimum’s curve to machine precision where computed.Source: §G.4 · p. 90
  • At (2, 1), Occamer’s endpoint leverage is 1.2224 versus Occam’s 1.0829, while Pragmatist greedy is less leveraged than random order at ℓ=2 (2.538 versus 2.582).Occamer lifts the curve without creating strategic choices; the Pragmatist’s greedy pair knows more but pays more surprisal.Source: Figure 13 · p. 90, §G.4 · p. 91
  • 0.405 bits remain under Pragmatist greedy, versus 0.198 for the optimal four; greedy nevertheless has higher leverage (4.445 versus 4.355).The optimal quadruples are the even-weight inputs and their odd-weight image under negating one input bit.Source: Figure 14 · p. 90, §G.4 · p. 91
  • At (4, 1), Occamer’s C0 is 8.10 bits versus Occam’s 2.48, and the average curve peaks at 2.20 at ℓ=6.The optimal eight questions form a parity class in every setting; greedy misses that class under both complexity-only settings but finds it under the Pragmatist.Source: §G.4 · p. 91, Figure 15 · p. 91

H Computing the circuit complexities

  • Circuit complexities are computed by reducing truth tables to relabeling-group orbits, then applying exact SAT synthesis to class representatives.The reduction leaves 222 classes at (4, 1) and 308 at (3, 2); the (4, 1) values come from a published dataset, while all (3, 2) classes were synthesized from scratch.Source: H Computing the circuit complexities · p. 92
  • The minimum circuit size X_j is the first gate budget with a satisfiable formula; refuting every smaller budget establishes a proven minimum.The authors use a SAT solver backend and note that their own synthesizer cannot reach the hardest (4, 1) classes, so they adopt the proven published values.Source: H Computing the circuit complexities · p. 92

I Symbols

  • Table 10 lists the work’s most important symbols in order of appearance.The supplied passage identifies the table’s scope but does not enumerate its entries.Source: Table 10 · p. 93

J Scripts

  • The scripts are grouped by role: compile-time tables, generated figures, the circuit-complexity pipeline, and checks.The scripts produce the work’s numbers, curves, and combinatoric sets.Source: Table 11 · p. 94, J Scripts · p. 94
Loading 2609.08054v3…