Agentic AI systems that seem to get smarter don't always get more correct - and a new paper tries to prove exactly when they do.
Researchers propose a formal framework that treats an AI agent's verification process as a bounded computational "stage" with a strict terminal checker, then use complexity theory to separate different ways a system's score can rise: searching longer, getting more outside support, or changing how it generates and checks its own answers. They show that majority-vote amplification - running a system many times and taking the consensus answer - provably preserves correctness. But letting a system simply pick its single best-looking answer among many random attempts does not: it can let wrong outputs slip through disguised as verified. They also look at recursive self-improvement, where a system edits its own code, and prove that under a fixed, already-sound checking process, self-modification keeps the system within the same verification guarantees it started with rather than unlocking new provable capability.
That distinction cuts against a familiar AI marketing move: pointing to a jump in benchmark scores as proof of a genuinely smarter model, when the jump may just reflect more attempts and luckier picks. The paper's test family built around quota-enforced search makes this concrete, showing search success rates can climb by huge ratios with zero actual gain in which problems get correctly solved.
For anyone tracking the self-improving-agent hype cycle, the useful question isn't how much the number moved. It's what, exactly, was verified.