Computational Algebra with Attention: Transformer Oracles for Border Basis Algorithms

Hiroshi Kera; Max Zimmer; Nico Pelleriti; Sebastian Pokutta; Yuki Ishihara

REVIEW 4 major objections 5 minor 1 cited by

Computational Algebra with Attention: Transformer Oracles for Border Basis Algorithms

T0 review · 4 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A Transformer trained on border basis runs can predict which reduction steps are unnecessary, letting the Oracle Border Basis Algorithm skip them and achieve up to 3.5x fewer zero reductions and about 3x wall-clock speedup while still…

desk verdict A genuine but modest advance in learning-guided symbolic computation that needs a revision to close the early-exit proof gap and align its claims with its tables. read the letter →

arxiv 2505.23696 v1 pith:TTCFSBWB submitted 2025-05-29 cs.LG cs.SC

Hiroshi Kera , Nico Pelleriti , Yuki Ishihara , Max Zimmer , Sebastian Pokutta This is my paper

classification cs.LGcs.SC MSC 68W3013P1068T07

keywords borderbasistransformerpolynomialsystemsolvingalgorithmswithpredictionsmonomialembeddingzero-dimensionalidealssymboliccomputationdeeplearning

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper aims to show that a Transformer trained on labeled border basis runs can act as an oracle inside the algorithm, skipping expensive reduction steps while preserving an exact output. The payoff is that zero-dimensional polynomial systems could be solved faster in practice without the correctness loss that earlier deep-learning polynomial solvers accepted. The authors introduce the Oracle Border Basis Algorithm (OBBA), prove that it terminates and returns a border basis, and report up to 3.5x fewer zero reductions and about 3x wall-clock speedup over the improved border basis algorithm on five-variable systems. The guarantee is preserved by a strict cap: the oracle replaces the full expansion at most k times, after which the standard expansion resumes.

What carries the argument

The mechanism is the L-stable-span step of the border basis algorithm, where each iteration multiplies the current basis by variables and reduces the candidates; most candidates reduce to zero. OBBA replaces the candidate set C_i = V_i^+ with a predicted subset C_i = Oracle(L_i,V_i). The Transformer uses a monomial embedding that encodes each monomial as a single token, cutting token count by a factor of n+1. The k-call cap and fallback to full expansion carry the correctness proof. Training data comes from a new border basis sampling construction (order ideals plus vanishing ideals) and an ideal-invariant generator transform that converts basis polynomials into diverse generating sets with the same ideal.

What would settle it

Run OBBA on a family of zero-dimensional systems where reduction cost is spread evenly across all expansions rather than concentrated in the final stage; if wall-clock time does not improve over the improved border basis baseline, or if the relative border gap |V|/|L| is not monotonically related to the remaining number of expansions, the runtime-profile assumption that the method depends on is falsified.

Watch

Extended reading notes

Core claim

The central claim is that the wasteful part of border basis computation—reducing candidate polynomials that do not extend the basis—can be predicted and avoided. A Transformer oracle trained on the final five expansions of completed runs selects which variable-times-basis-element products to reduce; the algorithm spends its oracle budget only when the relative border gap |V|/|L| indicates the final stage. Because the oracle is capped at k calls and a full expansion follows, Theorem 3.1 guarantees the output is a border basis regardless of oracle accuracy. Empirically, the oracle eliminates up to 3.5x as many zero reductions and cuts wall-clock time by about 3x versus the improved border basis algorithm on n=5 systems over F31, and generalizes to degree-8 systems with up to 1.8x speedup.

Load-bearing premise

The load-bearing premise is that the final stage of the border basis algorithm—after the last enlargement of the computational universe—consumes 70-95% of the runtime and that the relative border gap |V|/|L| reliably marks the start of that stage; if this profile does not hold, the oracle budget is spent where it produces little or no speedup.

Editorial extensions

If this is right

If the Transformer oracle generalizes as reported, border basis computation for zero-dimensional systems with up to five variables can be accelerated without the correctness risk that accompanied earlier deep-learning solvers.
The k-call cap provides a general template: any learned oracle that proposes steps in an exact algorithm can be layered on without changing the output, as long as it can be overridden.
The monomial embedding could transfer to other monomial-centric symbolic computations, reducing input length and attention cost.
The border basis sampling and ideal-invariant transform enable supervised data generation for other algebraic computations that have a degree-by-degree structure.
The reported out-of-distribution generalization suggests the oracle may handle harder instances than those seen during training, though this is demonstrated only for moderate degree increases.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The speedup numbers are measured against a specific runtime profile; on problems where the final stage is not dominant, the benefit may shrink or invert because the oracle budget is spent before the expensive phase.
The oracle-plus-cap scheme could be attempted for Gröbner base computation, but the lack of an inherent degree-by-degree decomposition is precisely the obstacle noted for the earlier RL approach; a supervised analogue would need a new way to label successful S-polynomials.
Because the correctness guarantee is independent of oracle quality, even a low-accuracy oracle could be used safely; the observed benefit would then degrade gracefully rather than producing wrong answers.
Training on finite fields may not transfer to characteristic zero, since coefficient arithmetic and the density of polynomials differ; testing on rational or floating-point inputs would delimit the method's scope.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Short version: this is a solid, modest algorithms-with-predictions paper that deserves a real referee, but it needs a revision that closes a proof gap, fixes an overstated abstract, and tightens the empirical reporting.

