mlsanityData to 14 Oct 2026

Learning to Compute Gr"obner Bases

arXiv 2311.12904 ↗First posted 21 Nov 2023math.AC cs.LGcited by 7

Not on the map. Why?

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.

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

32 of 97 references.

References · 32

  1. 2017Attention Is All You Needcited by 60,361
  2. 2020Longformer: The Long-Document Transformercited by 3,413
  3. 2020Reformer: The Efficient Transformercited by 1,668
  4. 2022Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasetscited by 629
  5. 2023Retentive Network: A Successor to Transformer for Large Language Modelscited by 613
  6. 2023Faith and Fate: Limits of Transformers on Compositionalitycited by 503
  7. 2019Analysing Mathematical Reasoning Abilities of Neural Modelscited by 335
  8. 2019Deep Learning for Symbolic Mathematicscited by 270
  9. 2023LongNet: Scaling Transformers to 1,000,000,000 Tokenscited by 204
  10. 2022End-to-end symbolic regression with transformerscited by 203
  11. 2021Neural Symbolic Regression that Scalescited by 192
  12. 2023Grokking modular arithmeticcited by 83
20 more
  1. 2021Linear algebra with transformerscited by 63
  2. 2020Learning to Prove Theorems by Learning to Generate Theoremscited by 43
  3. 2023Deep Generative Symbolic Regression with Monte-Carlo-Tree-Searchcited by 41
  4. 2023Learning the greatest common divisor: explaining transformer predictionscited by 33
  5. 2023Primal-Attention: Self-attention through Asymmetric Kernel SVD in Primal Representationcited by 29
  6. 2022SALSA: Attacking Lattice Cryptography with Transformerscited by 28
  7. 2020Learning selection strategies in Buchberger's algorithmcited by 20
  8. 2022What is my math transformer doing? -- Three results on interpretability and generalizationcited by 19
  9. 2021Analyzing the Nuances of Transformers' Polynomial Simplification Abilitiescited by 9
  10. 2019Gradient Boosts the Approximate Vanishing Idealcited by 8
  11. 2023SALSA VERDE: a machine learning attack on Learning With Errors with sparse small secretscited by 8
  12. 2019Spurious Vanishing Problem in Approximate Vanishing Idealcited by 7
  13. 2022Transformers discover an elementary calculation system exploiting local attention and grid-like problem representationcited by 7
  14. 2020Analytic Manifold Learning: Unifying and Evaluating Representations for Continuous Controlcited by 6
  15. 2022Approximate Vanishing Ideal Computations at Scalecited by 6
  16. 2014Dual-to-kernel learning with idealscited by 5
  17. 2018Approximate Vanishing Ideal via Data Knottingcited by 5
  18. 2021Border basis computation with gradient-weighted normalizationcited by 5
  19. 2021Neural Sequence-to-grid Module for Learning Symbolic Rulescited by 5
  20. 2023Learning Label Encodings for Deep Regressioncited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 4; 2026: 2.

7 papers.

  1. 2025Computational Algebra with Attention: Transformer Oracles for Border Basis Algorithmscited by 7
  2. 2024Making Hard Problems Easier with Custom Data Distributions and Loss Regularization: A Case Study in Modular Arithmeticcited by 4
  3. 2025Discovering Learning-Friendly Generation Orders for Sequential Computationcited by 1
  4. 2025Tree-Based Deep Learning for Ranking Symbolic Integration Algorithmscited by 1
  5. 2025Algebraic Approach to Ridge-Regularized Mean Squared Error Minimization in Minimal ReLU Neural Networkcited by 0
  6. 2026Learning Fast Monomial Orders for Gr"obner Basis Computationscited by 0
  7. 2026Learning Large-Scale Modular Addition with an Auxiliary Moduluscited by 0