From LLM-Generated Conjectures to Lean Formalizations: Automated Polynomial Inequality Proving via Sum-of-Squares Certificates
Summary
NSPI is a novel neuro-symbolic framework designed for automated polynomial inequality proving, combining the strengths of Large Language Models (LLMs) and symbolic computation. It addresses scalability challenges in traditional symbolic methods and data scarcity in purely LLM-based approaches. The framework operates in three stages: an LLM proposes an approximate Sum-Of-Squares (SOS) decomposition conjecture, which is then refined into an exact polynomial SOS representation via symbolic computation, and finally certified in Lean, an interactive theorem prover. NSPI demonstrates superior performance and scalability on a new benchmark, PolyIneqBench, which includes 522 challenging polynomial inequality problems with up to 10 variables, outperforming existing symbolic and LLM-based methods in both success rate and efficiency.
Key takeaway
For AI Scientists and Machine Learning Engineers working on automated theorem proving, NSPI offers a robust approach to tackle high-dimensional polynomial inequalities. Your teams should consider adopting neuro-symbolic frameworks that leverage LLMs for initial conjecture generation, followed by rigorous symbolic correction and formal verification. This strategy can significantly improve success rates and efficiency, especially for problems with more than 5 variables, broadening the scope of formally verifiable mathematical reasoning.
Key insights
NSPI combines LLM conjecture generation with symbolic refinement and formal verification for scalable polynomial inequality proving.
Principles
- Integrate neural heuristics with symbolic precision.
- Formulate inequality proving as SOS-based certification.
- Progressive training enhances LLM structural reasoning.
Method
NSPI uses an LLM for approximate SOS conjecture, symbolic computation for exact rational recovery via Gauss-Newton refinement, and Lean for formal proof generation, creating an end-to-end pipeline.
In practice
- Generate synthetic polynomial-SOS pairs for LLM training.
- Use Gauss-Newton refinement for numerical precision.
- Employ rational recovery for exact SOS certificates.
Topics
- Automated Inequality Proving
- Sum-of-Squares Decomposition
- Neuro-Symbolic Framework
- LLM Conjecture Generation
- Lean Formal Verification
Best for: AI Scientist, Machine Learning Engineer, Research Scientist
Related on AIssential
Editorial summary, takeaway, and curation by AIssential. Original article published by cs.AI updates on arXiv.org.