PaperlayerView exact revision on arXiv

Source-linked AI summary

Verification with Transfer: Exact Information Frontiers and Their Price in Calls

Hazar Yueksel

arXiv:2610.12211v1cs.LGcs.CRcs.ITmath.ITstat.ML

TL;DR

Whole-answer verification can require exponentially many attempts for a flat-prior answer, motivating transfer from related source tasks. The paper derives information and call frontiers for protocols that interleave sources and verification, then identifies when source-first scheduling preserves performance and how the bounds apply to linear banks.

  • Problem

    Whole-answer verification reveals little, and the paper asks how much source information and how many calls are needed to succeed within a verification budget, including when source-first scheduling loses nothing.

    Source: §1 · p. 1

  • Method

    The paper characterizes interleaved protocols through a list rate-distortion information frontier and call bounds, then analyzes source-first guarantees and linear task banks.

    Source: §2.1 · p. 3, §2.2 · p. 4, §3 · p. 5

  • Results

    The information price lower-bounds expected binary calls, designed sources meet it within 1 + log2 5 calls for unique answers, and fixed-source reordering preserves hard caps only with exact verification.

    Source: §1 · p. 1, §6 · p. 8

  • Takeaways & Limitations

    For linear banks at zero error under a hard call cap, calls beyond the rounded-up information price are spent on nuisance directions identified by the planner.

    Source: §6 · p. 8

    The frontiers assume finite alphabets, and the rank law, planner, and learner results assume uniform, noiseless linear banks; planner efficiency requires small nuisance dimension.

    Source: §6 · p. 8

Abstract

from arXiv · show

A verifier that accepts or rejects whole answers reveals little: under a flat prior over $k$-bit answers, zero error needs $2^k-1$ verifications. The usual remedy is to solve related source tasks, either all first, as a curriculum does, or interleaved with verification. We price this remedy in information and in calls. With an exact verifier, the least causal information that any interleaving of source calls and $n$ verifications needs to succeed with probability $s$ is a list rate-distortion function, attained by one observation before any verification. It lower-bounds the expected number of binary source calls, which designed sources meet within $1+\log_25$ calls for unique answers and within a logarithmic term in general, where no additive constant suffices. With an exact verifier and fixed sources, moving every call before the first verification preserves all hard caps on calls, although interleaving can save unboundedly many expected calls; under a noisy verifier, source-first protocols can lose unbounded factors in information and in error. For linear banks over $\mathbb{F}_2$, optimal accuracy has a closed form, and after a polynomial-time reduction the budget profile is computable in time $2^{O(h^2)}\operatorname{poly}(J,k+h)$ for $J$ sources and nuisance dimension $h$. In these banks, for zero error under a hard cap, the calls beyond the rounded-up information price are exactly those spent on nuisance. Every numbered result apart from two clauses about the planner is machine-checked in Lean 4, assuming two published results. Used as a ruler, the frontier shows a small transformer using all delivered bits at latent dimension $5$ and none at $11$ within fixed training budgets; in a test with predictions recorded before training, low XOR degree of the target bits did not suffice for their use.

1 Introduction

Whole-answer verification is information-poor, motivating transfer from related source tasks and a choice between source-first and interleaved schedules. The paper prices these protocols in information and calls, characterizes when source-first scheduling suffices, and applies the resulting frontier to linear banks and learned decoders.

1 Introduction

  • For a flat prior over k-bit answers, zero error requires 2^k - 1 verifications; related source tasks can exclude many target answers at once.Curricula solve source tasks first, while an alternative is to interleave source calls with verification.Source: §1 · p. 1
  • With exact verification, source-first scheduling preserves hard call caps for fixed sources, but interleaving can save unbounded expected calls against given sources; noise can make source-first lose unbounded factors in information and error.For unique answers with designed sources, interleaving saves only a constant number of expected calls.Source: §1 · pp. 1–2
  • The least causal auxiliary information for success probability s within n verifications equals a list rate-distortion function, attained by one observation before verification.The exact-verifier converse leaves verification transitions unchanged, so they are not charged as auxiliary information.Source: §1 · pp. 1–2
  • Binary source calls lower-bound the information price; designed sources approach it within a constant for unique answers, while general acceptance sets can have an unbounded, at-most-logarithmic excess.For unique answers, the stated additive bound is 1 + log2 5; for general acceptance sets, no constant suffices.Source: §1 · p. 2
  • For uniform linear banks over F2, optimal accuracy is min{1, (n + 1)2^-k+ρ_b}, and the budget profile is computable after polynomial-time reduction in 2^O(h^2) poly(J, k+h) time.At zero error under a hard cap, calls beyond the rounded-up information price are exactly those spent on nuisance.Source: §1 · p. 2
  • The paper uses the frontier to measure how much information a small transformer converts into target probability and what the remainder costs in verifications.Every numbered result apart from two planner clauses is machine-checked in Lean 4.Source: §1 · p. 2

