- 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 levels of unresolved problems, this approach uses at most 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
- 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.
- 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 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 . The lower bound is the usual argument that an online algorithm facing candidates, one of which works with probability , needs about trials, and the lower bound of Corollary 4.3 uses the same chain with of the order of OPT. Theorem 5.1 is a needle in a haystack with 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 or that real harnesses have a height 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 and , 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 , adds in parentheses that it recovers a factor of 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 at , and the introduction should say so.
Even with exact estimates the worst-case ratio is , 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 decomposition calls at the level with 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 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 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
- 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 for a difficulty estimator and the realized cost ratio would help.
- Is tight for your algorithm, or an artifact of the recurrence ? The appendix shows tightness only for .
- 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
Thanks for the reply. Adding the papers I mentioned to the related work and writing up the tightness example for 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.
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) 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→f where f is verified and all ai are initially unverified. The optimal strategy will be to prove the root statement directly by proving a1 but we will choose approximate estimates so as to prefer decompositions all the way down to proving that f implies aH. Specifically, at each level, overestimating the direct-proof cost by a factor (α) and underestimating the decomposition cost by a factor (α) can make the algorithm prefer a route whose true completion cost is almost (α2) times larger. Nesting these choices along the chain makes the losses compound across all the H levels. Including the algorithm’s sampling costs, this construction approaches the exact bound given by the recurrence (Rh=α+α2Rh−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.