acceptodds
Under review as a conference paper at ICLR 2027

IneqAgent: Agentic Inequality Proving in Lean with Symbolic Computation

Abstract

Formal inequality proving requires mathematical reasoning and exact computation, often connected through intermediate lemmas and goal reformulations. We introduce IneqAgent, an agentic framework combining LLM reasoning with symbolic computation for inequality proving in Lean 4. Lemma-level Monte Carlo Tree Search coordinates lemma construction, goal reformulation, and symbolic backend selection. Complementary sum-of-squares, Bernstein, and successive difference-substitution backends produce exact certificates for local Lean proof generation. The agent integrates these proofs with LLM-generated steps and uses Lean feedback to construct complete proofs checked against the original theorem statements. On four benchmarks, IneqAgent with DeepSeek-V4-Flash solves 178 of 190 problems (93.68%), achieving the highest overall success rate among the evaluated methods. Across four backbones, it achieves higher success rates at low LLM inference cost thresholds than Direct Agent using the same backbone, with lower mean inference costs over each method's successful runs. We also obtain Lean-verified strengthenings of Dittert's conjecture in dimensions four and five, and certify the Holens–Djokovic inequality, implying Merris's conjecture in dimension four.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
formal theorem proving, AI for mathematics, Lean 4, LLM agent

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_RNmWOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes IneqAgent, which combines lemma-level MCTS, LLM reasoning, and symbolic computation to prove inequalities in Lean 4. It solves 93.68% of 190 benchmark problems and verifies three mathematical problems involving matrix permanents.

Critical strengths
  1. Combines multiple symbolic methods with Lean to generate formally verified proofs.

  2. Solves 93.68% of 190 problems and demonstrates applications to matrix permanent conjectures.

Critical weaknesses
  1. MCTS, SOS, Bernstein, and difference substitution are existing methods. Although the paper introduces lemma-level search and multiple symbolic backends, it mainly combines existing techniques without clear new algorithmic contributions.

  2. IneqAgent solves only 8 more problems than the Base Agent (178 vs 170), without statistical significance tests. Qwen and Kimi perform worse without cost limits, and the cost analysis excludes symbolic computation and Lean verification.

Questions for authors
  1. What are the new algorithmic contributions of IneqAgent compared with LIPS, NSPI, and existing SOS methods? Can their effects be evaluated separately?

  2. Can the authors test the significance of the gains under equal end-to-end compute budgets, and explain why Qwen and Kimi perform worse without cost limits?

1 comment
AuthorsOpenReview ↗

Response to Reviewer RNmW

We thank the reviewer for the valuable comments on algorithmic contributions, the significance of the gains, and computational budgets. We respond in two parts below.

Q1: Algorithmic contributions and differences from existing methods

IneqAgent is not a simple combination of existing techniques such as MCTS, SOS, Bernstein, and difference substitution. Its contribution lies in the design of a lemma-level MCTS search coupled with verifiable symbolic certificate generation. Numerical computation in SOS and Bernstein solving only assists exact certificate recovery; final certificates are still checked exactly and verified in Lean.

  • vs. LIPS: LIPS builds candidate steps via inequality scaling and rewriting, selected by symbolic filtering, numerical counterexample checks, and the LLM. IneqAgent searches over lemma states and assembles backend certificates into a complete Lean proof. Our main experiments already compare with LIPS.
  • vs. NSPI: NSPI also performs exact SOS recovery, but mainly targets unconstrained polynomial nonnegativity. Our SOS procedure also handles equality and inequality constraints by first fixing the inequality multipliers and then jointly recovering the main SOS block and the equality multipliers.
  • vs. Isabelle SOS: Both aim at exact certificates but differ in recovery strategy: Isabelle SOS eliminates the coefficient-matching equations exactly before rational recovery, whereas we use staged recovery with joint Gauss–Newton refinement and rational recovery.

For the search, under the same 2-hour limit, lemma-level MCTS solves 178 problems versus 172 for BFS, with mean times of 142.60 s versus 196.90 s on the 169 solved by both. We evaluated the SOS and Bernstein procedures separately against existing approaches on all instances of the relevant subsets; an instance counts as solved only if its exact certificate passes checking.