2 Verification with side information

The section models a learner choosing between whole-response verification and information-bearing auxiliary calls, then characterizes the information and call costs of succeeding within a verification budget. Its results distinguish designed from fixed sources, exact from noisy verification, and unique answers from general acceptance sets.

2 Verification with side information

  • The model permits history-dependent auxiliary observations about a latent world, while verifications accept or reject responses and accepted responses may themselves be output.Auxiliary information is measured causally, discounting what verifications and earlier calls have already revealed.Source: §2 · pp. 2–3
  • Without auxiliary calls, success within n verifications is bounded by the prior mass of a list of at most n + 1 responses; for unique answers this is the mass of the n + 1 most probable answers.For general acceptance sets, the benchmark is weighted maximum coverage.Source: §2 · pp. 2–3

2.1 The information frontier

  • The minimum auxiliary information for success probability s with at most n verifications is R_n(q, s), attained by a single observation before any verification.An optimal list can be sent, then all but its last entry verified; if none is accepted, the last entry is output.Source: §2.1 · p. 3
  • For unique answers under a uniform prior, the frontier is the list-Fano value kl+(s ∥ (n+1)/M); with overlapping acceptance sets, the optimal reference prior need not equal q.For q = (0.8, 0.1, 0.1) and n = 1, zero error costs 0.2 bits.Source: §2.1 · p. 3

2.2 From information to calls

  • Binary source calls cost at least R_n(q, s), and designed sources meet the information price within 1 + log2 5 calls for unique answers, or within 2 calls at zero error.For unique answers, the bound is tight to an additive constant at every success level.Source: §2.2 · p. 4
  • For general acceptance sets, the excess call cost over the information price can be unbounded, though it is at most logarithmic.At zero error with n = 0, binary-source protocols require at least the graph's chromatic entropy, while the information price is its graph entropy.Source: §2.2 · p. 4
  • Against fixed sources, interleaving can save unbounded expected calls; with exact verification, moving source calls first preserves hard caps and at least the same success probability.For unique answers and designed sources, the expected-call saving is bounded by 1 + log2 5, and by 2 at zero error.Source: §2.2 · pp. 4–5
  • With a noisy verifier, source-first protocols can require an unbounded factor more information or incur an unbounded factor more error than interleaving.At equal call caps, the cited instance has an error ratio of 1/(2η) when ϵ = η.Source: §2.2 · p. 5

3 Linear task banks

For uniform linear banks, exact accuracy under arbitrary interleaving is attained by a fixed maximizing source subset, and the planner reduces source selection to nuisance-quotient subspaces. Under zero error and a hard cap, calls beyond the rounded-up information price are spent on nuisance directions.

Exact accuracy

  • A fixed maximizing source subset followed by enumeration attains the exact accuracy for arbitrary adaptive interleaving; adaptive source selection and budget allocation do not help.The bank has a linear target and binary sources that return linear forms of the latent world.Source: §3 · p. 5

Computing the profile

  • QSP enumerates subspaces of the nuisance quotient rather than all 2^J source subsets, using enumeration on the small side of Forney’s duality.With unbounded nuisance, maximizing-subset selection contains syndrome decoding and is NP-hard; the reported algorithm does not claim its exponent is optimal.Source: §3 · pp. 5–6

The call price of nuisance

  • At zero error under a hard cap, the minimum source budget is bn = κ + u(κ), and the excess u(κ) is exactly the number of calls spent on nuisance directions.The excess is at most h and vanishes when an optimal subset resolves one new target dimension per call.Source: §3 · p. 6
  • With k = 2, two sources that each reveal one target bit and n = 2, interleaving uses 1/2 expected calls, versus a source-first price of 1.The protocol verifies two candidates first and calls a source only if both are rejected.Source: §3 · p. 6

Learning the bank, and checks

  • A rank-ℓ bank can be recovered from ℓ0 + ⌈log2(1/δ)⌉ fully labelled contexts with probability 1 − δ when its rank is at most ℓ0.After recovery, QSP plans optimally.Source: §3 · p. 6
  • QSP recovered profiles matching a comparison solver wherever both finished; under a 15-second cap, QSP finished all 27 banks and GHWs finished 21.The best source-aware baseline reached accuracy 0.750 on independent banks and 0.875 on nuisance-clustered banks at the exact zero-error cap, while QSP reaches one there.Source: §3 · p. 6