What's genuinely new: the OBBA framework—a Transformer oracle that proposes candidate BBA expansions, capped at k calls per run, after which the algorithm reverts to the exact full expansion. The correctness guarantee is real and simple in the k-call case, and it's the first work in this line to preserve exactness rather than just steering with no guarantees. The monomial embedding (Section 4.2) is a clean, reusable idea: one token per monomial instead of n+1, with O(n) token reduction and real gains in memory and predictive accuracy. The data-generation pipeline is also useful: order ideal sampling plus the ideal-invariant generator transform (Theorem 4.5) gives a way to create diverse zero-dimensional systems, and the FGE kernel is a nice orthogonal speedup.

Now the soft spots, in order of size.

1. The early-exit correctness gap. The proof of Theorem A.1 covers only the path where all k oracle calls are used and then a final full expansion is made. But the algorithm's loop can exit earlier, as soon as Vi+1=Vi and BorderBasisCheck passes. All 100-instance runs in Section 5.3.1 terminated without ever reverting to the fallback, so the tested path is the one the proof doesn't cover. This is fixable: BorderBasisCheck is the Buchberger criterion, which is sufficient for V to be a border basis, so the early exit is likely safe. But the paper never states that argument, and a referee should insist on it. The stress-tester's concern here is a proof gap, not a demonstrated counterexample.

2. The abstract's 'up to 3.5x speedup' is misleading. Table 2 reports a 3x wall-clock speedup over IBBA; the 3.5x figure in Table 5 is a reduction count, not runtime. They should report the former prominently and the latter as a secondary metric.

3. Theorem 4.5's r=n case has a proof issue: it assumes pure-power leading terms for the border basis, which general term-order-free border bases need not have. The r>n case is what's used, so the gap shouldn't hold up the paper, but it should be stated with the needed hypothesis or removed.

4. The baseline is the authors' own IBBA implementation, with no comparison to optimized Gröbner solvers. That's acceptable for isolating the oracle's effect, but it limits the headline claim's real-world reach. And the paired 100-run results lack significance tests; for n=3 and 4 the speedups are within noise given the large standard deviations.

Who this is for: people working on ML-steered symbolic computation, algorithms with predictions, and border basis methods. It's a good data point and a reusable representation idea. Give it a serious referee, with the expectation of moderate revision.

Referee Report

4 major / 5 minor

Summary. The paper proposes the Oracle Border Basis Algorithm (OBBA), which integrates a Transformer oracle into the border basis algorithm to select which polynomial expansions to reduce, with a cap of k oracle-guided iterations after which the algorithm reverts to full expansions. The authors introduce a sampling framework for border bases based on vanishing ideals, an ideal-invariant generator transform, and a monomial embedding that reduces token counts. Experiments over F_7, F_31, and F_127 with n = 3, 4, 5 report in-distribution wall-clock speedups of about 3x over IBBA (Table 2) and out-of-distribution speedups up to 1.8x (Figure 3), while Theorem 3.1 claims termination and correctness of the output.

Significance. The proposed combination is interesting and, if the correctness guarantee is fully established, would be a useful contribution: unlike prior learning-based Groebner basis methods, OBBA preserves exactness by construction through the k-call fallback. Strengths include the non-circular data generation (labels come from exact BBA runs), the monomial embedding with measured token reductions, the orthogonal FGE kernel, and the release of code. The out-of-distribution generalization from degree 2 to degree 8, despite increased fallbacks, is a noteworthy empirical result. However, the correctness proof has a gap for early termination, and the headline speedup number is not consistently supported by the wall-clock tables.

major comments (4)