SOS certificate generation (115 polynomial optimization instances):

MethodSolved / TotalAvg. time on the 20 commonly solved (s)
Isabelle SOS22 / 11519.70
Our SOS method51 / 11512.10

Bernstein exact solving (45 box-constrained instances):

MethodSolved / TotalAvg. time on the 5 commonly solved (s)
Exact solving of full LP (baseline)5 / 4572.16
Float screening + exact reduced LP (ours)28 / 452.97

Our SOS procedure solves 51 instances versus 22 for Isabelle SOS, and reduces mean runtime by 38.6% on the 20 commonly solved instances. In the inspected Isabelle SOS timeout cases, we observed near-zero estimated minima, rational-recovery failures, and subsequent degree increases before the time limit was reached. For Bernstein, both use the same degree, subdivision, and time limit, with screening time included. Exact solving of the full LP is costly and most instances time out at the initial degree; the reduced LP raises solved instances from 5 to 28 and reduces mean runtime by 95.9% on the 5 commonly solved instances.

Q2: Computational budget, significance of the gains, and Qwen/Kimi results

Computational budget. We additionally measured the average per-problem time of IneqAgent with the main backbone, DeepSeek, on solved instances:

Symbolic computation (s)Lean verification (s)End-to-end total (s)
17.1884.32154.75

For comparison, the corresponding end-to-end time of Direct Agent (the Base Agent in the review) is 336.24 s. The 2-hour per-problem wall-clock limit includes all symbolic computation and Lean verification, and all local computations use the same hardware. The monetary cost covers only LLM API fees, not total compute; we will state this explicitly.

Significance of the gains. We thank the reviewer for the valuable suggestion. With DeepSeek, based on per-problem paired outcomes of IneqAgent and Direct Agent (9 problems solved only by IneqAgent, 1 solved only by Direct Agent), a two-sided exact McNemar test gives p=0.0215p = 0.0215, significant at the 0.05 level for this DeepSeek configuration.

Qwen and Kimi. We acknowledge that these results show the framework does not improve the final success rate under every model and cost setting. In the inspected Kimi failures, the framework steers the model to call the backends early, but Kimi tends to hand the whole goal to them instead of first constructing lemmas, so calls time out and the budget is exhausted. Under the same 2-hour limit, Direct Agent instead spends this time on direct proof attempts. We have not yet determined the cause for Qwen. We will include this analysis in the revision and narrow our claims about gains across models accordingly.

We thank the reviewer again for the valuable suggestions. We hope these responses address the concerns, and we would be glad to discuss any further questions.

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

This paper presents IneqAgent, a framework that combines LLM reasoning, lemma-level MCTS, and three symbolic backends to prove inequalities in Lean. It reports solving 178 of 190 benchmark problems and presents cases related to the Dittert, Holens-Djokovic, and Merris conjectures.

Critical strengths
  • The framework connects proof search, symbolic computation, and Lean verification. The paper states that complete proofs are checked against the original theorem statements.

  • The experiments include several benchmarks, four LLM backbones, and ablations of MCTS and symbolic computation. With DeepSeek-V4-Flash, the full framework solves 178 problems, compared with 170 for the base agent.

Critical weaknesses

Several important implementation details remain unclear, especially normalization and the Translator. The scope of the conjecture proofs also need clarification.

others could refer to Quesstions.

Questions for authors
  1. Is normalization implemented with fixed rules, an LLM, or both? Please give an exact normalization process of a complex inequality problem, which contain (some of) square root, absolute values, logarithms, exponentials, or trigonometric functions? And also please explain how translations from HOL Light/PVS statements into Lean are checked for correctness.
  2. Is the Translator a deterministic parser, a template-based proof generator, an LLM, or a combination of these?
  3. Section 3.2 should separate existing backend methods from the paper's own contributions more clearly. For reused methods, should focus on their requirements (how to match) and failure feedback.
  4. Appendix C states that six Flyspeck instances contain non-polynomial expressions, but their names or identifiers are not listed in the PDF. Polynomial inequalities are normally easy, it would be helpful to give these instances to??? difficulty.
  5. In Table 2, Direct Agent reaches similar or higher success rates with some backbones when the cost limit is removed. Does the framework solve problems that Direct Agent cannot solve under the same conditions?
  6. I cannot directly know the mathematical importance of these results and how much human help was needed. For the Merris result, clarify whether the full conclusion, including the column permutation step, is verified in Lean.