4 The frontier as a ruler

The frontier measures whether a small transformer uses information delivered by a planner’s sources. Use declines with latent dimension in the reported runs, and low XOR degree alone does not guarantee use.

How much is used

  • The decoder used all 12 of 12 contexts within 0.2 bit of delivered information at d = 5, but pooled use fell to 84% at d = 6, 49% at d = 7, 14% at d = 8, and 0% at d = 11.The two-layer, 0.4M-parameter transformer was trained from scratch; the reported zero-error-split fractions use four secrets per bank.Source: §4 · p. 6
  • Figure 3 compares bits used with bits delivered against the exact-posterior line, and plots zero-error-split use against the largest XOR degree of determined target bits.The degree-controlled banks were selected and predicted before training.Source: Figure 3 · p. 7, §4 · p. 7
  • At d = 8, the planner’s sources left the learner 20.9 guesses against 1.8 for the exact posterior; none of eight tested configurations reached the frontier.The configurations used widths 64–512 and up to 20,000 training steps.Source: §4 · p. 7

Which bits are used

  • Across 15 banks, the decoder was on the frontier exactly on the five banks where every determined target bit had degree at most two, but the controlled test rejected the prediction that low degree ensures use.On controlled low-degree banks, the decoder used 66%–69% of delivered bits; on high-degree banks, it used 42%–67%.Source: §4 · p. 7
  • The ruler adds a count of unused delivered bits against an exact reference and prices those bits in verifications, extending known parity failures.Three of six controlled banks recover further bits at four times the training budget.Source: §4 · p. 7

5 Related work

The paper connects verification and transfer to exact learning, guessing, information complexity, and coding theory. Its stated addition is the causal information frontier for interleaved source calls and verifications.

Verification, guessing and exact learning

  • For unique answers, target-only verification is guessing, while whole-answer verification is an equivalence-query oracle [Angluin, 1988; Heged˝us, 1995].Prior work studied how side information reduces guessing under fixed helpers, compressed descriptions, or distortion criteria [Bunte and Lapidoth, 2014; Graczyk et al., 2022].Source: §5 · p. 7
  • The static list rate–distortion function and list-Fano special case are classical [Csiszár, 1974; Sakai, 2020]; this paper adds their interleaved, causal version, where exact-verification adaptivity buys nothing in information.The call results characterize what interleaving buys in calls.Source: §5 · p. 7

Lower bounds with interaction and value of information

  • The converse uses a change-of-measure approach [Kaufmann et al., 2016; Simchowitz et al., 2017; Garivier et al., 2019] of the interactive-Fano type [Chen et al., 2024], with exact verifications canceling in the reference law.Charging interaction by information rather than messages follows information complexity.Source: §5 · pp. 7–8
  • Noisy verification is related to search games with lies and noisy twenty questions, where adaptive query selection can matter for error probability [Naghshvar and Javidi, 2013].Non-adaptive policies are optimal for entropy loss in noisy twenty questions.Source: §5 · p. 8

Codes and parities

  • The linear-bank profile is a relative dimension/length profile [Wei, 1991; Forney, 1994; Luo et al., 2005; Kurihara et al., 2012; Zhuang et al., 2014], and its delivered-versus-usable information gap connects to V-information [Xu et al., 2020].The paper’s ruler measures that gap against an exact reference and prices it in verifications.Source: §5 · p. 8

6 Limitations and conclusion

The paper’s guarantees depend on the verification and source setting: source-first scheduling preserves hard caps with fixed sources under exact verification, but can lose in expectation or under noise. The neural study is limited to small synthetic-bank experiments.

Limitations

  • The frontiers assume finite alphabets; the rank law, planner, and learner assume uniform, noiseless linear banks, and the planner is efficient only for small nuisance dimension.The noisy-verifier results are converses, with one exact result on the paper’s instance, rather than a general frontier.Source: §6 · p. 8
  • The neural measurements use small transformers trained from scratch on synthetic banks, with three banks per dimension, few seeds, and fixed training budgets; the results are not claims about pretrained language models.At 24,000 steps, three of six controlled banks recover further bits, so use fractions depend on training budget; the degree analysis also rests on few banks.Source: §6 · p. 8

What this means for curricula

  • Source-first scheduling preserves hard caps with fixed sources under exact verification, but interleaving can save expected calls and, under noisy verification, can reduce error at equal caps by an unbounded factor.Under noise, the information needed for zero error can also increase by an unbounded factor for source-first protocols.Source: §6 · p. 8

