mlsanityData to 14 Oct 2026

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

arXiv 2610.12211 ↗First posted 8 Oct 2026cs.LG cs.CR cs.ITcited by 0

Not on the map. Why?

Abstract (arXiv)

A verifier that accepts or rejects whole answers reveals little: under a flat prior over k-bit answers, zero error needs 2k-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+log25 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 mathbbF2, optimal accuracy has a closed form, and after a polynomial-time reduction the budget profile is computable in time 2O(h2)operatornamepoly(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.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 17 of its 94 references that are in the map. First posted on arXiv 8 Oct 2026.

Builds on

17 of 94 references.

References · 17

  1. 2024DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Modelscited by 9,379
  2. 2021Evaluating Large Language Models Trained on Codecited by 8,320
  3. 2024Large Language Monkeys: Scaling Inference Compute with Repeated Samplingcited by 991
  4. 2022What Can Transformers Learn In-Context? A Case Study of Simple Function Classescited by 715
  5. 2022What learning algorithm is in-context learning? Investigations with linear modelscited by 684
  6. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspectivecited by 294
  7. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problemscited by 260
  8. 2022Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limitcited by 187
  9. 2025RL's Razor: Why Online Reinforcement Learning Forgets Lesscited by 176
  10. 2023Pretraining task diversity and the emergence of non-Bayesian in-context learning for regressioncited by 146
  11. 2023The Expressive Power of Transformers with Chain of Thoughtcited by 50
  12. 2022Sub-Task Decomposition Enables Learning in Sequence to Sequence Taskscited by 41
5 more
  1. 2026On the Emergence of Implicit Curriculum in RLVR Learning Dynamicscited by 10
  2. 2026Outcome-Based RL Provably Leads Transformers to Reason, but Only With the Right Datacited by 6
  3. 2026A Relative-Budget Theory for Reinforcement Learning with Verifiable Rewards in Large Language Model Reasoningcited by 4
  4. 2026Learning to Reason with Curriculum II: Compositional Generalizationcited by 3
  5. 2026When Is Compositional Reasoning Learnable from Verifiable Rewards?cited by 1

Built on by

Not cited yet.