Imagine you're playing 20 Questions, but instead of asking free-form questions, you can only ask yes/no questions of a specific oracle — and you have to decide how many hints to buy from a tutor before you start guessing. The paper's core question is: what's the minimum amount of tutoring (source tasks) you need so that a fixed budget of yes/no verification checks actually succeeds? Yueksel prices that tutoring in bits and in oracle calls, and proves the answer is a rate-distortion function — the same mathematical object that governs lossy data compression. The committed claim: for exact verification of k-bit answers, the minimum causal information any protocol needs is characterized by a list rate-distortion function, and this minimum is achievable by front-loading all source observations before any verification call. The paper then shows this information-theoretic floor translates into call-count bounds — optimal source designs meet the floor within 1 + log₂5 calls for unique answers, with a logarithmic gap in general where no constant gap suffices. This is a genuine new result in the intersection of information theory, learning theory, and formal verification. The architecture here is pure mathematics: no neural networks in the theory, no gradient descent. The framework lives in the family of information-theoretic lower bounds for interactive protocols, closer to Fano's inequality and rate-distortion theory than to any ML pipeline. The computational result for linear banks over F₂ uses a polynomial-time reduction with runtime 2^{O(h²)} · poly(J, k+h), where h is nuisance dimension and J is number of sources. The key structural insight is that every call beyond the information-theoretic price is spent purely on nuisance — separating signal from irrelevant variation. Integrity is the headline story. Every numbered result except two clauses about the planner is machine-checked in Lean 4, assuming only two published results. This is extraordinary for a paper at this intersection — most information-theory papers rely on pen-and-paper proofs that occasionally harbor subtle errors. The Lean formalization in ancillary files means any reader can mechanically verify the claims. The two unverified clauses and two assumed results are explicitly flagged, which is honest practice. The empirical component is small but well-designed: a transformer tested against the information frontier as a ruler. At latent dimension 5, the transformer uses all delivered bits; at dimension 11, it uses none — within fixed training budgets. A pre-registered prediction (recorded before training) tested whether low XOR degree of target bits sufficed for their use, and the answer was no. This is a clean falsification of a plausible hypothesis, not a cherry-picked success. The paper's limitation is scope of empirical validation. The theory is airtight (machine-checked), but the transformer experiment is a single small-scale test. The frontier is proven as a mathematical object; its utility as a diagnostic ruler for real ML systems is demonstrated once. The natural successor experiment — applying the frontier to larger models, different architectures, or real transfer-learning benchmarks — is conspicuously absent. The honest read: this is a theory paper that includes an empirical proof-of-concept, not an empirical paper. Scaling the diagnostic use is likely saved for follow-up work. For practitioners, the takeaway is a new diagnostic tool: if you can characterize your verification and source tasks information-theoretically, this paper gives you exact bounds on how much transfer you need and whether your model is actually using the information it receives. The frontier acts as an efficiency audit. The 46-page length (8 main, 38 appendix + formalization) signals a paper that front-loads accessibility and buries the machinery — the right structure for a result this technical.