Conclusion

  • The information price lower-bounds expected binary calls, and designed sources meet it within 1 + log2 5 calls for unique answers; in linear banks, hard-cap calls beyond the rounded-up price go to nuisance.Whether a learned decoder uses the delivered information is a separate question measured by the ruler.Source: §6 · p. 8

AI Use Statement

The appendices formalize the information and verification bounds, show how list coverage attains the information frontier, and document the use and checking of AI-assisted work.

AI Use Statement

  • The authors used generative AI across theory, proofs, experiments, code, literature work, and drafting, reviewed the assisted work, and machine-checked numbered results except stated exceptions.They state that datasets and results were not generated by AI; reported numbers came from released code and logged runs.Source: AI Use Statement · pp. 8–9

A Complete proof of the local benchmark

  • Fixing the learner’s complete random seed makes its actions deterministic; a silent trajectory then yields at most n + 1 candidate answers covering every successful path.A list of at most n + 1 answers attains the bound by querying all but the fallback answer.Source: A Complete proof of the local benchmark · p. 14

B Complete selective-channel construction

  • A selective-channel argument bounds success under a call cap by the binary-KL divergence between actual and reference success, with source information and prior divergence as the budget.The proof applies to the joint event of success and staying within the cap; it does not assume the call count is independent of the world.Source: B Complete selective-channel… · p. 15

C Rate–distortion dual and exact operational reduction

C.3 From the dual to the protocol theorem

  • The information lower bound is attained by sending an optimal answer list before verification and then querying its entries until success, with the final entry as fallback.The list channel’s information is the causal information charge, and the strategy succeeds whenever the list covers the world.Source: §C.3 · pp. 16–17

D.1 Coverage-polytope entropy

  • At zero error, list-channel information equals the prior-weighted log inverse of each world’s coverage probability, linking a coverage-polytope optimization to the causal price.The construction supplies an attaining channel.Source: §D.1 · p. 17

D.2 Unique answers

  • For unique answers, the zero-error optimum assigns inclusion probabilities proportional to prior mass until they saturate; for q = (0.8, 0.1, 0.1) and one query, the price is 0.2 bits.An interleaved protocol attains the same causal information cost, although its upfront message has one raw bit of entropy.Source: §D.2 · p. 17

D.3 Uniform finite-error frontier

  • For a uniform prior, an upfront list channel attains the finite-error list-Fano frontier, while no source information is needed when success is at most the list’s baseline coverage.The matching converse extends optimality to interleaved protocols under the causal information budget.Source: §D.3 · p. 17

E Zero-error price and the remaining exponential cost

The section characterizes zero-error transfer through list coverage, including a prior-dependent formula for unique answers. It also distinguishes exact prices from simpler bounds and relates information to verification and call budgets.

E Zero-error price and the remaining exponential cost

  • The exact zero-error information price with n target queries is characterized through list coverage; for unique answers, the price is zero when n + 1 covers all M answers.For fewer than M list positions, the section gives a clipped prior-dependent formula.Source: E Zero-error price and the remaining… · p. 18
  • For q = (0.8, 0.1, 0.1) and one query, the exact price is 0.2 bits, versus 0.1520 bits from fixing the comparison prior at q.The optimizing comparison prior is (2/3, 1/6, 1/6).Source: E Zero-error price and the remaining… · p. 18
  • For uniform unique answers, zero error with B optimally placed auxiliary bits is possible exactly when n + 1 ≥ M2^-B; these bits halve the required verifications but their acquisition calls are priced separately.The complete uniform finite-error frontier is the classical list-Fano value.Source: E Zero-error price and the remaining… · p. 18
  • With overlapping acceptance sets, fixing the comparison prior at q can be strict: for M = 4 and n = 0, the exact zero-error price is 0.811 bits, versus a 0.415-bit lower bound.The stated equality condition is transitivity of the acceptance structure’s automorphism group on worlds.Source: E Zero-error price and the remaining… · p. 18

G Source-first suffices for fixed sources

With fixed sources and exact verification, source-first protocols preserve hard call caps, though they need not preserve expected call or information costs. In linear banks, source replies reduce the target’s uniform support according to transfer rank, yielding closed-form budget profiles.

