acceptodds
Under review as a conference paper at ICLR 2027

On the Theory of LLM-Assisted Problem Solving

Abstract

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.

Primary area:
foundation or frontier models, including LLMs
Keywords:
LLM theory

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 4 reviews, above 27% of the others.
Reviewer_12jiOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
2(+1)
Presentation
2
Soundness
2
Read review
Paper summary

The paper asks when an AI should keep trying to solve a mathematical problem directly, break it into smaller problems, or search for a different way to break it down.

The authors study a simplified model: every AI call costs the same, repeated proof attempts have fixed success probabilities, and proofs can be checked perfectly for free.

First, they assume each problem has one fixed decomposition into smaller problems. Their algorithm works on those smaller problems while periodically retrying the larger problems above them. This avoids spending forever on a difficult subproblem when the original problem might admit a direct proof. They show that, with at most HH levels of unresolved problems, this approach uses at most H+1H+1 times the expected work of an ideal solver that already knows the difficulty of every option. Without a depth limit, its expected work is at most quadratic in the ideal solver’s cost.

Next, they allow the AI to propose different decompositions. Blindly exploring these alternatives can be exponentially wasteful. Reliable estimates of how much work each alternative requires can help the system decide when to stop searching and commit to a route. The authors characterize the best decision rule when the relevant probabilities are known, and give a performance guarantee when only approximate cost estimates are available. That guarantee worsens rapidly with decomposition depth and estimation error.

The paper contains theoretical guarantees under these assumptions, with no experiments on actual LLMs.

Critical strengths
  1. The model is stated cleanly and I found no substantive gaps in the proofs I checked. I checked Theorems 4.2, 4.3, 5.1 and Corollary 5.3 and Lemma C.1 and found no gaps. The reduction of the stochastic optimum to a per-node reservation value (Theorem 5.2) is a tidy argument.
  2. The paper is open about what it assumes away (fixed independent success probabilities, a free sound verifier, no sharing of lemmas between routes) and about what it leaves open (whether any guided algorithm can avoid the height dependence).
Critical weaknesses

1. The results follow from standard arguments, and the paper omits closely related work on satisficing search and on value-guided theorem proving.

The proofs rely on familiar techniques. The deterministic setting is a probabilistic AND/OR tree in which every action costs one unit and succeeds independently with a fixed probability. Optimal strategies for such trees have been studied since the satisficing search of Simon and Kadane (1975), and Greiner et al. (2006) treat AND/OR trees directly. Those models perform each test once and treat its outcome as final, while here an attempt can be repeated, so the correspondence is not exact. But the paper cites neither work and never makes the comparison, and Proposition 4.1 is presented without a reference point. Ancestor dovetailing makes at most HH direct attempts along the active path and then one frontier operation per round, and the upper bound charges every round to one operation of the optimal plan, so the ratio is H+1H+1. The lower bound is the usual argument that an online algorithm facing kk candidates, one of which works with probability δ\delta, needs about k/δk/\delta trials, and the lower bound of Corollary 4.3 uses the same chain with HH of the order of OPT. Theorem 5.1 is a needle in a haystack with mhm^h leaves. Theorem 5.2 is, as the paper says, Weitzman's reservation rule applied node by node, plus a potential argument showing that interleaving partial execution with further sampling does not help. Theorem 5.3 analyzes a rule that samples until the best estimate is at most the number of samples plus one.

The framing is not new either. The paper says its three agent roles are widely used and cites one harness, but not the theorem-proving systems that already built what it recommends. A decomposer that proposes subgoals, a prover that fills them and a formal verifier is the architecture of Draft, Sketch, and Prove (Jiang et al., 2023). Searching an AND/OR tree of subgoals with a learned estimate of how hard each one is, and using that estimate to choose which route to pursue, is HyperTree Proof Search (Lample et al., 2022). Choosing a decomposition by predicted subgoal difficulty is what Zhang et al. (2026) build. The latter two systems are built around learned value or difficulty estimates that guide proof search, so the abstract's "Perhaps surprisingly" conclusion that difficulty estimation is "a key property" is their design premise, and the paper cites none of them.