1 comment
AuthorsOpenReview ↗

Response to Reviewer hNva

We thank the reviewer for the careful reading and for recognizing our integration of proof search, symbolic computation, and Lean verification. We address each question below.

Q1: Normalization and HOL Light/PVS translation

Normalization combines fixed rules with the LLM. Fixed rules handle format standardization, hypothesis/goal separation, and constraint elimination; the LLM handles goal feature recognition and equivalence-preserving transformations, each checked by Lean. Take IneqComp-real P15 as an example:

2a+18b≥14,a,b∈R, a−3b+6=02^a + \frac{1}{8^b} \ge \frac14,\qquad a,b\in\mathbb{R},\ a - 3b + 6 = 0

  1. Standardization (fixed rules): separate the hypothesis from the goal, rewrite the goal as ≥0\ge 0, and identify the linear equality constraint.
  2. Constraint elimination (fixed rules): substitute a=3b−6a = 3b-6 to get 23b−6+8−b≥142^{3b-6} + 8^{-b} \ge \frac14.
  3. Equivalent transformation (LLM, checked by Lean): using 23b−6=8b/642^{3b-6} = 8^b/64, set t=8b>0t = 8^b > 0 and multiply by 64t>064t>0 to get t2−16t+64≥0t^2-16t+64 \ge 0.
  4. Symbolic backend: SOS proves it with the certificate (t−8)2(t-8)^2.

For statements translated from HOL Light/PVS into Lean, we manually compared each against its original to ensure semantic agreement in variable domains, hypotheses, and conclusions.

Q2: Nature of the Translator

Thank you for your insightful observation. The Translator is a pre-implemented, template-based, deterministic proof generator and does not involve an LLM. It runs before proof checking and converts the exact certificates from the symbolic backends into Lean code using fixed templates. Its correctness therefore need not be an additional trust assumption: the generated proofs must still pass the final Lean verification against the original theorem statements.

Q3: Separating existing backend methods from our contributions

We acknowledge that the underlying mathematical methods, namely the SOS/Putinar certificate framework, Bernstein representation with interval subdivision, and difference substitution, are existing techniques. Our improvements concern exact certificate solving. The SOS backend uses staged recovery, first fixing the inequality multipliers and then jointly recovering the main SOS block and the equality multipliers, so that our exact recovery supports equality and inequality constraints. The Bernstein backend identifies a candidate support from a floating-point solution and then solves a much smaller reduced LP exactly; compared with exact solving of the full LP, this raises solved box-constrained instances from 5/45 to 28/45.

In the revision, we will strengthen this section to state explicitly what is improved in each backend, when each backend applies, and what feedback is returned to the agent upon failure.

Q4: The six non-polynomial Flyspeck instances

Thank you for this valuable feedback. The six non-polynomial Flyspeck instances included in LitIneq are 5512912661, 6843920790, SDCCMGA b, 7067938795, 5490182221, and 3318775219. We will add them with their full statements to Appendix C.

Q5: Does the framework solve problems that Direct Agent cannot?

Yes. With our main backbone, DeepSeek, the per-problem outcomes under the same conditions are:

OutcomeProblems
Solved only by IneqAgent9
Solved only by Direct Agent1
Solved by both169

These 9 problems generally have complex forms involving radicals, transcendental functions, or other non-polynomial components, and their generated proofs use intermediate lemmas to transform and simplify the goals before the symbolic backends finish the proof. We also acknowledge that, without an LLM cost cap, Direct Agent matches or exceeds IneqAgent with some other backbones. In the Kimi runs we inspected, calls on unreduced goals led to repeated backend timeouts and exhausted the search budget. We will discuss this observed failure mode and narrow our claims about cross-model gains in the revision.