G Source-first suffices for fixed sources

  • At ϵ = 0.01 under noisy feedback, the exact information costs are 0.9900 bits upfront and 0.0793 bits with interleaving.The figure concerns a uniform binary target, one noisy query, and error tolerance δ = ϵ2.Source: Figure 5 · p. 19
  • Moving source calls before verification preserves separate source and target hard caps, and also preserves a hard total cap, while success is maintained.A source-first policy may still choose later sources based on earlier source outcomes; this does not imply preservation under expected-call constraints.Source: G Source-first suffices for fixed… · p. 20
  • Adaptive source selection can outperform every fixed two-source subset in the supplied four-world example, which is not a linear uniform source bank.Two adaptive calls identify the world, while any fixed two-source subset reaches only 3/4 accuracy without target queries.Source: G Source-first suffices for fixed… · p. 20
  • With prior (1−2p, p, p), interleaving achieves zero error using one source call in expectation, whereas an upfront protocol must always acquire the source.The corresponding causal source information is 2p bits for the interleaved protocol and h2(p) bits upfront.Source: G Source-first suffices for fixed… · p. 20

H Exact transfer rank and total-query optimization

  • In linear banks, a fixed source subset leaves a uniform target support of size 2^(k−ρ(S)), where ρ(S) is the number of target dimensions it resolves.The entropy–rank correspondence is described as familiar rather than a new result.Source: H Exact transfer rank and total-query… · p. 20
  • Under a total cap C, optimal accuracy is obtained by maximizing over source budgets b the value min{1, (C − b + 1)2^(−k+ρb)}.A maximizing fixed subset attains the bound; unused source capacity need not be spent.Source: H Exact transfer rank and total-query… · p. 21

I.1 Proof of Theorem 4

These proofs establish information and call bounds for exact verification, then show how call ordering behaves with fixed sources and noisy verification. They also derive a nuisance-dimension budget identity for linear banks and an exact noisy-verification separation.

I.1 Proof of Theorem 4

  • Expected binary source calls are at least the list rate–distortion information price; designed sources attain it within 1 + log2 5 calls for unique answers and a logarithmic excess in general.For unique answers, the zero-error construction is within 2 calls; for general acceptance sets, the chromatic- versus graph-entropy gap makes the excess unbounded but at most logarithmic.Source: §I.1 · pp. 21–22, §I.2 · p. 22

I.2 Proof of Proposition 5

  • For graph acceptance sets, expected calls can exceed the graph-entropy information price by an unbounded amount, because zero-error protocols must pay at least chromatic entropy.The gap is unbounded even for chordal graphs with uniform priors and persists for every fixed verification cap.Source: §I.2 · pp. 22–23

I.3 Proof of Proposition 6

  • With a given source bank, interleaving can save an unbounded number of expected calls over source-first protocols, although designed sources limit that saving to a constant for unique answers.For q = (1 − 2p, p, p), one verification and zero error cost 2p expected calls when interleaved, while source-first requires at least one call.Source: §I.3 · p. 23

I.4 Proof of Corollary 11

  • For linear banks under a hard cap and zero error, calls beyond the rounded-up information price equal the optimal subset’s calls spent on nuisance directions.The excess vanishes exactly when each call in an optimal subset resolves a new target dimension.Source: §I.4 · p. 23

I.5 Proof of Proposition 8

  • With a noisy verifier, interleaving can have unboundedly lower error than source-first protocols at equal call caps, even though calling both sources first can recover the interleaved error at one extra call.At ϵ = η, interleaved error is ϵη, while the best source-first error is η/2.Source: §I.5 · p. 24

J Noisy verification makes information order matter

  • For a uniform binary answer and one noisy query, the minimum interleaved auxiliary information is h2(ϵ) − h2(δ), while requiring information upfront can cost more.At zero error, the respective costs are h2(ϵ) and one bit; at δ = ϵ^2, the interleaved cost tends to zero while the upfront cost tends to one as ϵ → 0.Source: J Noisy verification makes information… · p. 24

K.1 Optimal arbitrary interleaving

  • The interleaved information bound follows because a noisy reply contributes at most 1 − h2(ϵ) bits, whereas error at most δ requires 1 − h2(δ) transcript bits.Querying first and describing the residual Bernoulli-ϵ error attains the bound.Source: §K.1 · p. 25

K.2 Optimal upfront information

  • For upfront information, the optimal cost is determined by the upper concave envelope of posterior entropy against error; at δ = ϵ^2, this cost tends to one as ϵ → 0.The corresponding interleaved cost tends to zero, so the information-cost advantage is unbounded and is not limited to zero error.Source: §K.2 · p. 25, §K.3 · p. 26

L Information quantity is not source usefulness

This section distinguishes source information from its usefulness for verification and develops exact planning methods for linear banks. It then reports their learning and planning behavior, including the scope limits of the experiments.

