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