Simon, Kadane (1975). Optimal problem-solving search: All-or-none solutions. Artificial Intelligence 6(3), 235-247.

Greiner, Hayward, Jankowska, Molloy (2006). Finding optimal satisficing strategies for and-or trees. Artificial Intelligence 170(1), 19-58.

Lample, Lachaux, Lavril, Martinet, Hayat, Ebner, Rodriguez, Lacroix (2022). HyperTree proof search for neural theorem proving. NeurIPS 2022.

Jiang, Welleck, Zhou, Li, Liu, Jamnik, Lacroix, Wu, Lample (2023). Draft, sketch, and prove: Guiding formal theorem provers with informal proofs. ICLR 2023.

Zhang, Di, Li, Yao, Ma (2026). Planning to hammer: Difficulty-aware decomposition for automating Rocq proofs. arXiv: 2606.17981.

2. The practical relevance of the guarantees is not established, and the positive results are weaker than they look.

The title promises a theory of LLM-assisted problem solving, but the paper runs no LLM, and no quantity in the model is measured, estimated or simulated. There is no experiment, not even a synthetic one showing how the two algorithms behave, and no evidence that an LLM's difficulty estimates have any particular α\alpha or that real harnesses have a height HH at which the bounds say something. A theory paper can do without experiments, but this one makes claims about practice in its title, abstract and Section 2.1, and nothing in it tests them.

The guarantee of Theorem 5.3 can also be numerically large. With α=1.5\alpha = 1.5 and H=6H = 6, for example, it allows about 908 times the optimum, and the paper gives no simulation that would show the algorithm doing better. The introduction states the bound (H+1)α2H(H+1)\alpha^{2H}, adds in parentheses that it recovers a factor of H+1H+1 under exact costs, and then says "this factor is tight for our algorithm", which leaves open which factor is meant. Section 5.3 and Appendix C.3 show tightness only for H+1H+1 at α=1\alpha = 1, and the introduction should say so.

Even with exact estimates the worst-case ratio is H+1H+1, and Appendix C.3 gives a family of instances whose ratio approaches it, a chain with a deterministic decomposer. On that chain the algorithm makes M+2h−3M+2h-3 decomposition calls at the level with hh uncertified nodes remaining, every one of which returns the same output, because its stopping rule counts repeated outputs as samples. An algorithm that calls the decomposer once per node and trusts the exact estimate pays exactly OPT there, so on that family the extra factor comes from the stopping rule. Whether any guided algorithm must depend on HH is left open, as the conclusion says, so no lower bound is established for algorithms that receive cost estimates.

The negative and positive results are stated on different instance classes. In the family of Theorem 5.1 every wrong branch has infinite completion cost, and the positive theorems assume finite expected completion cost almost surely, so as stated they do not cover the family that motivates them. If the estimate condition in equation (5.2) were extended to infinite costs, an estimate satisfying it would name the solvable branch outright once that branch was sampled.

Finally, the model leaves out several of the practical difficulties of harness design. Verification is free and perfect, every call costs the same, attempts are independent coin flips with fixed probabilities, and a failed attempt yields no partial proof, no error message and no change in the next attempt's chance of success. Under these assumptions the abstract's qualitative conclusions, that decomposition pays when the direct cost 1/qa1/q_a exceeds the decomposition's cost and that the best approach depends on difficulty and solver strength, follow directly from the recurrence in equation (4.1).