L Information quantity is not source usefulness

  • With 256 uniform targets and 15 exact queries, a balanced 16-way partition permits accuracy 1, while a reveal–erasure source carrying the same four bits reaches only 0.53125.Even 4.4 bits from the reveal–erasure source reaches only 0.578125; the gap persists under perfect posterior decoding.Source: L Information quantity is not source… · p. 26

M.1 Exact profile and attaining subsets

  • The quotient-subspace profile gives the maximum target-rank gain at each source budget, and enumerating generated quotient states computes it in 2^O(h^2) poly(J, k + h) time.The bound counts polynomial-length source witnesses as well as optimum values.Source: §M.1 · p. 27, §M.2 · p. 27

M.3 Checkable proof objects

  • An independent verifier checks closure, ranks, and attaining source-basis prefixes in exported proof objects, but does not establish that a fitted model describes a real data source.Online target generation solves the observed source-label system and enumerates at most n + 1 compatible target candidates.Source: §M.3 · p. 27, §M.4 · p. 28

N Relation to relative generalized Hamming weights

  • The target-rank profile inverts relative generalized Hamming weights, while computing it without a nuisance bound contains syndrome decoding.The algorithm’s parameter dependence is on nuisance dimension h; the reduction is not claimed as a new coding-hardness result.Source: N Relation to relative generalized… · p. 28

O Learning the full uniform-linear joint model

  • For a uniform-linear joint model, training contexts spanning the rank-ℓ support let the planner return optimal policies for every budget, with nuisance dimension h = ℓ − k.Recovery is probabilistic under the stated sample-size bound; assumptions include a known model class, a rank bound, and exact labels.Source: O Learning the full uniform-linear… · pp. 28–29

P Planner and learning experiments

  • The experiments use finite binary linear tasks with exact algebra and noiseless source and target acceptance, and release the instances, labels, plans, and timings.The learned model is obtained by row-space estimation followed by algebraic planning.Source: P Planner and learning experiments · p. 29

P.2 Baselines and budget matching

  • Across three main planner families, source-only reconstruction used 20, 20, and 17 calls, versus mean optimal mixed budgets of 18.4375, 17.6875, and 15.Two-exchange local search matches exact-planner accuracy on the coded family.Source: §P.2 · p. 30

P.3 General-bank model learning and undersampling

  • At m = ℓ + 7, all 80 learned fits recovered the support and all held-out policies succeeded; at m = ℓ and below, fitted supports were often incorrect and test contexts failed.The method covers uniform-linear models, not nonlinear, noisy, or nonuniform latent relations.Source: §P.3 · p. 30

P.4 Scaling, exact checks, and reproducibility

The scaling study measures complete planner calls across source counts and nuisance dimensions; separate checks compare computed profiles with exhaustive search and validate certificates.

P.4 Scaling, exact checks, and reproducibility

  • Figure 6 averages three generated inputs per point, with target dimension k = J/4 and at most 5, 67, and 2825 subspace states for h = 2, 4, and 6.The timing grid crosses k = 16, 32, 64, J = 4k, and h = 2, 4, 6; timings include quotient preprocessing and all budget witnesses.Source: Figure 6 · p. 31, §P.4 · p. 31
  • Exhaustive subset search agreed on all 1911 budget entries across 240 small random banks, and the independent checker validated 40 exports covering 4104 states and 1728 profile entries.Tamper tests included incorrect ranks and incomplete state sets.Source: §P.4 · p. 31
  • The planner suite, certificate verifier, and learned-plan audit regenerate and check the finite-model results; numbered results are checked separately in Lean 4.No pretrained model is used.Source: §P.4 · p. 31

Q External comparison, local search and stress tests: results

The experiments compare QSP with an external solver and source-aware baselines, then test learned models under source-label noise and prior shift. QSP’s savings over source-aware baselines are modest, while stress tests expose sensitivity to the learning assumptions.

Q External comparison, local search and stress tests: results

  • QSP completes all 27 external-comparison banks, while GHWs completes 21; profiles agree wherever both finish, and the speed advantage depends on regime.GHWs is faster on high-nuisance short banks and RM(2,4).Source: Table 2 · p. 32, Q External comparison, local search… · p. 32
  • Against the per-bank best over all released source-aware baselines, QSP’s gaps were 2.28 and 1.10 percentage points, averaged over the complete integer-budget grid (zero through source rank plus one).For two-exchange, the corresponding gaps were 2.83 and 2.36 percentage points; against source-aware baselines, QSP’s savings are modest, not exponential.Source: Q External comparison, local search… · p. 32, Table 3 · p. 33
  • At 1% source-label noise, three-measurement voting raises yield to 0.9979, but training calls rise from 432 to 1296 and mean online physical cap reaches 25.25.Without repetition, yield is 0.402 overall; at 3% noise the learner abstains on every bank.Source: Q External comparison, local search… · p. 33
  • At p = 0.05 and m = 44, only 9/24 supports recover, with yield 0.876 under the training prior and 0.642 on uniform test worlds.The finite-sample guarantee assumes uniform data, and span learning needs training data to cover the latent support.Source: Q External comparison, local search… · p. 33