[Appendix A.1, Theorem A.1; Algorithm 2] The proof of Theorem A.1 only covers runs that exhaust the k oracle calls: 'After the oracle has been invoked k times, we make one more full expansion.' It does not address the early-exit path in Algorithm 2, where the while-loop breaks as soon as V_{i+1} = V_i and BorderBasisCheck passes (lines 6, 10, 18) before k calls are used. Because the oracle can return an empty candidate set (Table 4 reports No Expansion accuracy between 96.3% and 99.7%), a false 'no expansion' prediction can terminate the loop before the safety-net full expansion, and the output then depends on an incomplete V. No experiment compares OBBA outputs against IBBA outputs to rule out wrong results on that path. The correctness guarantee is therefore not established as stated; please either modify the algorithm to force a final full expansion or a border-basis check regardless of the exit path, or extend the proof to cover early exit.
[Section 3, Algorithms 1 and 2; Section 5.3.1] The pseudocode does not match the described and implemented method. Algorithm 1 (and Algorithm 2) unconditionally executes both C_i <- V_i^+ and C_i <- Oracle(L_i, V_i), with no k-call counter and no relative-border-gap condition; Section 3.2 and Section 5.3.1 state that the oracle is invoked only after |V|/|L| reaches a threshold and then at most k times. Since Theorem A.1's argument relies on the k-call cap, the theorem applies to an algorithm that is not the one written down. Please align the pseudocode, the proof, and the implementation (including the fallback and the gating heuristic).
[Abstract; Conclusion; Table 2; Table 5] The abstract and conclusion claim wall-clock 'speedup factors of up to 3.5x', but Table 2 reports a maximum wall-clock speedup of about 3x (n = 5, F31: 7.60/2.58 is approximately 2.95). The 3.5x figure in Table 5 is an improvement in the number of zero reductions, not runtime. Please either report the 3.5x as reduction count, or locate a wall-clock setting that achieves 3.5x and cite it.
[Section 3.2; Lemma A.2; Table 9; Figures 10-12] The practical speedup rests on the assumption that the last stage after the final universe enlargement consumes 70-95% of runtime (Table 9) and that the relative border gap |V|/|L| reliably identifies that stage. Lemma A.2 does not establish the heuristic: it assumes |L| - |V| = |O| and then observes that adding an element would contradict the equality; it says nothing about how to detect the final stage from the gap. The paper should state the gap heuristic as an empirical assumption, report sensitivity of the speedup to the invocation threshold (the OOD figures already show threshold dependence), and avoid presenting Lemma A.2 as a theoretical justification for the detection rule.

minor comments (5)

[Section 5.2, Dataset] Please clarify whether the 1M training samples are per (n, p, l) configuration or total across all 27 datasets; the text says 'one million training and one thousand evaluation samples' after collecting 'approximately five million samples' from the final five expansions, and the aggregation is ambiguous.
[Table 2 caption] There is a typo: 'unneccessary' should be 'unnecessary'.
[Appendix B.2 and Appendix E.1] There are typos: 'boder' should be 'border' in Appendix B.2, and 'predesgianated' should be 'predesignated' in Appendix E.1; reference [9] also contains a stray 'V ol'.
[Section 5, experimental setup] The experiments do not specify the monomial order used to determine leading terms in the BBA runs and in the generated data; since the oracle input representation and the training labels depend on it, this should be stated for reproducibility.
[Figure 3 and Figures 8-9] The speedup plots are shown as mean lines without error bars or confidence intervals; given the large standard deviations reported in the runtime tables, adding variance information would make the comparisons more informative.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: the oracle's ground truth comes from exact BBA runs, correctness is anchored to the k-call/full-expansion fallback, and the sampling theorems are proved independently; the main flagged issue is a non-circular proof gap for the early-exit path.

full rationale

The central correctness claim does not reduce to the oracle's predictions. Training labels are produced by running the standard BBA and recording which candidate expansions actually extend the basis (Section 4.1: 'collecting samples only from the final five expansions of each border basis computation'), so ground truth is algorithm-independent of the Transformer. Theorem A.1 anchors correctness to a fallback: 'After the oracle has been invoked k times, we make one more full expansion' followed by reversion to the standard BBA; this is an external correctness anchor, not a self-citation or a fitted quantity. The sampling theorems (Theorem 4.2 and Theorem 4.5) are proved in Appendices B and C from standard commutative algebra and do not presuppose the oracle or the speedup. The self-citations to [32] and [8] are background or are generalized with independent proofs, so they are not load-bearing. The relative-border-gap heuristic (Section 3.2, Lemma A.2, Figures 10-12) is an empirical allocation rule, not a definition of correctness. The in-distribution speedup measurements are held-out evaluations, not a fitted parameter renamed as a prediction. Per the reviewing rule, a non-circular gap is flagged: the proof of Theorem A.1 only covers runs that exhaust all k oracle calls and does not explicitly handle the early-exit path in Algorithm 2 where the loop breaks after BorderBasisCheck passes before k calls; this is an omitted proof for an edge case, not a circular reduction, and therefore does not raise the circularity score beyond the minor-self-citation level of 2.

Assumptions & free parameters 4 free parameters · 5 assumptions · 0 invented entities

The central empirical claims rest on four design or free parameters (oracle threshold scan, k = 5 cap, truncation l, sampling distribution) and on five axioms, of which the heavy ones are: zero-dimensionality of the input ideals, the r > n ideal-preservation theorem that underpins the training data pipeline (Theorem 4.5 case 2), and, for the speedup rather than correctness, the empirical claim that the final BBA stage dominates runtime and is detectable via the border gap. Lemma A.2's proof of the gap criterion is circular in its current form. No invented entities are introduced: the oracle is a trained model, not a postulated object.

free parameters (4)

relative border gap invocation threshold |V|/|L| = scanned over {0.70, 0.75, 0.80, 0.85, 0.90, 0.95, 0.975}
Heuristic in Section 3.2 deciding when to start spending the oracle calls; the paper reports results across all thresholds rather than a single tuned value, and Figure 9 shows the speedup is sensitive to this choice in OOD settings.
oracle call cap k = 5
Chosen to match the empirical finding (Table 9) that the final five expansions account for roughly 70-95% of final-stage runtime; design parameter, not fitted to the speedup.
leading-term truncation l = 1, 3, or 5
Input polynomials in V are truncated to their l leading terms (Section 4.2); Table 1 shows minor accuracy impact, so l is a computational trade-off parameter.
training distribution parameters = G of degree <= 2, A polynomials with <= 10 terms, r in {n+1, ..., 2n}
Sampling choices in Section 5.2 that define the training and in-distribution test distribution; the headline speedups are in-distribution.