Questions for authors
  1. What does the model predict that HyperTree Proof Search or Draft, Sketch, and Prove did not already build in, and how would the prediction be tested? Any experiment, simulated or with an LLM, that measures α\alpha for a difficulty estimator and the realized cost ratio would help.
  2. Is α2H\alpha^{2H} tight for your algorithm, or an artifact of the recurrence Rh=α+α2Rh−1R_h = \alpha + \alpha^2 R_{h-1}? The appendix shows tightness only for α=1\alpha = 1.
  3. How does the deterministic model relate to the probabilistic AND/OR tree problems of Simon and Kadane (1975) and Greiner et al. (2006)? Those models perform each test once, while here attempts repeat. What changes in the optimal strategy, and which parts of Proposition 4.1 and Theorem 4.2 are new relative to that literature?
2 comments

Thank you for the review, we will certainly address these points in the final draft.

We really appreciate the effort of the reviewer to point us to multiple interesting papers designing practical harnesses and we will add them to the related work section. We believe that the existence of such literature strengthens the need for a theoretical study of the problem. In fact, our main goal is to formalize a model that abstracts the current harnesses to formally study their power and optimization from a theoretical perspective. To this end, we would like to find the minimal setting that allows us to capture the benefits of harnesses as well as the difficulties with making them efficient in practice. We tried hard to not overfit to the methods du jour, but to abstract the different research threads into a common vocabulary, set of critical definitions, and metrics that the theory community can build on.

Regarding the tightness of the algorithm. Thank you for pointing this out. One can prove that there are examples where this analysis is tight for our algorithm (for α>1\alpha >1) and we will strengthen the paper by including it. A high level description is as follows. It is based on a deterministic chain a1→a2→…→aH→fa_1 \rightarrow a_2 \rightarrow … \rightarrow a_H \rightarrow f where ff is verified and all aia_i are initially unverified. The optimal strategy will be to prove the root statement directly by proving a1a_1 but we will choose approximate estimates so as to prefer decompositions all the way down to proving that ff implies aHa_H. Specifically, at each level, overestimating the direct-proof cost by a factor (α\alpha) and underestimating the decomposition cost by a factor (α\alpha) can make the algorithm prefer a route whose true completion cost is almost (α2\alpha^2) times larger. Nesting these choices along the chain makes the losses compound across all the HH levels. Including the algorithm’s sampling costs, this construction approaches the exact bound given by the recurrence (Rh=α+α2Rh−1R_h=\alpha+\alpha^2R_{h-1}).

Thanks for pointing us to the work of Simon and Kadane (1975) and Greiner et al. (2006), they are related and we will cited in the final version of the paper although it is important to notice that they model are deterministic and so their approach and techniques cannot be used in our setting with unknown probabilities and paid revelation.

Thanks for the reply. Adding the papers I mentioned to the related work and writing up the tightness example for α>1\alpha > 1 both help, so I'm raising my score to 2.

Two small things: Simon and Kadane (1975) and Greiner et al. (2006) do have success probabilities. They're known in advance, same as for your offline oracle, so it's still worth saying how Proposition 4.1 relates to them. And since the paper doesn't run any experiments, I'd tone down the practical claims in the abstract.

Reviewer_UH5oOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper formalizes LLM-assisted proof search using probabilistic proof attempts and deterministic or stochastic decompositions. It establishes tight bounds for fixed decompositions, characterizes an optimal stochastic policy and analyzes search guided by approximate completion costs. Validation consists entirely of mathematical proofs and worst-case constructions.

Critical strengths
  1. Matching theoretical guarantees: The deterministic setting includes matching upper and lower bounds for both bounded height and unbounded height. These results precisely characterize the worst-case cost of lacking knowledge about proof difficulty within the proposed model.

  2. Optimal stochastic policy: Theorem 5.2 establishes that a local sample-then-commit policy is optimal even against policies that interleave sampling and partial execution. Extending the reservation-rule argument to recursive proof obligations provides a substantive structural result.

