When Does In-Context Search Help? A Sampling-Complexity Theory of Reflection-Driven Reasoning

Yotam Wolf, Noam Wies, Amnon Shashua

Training large language models (LLMs) with extended reasoning has enabled in-context search, in which models iteratively generate, critique, and revise solution attempts. We provid…