In-Context Search: Why LLM Retry Loops Actually Work

Why does a language model sometimes get the right answer on its second try after failing on its first? A recent theoretical paper offers an answer: the model isn't just "trying again" - it's doing something that looks a lot like search, and under the right conditions, that search pays off exponentially.

In-Context Search Is Really Approximate Inference

The paper models what it calls in-context search - the loop where a model generates a solution attempt, critiques it, and revises it within the same conversation - as approximate inference over reasoning traces. Here's what that means in plain terms: the model's first guess reflects its prior, its built-in beliefs about what a good answer looks like. Each round of self-reflection acts as feedback that updates those beliefs, the way evidence updates a posterior in Bayesian statistics.

The key insight is that this isn't magic or mere repetition. If the model's reflections reliably point at where things went wrong early in a reasoning trace, each revision is genuinely narrowing down the space of possible answers rather than rolling the dice again.

Why Exponential Improvement Only Needs Polynomial Effort

The paper's central result is the asymmetry between what you put in and what you get out. When reflections reliably localize early mistakes, in-context search yields exponential improvements over the base model - but it only needs a polynomial number of sequential attempts to get there. That gap between exponential gain and polynomial cost is the whole story.

The analysis also shows this behavior can be trained efficiently: cross-entropy training on search rollouts recovers the required behavior with polynomial sample complexity. And under reinforcement learning, the optimal policy ends up implementing the same posterior reweighting rule - meaning whether you train by imitation or by RL, you converge on essentially the same mechanism.

The Catch Is in One Word: Reliably

Most coverage of iterative refinement stops at "the model critiques itself and gets better." But everything hinges on that condition - reflections must reliably localize early mistakes. If self-critique flags the wrong error, or misses the real one buried three steps back, each revision isn't updating toward truth; it's drifting. The exponential guarantee doesn't apply to vague reflection, only to reflection that actually finds the fault.

That distinction matters because it reframes what we should be measuring. The real story here isn't "models can check their work" - it's that check quality is a multiplier on everything else. A base model with sharp self-diagnosis behaves like an exponentially stronger system; one with sloppy diagnosis behaves like itself with extra steps.

In my reading, this also connects to why some reasoning models feel inconsistent: their reflection loop is only as good as its ability to localize where reasoning actually broke, which is a much narrower skill than sounding reflective. It echoes a theme I keep returning to - surface-level review behavior and genuine error-finding are easy to conflate but very different things.

So when you see a model succeed on attempt five after failing attempts one through four, don't credit persistence. Credit accurate localization - that's the mechanism doing the heavy lifting.