Wu’s Method Boosts Symbolic AI to Rival Silver Medalists and AlphaGeometry to Outperform Gold Medalists at IMO Geometry

Shiven Sinha, Ameya Prabhu, Ponnurangam Kumaraguru, Siddharth Bhat, Matthias BethgeMATH-AI @ NeurIPS 2024 · OpenReview

TL;DR

This paper revisits Wu's method, a classic symbolic AI technique for geometry theorem proving, and finds it surprisingly effective. By combining Wu's method with traditional synthetic geometry techniques, the authors establish a new state-of-the-art symbolic baseline that rivals human silver medalists. Furthermore, when combined with AlphaGeometry, they achieve a new AI record, outperforming human gold medalists on the challenging IMO-AG-30 benchmark.

What Problem Does This Paper Address?

Automated theorem proving (ATP) in geometry, especially for Olympiad-level problems like those from the International Mathematical Olympiad (IMO), is a significant challenge. These problems require a blend of logical deduction, visual intuition, and algebraic manipulation. While recent neuro-symbolic approaches like AlphaGeometry have shown impressive results, solving 25 out of 30 IMO problems, the performance of older, purely symbolic methods like Wu's method has been less explored on modern benchmarks. This paper aims to re-evaluate Wu's method and explore its potential, particularly in combination with other established techniques, to push the boundaries of symbolic AI in geometric reasoning.

Methods

The core of this work involves re-evaluating and combining different automated reasoning techniques.

  • Wu's Method: This is a well-established algebraic method that transforms geometric hypotheses into a system of polynomial equations. It's known for its theoretical guarantees and ability to handle degenerate cases automatically. The authors implement Wu's method using the JGEX software.
  • Synthetic Methods (DD+AR): This refers to a combination of Deductive Databases (DD) and Angle, Ratio, and Distance chasing (AR). These methods mimic human-like proving by applying a set of geometric rules and deductions. This approach was used as a baseline in previous work.
  • Combination (Wu&DD+AR): The authors propose combining Wu's method with the DD+AR synthetic methods. This is achieved by running both methods in parallel and accepting a solution from either.
  • Ensemble (Wu&AG): The paper also explores combining the strengths of Wu's method with AlphaGeometry (AG), a state-of-the-art neuro-symbolic prover.

Datasets

The primary dataset used is the IMO-AG-30 benchmark. This benchmark, introduced by Trinh et al. [24], consists of 30 classical geometry problems collected from IMO competitions since 2000. These problems have been adapted for use in interactive graphical proof assistants. The authors also provide their own translated versions of these problems for the JGEX solver.

Key Insights and Ideas

  • Wu's Method is Underrated: Contrary to previous benchmarks that reported Wu's method solving only 10 problems, this paper demonstrates its surprising strength, solving 15 problems on the IMO-AG-30 benchmark, including some that other methods missed.
  • Synergy of Symbolic and Synthetic: Combining Wu's algebraic method with classic synthetic techniques (DD+AR) yields a powerful fully symbolic baseline. This highlights the complementary nature of different reasoning paradigms.
  • Symbolic AI Can Rival Human Performance: The Wu&DD+AR combination achieves a performance level comparable to IMO silver medalists, establishing a strong symbolic baseline that was previously lacking.
  • Algebraic Methods Solve Difficult Cases: Wu's method uniquely solves two problems that even AlphaGeometry struggled with, underscoring its value for specific challenging geometric configurations.
  • AI Outperforms Human Gold Medalists: The ensemble of AlphaGeometry and Wu's method (Wu&AG) achieves a new state-of-the-art, solving 27 out of 30 problems, surpassing the average performance of IMO gold medalists.

Key Results

  • Wu's Method Alone: Solved 15 out of 30 problems on the IMO-AG-30 benchmark.
  • Wu&DD+AR (Symbolic Baseline): Solved 21 out of 30 problems. This combination achieved this performance on a CPU-only laptop within a 5-minute time limit per problem, with most problems solved in under 5 seconds. This rivals the performance of IMO silver medalists (average 22.9 problems).
  • Wu&AG (State-of-the-Art): Solved 27 out of 30 problems. This ensemble outperforms IMO gold medalists (average 25.9 problems) and represents the first AI method to do so.
  • Computational Efficiency: Wu's method demonstrated remarkable efficiency, solving many problems almost instantly.

Limitations and Future Work

  • Limited Implementations: The authors note that the availability of robust and comprehensive implementations for algebraic methods is scarce, hindering broader exploration.
  • Human Interpretability: While Wu's method is theoretically powerful, its proofs are not easily human-readable, which has historically been a drawback. The authors advocate for not dismissing it solely on this basis.
  • Future Directions:
    • Encouraging improvements in software for classical computational approaches in geometry.
  • Exploring enhancements to other symbolic methods and geometry-specific languages.
  • Investigating the interplay between human-like synthetic reasoning and abstract algebraic methods.
  • Developing new benchmarks that offer greater diversity and open-ended testing to advance general reasoning skills.

Summary updated

Abstract

Proving geometric theorems constitutes a hallmark of reasoning combining intuitive, visual, and logical skills, making automated theorem proving of Olympiad-level geometry problems a milestone for human-level automated reasoning. AlphaGeometry, a neuro-symbolic model trained with 100M synthetic samples, solved 25 of 30 International Mathematical Olympiad (IMO) problems. It marked a major breakthrough compared to the reported baseline using Wu's method which solved only 10. Revisiting the IMO-AG-30 benchmark, we find that Wu's method is surprisingly strong and solves 15 problems, including some unsolved by other methods. This leads to two key findings: (i) Combining Wu's method with the classic synthetic methods of deductive databases and angle, ratio & distance chasing solves 21 out of 30 problems on a CPU-only laptop limited to 5 minutes per problem. Essentially, this classic method solves just 4 fewer problems than AlphaGeometry and establishes the first *fully symbolic* baseline that rivals the performance of IMO silver medalists. (ii) Wu's method even solves 2 of the 5 problems that AlphaGeometry failed on. Combining both, we set a new state-of-the-art for automated theorem proving on IMO-AG-30 solving 27 out of 30 problems - the first AI method which outperforms an IMO gold medalist.
BibTeX
@inproceedings{sinha2024wus,
  author = {Shiven Sinha and Ameya Prabhu and Ponnurangam Kumaraguru and Siddharth Bhat and Matthias Bethge},
  title = {{Wu’s Method Boosts Symbolic AI to Rival Silver Medalists and AlphaGeometry to Outperform Gold Medalists at IMO Geometry}},
  booktitle = {MATH-AI @ NeurIPS},
  year = {2024},
  url = {https://openreview.net/forum?id=aKRtC45gle},
}
Figure