# Computational Algebra with Attention: Transformer Oracles for Border Basis Algorithms

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 71 references that are in the map.
- First posted on arXiv 29 May 2025.

## Builds on (most cited first, 22 of 22)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Deep Learning for Symbolic Mathematics](https://mlsanity.com/paper/1912.01412/) (2019)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [A Survey of Imitation Learning: Algorithms, Recent Developments, and Challenges](https://mlsanity.com/paper/2309.02473/) (2023)
- [Deeply AggreVaTeD: Differentiable Imitation Learning for Sequential Prediction](https://mlsanity.com/paper/1703.01030/) (2017)
- [Failures of Gradient-Based Deep Learning](https://mlsanity.com/paper/1703.07950/) (2017)
- [Why are Sensitive Functions Hard for Transformers?](https://mlsanity.com/paper/2402.09963/) (2024)
- [Is Behavior Cloning All You Need? Understanding Horizon in Imitation Learning](https://mlsanity.com/paper/2407.15007/) (2024)
- [Linear algebra with transformers](https://mlsanity.com/paper/2112.01898/) (2021)
- [Transformers Provably Solve Parity Efficiently with Chain of Thought](https://mlsanity.com/paper/2410.08633/) (2024)
- [SALSA: Attacking Lattice Cryptography with Transformers](https://mlsanity.com/paper/2207.04785/) (2022)
- [FoNE: Precise Single-Token Number Embeddings via Fourier Features](https://mlsanity.com/paper/2502.09741/) (2025)
- [Learning selection strategies in Buchberger's algorithm](https://mlsanity.com/paper/2005.01917/) (2020)
- [Gradient Boosts the Approximate Vanishing Ideal](https://mlsanity.com/paper/1911.04174/) (2019)
- [Spurious Vanishing Problem in Approximate Vanishing Ideal](https://mlsanity.com/paper/1901.08798/) (2019)
- [Learning to Compute Gr"obner Bases](https://mlsanity.com/paper/2311.12904/) (2023)
- [Using Machine Learning to Improve Cylindrical Algebraic Decomposition](https://mlsanity.com/paper/1804.10520/) (2018)
- [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)
- [Approximating Latent Manifolds in Neural Networks via Vanishing Ideals](https://mlsanity.com/paper/2502.15051/) (2025)

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

- [The Agentic Researcher: A Practical Guide to AI-Assisted Research in Mathematics and Machine Learning](https://mlsanity.com/paper/2603.15914/) (2026)
- [Neural Sum-of-Squares: Certifying the Nonnegativity of Polynomials with Transformers](https://mlsanity.com/paper/2510.13444/) (2025)
- [Discovering Learning-Friendly Generation Orders for Sequential Computation](https://mlsanity.com/paper/2506.23875/) (2025)
- [HATSolver: Learning Groebner Bases with Hierarchical Attention Transformers](https://mlsanity.com/paper/2512.14722/) (2025)
- [CALT: A Library for Computer Algebra with Transformer](https://mlsanity.com/paper/2506.08600/) (2025)
- [Learning Moderately Input-Sensitive Functions: A Case Study in QR Code Decoding](https://mlsanity.com/paper/2506.20305/) (2025)
- [Learning Large-Scale Modular Addition with an Auxiliary Modulus](https://mlsanity.com/paper/2605.07648/) (2026)

## Abstract (arXiv)

Solving systems of polynomial equations, particularly those with finitely many solutions, is a crucial challenge across many scientific fields. Traditional methods like Gr"obner and Border bases are fundamental but suffer from high computational costs, which have motivated recent Deep Learning approaches to improve efficiency, albeit at the expense of output correctness. In this work, we introduce the Oracle Border Basis Algorithm, the first Deep Learning approach that accelerates Border basis computation while maintaining output guarantees. To this end, we design and train a Transformer-based oracle that identifies and eliminates computationally expensive reduction steps, which we find to dominate the algorithm's runtime. By selectively invoking this oracle during critical phases of computation, we achieve substantial speedup factors of up to 3.5x compared to the base algorithm, without compromising the correctness of results. To generate the training data, we develop a sampling method and provide the first sampling theorem for border bases. We construct a tokenization and embedding scheme tailored to monomial-centered algebraic computations, resulting in a compact and expressive input representation, which reduces the number of tokens to encode an n-variate polynomial by a factor of O(n). Our learning approach is data efficient, stable, and a practical enhancement to traditional computer algebra algorithms and symbolic computation.