In-Context Search: Sampling-Complexity Theory (2026 paper)

When Does In-Context Search Help?, a paper by Yotam Wolf, Noam Wies and Amnon Shashua submitted 7 Jul 2026 as arXiv:2607.06720, provides a formal sampling-complexity account of reflection-driven in-context search. The authors model in-context search as "approximate inference over reasoning traces" and derive when iterative generate-critique-revise loops reduce the number of attempts needed to reach a correct solution.

What did the paper prove?

The paper proves that in-context search can deliver exponential improvements in sampling complexity, but only under a concrete condition: reflections must reliably localize early mistakes. If that condition holds, problems with exponentially small zero-shot pass rates become solvable with only a polynomial number of sequential attempts. If the reflections fail to localize early errors, conditioning on past attempts gives no asymptotic advantage over parallel sampling.

Wolf, Wies and Shashua frame these results in terms of inference-time sampling complexity, meaning the number of sequential attempts required to reach high success probability. The paper contrasts two regimes: one where self-reflection yields posterior updates that concentrate mass on correct reasoning traces, and one where reflections do not concentrate posterior mass and hence do not reduce asymptotic sampling cost.

How does the theoretical model describe in-context search?

The authors model the base language model as a prior over reasoning traces and treat self-reflection as a mechanism for posterior updates: reflections act as feedback that reweights candidate traces. They analyze the sampling complexity of this approximate inference process and show that approximate posterior updates suffice for the exponential-to-polynomial gain.

Concretely, the paper demonstrates that cross-entropy training on search rollouts can recover the required posterior-update behavior with polynomial sample complexity, making the gains learnable. The authors also connect the rule to reinforcement learning: under a stagewise abstraction with verifiable rewards, the optimal policy extension implements the same posterior reweighting rule derived in the inference perspective.

How did the authors validate their theory?

The paper states the authors validated key qualitative predictions of the theory on real large reasoning models. Those empirical checks are presented as validation of the theory's main qualitative claims rather than as precise numeric benchmarks. The submission lists the theoretical results and reports that the qualitative predictions align with observations from experiments on large reasoning models.

Why it matters

The paper pinpoints when iterative self-reflective prompting is more than a heuristic: it can change the scaling law of search from exponential to polynomial when reflections reliably identify early mistakes. That distinction explains why some reasoning tasks see dramatic improvement from reflection-driven loops while others do not, and it ties practical training choices, such as cross-entropy on rollouts, directly to provable sampling benefits.

What to watch

Check for follow-up empirical work that quantifies the assumed reflection reliability and measures the polynomial degree required in practice. Also watch for implementations that adopt the cross-entropy on search-rollouts training objective the paper identifies as sufficient to recover the needed posterior updates.

Bibliographic details: the paper is arXiv:2607.06720, submitted 7 Jul 2026, by Yotam Wolf, Noam Wies and Amnon Shashua. The authors situate the work in Artificial Intelligence and Computation and Language.