# Learning to Compute Gr"obner Bases

arXiv: https://arxiv.org/abs/2311.12904 · HTML: https://mlsanity.com/paper/2311.12904/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 97 references that are in the map.
- First posted on arXiv 21 Nov 2023.

## Builds on (most cited first, 30 of 32)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [Reformer: The Efficient Transformer](https://mlsanity.com/paper/2001.04451/) (2020)
- [Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets](https://mlsanity.com/paper/2201.02177/) (2022)
- [Retentive Network: A Successor to Transformer for Large Language Models](https://mlsanity.com/paper/2307.08621/) (2023)
- [Faith and Fate: Limits of Transformers on Compositionality](https://mlsanity.com/paper/2305.18654/) (2023)
- [Analysing Mathematical Reasoning Abilities of Neural Models](https://mlsanity.com/paper/1904.01557/) (2019)
- [Deep Learning for Symbolic Mathematics](https://mlsanity.com/paper/1912.01412/) (2019)
- [LongNet: Scaling Transformers to 1,000,000,000 Tokens](https://mlsanity.com/paper/2307.02486/) (2023)
- [End-to-end symbolic regression with transformers](https://mlsanity.com/paper/2204.10532/) (2022)
- [Neural Symbolic Regression that Scales](https://mlsanity.com/paper/2106.06427/) (2021)
- [Grokking modular arithmetic](https://mlsanity.com/paper/2301.02679/) (2023)
- [Linear algebra with transformers](https://mlsanity.com/paper/2112.01898/) (2021)
- [Learning to Prove Theorems by Learning to Generate Theorems](https://mlsanity.com/paper/2002.07019/) (2020)
- [Deep Generative Symbolic Regression with Monte-Carlo-Tree-Search](https://mlsanity.com/paper/2302.11223/) (2023)
- [Learning the greatest common divisor: explaining transformer predictions](https://mlsanity.com/paper/2308.15594/) (2023)
- [Primal-Attention: Self-attention through Asymmetric Kernel SVD in Primal Representation](https://mlsanity.com/paper/2305.19798/) (2023)
- [SALSA: Attacking Lattice Cryptography with Transformers](https://mlsanity.com/paper/2207.04785/) (2022)
- [Learning selection strategies in Buchberger's algorithm](https://mlsanity.com/paper/2005.01917/) (2020)
- [What is my math transformer doing? -- Three results on interpretability and generalization](https://mlsanity.com/paper/2211.00170/) (2022)
- [Analyzing the Nuances of Transformers' Polynomial Simplification Abilities](https://mlsanity.com/paper/2104.14095/) (2021)
- [Gradient Boosts the Approximate Vanishing Ideal](https://mlsanity.com/paper/1911.04174/) (2019)
- [SALSA VERDE: a machine learning attack on Learning With Errors with sparse small secrets](https://mlsanity.com/paper/2306.11641/) (2023)
- [Spurious Vanishing Problem in Approximate Vanishing Ideal](https://mlsanity.com/paper/1901.08798/) (2019)
- [Transformers discover an elementary calculation system exploiting local attention and grid-like problem representation](https://mlsanity.com/paper/2207.02536/) (2022)
- [Analytic Manifold Learning: Unifying and Evaluating Representations for Continuous Control](https://mlsanity.com/paper/2006.08718/) (2020)
- [Approximate Vanishing Ideal Computations at Scale](https://mlsanity.com/paper/2207.01236/) (2022)
- [Dual-to-kernel learning with ideals](https://mlsanity.com/paper/1402.0099/) (2014)
- [Approximate Vanishing Ideal via Data Knotting](https://mlsanity.com/paper/1801.09367/) (2018)
- [Border basis computation with gradient-weighted normalization](https://mlsanity.com/paper/2101.00401/) (2021)

## Built on by (most cited first, 7 of 7)

- [Computational Algebra with Attention: Transformer Oracles for Border Basis Algorithms](https://mlsanity.com/paper/2505.23696/) (2025)
- [Making Hard Problems Easier with Custom Data Distributions and Loss Regularization: A Case Study in Modular Arithmetic](https://mlsanity.com/paper/2410.03569/) (2024)
- [Discovering Learning-Friendly Generation Orders for Sequential Computation](https://mlsanity.com/paper/2506.23875/) (2025)
- [Tree-Based Deep Learning for Ranking Symbolic Integration Algorithms](https://mlsanity.com/paper/2508.06383/) (2025)
- [Algebraic Approach to Ridge-Regularized Mean Squared Error Minimization in Minimal ReLU Neural Network](https://mlsanity.com/paper/2508.17783/) (2025)
- [Learning Fast Monomial Orders for Gr"obner Basis Computations](https://mlsanity.com/paper/2602.02972/) (2026)
- [Learning Large-Scale Modular Addition with an Auxiliary Modulus](https://mlsanity.com/paper/2605.07648/) (2026)

## Abstract (arXiv)

Solving a polynomial system, or computing an associated Gr"obner basis, has been a fundamental task in computational algebra. However, it is also known for its notorious doubly exponential time complexity in the number of variables in the worst case. This paper is the first to address the learning of Gr"obner basis computation with Transformers. The training requires many pairs of a polynomial system and the associated Gr"obner basis, raising two novel algebraic problems: random generation of Gr"obner bases and transforming them into non-Gr"obner ones, termed as backward Gr"obner problem. We resolve these problems with 0-dimensional radical ideals, the ideals appearing in various applications. Further, we propose a hybrid input embedding to handle coefficient tokens with continuity bias and avoid the growth of the vocabulary set. The experiments show that our dataset generation method is a few orders of magnitude faster than a naive approach, overcoming a crucial challenge in learning to compute Gr"obner bases, and Gr"obner computation is learnable in a particular class.