INT: An Inequality Benchmark for Evaluating Generalization in Theorem Proving
INT benchmark evaluates generalization in theorem proving using inequalities; MCTS enhances proving new theorems.
Key Findings
Methodology
INT benchmark tests generalization in automated theorem proving using inequality theorem generation. Baselines include transformers and graph neural networks (GNNs), with Monte Carlo Tree Search (MCTS) added at test time to enhance proving new theorems.
Key Results
- Transformers outperform GNNs in most generalization tasks despite larger out-of-distribution gaps. MCTS significantly boosts test success rates.
- GNNs show better generalization with different initial conditions and unseen axiom combinations.
- Transformers excel when training and test data are from the same distribution but struggle in out-of-distribution tasks.
Significance
This study significantly advances learning-assisted theorem proving by introducing the INT benchmark, addressing data scarcity and out-of-distribution generalization issues, and providing a lightweight, user-friendly environment for further research.
Technical Contribution
INT offers a theoretically infinite data generation process, allowing evaluation across six generalization dimensions. Its lightweight design enables fast simulation, supporting complex planning methods like MCTS.
Novelty
INT is the first benchmark specifically designed to evaluate theorem proving generalization. Unlike prior benchmarks, it provides a lightweight and fast proving environment.
Limitations
- Transformers have poor generalization in out-of-distribution tasks, especially with varying axiom orders.
- Theorems generated by INT may lack realism, affecting practical application.
- MCTS has high computational costs, potentially limiting its application to large-scale problems.
Future Work
Future research could explore enhancing transformers' out-of-distribution generalization and reducing MCTS computational costs. Expanding INT to generate more complex and realistic theorems is also a direction.
AI Executive Summary
Generalization is a critical challenge in learning-assisted theorem proving. Existing solutions often perform poorly in out-of-distribution tasks, limiting their applicability. To address this, researchers have introduced INT, a benchmark specifically designed to evaluate generalization in theorem proving using inequalities. INT provides a lightweight and fast proving environment by generating theoretically infinite numbers of theorems and proofs.
The core of INT lies in its flexible theorem generation process, allowing evaluation across six different dimensions of generalization. Researchers used transformers and graph neural networks as baselines, adding Monte Carlo Tree Search (MCTS) at test time to enhance proving new theorems. Experimental results show that transformers outperform GNNs in most generalization tasks despite larger out-of-distribution gaps.
While INT has made significant progress in evaluating generalization, it still has limitations. Transformers perform poorly in out-of-distribution tasks, especially with varying axiom orders. Additionally, theorems generated by INT may lack realism, affecting practical application. Future research could explore enhancing transformers' out-of-distribution generalization and reducing MCTS computational costs.
Deep Dive
Abstract
In learning-assisted theorem proving, one of the most critical challenges is to generalize to theorems unlike those seen at training time. In this paper, we introduce INT, an INequality Theorem proving benchmark, specifically designed to test agents' generalization ability. INT is based on a procedure for generating theorems and proofs; this procedure's knobs allow us to measure 6 different types of generalization, each reflecting a distinct challenge characteristic to automated theorem proving. In addition, unlike prior benchmarks for learning-assisted theorem proving, INT provides a lightweight and user-friendly theorem proving environment with fast simulations, conducive to performing learning-based and search-based research. We introduce learning-based baselines and evaluate them across 6 dimensions of generalization with the benchmark. We then evaluate the same agents augmented with Monte Carlo Tree Search (MCTS) at test time, and show that MCTS can help to prove new theorems.