R External comparison, local search and stress tests: protocols

  • The appendix reports replay and audit checks across stored outcomes, including noise and prior-shift failures, alongside protocols, acquisition costs, uncertainty, and seeds.The test suite passes 199 tests; saved-label replay checks 368,640 stored context outcomes.Source: Q External comparison, local search… · pp. 32–33

R.1 Pinned external solver and equal computational task

The appendix specifies the external solver, local-search, noise, and prior-shift protocols and reports saved-evidence checks. Together, these tests show regime-dependent solver timing, limited heuristic gaps, and learning sensitivity to noise and training-prior coverage.

R.1 Pinned external solver and equal computational task

  • 35.46 ms versus 18.25 ms on high-nuisance short banks, and 106.79 ms versus 18.95 ms on RM(2,4), favor GHWs; on wider low-nuisance banks, QSP takes 1.49 ms while GHWs times out.With six banks per random regime and two timing repetitions, the runs locate the crossover but do not give precise speed ratios.Source: §R.1 · p. 34, Figure 7 · p. 34

R.2 Expanded two-exchange local search

  • The two-exchange heuristic matches QSP’s zero-error threshold on all eight coded scramblings, but this does not imply equality at smaller budgets.The coded banks are scramblings of one geometry.Source: §R.2 · p. 35, Table 4 · p. 35

R.3 Source-label noise and repeated measurements

  • At 1% noise, three repeats yield 0.9979 with a mean physical online cap of 25.25 and 1296 training source calls; repetition factors were not optimized.At 3% noise, one measurement produces no plans; three repeats yield 0.9705.Source: §R.3 · pp. 36–37, Table 5 · p. 36

R.4 Nonuniform training and prior shift

  • At p = 0.05 and m = 44, only nine supports recover; yield is 0.8761 on matched-prior worlds and 0.6416 on uniform worlds.The uniform-data theorem does not provide its stated finite-sample recovery guarantee when p < 1/2.Source: §R.4 · p. 37, Table 6 · p. 37, Figure 9 · p. 37

R.5 Saved evidence and reproduction

  • The saved-evidence audit replays selected-source decoding for 559 of 720 planned stress cells and checks all 368,640 stored per-context outcomes.The 199-test suite includes 1,911 exhaustive profile comparisons, 5,440 exact Bellman comparisons, and 960 numerical rate-distortion points.Source: §R.5 · p. 38

S Neural transfer experiments: details

The experiments probe whether in-weight, in-context, and scratchpad learners use information from acquired sources. They vary latent dimension, source-selection curricula, and training capacity, with results reported against the information frontier.

In-weight learner

  • The in-weight learner is pretrained on known and uncertain contexts, then acquires source labels through SFT or GRPO before target-answer training.Target prompts for one quarter of known contexts are held out during pretraining; post-training uses a secret world per seed.Source: S Neural transfer experiments: details · p. 38

In-context learner

  • The in-context learner receives acquired source labels in its prompt; its budget profile measures bits used, coset mass, and target-answer probabilities across fresh worlds.Pretraining uses uniformly sampled worlds and predicts source labels and target bits.Source: S Neural transfer experiments: details · pp. 38–39

Scratchpad learner

  • The scratchpad executor is trained to process source equations in a row-reduction trace and generate target bits sequentially from that trace.Its trace grows linearly with acquired sources and quadratically with latent dimension.Source: S Neural transfer experiments: details · p. 39

In-weight learner

  • Under GRPO, 16 of 27 curriculum runs end with a locked-in source; the authors caution that the target-prior damage is partly an implementation artifact.They state these runs do not support a general conclusion about policy-gradient methods.Source: S Neural transfer experiments: details · p. 40

Neural transfer experiments

  • At the zero-error split, Figure 11 plots fraction of delivered bits used against latent dimension; the d = 5 scratchpad executor falls below the uniform prior.The caption notes that this executor’s fraction is negative because it assigns less probability to A⋆ than the uniform prior.Source: Figure 11 · p. 41
  • At d = 8, no capacity-sweep configuration reaches the frontier, and one seed per configuration yields no clear trend with width or training steps.The sweep uses three banks and marks their delivered bits as 4, 5, and 5.Source: Figure 12 · p. 41