Critical weaknesses
  1. Strong guidance assumptions: Theorem 5.3 assumes uniformly accurate estimates of completion costs containing optimal values for unexplored descendants, without accounting for obtaining these estimates. Moreover, its (H+1)α2H(H+1)\alpha^{2H} guarantee remains exponential in depth HH for any fixed α>1\alpha > 1.

  2. Unclear progress guarantee: Section 4.2 selects the first uncertified node in an in-order traversal. Read literally, this can revisit a parent with an already obtained conditional certificate while another child remains unproved, repeatedly performing completed work. Appendix B.1 assumes every round advances or eliminates remaining planned work; the stated algorithm needs an explicit rule ensuring this.

Questions for authors
  1. Algorithm clarification: How is the frontier selected after a parent’s conditional certificate is obtained but some children remain unproved? Please clarify the two-child case where the first child is certified and an in-order traversal next visits the parent.

  2. Guidance justification: What supports interpreting the estimates in Equation (5.2) as attainable evaluative feedback from an LLM? They approximate optimal recursive completion costs, which appears substantially stronger than estimating local proof difficulty.

  3. Approximation regime: For fixed (α>1),(\alpha>1), Theorem 5.3 remains exponential in (H). Under which accuracy and branching regimes does it establish an improvement over unguided search, and should the corresponding claims be qualified?

3 comments

Thank you for the point raised in question 1, we will clarify this point in the pseudo-code. Obviously the method should not redo completed work. The fix is to accurately state the procedure precisely by starting from the root, stop at an uncertified node if its decomposition is unknown, its revealed decomposition is empty, or its conditional certificate is missing. Otherwise, descend to its first uncertified child. Never repeat an already obtained conditional certificate.

Guidance justification:

In the submission we tried to strike a balance between complexity of the model and accessibility of the results and we decided to consider a simpler version of guidance. From a practical perspective, our choice is motivated by the Stellar Colosseum [Lin et al. 2026] harness that shows how in-depth analysis works well to obtain accurate estimates on the complexity of a subproblem. Let us also mention that an attractive weaker guidance is that some estimates are allowed to be completely wrong with some small probability epsilon. This however, leads to a similar lower bound as the exponential lower bound of Theorem 5.1 but with the base replaced with ϵ⋅m\epsilon \cdot m. We can include this in the final paper to further motivate our choice of guidance.

Thank you for clarifying the procedure; the proposed change addresses my concern about repeated work. However, the practical motivation still leaves unclear how uniformly accurate estimates of optimal recursive completion costs would be obtained. Could you also clarify which accuracy and branching regimes yield an improvement over unguided search given the exponential dependence on depth?

Thanks for your response.

Theorem 5.1 says that an unguided search may lose a factor of ~ mh−1m^{h-1} where hh is the height and mm is the number of ways a statement can be decomposed. In general, we would expect that mm is \emph{large} as there are many options on how to decompose a statement.

While the bound in the guided search is still exponential in the height, the base now only depends on the accuracy of the estimator (the parameter α\alpha), Theorem 5.3. So if you have a "reasonable" estimator that is even a factor of 55 off, you would expect significantly better guarantees. We think this highlights the importance of the guidance in the search that AI systems such as colosseum use. However, we do stress that this is a theoretical study.

Reviewer_TqCqOpenReview ↗
Rating
1
Confidence
3
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper develops a formal model of LLM-assisted mathematical problem solving in which an online orchestration algorithm interacts with a probabilistic prover, a sound verifier, and a decomposer. A direct proof attempt or a conditional proof attempt succeeds independently with a fixed probability, while a decomposition reveals subproblems. The objective is to minimize the expected number of paid operations needed to certify the root statement, relative to an oracle that knows proof probabilities and, where applicable, decomposition distributions.

For deterministic decomposition trees, the paper proves that the offline optimum has a static proof plan and introduces ancestor dovetailing, which interleaves direct attempts along the active ancestral path with exploration at the frontier. The algorithm is shown to have a tight competitive ratio of H+1 for trees of full height H; without a height bound, its expected cost is O(OPT^2), with a matching asymptotic lower bound. For stochastic decomposers, the paper proves an exponential lower bound without side information. It then characterizes a distribution-aware optimal policy using a recursive Pandora's-box reservation rule: sample decompositions until a route falls below a reservation threshold and then commit recursively. Finally, it proposes a value-guided online algorithm using uniformly multiplicative approximate cost estimates and proves expected cost at most (H+1) alpha^(2H) OPT, recovering H+1 with exact estimates.

