Paper Overview
- Research area: Machine Learning
- Authors: Salman Avestimehr, Ken Duffy, Muriel Médard
- Published: 2025-05-15
- arXiv: 2505.10886
- Coverage conditions: The authors identify sufficient conditions under which accumulated genuine knowledge eventually covers a finite domain, and show how violations of these conditions produce distinct failure modes:
- Contamination
- Forgetting
- Exploration failure
- Acceptance failure
- The contamination trap: With imperfect verification, as easy-to-find knowledge is exhausted, the model mass assigned to new valid artifacts shrinks. Consequently, even small false-positive rates can cause invalid artifacts to enter the knowledge base faster than genuine discoveries.
- Good-Turing estimation: The paper clarifies that Good-Turing estimation is a *local batch-level diversity diagnostic*, not an estimator of the historically undiscovered valid mass that controls long-term discovery.
- Scaling law: Under a separate tail-equivalence assumption linking the model's effective discovery distribution to a Zipf law with exponent
alpha > 1, the cumulative generation cost to obtain D distinct true findings satisfies: - Human augmentation: The paper formalizes human augmentation through guidance, generation, and verification, explaining why expert input is most valuable near autonomous exploration barriers.
Summary
Can AI systems discover genuinely new knowledge through iterative self-improvement, and if so, at what cost? The paper introduces the NOVA framework, which models the common "generate, verify, accumulate, retrain" loop as an adaptive sampling process over a knowledge space.
Key contributions
R_cum(D) = Theta(c_gen * D^alpha)
where c_gen is the generation cost per candidate. This scaling law quantifies the asymptotically diminishing returns of pushing forward the discovery frontier.
Original Abstract (excerpt)
> Can AI systems discover genuinely new knowledge through iterative self improvement, and if so, at what cost? We introduce the NOVA framework, which models the common "generate, verify, accumulate, retrain" loop as an adaptive sampling process over a knowledge space. We identify sufficient conditions under which accumulated genuine knowledge eventually covers a finite domain, and show how their violations produce distinct failure modes: contamination, forgetting, exploration failure, and acceptance failure. We then analyze imperfect verification and identify a contamination trap: as easy-to-find knowledge is exhausted, the model mass assigned to new valid artifacts shrinks, so even small false-positive rates can cause invalid artifacts to enter the knowledge base faster than genuine disco...
Read the full paper on arXiv: 2505.10886
---
*Auto-collected on 2026-05-19*