Verification methods reveal tradeoffs in information and calls needed
Verification with Transfer: Exact Information Frontiers and Their Price in Calls
Machine LearningCryptography and SecurityInformation Theory
Summary
Sometimes when checking a big answer, you need many steps to be sure it’s right, which can be very expensive. This paper explores how checking related smaller tasks either all before or mixed with verification can save effort, but also comes with costs. The authors analyze exactly how much information and how many calls to sources are needed to be sure of an answer, especially under perfect or noisy checks. They also provide formulas and computer-verified proofs to describe this tradeoff and show when mixing calls helps or hurts. Their work helps understand the exact limits and costs of verifying answers efficiently.
What this means in practice
- •For machine learning engineers: Optimize training protocols that verify model outputs by scheduling source queries before or interleaving with verification steps for efficiency.
- •For coding theory developers: Design linear code-based verifiers knowing exact tradeoffs between information budget and the number of verification calls for error-free decoding.
A theory result. No direct application yet.
Authors
Hazar Yueksel
Abstract
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.