assumptions (5)

domain assumption Zero-dimensionality of the input ideals
Border bases are only defined for zero-dimensional ideals; the Limitations section states this explicitly, so all claims are scoped to this class.
standard math Standard commutative algebra facts (primary decomposition, codimension, dimension, Groebner basis lemmas)
Used in Appendix C (proof of Theorem 4.5) via citations [6], [7], [19], [57]; accepted background.
domain assumption For r > n a generic polynomial matrix A preserves the ideal: <AG> = <G> (Theorem 4.5 case 2)
Load-bearing for the data generation pipeline (Section 4.1.2); the proof in Appendix C is intricate and has notational errors, and for finite fields Corollary C.11 bounds the failure probability by d_max/p, which is vacuous for small p relative to d_max (e.g., F7).
ad hoc to paper Fixed term order makes pure variable powers the leading terms of a general border basis (proof of Theorem 4.5, r = n case)
Appendix C.2 asserts that for each variable x_i there is a generator with LC(g) = x_i^{d_i} under an arbitrary fixed term order; this does not hold for general term-order-free border bases (e.g., O = {1, x, y^5}), and the case is unused in experiments (always r > n).
ad hoc to paper The final-stage characterization |L| - |V| = |O| (Lemma A.2)
Lemma A.2's proof assumes the conclusion; the relation between border gap and remaining border distance is justified empirically in Figures 10-12, not by the proof as written.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Computational Algebra with Attention: Transformer Oracles for Border Basis Algorithms." pith.science (2026). https://pith.science/paper/TTCFSBWB

@misc{pith2026250523696,
  author       = {Pith},
  title        = {Pith review of: Computational Algebra with Attention: Transformer Oracles for Border Basis Algorithms},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TTCFSBWB}},
  note         = {Machine review of arXiv:2505.23696}
}

abstract

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.

Figures

Figures reproduced from arXiv: 2505.23696 by the authors.