Q6: Mathematical significance, human involvement, and scope of the Merris verification

Regarding significance, the Dittert and Merris conjectures are classical problems in permanent theory. We obtain a quantitative stability form of Dittert's conjecture in dimension five, and our HD(4,4) result implies Merris's conjecture in dimension four.

Regarding human involvement, collecting the problems, reducing them to inequalities, and formalizing them as Lean statements were done manually; the subsequent proving is fully automated and yields complete, sorry-free proofs verified by the Lean kernel.

Regarding Merris, we prove the four-dimensional case of Merris's conjecture, including the column permutation step, entirely in Lean:

∀A∈Ω4,∃j,∑iper⁡(A(i∣j))≤4per⁡(A).\forall A \in \Omega_4,\quad \exists j,\quad \sum_i \operatorname{per}\big(A(i \mid j)\big) \le 4\operatorname{per}(A).

We thank the reviewer again for the valuable suggestions. We hope these responses address the concerns, and we would be glad to discuss any further questions.

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

IneqAgent combines lemma-level MCTS, symbolic computation, and Lean 4 verification for formal inequality proving. Three symbolic backends (SOS, Bernstein, and DiffSub) generate exact certificates integrated into Lean proofs. The system solves 178/190 benchmark problems (93.68%) and demonstrates improved success under low LLM inference-cost thresholds. Mathematical applications include quantitative Dittert bounds for n=4,5n=4,5 and a Lean-verified Holens–Djoković (4,4) inequality.

Critical strengths

1.The paper presents Lean-verified stability results for Dittert's conjecture in dimensions n=4n=4 and n=5n=5.

In particular, the dimension-four result establishes:

\ge \frac{1}{52}\\|A-J_4\\|_F^2.$$ 2.IneqAgent achieves higher success rates than Direct Agent at the 5-, 10-, and 50-cent LLM inference cost thresholds.
Critical weaknesses
  1. The full system improves over the base agent by only 8/190 problems (Table 3). Without comparisons against simpler search strategies or an analysis of when intermediate lemmas and backend selection are essential, the specific contribution of lemma-level MCTS remains unclear.

  2. IneqSearch (NeurIPS 2025) reports Lean-verified 20/20 success on MO-INT-20, compared with 19/20 here, but is omitted from Table 1. Moreover, arXiv:2607.29191 already reports the same Dittert n=4n=4 stability bound and SOS certificate structure. These overlaps require clearer empirical positioning and novelty attribution.

Questions for authors
  1. Why is IneqSearch excluded from Table 1, given its reported 20/20 result on MO-INT-20?

  2. Which benchmark successes specifically require lemma-level MCTS or agent-generated intermediate lemmas? Could simpler search strategies achieve similar results?

  3. How does the Dittert n=4n=4 contribution differ from arXiv:2607.29191? Which mathematical case-study steps were discovered automatically rather than manually designed?

  4. How do you reconcile the Holens–Djoković (4,4) result with the contrary claim in Udayan and Somasundaram (2021, Theorem 6)?

1 comment
AuthorsOpenReview ↗

Response to Reviewer aCDK

We thank the reviewer for the valuable comments on baseline comparison, search strategy, and the mathematical case studies. We address each question below.

Q1: Comparison with IneqSearch

We agree that IneqSearch is closely related; we will add its reported 20/20 on MO-INT-20 (under its original setting) to Table 1.

The unsolved MO-INT-20 problem P10 states: for a,b,c,d>0a,b,c,d>0,

aa3+63bcd3+bb3+63cda3+cc3+63dab3+dd3+63abc3≥1.\frac{a}{\sqrt[3]{a^3+63bcd}}+\frac{b}{\sqrt[3]{b^3+63cda}}+\frac{c}{\sqrt[3]{c^3+63dab}}+\frac{d}{\sqrt[3]{d^3+63abc}} \ge 1.

Its search process is summarized below:

