Research map / Learning theory and algorithms / Combinatorial and search optimization
Learning to compute Gröbner bases
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces the first Transformer-based learning approach to Gröbner basis computation, with a backward dataset-generation method for 0-dimensional radical ideals in shape position and a hybrid discrete/continuous coefficient embedding.
Problem
Gröbner basis computation is NP-hard (doubly exponential worst case), and training Transformers for it requires many (non-Gröbner set, Gröbner basis) pairs, which are prohibitively expensive to generate forward; coefficient tokenization over infinite fields also blows up vocabulary or sequence lengt
Approach
Generate datasets backward: sample a reduced lex Gröbner basis in shape position, then multiply by random unimodular upper-triangular and permutation matrices to obtain a non-Gröbner generating set with the same ideal; embed continuous coefficients with a small feed-forward network instead of large number-token vocabularies.
Key results
- Backward generation of 1,000 samples over Q for n=5 takes 7.91 s versus 1411.1 s for forward SageMath std, a speedup of a few orders of magnitude.
- Transformer with discrete embedding reaches 93.7% accuracy (95.4% support accuracy) on Q, n=2 shape-position ideals and 86.5% on Q, n=5.
- Accuracy drops on finite fields (F31 discrete: 46.8% at n=2, 28.6% at n=5) while support accuracy stays around 77-84%.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace discrete coefficient tokens with hybrid continuous coefficient embedding | Transformer Gröbner basis computation · Shape position, Q | accuracy (%): 93.7 -> 66.8 | Hurt |
| Replace discrete coefficient tokens with hybrid continuous coefficient embedding | Transformer Gröbner basis computation · Shape position, F7 and F31 | accuracy (%): 72.3 -> 54.1; 46.8 -> 6.1 | Hurt |
| Replace discrete coefficient tokens with hybrid continuous coefficient embedding | Transformer Gröbner basis computation · Cauchy module, Q and F31 | accuracy (%): 99.7 -> 98.3; 93.8 -> 15.1 | Hurt |
| Use hybrid coefficient embedding instead of discrete tokens | Transformer Gröbner basis computation · Shape position, R | accuracy (%) | No clear effect |
| Generate the dataset backward from sampled Gröbner bases rather than forward-computing them | Dataset generation for Q, n=3, 4, 5 · Q dataset, 1,000 samples | runtime (seconds): 8.29 -> 5.46; 21.0 -> 7.05; 164.3 -> 7.91 | Helped |
| Use two hidden layers rather than one in coefficient embedding (ablation) | Hybrid input embedding · Shape position, Q and F7, n=2 | accuracy (%): 66.8 -> 67.2; 54.1 -> 54.3 | Helped |
| Use two hidden layers rather than one in coefficient embedding (ablation) | Hybrid input embedding · Shape position, F31 and R, n=2 | accuracy (%): 6.1 -> 5.6; 57.2 -> 56.2 | Hurt |
Surprising findings
- Learning is more successful over infinite fields (Q, R) than over finite fields F_p, despite the larger coefficient space for Q.
- The hybrid continuous embedding performs worse than discrete tokens for Q and F_p (e.g., 0.0% accuracy on Q with n=5), though it avoids the vocabulary blow-up.
Limitations
- Restricted to 0-dimensional radical ideals in shape position (and Cauchy modules); general Gröbner computation not addressed.
- Regression-based hybrid embedding accumulates coefficient errors and underperforms classification-based discrete tokens.
- Learned model has no worst-case guarantee; experiments limited to small n (2-5) and sparse, bounded-coefficient polynomials.
Experimental setup
Datasets: synthetic 0-dimensional shape-position Gröbner basis datasets over Q, F7, F31, R (n=2..5) Cauchy module datasets
Benchmarks: synthetic test sets D_n^-(k) for n=2..5 over Q, F7, F31, R Cauchy module test sets for n=2,3
Metrics: accuracy (exact match) support accuracy runtime in seconds success rate of forward generation
Baselines: SageMath std (Buchberger) SageMath slimgb SageMath stdfglm
Builds on: Lample and Charton symbolic mathematics with Transformers FGLM algorithm Bruhat decomposition AdamW
Closest papers by meaning
- Computational Algebra with Attention: Transformer Oracles for Border Basis Algorithms (NeurIPS 2025 · similarity 0.88)
- Learning Polynomial Problems with $SL(2, \mathbb{R})$-Equivariance (ICLR 2024 · similarity 0.85)
- Machine Learning meets Algebraic Combinatorics: A Suite of Datasets Capturing Research-level Conjecturing Ability in Pure Mathematics (ICML 2025 · similarity 0.84)
- Composing Global Solutions to Reasoning Tasks via Algebraic Objects in Neural Nets (NeurIPS 2025 · similarity 0.82)
- Position: Algebra Unveils Deep Learning - An Invitation to Neuroalgebraic Geometry (ICML 2025 · similarity 0.82)
- Automated Proof of Polynomial Inequalities via Reinforcement Learning (CVPR 2025 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.