On the Theory of LLM-Assisted Problem Solving

What is the most effective way to use an LLM to solve a math problem? If the problem is easy, then "one-shotting," i.e. simply posing the query, is likely to be enough. However, if the problem is harder, empirical evidence suggests that such a naive approach has a low probability of success. Instead, researchers use multiple agents and harnesses, to break the problem into subcomponents, explore different approaches, verify progress, and then combine these into a final solution. In this work we give a formal framework for exploring such harnesses. We provably show that the optimal approach for solving a problem depends on its inherent difficulty as well as the power of the LLM-solver, and that harnesses are helpful when the problem is sufficiently harder than what an LLM can solve directly. Perhaps surprisingly, our analysis identifies a key property governing the power of such explorations: it is not merely the model’s ability to solve mathematical statements, but its ability to reliably estimate their difficulty.