RoundAction in this roundSymbolic backend
1Normalize with x1=63bcd/a3x_1=63bcd/a^3; prove ∏xi=634\prod x_i=63^4; goal becomes 1≤∑(1+xi)−1/31\le\sum(1+x_i)^{-1/3}—
2Substitute ti=(1+xi)−1/3t_i=(1+x_i)^{-1/3}; prove 0<ti<10<t_i<14 calls, all timed out
3Derive ∏(1−ti3)=634∏ti3\prod(1-t_i^3)=63^4\prod t_i^3; remaining goal 1≤∑ti1\le\sum t_i under a degree-12 constraint1 call, timed out
4Try a contradiction route; goal unchanged3 calls, all timed out
5New branch from the root: propose (∑a)4≥∑a4+252abcd(\sum a)^4\ge\sum a^4+252abcdproved by diff_sub
6Reduce the goal via Titu's lemma to a Hölder-type bound—
7Finish with Mathlib's weighted Hölder inequality and the round-5 lemma—

The substitution route in rounds 1–4 left a degree-12 constraint on which all backend calls timed out, and the search spent considerable time there before returning to the root. The Hölder route from round 5 left only a quartic core, proved by diff_sub, but the earlier rounds had consumed much of the budget, so the proof was incomplete at the 2-hour limit and the problem was counted as a failure. With the limit removed, the search continued from that state and completed the proof at 2 hours and 6 minutes in total.

This case reveals the main limitation of the current system: it does not reliably anticipate whether a goal is within reach of the symbolic backends, and can therefore spend considerable time on goals the backends do not solve within the budget. We will discuss this limitation in the revision.

Q2: Role of lemma-level MCTS and comparison with simpler search

Thank you for your insightful observation. Based on the run logs, 131 of the 178 problems solved by IneqAgent use agent-generated intermediate lemmas.

To test whether a simpler search strategy could achieve similar results, we ran a controlled comparison between BFS and lemma-level MCTS. Both use the same datasets, model, symbolic backends, prompts, and 2-hour per-problem time limit; only the search scheduling differs:

Search strategySolved / 190Mean time on the 169 solved by both (s)
BFS172196.90
Lemma-level MCTS178142.60

Under the same 2-hour limit, MCTS solves 9 problems that BFS fails on, while BFS solves 3 that MCTS fails on (net +6). On the 169 solved by both, MCTS saves about 54 s per problem on average (27.6%).

Q3: Relation to arXiv:2607.29191 and scope of automation

Thank you for this valuable feedback. The dimension-four stability bound and its exact SOS certificate construction were previously reported in arXiv:2607.29191, which also describes the sequential rational-recovery procedure. We will explicitly attribute these results and methods to that work. In the present paper, the dimension-four case serves as a research-level application of IneqAgent’s general proving framework, and we do not claim the bound or its certificate-construction method as new contributions.

For the three mathematical case studies in Section 4.5, the reductions to constrained polynomial inequalities and the corresponding Lean statements were prepared manually. The steps connecting the original matrix theorems to the polynomial goals were also proved manually in Lean. IneqAgent automatically constructs proofs of the resulting polynomial goals.

Q4: Relation to Theorem 6 of Udayan and Somasundaram (2021)

We examined the proof of Theorem 6 in that paper and found an error in the endpoint computation. The paper defines Δ(t)=per⁡(A)−per⁡(tJ4+(1−t)A)\Delta(t) = \operatorname{per}(A) - \operatorname{per}(tJ_4 + (1-t)A) and uses Δ(1)=0\Delta(1) = 0. However, Δ(1)=per⁡(A)−per⁡(J4)=per⁡(A)−332\Delta(1) = \operatorname{per}(A) - \operatorname{per}(J_4) = \operatorname{per}(A) - \frac{3}{32}, which is nonzero in general. For instance, A=I4A = I_4 satisfies the conditions of the theorem, yet Δ(1)=2932≠0\Delta(1) = \frac{29}{32} \neq 0. Hence the argument there that relies on this identity to refute HD(4,4) does not hold.

Our HD(4,4) result is established independently by an exact rational SOS certificate and a Lean formal proof. In the revision, we will present the erroneous step in the original proof alongside our formal statement and proof files.

We thank the reviewer again for the valuable suggestions. We hope these responses address the concerns, and we would be glad to discuss any further questions.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.