Research map / Architectures and efficiency / Attention and transformers
Computational Algebra with Attention: Transformer Oracles for Border Basis Algorithms
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.
Proposes the Oracle Border Basis Algorithm, which uses a Transformer oracle to skip unnecessary reduction candidates in border basis computation while keeping output correctness, achieving up to 3.5x speedup.
Problem
Border basis computation for zero-dimensional polynomial systems spends most runtime reducing candidate polynomials that fail to extend the basis; prior deep learning approaches for Gröbner bases lack output guarantees.
Approach
A Transformer oracle predicts which variable-times-generator expansions will succeed, invoked only in the final stage with a cap of k calls and fallback to standard expansion, so correctness is preserved. Also introduces border basis sampling (via vanishing ideals), an ideal-invariant generator transform, and monomial-level token embedding.
Key results
- OBBA+FGE reduces runtime versus IBBA by up to about 3x for five-variable systems over F_31 (e.g., 7.60s to 2.58s for OBBA alone, 0.60s with FGE).
- Oracle predictions for expansion directions reach F1 scores around 85-95% across settings, with near-perfect (98.8-99.7%) no-expansion accuracy.
- Out-of-distribution generalization to total degree 3-8 systems yields speedups up to 1.8x; the paper claims up to 3.5x in unnecessary expansions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the Transformer oracle instead of full expansion | IBBA / border basis algorithm · F31, n=5, total degree ≤4 | runtime: up to a 3$\times$ speedup | Helped |
| Add fast Gaussian elimination | IBBA · F31, n=5, total degree ≤4 | runtime: approximately 10× wall-clock speedup in data generation | Helped |
| Add fast Gaussian elimination alongside the oracle | OBBA · F31, n=5, total degree ≤4 | runtime: up to two orders of magnitude improvement over IBB | Helped |
| Train on degree-2 systems and apply the oracle to higher-degree systems | OBBA · Four-variable systems, total degree 3, 4, 6, and 8 | speedup: up to 1.8-times | Helped |
| Increase the number of leading terms retained from 1 to 5 (ablation) | Transformer oracle · Expansion prediction across n=3, 4, 5 | F1 score | Helped |
| Truncate input polynomials to their leading terms (ablation) | Transformer oracle · Expansion prediction | predictive performance | No clear effect |
| Use monomial embedding instead of standard tokenization (ablation) | Transformer oracle · Cumulative polynomial product tasks | success rate | Helped |
| Use the oracle-guided expansion in place of the standard BBA expansion | Border basis algorithm · In-distribution systems, n=3 | runtime | No clear effect |
Surprising findings
- The oracle trained only on total-degree-2 systems with n=4 still generalizes to harder degree 3-8 systems.
Limitations
- Restricted to zero-dimensional ideals, since border bases are not defined for positive-dimensional ideals.
- Experiments only over finite fields with up to five variables; characteristic-0 not explored.
- Oracle invoked at most k times with fallback, so gains depend on heuristic invocation ratio.
Experimental setup
Datasets: synthetic border basis samples over F_p polynomial rings generated via border basis sampling and ideal-invariant generat
Benchmarks: randomly sampled zero-dimensional systems over F_31 with n=3,4,5 variables out-of-distribution higher-degree systems over F_7, F_31, F_127 with n=4
Metrics: wall-clock runtime (s) precision recall F1 score no-expansion accuracy speedup factor
Baselines: BBA IBBA IBBA+FGE
Builds on: Border basis algorithm (BBA) Improved Border Basis Algorithm (IBBA) Buchberger-Möller algorithm Transformer encoder-decoder
Closest papers by meaning
- Learning to compute Gröbner bases (NeurIPS 2024 · similarity 0.88)
- Machine Learning meets Algebraic Combinatorics: A Suite of Datasets Capturing Research-level Conjecturing Ability in Pure Mathematics (ICML 2025 · similarity 0.84)
- Learning Polynomial Problems with $SL(2, \mathbb{R})$-Equivariance (ICLR 2024 · similarity 0.83)
- Position: Algebra Unveils Deep Learning - An Invitation to Neuroalgebraic Geometry (ICML 2025 · similarity 0.83)
- Composing Global Solutions to Reasoning Tasks via Algebraic Objects in Neural Nets (NeurIPS 2025 · similarity 0.83)
- Transport of Algebraic Structure to Latent Embeddings (ICML 2024 · similarity 0.83)
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.