arXiv：cs.LG· Hazar Yueksel·· 3 小时前
验证与迁移：精确信息前沿及其调用代价
Verification with Transfer: Exact Information Frontiers and Their Price in Calls
AI 导读
论文提出以列表率失真函数刻画精确验证器下源任务调用与验证交错所需的最小因果信息，并将该下界在唯一答案场景做到1+log₂5次调用以内。对F₂上的线性题库，最优准确率有闭式解，预算分布可在2^{O(h²)}·poly(J,k+h)时间内计算；除两条关于规划器的命题外，全部编号结果已在Lean 4中机器验证。
正文
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.
| Comments: | 46 pages, of which 8 pages main text. The Lean 4 formalization is in the ancillary files |
| Subjects: | Machine Learning (cs.LG); Cryptography and Security (cs.CR); Information Theory (cs.IT); Machine Learning (stat.ML) |
| Cite as: | arXiv:2610.12211 [cs.LG] |
| (or arXiv:2610.12211v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.12211 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Hazar Yueksel [view email]
[v1]
Thu, 8 Oct 2026 16:00:23 UTC (480 KB)
来源：arXiv：cs.LG · arxiv.org