T Curricula, degree analysis and controls

The section compares the decoder’s use of source information across curricula and tests whether XOR degree explains which bits it uses. It also describes two independent numerical formulations for the information frontier.

T Curricula, degree analysis and controls

  • At the zero-error split, used-bit fractions range across banks from 49%–100% at d = 6, 0%–78% at d = 7, and 0%–20% at d = 8.Across three seeds on bank 0, the corresponding ranges are 49%–66%, 1%–26%, and 0%–12%.Source: T Curricula, degree analysis and… · p. 41
  • At d = 5, planner sources require 2.7 expected samples versus the posterior’s 2.7; at d = 8, the exact references differ by 24.0× for planner sources versus none, but learner costs differ by 1.4×.For distinct verifications at d = 8, planner sources leave the learner at 20.9 guesses versus the posterior’s 1.8, while no sources cost 34.8 guesses.Source: T Curricula, degree analysis and… · pp. 41–42
  • In the controlled degree test, low-degree banks used 66%–69% of delivered bits and high-degree banks 42%–67%; low degree neither guaranteed nor bounded use.Prediction P1 failed, while P2 held on the controlled banks but failed on two of the 15 other banks.Source: T Curricula, degree analysis and… · pp. 42–43
  • At 6,000 steps, determined bits were used almost fully or almost not at all, and the bit used depended on its position rather than its degree.With all sources, the first target bit was never used; the authors report no explanation for this pattern.Source: T Curricula, degree analysis and… · p. 43
  • After training four times longer, loss fell on every bank, but bit recovery still was not predicted by degree.The recorded predictions about low-degree and high-degree banks both failed; one degree-two bit remained lost while a degree-four bit was partly recovered.Source: T Curricula, degree analysis and… · p. 43
  • The scratchpad comparison covers one bank and twelve contexts, with learners differing in supervision, architecture, size, and serial computation.A trace-supervised variant used 91% of delivered bits on a separately drawn d = 8 bank, but its larger size and stepwise supervision prevent isolating those factors.Source: T Curricula, degree analysis and… · pp. 42–43

U.1 Two independently formulated optimizations

  • One frontier optimization searches for a simplex-valued parameter and evaluates the returned Gibbs channel using its actual marginal.A second formulation optimizes a rate-distortion dual without parameterizing a list marginal or constructing a Gibbs channel.Source: §U.1 · p. 44
  • The first formulation provides a primal–dual gap certificate, while the second restores feasibility by subtracting the largest constraint violation plus 10^-13.Both use floating-point arithmetic, and the release reports numerical tolerances.Source: §U.1 · p. 44

U.2 Experimental configurations

The appendix describes configurations for numerical and protocol audits, along with computational limits. It situates the paper’s information, query, linear-bank, and learned-decoder analyses alongside related work, while distinguishing their scope.

U.2 Experimental configurations

  • The certificate study covers 240 prior–geometry settings and 960 optimization points; source-protocol audits exhaustively enumerate finite transcripts, and noisy-theorem tests use 81 noise values.A separate program computes zero-error values for every setting, and independently optimized duals check the first 240 audit trees.Source: §U.2 · p. 45
  • Response-list enumeration is exponential, and the information ledger requires the true probabilistic model.Released channel matrices and independent dual variables can be checked without optimization.Source: §U.2 · p. 45

V Extended related work

  • The information frontier builds on rate-distortion, guessing with side information, and directed-information work, while its converse draws on change-of-measure and interactive-Fano results.The passage identifies Saito and Matsushima (2018) as allowing acceptability queries corresponding to overlapping acceptance sets.Source: V Extended related work · p. 45
  • The paper distinguishes its verifier-budget setting from query models that count every query and from transfer-learning work on statistical estimation.It connects zero-error source-first protocols to minimum-entropy covers and the terminal utility to classical value of information.Source: V Extended related work · p. 45
  • Linear-bank analysis draws on relative dimension/length profiles and subspace-closure learning; the paper also notes an existing solver that it runs directly.Source: V Extended related work · p. 46
  • The paper prices source-task information for one instance rather than modeling generalization across prompts, and relates its decoder to work on in-context parities and usable versus Shannon information.It distinguishes expressivity results for chains of thought from learnability and identifies the policy-gradient learner as GRPO.Source: V Extended related work · p. 46

Related papers

Loading 2610.12211v1…