**Figure 2.** (F31, k = 5). The term truncation and monomial embedding significantly reduce input size. See also [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗

**Figure 3.** Speed-up of OBBA over IBBA on OOD systems with [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗

Figures from the paper (9 more)

**Figure 4.** Figure 4: The gallery of randomly sampled order ideals for [PITH_FULL_IMAGE:figures/full_fig_p028_4.png]

**Figure 5.** Figure 5: The empirical success rate of the backward transform from [PITH_FULL_IMAGE:figures/full_fig_p029_5.png]

**Figure 6.** Figure 6: The average number of tokens with infix and the proposed embeddings. [PITH_FULL_IMAGE:figures/full_fig_p029_6.png]

**Figure 7.** Figure 7: Reduction of the maximum number of tokens of input sequences with [PITH_FULL_IMAGE:figures/full_fig_p030_7.png]

**Figure 8.** Figure 8: OOD Experiment for n = 3 measured by the number of fallbacks plotted against the relative border gap. As we increase the degree of the polynomials (and thereby moving away from the training distribution), the number of fallbacks increases. Invoking the oracle at a lowe…

**Figure 9.** Figure 9: OOD Experiment for n = 3 measured by the speedup of the proposed method over the baseline. Even a moderate number of fallbacks still allows for a significant speedup. However, for the harder settings, we observe that the speedup is highest for a relative border gap of …

**Figure 10.** Figure 10: Border gap vs border distance for n = 3 over F31. 31 [PITH_FULL_IMAGE:figures/full_fig_p031_10.png]

**Figure 11.** Figure 11: Border gap vs border distance for n = 4 over F31. 0 1 2 3 4 5 Border Distance ( , ) 0.2 0.4 0.6 0.8 1.0 B o r d e r G a p | | | | Border Gap vs Border Distance Quartiles Whisker/Cap Median Mean [PITH_FULL_IMAGE:figures/full_fig_p032_11.png]

**Figure 12.** Figure 12: Border gap vs border distance for n = 5 over F31. 32 [PITH_FULL_IMAGE:figures/full_fig_p032_12.png]

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Learning Moderately Input-Sensitive Functions: A Case Study in QR Code Decoding
cs.LG 2025-06 conditional novelty 5.0 of 10

A Transformer can learn to decode QR codes from bit strings, outperforming standard error correction on corrupted codes by exploiting language structure, but only under a simplified fixed-mask setup.

Reference graph

Works this paper leans on

81 extracted references · 78 canonical work pages · cited by 1 Pith paper

[1]

Abbott, C

J. Abbott, C. Fassino, and M.-L. Torrente. Stable border bases for ideals of points. Journal of Symbolic Computation, 43(12):883–894, 2008

2008
[2]

Abbott, M

J. Abbott, M. Kreuzer, and L. Robbiano. Computing zero-dimensional schemes. Journal of Symbolic Computation, 39(1):31–49, 2005

work page 2005
[3]

Abril Bucero and B

M. Abril Bucero and B. Mourrain. Border basis relaxation for polynomial optimization. Journal of Symbolic Computation, 74:378–399, 2016

work page 2016
[4]

Alfarano, F

A. Alfarano, F. Charton, and A. Hayat. Global Lyapunov functions: a long-standing open problem in mathematics, with symbolic transformers, 2024

work page 2024
[5]

A. M. Alvarez, Q. Louveaux, and L. Wehenkel. A machine learning-based approximation of strong branching. INFORMS Journal on Computing, 29(1):185–195, 2017

work page 2017
[6]

M. F. Atiyah and I. G. MacDonald. Introduction To Commutative Algebra. Addison-Wesley series in mathematics. Avalon Publishing, 1994

work page 1994
[7]

Becker, V

T. Becker, V . Weispfenning, and H. Kredel.Gröbner Bases: A Computational Approach to Commutative Algebra. Graduate texts in mathematics. Springer-Verlag, 1993

work page 1993
[8]

Braun and S

G. Braun and S. Pokutta. A polyhedral characterization of Border Bases. SIAM Journal on Discrete Mathematics, 30(1):239–265, 2016

work page 2016

Show all 81 references

[9]

Buchberger

B. Buchberger. Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal (An Algorithm for Finding the Basis Elements in the Residue Class Ring Modulo a Zero Dimensional Polynomial Ideal). PhD thesis, Mathematical Institute...

1965
[10]

D. Cox, J. Little, and D. O’shea. Ideals, varieties, and algorithms, volume 3. Springer, 1992

1992
[11]

D. A. Cox, J. Little, and D. O’Shea. Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra . Undergraduate Texts in Mathematics. Springer International Publishing, 2015

2015
[12]

R. S. Datta. Using computer algebra to find nash equilibria. In Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation, ISSAC ’03, page 74–79, New York, NY , USA, 2003. Association for Computing Machinery

2003
[13]

T. W. Dubé. The structure of polynomial ideals and Gröbner bases.SIAM Journal on Computing, 19(4):750–773, 1990

1990
[14]

C. Fassino. Almost vanishing polynomials for sets of limited precision points. Journal of Symbolic Computation, 45(1):19–37, 2010

2010
[15]

J.-C. Faugère. A new efficient algorithm for computing Gröbner bases (F4). Journal of Pure and Applied Algebra, 139(1):61–88, 1999. 10

1999
[16]

J.-C. Faugère. A new efficient algorithm for computing Gröbner bases without reduction to zero (F5). In Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, ISSAC ’02, page 75–83, New York, NY , USA, 2002. Association for Computing Machinery

2002
[17]

D. J. Foster, A. Block, and D. Misra. Is behavior cloning all you need? understanding horizon in imitation learning. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang, editors, Advances in Neural Information Processing Systems, volume 37, pag...

2024
[18]

one sugar cube, please

A. Giovini, T. Mora, G. Niesi, L. Robbiano, and C. Traverso. “one sugar cube, please” or selection strategies in the buchberger algorithm. In Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation, ISSAC ’91, page 49–54, New York, NY , USA, 1991....

1991
[19]

Gruel and G

G.-M. Gruel and G. Pfister. A Singular Introduction to Commutative Algebra, 2nd Edition . Sringer Verlag, 2008

2008
[20]

Heldt, M

D. Heldt, M. Kreuzer, S. Pokutta, and H. Poulisse. Approximate computation of zero- dimensional polynomial ideals. Journal of Symbolic Computation, 44(11):1566–1591, 2009

2009
[21]

Horácek, M

J. Horácek, M. Kreuzer, and A. S. M. Ekossono. Computing boolean border bases. In 2016 18th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC), pages 465–472, 2016

2016
[22]

C. Hou, F. Nie, and D. Tao. Discriminative vanishing component analysis. InProceedings of the Thirtieth AAAI Conference on Artificial Intelligence, pages 1666–1672, Palo Alto, California,
[23]

Huang, M

Z. Huang, M. England, D. J. Wilson, J. Bridge, J. H. Davenport, and L. C. Paulson. Using machine learning to improve cylindrical algebraic decomposition. Mathematics in Computer Science, 13:461–488, 2019

2019
[24]

Ikematsu, R

Y . Ikematsu, R. Perlner, D. Smith-Tone, T. Takagi, and J. Vates. HFERP-a new multivariate encryption scheme. In Post-Quantum Cryptography: 9th International Conference, PQCrypto 2018, Fort Lauderdale, FL, USA, April 9-11, 2018, Proceedings 9, pages 396–416. Springer, 2018

2018
[25]

Kehrein and M

A. Kehrein and M. Kreuzer. Characterizations of border bases. Journal of Pure and Applied Algebra, 196(2):251–270, 2005

2005
[26]

Kehrein and M

A. Kehrein and M. Kreuzer. Computing border bases. Journal of Pure and Applied Algebra, 205(2):279–295, 2006

2006
[27]

H. Kera. Border basis computation with gradient-weighted normalization. In Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation, pages 225–234, New York, 2022. Association for Computing Machinery

2022
[28]

Kera and Y

H. Kera and Y . Hasegawa. Approximate vanishing ideal via data knotting. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, pages 3399–3406, Palo Alto, California, 2018. AAAI Press

2018
[29]

Kera and Y

H. Kera and Y . Hasegawa. Spurious vanishing problem in approximate vanishing ideal.IEEE Access, 7:178961–178976, 2019

2019
[30]

Kera and Y

H. Kera and Y . Hasegawa. Gradient boosts the approximate vanishing ideal. InProceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence, pages 4428–4425, Palo Alto, California, 2020. AAAI Press

2020
[31]

Kera and Y

H. Kera and Y . Hasegawa. Monomial-agnostic computation of vanishing ideals. Journal of Computational Algebra, 11:100022, 2024

2024
[32]

H. Kera, Y . Ishihara, Y . Kambe, T. Vaccon, and K. Yokoyama. Learning to compute Gröbner bases, 2024. 11

2024
[33]

Khalil, P

E. Khalil, P. Le Bodic, L. Song, G. Nemhauser, and B. Dilkina. Learning to branch in mixed integer programming. In Proceedings of the AAAI conference on artificial intelligence, volume 30, 2016

2016
[34]

Kim and T

J. Kim and T. Suzuki. Transformers provably solve parity efficiently with chain of thought. In The Thirteenth International Conference on Learning Representations, 2025

2025
[35]

Kipnis, J

A. Kipnis, J. Patarin, and L. Goubin. Unbalanced oil and vinegar signature schemes. In International Conference on the Theory and Applications of Cryptographic Techniques, pages 206–222. Springer, 1999

1999
[36]

F. J. Király, M. Kreuzer, and L. Theran. Dual-to-kernel learning with ideals. arXiv, abs/1402.0099, 2014

2014 arXiv
[37]

Kreuzer and L

M. Kreuzer and L. Robbiano. Computational Commutative Algebra 2, volume 2 of Algorithms and Computation in Mathematics. Springer, 2005

2005
[38]

Lample and F

G. Lample and F. Charton. Deep learning for symbolic mathematics. InInternational Conference on Learning Representations, 2020

2020
[39]

J. B. Lasserre. Global optimization with polynomials and the problem of moments. SIAM Journal on Optimization, 11(3):796–817, 2001

2001
[40]

Laubenbacher and B

R. Laubenbacher and B. Stigler. A computational algebra approach to the reverse engineering of gene regulatory networks. Journal of Theoretical Biology, 229(4):523–537, 2004

2004
[41]

Laubenbacher and B

R. Laubenbacher and B. Sturmfels. Computer algebra in systems biology. American Mathemat- ical Monthly, 116(10):882–891, 2009

2009
[42]

Lidl and H

R. Lidl and H. Niederreiter. Finite Fields. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2 edition, 1996

1996
[43]

J. Limbeck. Computation of approximate border bases and applications. PhD thesis, Passau, Universität Passau, 2013

2013
[44]

Livni, D

R. Livni, D. Lehavi, S. Schein, H. Nachliely, S. Shalev-Shwartz, and A. Globerson. Vanishing component analysis. In Proceedings of the 30th International Conference on Machine Learning, volume 28(1) of Proceedings of Machine Learning Research, pages 597–605, Atlanta, Georgia, ...

2013
[45]

E. N. Lorenz. Deterministic nonperiodic flow. Journal of Atmospheric Sciences, 20(2):130 – 141, 1963

1963
[46]

Loshchilov and F

I. Loshchilov and F. Hutter. Decoupled weight decay regularization. InInternational Conference on Learning Representations, 2019

2019
[47]

E. W. Mayr and A. R. Meyer. The complexity of the word problems for commutative semigroups and polynomial ideals. Advances in Mathematics, 46(3):305–329, 1982

1982
[48]

Mitzenmacher and S

M. Mitzenmacher and S. Vassilvitskii. Algorithms with predictions, 2020

2020
[49]

H. M. Möller and B. Buchberger. The construction of multivariate polynomials with preassigned zeros. In Computer Algebra. EUROCAM 1982. Lecture Notes in Computer Science , pages 24–31. Springer Berlin Heidelberg, 1982

1982
[50]

Park and G

H. Park and G. Regensburger, editors. Gröbner Bases in Control Theory and Signal Processing. De Gruyter, 2007

2007
[51]

Peifer, M

D. Peifer, M. Stillman, and D. Halpern-Leistner. Learning selection strategies in buchberger’s algorithm. In Proceedings of the 37th International Conference on Machine Learning, ICML’20. JMLR.org, 2020

2020
[52]

Pelleriti, M

N. Pelleriti, M. Zimmer, E. Wirth, and S. Pokutta. Approximating latent manifolds in neural networks via vanishing ideals, 2025. 12

2025
[53]

S. Ross, G. Gordon, and D. Bagnell. A reduction of imitation learning and structured prediction to no-regret online learning. In G. Gordon, D. Dunson, and M. Dudík, editors, Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, volum...

2011
[54]

Shalev-Shwartz, O

S. Shalev-Shwartz, O. Shamir, and S. Shammah. Failures of gradient-based deep learning. In Proceedings of the 34th International Conference on Machine Learning - Volume 70, ICML’17, page 3067–3075. JMLR.org, 2017

2017
[55]

Stewenius

H. Stewenius. Gröbner Basis Methods for Minimal Problems in Computer Vision. PhD thesis, Mathematics (Faculty of Engineering), 2005

2005
[56]

W. Sun, A. Venkatraman, G. J. Gordon, B. Boots, and J. A. Bagnell. Deeply AggreVaTeD: Differentiable imitation learning for sequential prediction. In D. Precup and Y . W. Teh, edi- tors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceed...

2017
[57]

Suzuki and Y

A. Suzuki and Y . Sato. A simple algorithm to compute comprehensive gröbner bases using gröbner bases. In Proceedings of the 2006 International Symposium on Symbolic and Algebraic Computation, ISSAC ’06, page 326–331, New York, NY , USA, 2006. Association for Computing Machinery

2006
[58]

Vaswani, N

A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. u. Kaiser, and I. Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017

2017
[59]

Wenger, M

E. Wenger, M. Chen, F. Charton, and K. E. Lauter. SALSA: Attacking lattice cryptography with Transformers. In Advances in Neural Information Processing Systems, volume 35, pages 34981–34994, 2022

2022
[60]

E. S. Wirth, H. Kera, and S. Pokutta. Approximate vanishing ideal computations at scale. In International Conference on Learning Representations, 2023

2023
[61]

E. S. Wirth and S. Pokutta. Conditional gradients for the approximately vanishing ideal. In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics , volume 151, pages 2191–2209, 28–30 Mar 2022

2022
[62]

W. Xu, L. Hu, M. C. Tsakiris, and L. Kneip. Online stability improvement of gröbner basis solvers using deep learning. In 2019 International Conference on 3D Vision (3DV) , pages 544–552. IEEE, 2019

2019
[63]

Yasuda, X

T. Yasuda, X. Dahan, Y .-J. Huang, T. Takagi, and K. Sakurai. MQ challenge: hardness evaluation of solving multivariate quadratic problems. Cryptology ePrint Archive, 2015

2015
[64]

# of full BBA expansions still required for V

M. Zare, P. M. Kebria, A. Khosravi, and S. Nahavandi. A survey of imitation learning: Algo- rithms, recent developments, and challenges. IEEE Transactions on Cybernetics, 54(12):7173– 7186, 2024. 13 A Theory of Oracle Border Basis Algorithm In this section we provide proofs to...

2024
[65]

Select a cell C = ({∆i}n i=1, l) ∈ Q and remove it from the list
[66]

, pn)⊤ ∈ Nn with pi ∈ [li, ui] for i = 1,