Critical strengths
  1. The paper gives a clean theoretical vocabulary for an increasingly important systems question. The separation between execution within a fixed decomposition and discovery among stochastic decompositions yields nontrivial results: tight deterministic competitive bounds, a sharp impossibility result without guidance, and a recursive optimal-stopping characterization. The central message that evaluation of route difficulty can be as important as proof-generation ability is both insightful and actionable.

  2. The theory is largely self-contained and supported by explicit algorithms, oracle benchmarks, upper bounds, and lower-bound constructions. The sample-then-commit theorem handles a broader adaptive policy space than a simple proof-tree argument, and the appendix directly addresses partial execution and abandonment through a remaining-work potential. The limitations of independence and no sharing are stated rather than hidden.

Critical weaknesses
  1. The connection to actual LLM harnesses is currently conceptual rather than validated. The core assumptions—fixed independent success probabilities, free and perfect verification, unit costs, no context effects, and no sharing or reuse of proved lemmas across occurrences—remove several defining features of real long-horizon agent systems. In particular, decomposition and proof outcomes in practice depend strongly on accumulated context and correlated model behavior. Without an empirical or trace-based study showing that the proposed quantities and policies predict real harness performance, it is unclear how much practical guidance follows from the bounds.

  2. The approximate-guidance guarantee is fragile: a uniform multiplicative alpha approximation is assumed for both direct and recursive route costs, yet the bound degrades as alpha^(2H). Producing such estimates may itself be essentially as hard as estimating the unknown proof process, and no model is given for learning, querying, or calibrating them. Thus the paper identifies cost guidance as necessary, but the positive result does not yet establish that attainable LLM estimates suffice at realistic depths.

Questions for authors
  1. Can you evaluate ancestor dovetailing or value-guided stopping on traces from an existing theorem-proving harness, estimating action costs and comparing predicted versus observed performance? Even a retrospective study would materially strengthen the claim that the abstraction captures real orchestration tradeoffs.

  2. How do the results change if verified intermediate statements can be reused across decomposition proposals, or if two proposals share a subproblem? The no-sharing assumption is central to both the recursive cost decomposition and the potential argument, while reuse is a primary motivation for maintaining proof context in practical systems.

  3. Is there a meaningful positive result under weaker guidance, such as ordinal rankings, one-sided estimates, or stochastic calibration rather than uniform multiplicative accuracy? The answer would affect whether the proposed theory offers a feasible prescription for current LLM-based systems.

1 comment

We agree that the main result of this paper is conceptual, our goal is to formalize a model that abstracts the current harnesses to formally study their power and optimization from a theoretical perspective. To this end, we would like to find the minimal setting that allows us to capture the benefits of harnesses as well as the difficulties with making them efficient in practice. We tried hard to not overfit to the methods du jour, but to abstract the different research threads into a common vocabulary, set of critical definitions, and metrics that the theory community can build on.

Almost by design then, there are many parts of workflows that are common today that are not present in the framework we propose, including shared context and correlated model behavior. Indeed, making the models effective at solving hard questions is a rich area of empirical research, as highlighted by the papers cited by Reviewer 12ji. Formulating these ideas in a way that we can draw rigorous conclusions, (beyond one generation of models to the next) remains a challenging open question and definitely an interesting direction for future work, but we believe we take a first step towards that goal with this work.

Thanks for suggesting various forms of weaker guidance, they are all interesting directions that we plan to explore in future works although in the submission we tried to strike a balance between complexity of the model and accessibility of the results and we decide to consider a simpler version of guidance. From a practical perspective, our choice is motivated by the Stellar Colosseum [Lin et al. 2026] harness that shows how in-depth analysis works well to obtain accurate estimates on the complexity of a subproblem.

