Abstract
Automated Theorem Proving (ATP) faces significant challenges in handling combinatorial explosions and a lack of high-quality training data. This paper introduces AutoTrig, a deep learning-based prover for trigonometric identities developed by researchers at Huawei Noah’s Ark Lab. By integrating imitation learning from a pruned search strategy with reinforcement learning (PPO), AutoTrig achieves near-optimal proof lengths while operating 1,000 times faster than traditional search methods. The system demonstrates a 99.8% pass rate on synthetic datasets and outperforms both symbolic tools and human experts.
Introduction
Automated Theorem Proving is a fundamental goal of symbolic AI. However, it is hindered by the "combinatorial explosion" of deduction steps and the difficulty of generalizing to unseen problems. Trigonometric identities provide an ideal domain to test these challenges, as they require "mathematical intuition"—the ability to choose the most efficient path among many valid transformations. While tools like Sympy or Matlab can solve many identities, they often rely on heuristics that fail to find the most elegant or shortest proofs.
Methodology
The AutoTrig pipeline consists of several key stages designed to transform raw expressions into optimized proofs.
Data Generation and Normalization
To address the scarcity of human-proven data, the authors developed a "bottom-up" synthetic generator. Expressions are first normalized into a standard polynomial form using $\sin$ and $\cos$. The generator starts with a simple expression, applies random transformations to create a complex equivalent, and subtracts them to form an identity equal to zero.
Search and Learning Architecture
Initial "ground truth" proofs are generated using rBFS (Random Breadth-First Search), which prunes the search tree by exploring only three random branches per node. The core architecture utilizes a BERT (Transformer) backbone to process mathematical expressions as token sequences.
Training Pipeline
The training process involves two main phases:
- Imitation Learning (IL): The model is trained to mimic successful paths from rBFS. Theoretical analysis suggests the model can outperform its teacher by aggregating patterns across diverse samples.
- Reinforcement Learning (RL): Using Proximal Policy Optimization (PPO), the model is refined to minimize proof length. It receives rewards for successful proofs and penalties for each step taken.
Evaluation and Results
AutoTrig was evaluated against synthetic datasets (200,000 identities), shuffled terms (T1), unseen coefficients (T2), and real-world IMO-level problems (T3).
Efficiency and Quality
AutoTrig demonstrates a massive speedup, proving identities in an average of 0.159 seconds, compared to 166 seconds for a full BFS. Despite this speed, proof quality remains high; AutoTrig's average proof length of 4.40 steps is close to the theoretical minimum of 4.27 steps and significantly better than the rBFS teacher (4.94 steps).
Comparative Performance
AutoTrig achieved a 99.8% pass rate on synthetic tests, surpassing Sympy (90.5%) and Matlab (96.8%). In a comparative study with human experts (Master's degree or higher), AutoTrig found shorter proofs (5.6 steps vs. 7.58 steps) in a fraction of the time.
Discussion and Key Insights
A significant finding is the model's ability to learn the "min" operator. By training on sub-optimal rBFS data, the neural network learns to identify the best actions across many examples, effectively distilling an optimal policy. Through RL, the agent develops "mathematical intuition," such as identifying common factors early to reduce proof length.
Limitations and Future Work
Current limitations include a fixed sequence length in BERT (limiting expressions to 8 terms) and a restricted set of 8 transformation rules. Future work aims to expand the system to handle multivariable identities, complex summations, and a broader range of mathematical "tricks" required for high-level competition problems.
Summary updated