Sample a vector p = (p1, . . . , pn)⊤ ∈ Nn with pi ∈ [li, ui] for i = 1, . . . , n
[67]

Append a tuple (l, p) to R
[68]

, n, obtain a new cell C new i = ∆new j n j=1, l[i←pi] , where ∆new j = ∆ ∆[j←pj ] j , ∆j for j ̸= i and otherwise ∆new j = ∆( l, p)

For i = 1 , . . . , n, obtain a new cell C new i = ∆new j n j=1, l[i←pi] , where ∆new j = ∆ ∆[j←pj ] j , ∆j for j ̸= i and otherwise ∆new j = ∆( l, p). Append C new i to Q if it is a valid cell. We then have an order ideal O =   xa | a ∈ [ (l,p)∈R n × i=1 [li, pi]   . (B...
[69]

, oν(P )⟩k = K ν

⟨o1(P ), . . . , oν(P )⟩k = K ν
[70]

O-Gröbner basis

G ⊂ I(P ). then, G is the O-border basis of the vanishing ideal I(P ). Proof. We first show that G is the O-border basis of ⟨G⟩. The set G is a border prebasis and (obviously) generates ⟨G⟩, so we only need to show that K[X] = ⟨G⟩ ⊕ ⟨O⟩k holds. The border basis division algori...
[71]

If r ≤ n and G is a border basis, we have ⟨F ⟩ ̸= ⟨G⟩
[72]

X β1 = X β2 and Aα1 ≻A Aα2

If r > n, we have ⟨F ⟩ = ⟨G⟩. Proof. We write an outline of the proof (see below for details). When r < n, the codimension of ⟨AG⟩ is less than n and thus ⟨F ⟩ ̸= ⟨G⟩ holds for any A ∈ K[X]r×s. When r ≥ n, ⟨F ⟩ = ⟨G⟩ ∩J for some ideal J. If r = n, J ̸= K[X] for a generic matri...
[73]

⟨AG⟩ec is a prime ideal of K[A, X],
[74]

AG is a Gröbner basis of ⟨AG⟩e with respect to an arbitrary term ordering on K(X)[A],
[75]

For h = lcm(LC≻(f1),

Fix a term ordering ≻ on K(X)[A]. For h = lcm(LC≻(f1), . . . ,LC≻(fr)) ∈ K[X], ⟨AG⟩ec = ⟨AG⟩ : h = ⟨AG⟩ : h2,
[76]

If r ≥ n, then ⟨AG⟩ec ̸⊂ p ⟨G⟩

codim(⟨AG⟩) ≤ n and codim(⟨AG⟩ec) = r. If r ≥ n, then ⟨AG⟩ec ̸⊂ p ⟨G⟩. Proof. 1. Since AG is a set of linear polynomials over K(X), ⟨AG⟩e is a prime ideal of K(X)[A]. By Lemma C.5, ⟨AG⟩e ∩ K[A, X] is a prime ideal of K[A, X]
[77]

, r} with respect to any term ordering on K(X)[A]

Since fi and fj do not have common variables except X, LM(fi) and LM(fj) are disjoint for any i ̸= j ∈ {1, . . . , r} with respect to any term ordering on K(X)[A]. Thus, by Lemma C.6, AG is a Gröbner basis of ⟨AG⟩e with respect to an arbitrary term ordering on K(X)[A]
[78]

For g ∈ ⟨AG⟩ : h2, it follows that gh2 ∈ ⟨AG⟩ and thus g ∈ ⟨AG⟩ec since h2 ∈ K[X] has the inverse h−2 in K(X)[A]

First, we show that ⟨AG⟩ : h2 ⊂ ⟨AG⟩ec. For g ∈ ⟨AG⟩ : h2, it follows that gh2 ∈ ⟨AG⟩ and thus g ∈ ⟨AG⟩ec since h2 ∈ K[X] has the inverse h−2 in K(X)[A]. Second, prove that ⟨AG⟩ec ⊂ ⟨AG⟩ : h. Let g ∈ ⟨AG⟩ec and fix a term ordering ≻ on K(X)[A]. From (2), g can be divided by th...
[79]

As ⟨AG⟩ ⊂ ⟨G⟩, codim(⟨AG⟩) ≤ codim(⟨G⟩) = n

Since ⟨G⟩ is a zero-dimensional ideal of K[X], codim(⟨G⟩K[A,X]) = codim( ⟨G⟩) = n. As ⟨AG⟩ ⊂ ⟨G⟩, codim(⟨AG⟩) ≤ codim(⟨G⟩) = n. Since codim(⟨AG⟩ec) = codim(⟨AG⟩e) and AG consists of independent r-linear polynomials over K(X)[A], codim(⟨AG⟩ec) = codim( ⟨AG⟩e) = r. Assume r ≥ n....
[80]

Fix a term ordering ≻X on X

Assume that r = n and G is a border basis. Fix a term ordering ≻X on X. Then, for each i ∈ {1, . . . , n}, there exists fki ∈ G such that LC≻X (gki ) = xdi i for some positive integer di. For simplicity, we may assume that k1 = 1 , . . . , kn = n. Con- sider the parameter axi,...
[81]

Baseline

Assume that r > n. Then J ∩K[A] ̸= {0} by Proposition C.10. Fix q ∈ K D \V (J ∩K[A]). Then, for 0 ̸= f (A) ∈ J ∩ K[A], it follows that 0 ̸= f (q) ∈ σq(J), that is, σq(J) = K[X]. Since ⟨G⟩ ·J ⊂ ⟨AG⟩ and σq(⟨G⟩) = ⟨G⟩, ⟨σq(A)G⟩ = σq(⟨A)G⟩) ⊃ σq(⟨G⟩ ·J) = σq(⟨G⟩) · σq(J) = ⟨G⟩. S...

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

Abbott, C

J. Abbott, C. Fassino, and M.-L. Torrente. Stable border bases for ideals of points. Journal of Symbolic Computation, 43(12):883–894, 2008

2008

[2] [2]

Abbott, M

J. Abbott, M. Kreuzer, and L. Robbiano. Computing zero-dimensional schemes. Journal of Symbolic Computation, 39(1):31–49, 2005

work page 2005

[3] [3]

Abril Bucero and B

M. Abril Bucero and B. Mourrain. Border basis relaxation for polynomial optimization. Journal of Symbolic Computation, 74:378–399, 2016

work page 2016

[4] [4]

Alfarano, F

A. Alfarano, F. Charton, and A. Hayat. Global Lyapunov functions: a long-standing open problem in mathematics, with symbolic transformers, 2024

work page 2024

[5] [5]

A. M. Alvarez, Q. Louveaux, and L. Wehenkel. A machine learning-based approximation of strong branching. INFORMS Journal on Computing, 29(1):185–195, 2017

work page 2017

[6] [6]

M. F. Atiyah and I. G. MacDonald. Introduction To Commutative Algebra. Addison-Wesley series in mathematics. Avalon Publishing, 1994

work page 1994

[7] [7]

Becker, V

T. Becker, V . Weispfenning, and H. Kredel.Gröbner Bases: A Computational Approach to Commutative Algebra. Graduate texts in mathematics. Springer-Verlag, 1993

work page 1993

[8] [8]

Braun and S

G. Braun and S. Pokutta. A polyhedral characterization of Border Bases. SIAM Journal on Discrete Mathematics, 30(1):239–265, 2016

work page 2016