To the third question, an attractive weaker guidance is that some estimates are allowed to be completely wrong with some small probability epsilon. This however, leads to a similar lower bound as the exponential lower bound of Theorem 5.1 but with the base replaced with ϵ⋅m\epsilon \cdot m. We can include this in the final paper to further motivate our choice of guidance.

Reviewer_2e2aOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper asks how a prover should divide its calls between trying a theorem directly, solving its subgoals, and requesting a different decomposition. A decomposition rewrites the original theorem as a set of (hopefully) simpler lemmas and try to prove they altogether imply the original theorem: this can be naturally modeled as a tree. For a fixed decomposition tree, the paper gave a scheduler with a tight worst-case guarantee. When calls can return different decompositions, the authors characterizes the informed planner’s optimal policy and analyze a scheduler that uses estimated completion costs.

Critical strengths

The fixed-tree result is the strongest part of the paper. The paper proposes a “dovetailing” scheduler which keeps trying direct proofs along the active path while it works on smaller goals. Its expected cost is at most H+1H+1 times the informed optimum, where HH is the tree height. The matching lower bound gives a clear answer about the cost of searching without knowing the proof probabilities.

I also found the commitment result in Theorem 5.2 interesting. Once the prover commits to a decomposition, it can treat that route as one action with a recursively computed completion cost. That reduction could lose something if partial work makes it worthwhile to switch routes. The theorem show that an informed planner gains nothing from such interleaving under the paper’s assumptions of independence and no sharing of newly proved lemmas.

Critical weaknesses

My main concern is that the guided scheduler receives estimates of the cost to finish a route under an optimal policy. The paper gives no evidence that a real prover can estimate this quantity reliably or cheaply. Even with exact estimates, the paper’s own example shows that the scheduler can keep paying for the same decomposition while it waits for the stopping threshold. This makes it hard to see when I would use the rule, e.g., in a Lean prover.

There is a concrete comparison available. Rognvaldsson et al. use failed Lean attempts to decide whether to retry a goal or request a new breakdown. A small study could compares the two policies under the same compute budget, including the cost of producing estimates. I would especially like to see what happens when a cheap-looking route turns out to be hard. Rognvaldsson et al., 2026

Questions for authors

The paper credits Weitzman (1979) for the reservation rule. The local decision in the guided algorithm also has a close precedent. Paying for another proposal or choosing the cheapest option seen so far is the same decision studied in ski rental with decreasing buy prices. I would like the authors to isolate what their recursive analysis adds and compare the commitment theorem with prior work on multistage alternatives.

Other minor comments:

  1. Which part of Theorem 5.2 require a new argument beyond existing results on costly search with multistage alternatives?
  2. What practical signal would you use to estimate the cost to finish a proof route? Can you show a case where that signal leads to a better scheduling decision than an existing retry-or-restart policy?
1 comment

Thank you for the review, in the final version we will address the main points raised.

Our goal in the paper is to formalize a model that abstracts the current harnesses to formally study their power and optimization from a theoretical perspective. To this end, we would like to find the minimal setting that allows us to capture the benefits of harnesses as well as the difficulties with making them efficient in practice. We tried hard to not overfit to the methods du jour, but to abstract the different research threads into a common vocabulary, set of critical definitions, and metrics that the theory community can build on. Nevertheless we agree that the work of Rognvaldsson et al. is relevant (thank you for the pointer!) and using insights from it for refining the model is definitely an interesting direction for future research.

From a practical perspective, our assumption on the estimate on the cost to finish a route is inspired by the Stellar Colosseum [Lin et al. 2026] harness that shows how in-depth analysis works well to obtain accurate estimates on the complexity of a subproblem.

Finally, for the first question we think that the main contribution of Theorem 5.2 from a theoretical perspective is to connect the two problems more than introducing new complex techniques to solve it. We will clarify this point in the final version.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.