Computational Algebra with Attention: Transformer Oracles for Border Basis Algorithms
Authors: Hiroshi Kera
Nico Pelleriti
Yuki Ishihara
Max Zimmer
Sebastian Pokutta
Venue: NeurIPS 2025 poster ()
Keywords: Polynomial System Solving
Border Bases
Transformer
Computational Algebra
AI4Science
AI4Math
Primary area: machine_learning_for_sciences
TL;DR: We accelerate border basis computations with a Transformer-based oracle.

Abstract: Solving systems of polynomial equations, particularly those with finitely many solutions, is a crucial challenge across many scientific fields. Traditional methods like Gröbner 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.

Computational Algebra with Attention: Transformer Oracles for Border Basis Algorithms
Hiroshi Kera" 123
Nico Pelleriti*3
Yuki Ishihara
Max Zimmer? "Zuse Institute Berlin
Sebastian Pokutta 3 "Nihon University
Chiba University
National Institute of Informatics
Abstract
Solving systems of polynomial equations, particularly those with finitely many solutions, is a crucial challenge across many scientific fields. Traditional methods like Gröbner and Border bases are fundamental but suffer from high computa- tional 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, design and train Transformer-haan -hased 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 tokenization and embedding scheme tailored to monomial-come centered algebraic computations, resulting in a compact and expressive input representation, which reduces the number of tokens to encode an n-variate polynomial by factor of (n)). Our learning approach is data efficient, stable, and a practical enhancement to traditional computer algebra algorithms and symbolic computation.
Introduction
Polynomial equation systems serve fundamental model in wide range of fields, including
dynamical systems (such as those arising from the Lorenz attractor [48] or from digitalized gene-
regulatory networks [43
44),, cryptography where multivariate systems [27] 38) form the basis of signature schemes 667.. in data-manifold representation (55), camera-pose estimation [58). or
optimization 3 42 Solving these systems, even with small probability of success, reveals
critical properties such as stationary points [4] and optimal control strategies
[53], highlighting the
fundamental importance of polynomial system solving. Many of these applications involve so-called droodiiensionall systems with finitely many solutions, which are the focus of this work.
However, solving polynomial systems is notoriously hard: Even for zero-dimensional systems with finitely many solutions, the worst-case complexity is exponential in the number of variates 15] 50 and becomes practically intractable with few five variables. A most fundamental tool for their solution is the computation of Gröbner bases [10 I3 or Border bases [28 29 40) the former being interpretable the former in the zero-dimensional case.
nonlinear analogue of Gaussian elimination and the latter being generalization of
This work focuses on border basis computation, which is essentially iterative process that extends a polynomial basis set: at each step. new candidate polynomials are generated from the current basis and reduced to determine whether they extend the basis span. Crucially, reducing candidates that
Equul contribution. Conrespondence to kera@chiba- ppw.peeleritiezibb..
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

fail to extend the basis set is computationally wasteful and leads to long runtime of the algorithm.
While several computer-algebraic techniques, including heuristics, address this [24 29 the advances
in the field of Deep Learning (DI.) suggest new directions for symbolic computation 4 35 41 A
seminal work [54] introduced a Reinforcement Learning approach to optimize candidate polynomial construction in Gröbner basis computation, though their method was limited to binomial Gröbner bases and inputs. A recent work [35] used a Transformer [62] to directly predict Gröbner bases from input systems, but lacks output guarantees verifying the predicted basis requires full Gröbner computation, nullifying any efficiency gains.
In this study, we address this problem from the Algorithms with Predictions perspective enhancing algorithms with predictions for better performance, without sacrificing the correctness of the output. To that end, we propose the ORACLE BORDER BASIS ALGORITHM, the first output- cutput-certified algorithm for solving zero-dimensional polynomial systems using DI., Precisely, we develop a supervised training framework of a Transformer-based oracle that eliminates unnecessary reduction candidates, thereby significanlly improving the efficiency of border basis computation.
Contributions, Our contributions can be summarized as follows:
1. Algorithm for supervised data generation: develop a sampling method for diverse polynomial sets, realizing the random generation of diverse generators of vero-dimensional ideals. We present the first sampling theorem for border bases and also generalize the adeal-invarian transformation theorem [35].
To generate the oracle's training data,
2. Efficient monomial-leve token embedding: We propose a tokenization and embedding scheme tailored to monomial-ceme -enttered algebraic computations, resulting in a compact and expressive input representation, For n-variate polynomials. reduces token count by O(n) and attention memory by O(n²) while improving predictive accuracy.
3. Efficient oracle-guided algorithm with correctness guarantees: Finally, we propose a Transformer oracle specialized to the final stage of border basis computation, along with an effective heuristic for determining when to invoke the oracle. The resulting ORACLE BORDER BASIS ALGORITIM eliminates unnecessary reduction candidates and significantly improves the efficiency of border basis computation, validated across diverse parameter settings and prediction tasks.
key insight is that border basis computation proceeds begree-by-degres enabling us collect labeled training examples by recording which reductions extend the basis at each degree. In contrast, Gröbner basis computation lacks this natural decomposition, which why the previous study [54] had to rely on reinforcement learning less data-efficient and less stable approach than our supervised Since border bases generalize Gröbner bases in the zero- dimensional case, we can efficiently recover Gröbner bases from border bases when they exist.
learning framework
[19 56 59 68
Further related work. Buchberger's algorithm 100 computes Gröbner bases by iteratively forming and reducing S-polynomials until achieving closure under a monomial order (13). Faugère's s F4/F5 algorithms [17 18] improve upon this via sparse linear algebra and signature-based redundancy detection. Various heuristics (20) help mitigate combinatorial explosion. Border bases do not require a fixed variable ordering and are term-order-free [9), numerically stable alternative to Gröbner bases, defined relative to a chosen monomial set O with leading terms on its border 28 29).
Apart from the previously mentioned works using machine learning for symbolic computation, 26 enhanced cylindrical algebraic decomposition, while [66] improved the stability of Gröbner basis solvers. Our work further connects the broader field of learning-guided algorithms, where predictions have proven effective at steering heuristic decisions across combinatorial optimization problems (51). For example, in the context of mixed integer programming, (5) and (36] demonstrated the effectiveness of learning-basse approaches to improve branching decisions.
2 Preliminaries
We introduce the necessary notation well as the core concepts of border bases and their computation. For comprehensive treatments, see [28] (2) on border bases and [12 on ideals and polynomials.
An n-variate term or monomial ~ == o1 aha an is defined by an exponent vector E Z We
denote by Tn the set of all such terms and by K K[X] K K[æ1..... zn] the polynomial ring over

---

(a) Border Basis
(b) Naive BB expansions
(c) Oracie-guided expansions
LTWW
C
Extension
Discarded
Figure/ 1: Border basis concepts: (a) A border basis with order ideal {1,9} and border terms {v² 2.,, (b) BBA's iterative expansion of V. showing leading terms: two initial polynomials yield four expansions, then eight more though only two out of twelve were necessary. (c) The oracle approach achieves the same result with just four targeted expansions.
field K. We use K[X] <d for its restriction to polynomials of degree at most d. We use to denote term ordering on K K[X]. The leading term LT(f) of polynomial f is its largest term under x. For polynomial set F = { [ff,...... fr). LT( {LT(f1) .... LT((f)) denotes its leading terms. The set of polynomials = (fi...., (.) (fih ......... f,h, 1 hi,,... ht E [[X]] is called the ideal LT()) is finite set, the ideal is called zero-dimensional. The cardinality of the set denoted by I.. For an ideal I C K[X], the quotient ring K [X]/I equivalence classes of polynomials under + f f-3 g E I. The symbol @ denotes the direct sum of vector spaces: for
generated by F in K [XX]. L
denotes the factor ring of K[X] modulo I. Its elements the relation ff subspaces V, W C. K[X), V e W means every element can be uniquely written v with V. w E W, and V M.VV W = (0).
2.1 Defining border bases
A border basis of ideal I is set of polynomials (91...., ..1.....9.. I= that generates I with specific properties and is defined relative to an order ideal O, a subset monomials that is closed under division.
Definition 2.1. A finite set O t E O. Its border an (Ur O consists of terms obtained by multiplying elements of O by variables which are not O itself.
an order ideal if whenever / E Tn divides any o E O, then
Definition 2.2. Let Tr be an order ideal with border do G = [g...... Ix is an O-border prebasis if for all = 1,
A set of polynomials
9:
b;
cet.
(2.1)
LEO
with a K. If O forms basis of K[X) (G), then G is the O-border basis of (G). In other words, with the span of vector space (O) == 111ET get a E K), we have K [[X] I 0 (O)
To illustrate, consider a simple polynomial system over Q with polynomials x² + y² - and r 1. Taking the order ideal O {1, y). we obtain the border do (z, yr, yr,y") The corresponding border basis is {y², x 1, xy y). h. It generates the original ideal (x + y 1, x 1) and has the required structure; each polynomial's 's leading term lies in 00 while its remaining terms are in O.
2.2 Computing border bases
For clarity, we defer the full border basis algorithm to the appendix and focus on its most important component: the L-stable-span step (29]. This step central to the Border Basis Algorithm (BBA), and accelerating it is the primary objective of our work.
||a/] d}. which The L-stable-spaa span step operates follows. We begin with finite set L {a serves as our computational universe of monomials up to degree d. We are also given an initial set of polynomials Vn C (C), each with distinct leading term.
At each iteration, we expand the current set by multiplying every polynomial v V by each variable Zj. for n. n. This produces the set 4 {Iyv v V, n. Next,

---

we perform a linear algebra operation called BasisExtension: we compute basis for the span of the expanded set, and then restrict this basis those polynomials whose terms lie within C. If this process does not yield any new elements, the routine terminates.
To clarify the algorithmic process, consider again == 1 1,2 -y22- } and the initial computational universe - {1, x. y, x², zy, y²); Multiplying each E V by each variable yields four candidates (cf. Figure [b). After reduction modulo V. two candi-
Algorithm 1: L-Stable Span computa- tion in BBA and OBBA
Input: Polynomolys Vo, universe L;
dates have leading terms in L: I (x 1) x²
and y- (z - 1) yz y. Reducing x² modulo 2
repeat
gives x - (x y² 1) 2 y² + Thus. 3
C t V.
extended to include y² x 1 and yr y,.
C: Oracle Vi)
Most importantly for our setting, BBA identifies the successful candidates for the border basis only in hindsight. To address this, we introduce an oracle that predicts these key polynomials in advance, reducing unnecessary iterations and improving efficiency.
V++1 f BasisExtension(XI, L)
i it
until V: V141
3 The Oracle Border Basis Algorithm
In practice, most elements of C, are redundant-then vanish after reduction modulo V; To eliminate this inefficiency, we introduce an expansion oracle that selects much smaller subset C, S Vi: only these polynomials proceed to the reduction step. We refer to the resulting algorithm as the Oracle Border Basis Algorithm (OBBA). The difference BBA is highlighted Algorithm | instead of
setting
C V
as BBA does, we the oracle C
Oracle (Li, V4)
The oracle is a lightweight Transformer model (detailed in the next section) that takes a tokenized version of the current computational universe L; and generator set V; as input, and outputs set of pairs (ayg, Um)) where xy is a variable and Um LT((pm) distinct leading term in V. Each pair corresponds to a candidate polynomial ZePm E V
3.1 Termination of the algorithm
We allow the oracle to propose a reduced candidate set up to k times. After the k-th invocation, the algorithm defaults the standard BBA expansion, i.e., VT. This strict cap ensures correctness: the oracle can override the vanilla expansion at most & times, after which the algorithm reverts to the standard procedure, preserving both termination and exactness:
Theorem 3.1. OBBA terminates and returns a correct border basis.
Limiting the oracle to k non-standard expansions prevents repeated expansion in the same direction indefinitely and guarantees termination. For brevity, we present only our main conclusions here and defer detailed empirical and theoretical results to the appendix.
3.2 Allocating the oracle calls
As the algorithm progresses, the generator set V expands, increasing the number of polynomials to reduce each iteration. Empirically (cf. Table 1O), find that between 70 % to 95 % of the runtime is spent in the final stage, i.e., the iterations that follow the last enlargement universe L. Since the final iterations dominate the runtime, we aim to spend the oracle budget exclusively there, where every avoided reduction yields the greatest benefit.
the computational
A simple yet effective heuristic for recognizing this final stage is to monitor the gap 9 |C| V
When g approaches the size of the (unknown) order ideal of the target border basis, no further universe expansion is required (cf. Lemma A.2 and the relative version of this gap, [c] relationship with the remaining required expansions (cf. Figures
[V] has a strong
13

---

Invoking the oracle too early can be counterproductive: an inaccurate prediction may enlarge V while still leaving many expansions to run, so the algorithm ends up performing more reductions on bigger set. Reserving the k-oracle calls for the final stage prevents these costs (cf. Theorem A.5
4 Designing the transformer oracle
This section presents the architecture and training of the Transformer oracle
ORACLE (). S, where C V C K[X], 8 C (xI,..., x V.
(4.1)
We assume a standard encoder-decodes Transformer 622. a general model for
tasks, We collect a large number of training samples ((C, V), S) by running the border basis algorithm. Collecting diverse samples is non-trivial, and we develop new techniques to address this task. Since input sequences the Transformer oracle are often extremely long (typically tens of thousands of tokens), we also develop methods to substantially reduce their length. All proofs are provided in Appendices and C
4.1 Dataset generation
Our overall goal is to collect many input-output instances to train the Transformer oracle on, which we could achieve by running the BBA over many sets of polynomials. A crucial challenge is to generate diverse sets of polynomials as the following observation highlights. Recall that we are interested in cero-dimensional ideals and let F K[X] be collection of randomly sampled polynomials (see Appendix E.1 regarding the sampling from K [X)). If [F] < n, (F)) is not seroo-iiensional. If (F') is generally the unit idcal, i..., (F) K[X]. Thus, random sampling only works for Fl = n, which is a strong restriction.
however |F|
We will now address this issue in two steps. First, instead of sampling polynomial systems at random, we propose border basis sampling to generate diverse border bases [G,]-a problem that, to the best of our knowledge, has not been explored in the literature. Secondly, generalizing the results in (35). our iieealinvariant generator transform converts each G; into a non-basis F; such that (G.) = (F)). This backward approach not only yields a diverse set of polynomial systems with |F] > but also provides direct control over the complexity of the corresponding border bases, as the sizes and degrees of the border bases (particularly, the order idcals) can be predetermined.
4.1.1 Border basis sampling
Our algorithm first samples order ideals, and then constructs border bases supported by them. Recall that finite set O C Tr. is called an order ideal if for any E O its divisors are all included in O. Thus, for E Tn, O := (all the divisors of t} is an order ideal, and the union U O2, for ( ... by E T is also an order ideal. The latter observation provides a strategy for the sampling of order ideals, requiring refinement of this approach, with the formal algorithm deferred to Appendix B.]
Now that we can sample order ideals, let O = .ol,...,09 be an order ideal and d0 = (b.,...,b, b,. its border. A border prebasis G {99 ... ] takes the form 9i 6, E Croo for = 1 μr, with arbitrary coefficients Gjj K. To obtain
border basis, these coefficients must satisfy algebraic conditions ensuring that O spans the K-vector space K" [[X/(G)).
In consequence, random coefficients do not produce border bases. A crucial observation is that the coefficients of G can be readily obtained via simple linear algebra for so-called vanishing ideals, which we introduce next.
Definition 4.1. Let P (Pr....: p.} ) C K" be a set of points. The vanishing ideal of P is the set of all polynomials that vanish on P. namely, I(P) {g E K[X] g(p.) 0, i i= v.).
1/).
The following theorem formalizes the construction of border basis from order ideal. Theorem 4.2. Let O {oi..... ) and do = {bz,...,b,, be an order ideal and its border, respectively. Let P {pi,.... p K" be set of v distinct points. Let
(b((i) bx((i) 01(p1) os(Pi)
M(P) = (80(P) O(P)) =
E kux(u+v), (4.2)
(p(p)) ... (p() or (p(pe) ... (pv)
5

---

If OP) is full-rank, the nullspace of (P) is p-dimensional and spanned by {Dilier where v = (O..... L....,,... 0, C11. Giv) with the first ji entries being zero except for 1 in the i-th
position. The set {g: = b; Σド= Ciy j i=1 the O-border basis of the vanishing ideal I(P).
can compute a border basis of a vanishing ideal (P) from set of points P. However, it only leads to a special type of border bases, which are Zariski-closed (i.e., zero-measure set). Our method covers more general ones, refer to Appendix [B.3]
Remark 4.3. Several algorithms 23
30
46
64]
Remark 4.4. Non-trivial ideals from random generators are generically radical, and any radical ideal (fi..... fi-) is vanishing ideal ((P) if the solution set P of fi = = fx(X) = is finite subset of K A previous work (35 assumes ideals in shape position, and vanishing ideals involve them in this setup. Further generalization to non-radical, positive dimensional ideals still
an open problem.
4.1.2 Ideal-invariant generator transform
Now, we are able obtain border basis = ........99 ..) of a vanishing ideal I(P). Next, we design the following matrix A E K[X]"x to transform border basis G (.),..., 9.
F = AG, s.t. (F) (G).
(4.3)
This effectively allows sample generating sets of I(P). B3 recently identified sufficient condition: if A has a left inverse then the
condition (F) = (G) holds. A subset of such
matrices is given by Bruhat decomposition A U, P O] with unimodular upper-triangular matrices U1 [x] U2 K K[X]*x and permutation matrix P of size r. However, the key assumption F 2 G fails in our case, as typically G| >> n.
We therefore propose more general construction of A satisfying the ideal invariance condition.
Theorem 4.5. Let K be a field of characteristic 0, a zero-dimensional radical ideal of K [[X], and d positive integer. Let G E K[X]* be generating set of I and F AG E K[X]" set of polynomials given by generic matrix A E K[X]ZA
1. I S n. and G is a Grübner basis, we have (F) + (G).
2. I > n, we have (F)) (G).
This suggests that for (AG) = (G) is almost 1
n. and field K of characteristic O, the probability that random A satisfies The probability is also very close to when is finite field F3 with a
large prime number p.
Corollary 4.6. Let d and dmax be positive integers. Let K = F. be a finite field of order for prime number P and let G be a subset of F [Pp[[]<n <dmax such that (G) is O-dimensional radical ideal of E [X), Assume r > n and let {A 1 (AG) = (G) }. Then, a generically sampled A E FF [2] satisfies (AG) = (G) with probability
21 d'
Pr(p)= = F XX
(4.4)
P
for some positive integer d', which is determined by d and dmaax independent of any specific p.
Therefore, for sufficiently large p. the success rate of the ideal-invariant transform is almost 1 (note that the vanishing ideal Z(P) is a O-dimensional radical ideal). See Figure for a numerical experiment. In summary, sampling a random A with more than n rows, which is arguably the simplest approach, works.
4.2 Efficient input sequence representation
The input (C, V) and output S are respectively regarded as sequences of polynomials (in the fully expanded form), and tokenized into sequences of tokens. For example, with L = {1, x. y) and
Note that in this paper, a generically (or randomly) sampled polynomial f E K[X] refers to a linear combination of all monomials whose degrees are up to an (implicit) upper bound d. The combination coefficients sampled uniformly and independently from the field K.

---

V = -Ir + 2, y], the input sequence in the infix representation is
(C1, EO, EO, <sep>, , C1, E1, EO, <sep>, C1, EO, E1, <supsep>; C1, E1, EO, +, c2, EO, EO, <sep?, C1, EO, E1, <eos>),
(4.5)
where and En represent coefficient and exponent of values n. The token <sep> separates elements in set, and <supsep> separates sets. The token <eos> represents the end of the sequence.
In standard Transformers, the computational cost of self-attention grows quadratically with the imput size. The sizes of C. V are often large, and V contains polynomials with many terms. We introduce two methods that, when combined, significantly reduce input size as shown in Figure 2
Simplification of in- and output. We replace L with its minimal identifying subset L' C C (cf. Appendix D.3). Since the basis extension step in the BBA primarily relies on leading terms, we truncate each polynomial in to its leading terms, which we found to have minimal impact on the predictive performance of the oracle (cf. Table Tp. The target sequence is list of pairs like = {(z v) eex. Since the polynomials in V have mutually distinct leading terms, we can replace each v E V with LT(u).
Monomial embedding. fully expanded n-variate degree-d polynomial (e.g., ay + y instead of (x++ + 1)y) typically contains on the order of (*+d) monomials. Standard representations (e.g., infix) tokenize each monomial using + tokens one for the coefficient and n for the exponents. Each monomial is followed by a token like or <sep>, so a polynomial set F = ..,,...,Jf fr} yields a sequence of the order of (n + 2)s (ata)) We introduce an efficient embedding scheme for polynomials, representing each monomial with a single token. By combining monomial and its follow-up token into one vector, this approach removes the (n + 2) factor from the input size.
Definition 4.7. (Monomial embedding) Let 2 be the set of all tokens. Let (t, <+>) be pair consisting of monomial & ca" E Tn with coefficient E K, exponent vector E Z and follow-up token <*> E Σ. Let Sp.. Pe. and for denote embeddings of the coefficient, exponent vector, and follow- up token into d-dimensional space, respectively. The monomial embedding fm Tn E + Rd is given by
(m,, <+>) = pp(c) + (a(a)) + (pr(<))).
(4.6)
Symbolic computations are fundamentally monomial-centric monomials are compared, added, or divided. Without monomial embedding, attention-basel models must connect (n + 1) tokens per monomial; this is reduced to simple one-to-one mapping, substantially improving success rates in cumulative polynomial product tasks (cf. Table 3. See Appendix D.I for the exact implementation.
5
Experimental results
We empirically evaluate our approach dataset generation, training details, and additional results are in Appendix E
5.1 Fast Gaussian elimination
As an additional contribution, we present a fast Gaus- sian climination (FGE) kernel that replaces the standard elimination in BasisExxensionn (see Algorithm[1 T). FGE maintains the active reducer set in balanced search tree, enabling O(log(m)) (m)) look-ups and insertions; find- ing a reducer with a matching leading monomial is thus logarithmic, not linear. Combined with on-the-fly nor- malization and an index map for immediate reuse new reducers, our kernel makes the entire Basis Extension step quasi-lincar This yields an 10x wall-clock speedup in data generation (cf. Table 7 enabling to create an order magnitude more training samples.
Marma (dtta)
/Tema (Monsmaa (Ponmms
Max Token Count
10a
10%
11243
6348
2021
10a
620
126
209 209
337
4p9
907
102
70
10
n=3
n=
n=5
Number of Variables (n)
Figure 2: (F31, I cation and monomial embedding signifi- cantly reduce input size. See also Figure
5). The term trun-
Our code is available at wttatts://githu..com/// http:///hht...ooooo..././aa/aa/e
7

---

Table 1:
Evaluation results of Transformer predictions polynomial ring F'11 ( Zn.- Trans- former successfully learns the expansion directions. The input polynomials are truncated to their first / leading terms. The No Expansion Accuracy column shows that the Transformer model can determinate the termination with high accuracy. Refer to Table for the complete version.
Field Variables
Precision (%)
Recall (%)
Score (%)
No Expansion Acc.
(%)
84.4
86.8
85.6
99.7
71
3
89.4
90.0
89.7
99.7
5
91.6
93.2
92,4
99.7
1
90.7
91.6
91.1
98.8
33
1
3
92.9
93.7
93.3
98.8
5
94.2
94.7
94.4
98.8
92.7
93.1
92.9
99.6
n =
5
3
94.3
94.6
94.4
99.6
5
94.8
95.3
95.1
99.6
Importantly, FGE is orthogonal to the Transformer ora- cle: while the oracle eliminates unnecessary reductions. FGE accelerates all necessary ones, and their benefits compound.
5.2 Learning successful expansions
We begin by demonstrating that the Transformer model can learn to predict successful expansion.
Dataset. Datasets were generated as described in Section 4.1 with one million training and one thousand evaluation samples. We set C K| [ 22 and E K[xi..... ".,] _n,'" for r E {n 1...., 2n collecting samples only from the final five expansions of each border basis computation. Each polynomial in A has at most ten terms, sampled as detailed in Appendix [. In total, 27 datasets were constructed by varying the number of variables
{3, 4. 5). coefficient field Ep with p E (7,31, 127]. and truncation to the leading terms with / E (1,3,5] 5).
Setup. Experiments used a standard Transformer with 6 encoder and decoder layers, 8 attention heads, and our monomial embedding. Embedding and feedforward dimensions were (dmodel dæa) (512, 2048). We set dropout to 0.1. The positional embeddings were randomly initialized and trained throughout the epochs. The model was trained for epochs with Adam 449 (3, 0.9,
B2 = 0.999), linearly decaying learning rate from 10-1 and batch size 16.
Results. Table summarizes results. The Transformer predicts set S {3r,, 0z)} of expansion direction and target polynomial pairs. For non-empty predictions, we report precision, recall, and Fl score against ground truth; for empty predictions (indicating algorithm termination), we report accuracy. The Transformer consistently learns both expansion directions and target polynomials across all (n, p, k) settings. Notably, it achieves near-perfect accuracy in the No Expansion case, reliably identifying termination and avoiding at least the final unnecessary expansion step. Overall, the performance improves with larger and p. likely due the higher success rate of the ideal- invariant generator transform (as suggested by Corollary 4.6] and Figure ( It is also noteworthy that truncation to the leading terms has only a minor effect on predictive performance, despite significantly reducing input size (cf. Figure 8
5.3 Transformer oracle
We now demonstrate that integrating the Transformer accelerates the improved border basis algorithm. also evaluate the Transformer oracle's ouitt--distri performance on higher-degres systems, which are more challenging predict.
5.3.1 In-distribution performance
We assess the Transformer oracle's in-distribution performance, i.e., the performance on systems drawn from the same distribution the training data.

---

Table 2: Wall-clock runtime in seconds (mean + standard deviation over 100 random zero- dimensional systems of total degree Σ 4) for five algorithms over polynomial ring F31 [T1.... F.n] and variable counts 3, 4, 5 variables. BBA is the classical border basis algorithm: IBBA is the incremental BBA baseline; OBBA is our vracle-augmented BBA, reducing runtime by about 3x versus IBBA. IBBA+FGE and OBBA+FGE add fast Gaussian elimination (FGE), an orthogonal linear algebra speedup; OBBA+FGE is the fastest, reaching up to two orders of magnitude improvement over IBBA. A x.5x speedup in terms of unneccessary expansions is shown in the appendix in Table 6
Baseline
Ours
Field n
BBA
IBBA
OBBA
IBBA+FGE
OBBA+FGE
0.07 0.11
0.06 + 0.09
0.06 0.08
0.03 + 0.03
0.03 + 0.03
F31
0,46 + 0.43
0.35 1 0.25
0.22 + 0.13
0.09 1 0.05
0.09 1 0.05
5
11.44 1 8.25
7.60 + 5.13
2.58 + 1.37
0.88 1 0.49
0.60 + 0.32
Degres
Degree
2.2
Degroe
Degree
Failbacks BBA
40
40-
2.0
30
30
X 3.8
1.8
Speed-up up
2.6
Speed-up
1.6
20
20
2.4
1.4
10
1.0
1.2
1.2
1.0
1.0
0.7
0.8
0.9
0.8
1.0
0.9
1.0
1.0
Border gap [11/14]
Border gap |Н/|4]
Border gap |,/]4]
Border gap |Н/[4]
F31
F127
Figure 3: Speed-up of OBBA over IBBA on OOD systems with n 4 variables and increased degree. Each point averages 100 random instances per field. The relative border-gap [Z]
[V] is the threshold that
decides when the oracle is invoked; a ratio of corresponds to IBBA, where the oracle is never used. Although the oracle is trained only on systems of total degree 2 for n 4, it generalizes to degrees 4
and 8, achieving up to 1.8x speed-up even for degree 8. The average runtime for IBBA on the OOD systems is two orders of magnitude higher than for the in distribution case.
Setup. We compare five algorithmic variants: the classical BBA, the Improved Border Basis Algorithm (IBBA), IBBA with fast Gaussian elimination (IBBA+FGE), and the oracle-guided versions OBBA and OBBA+FGE. For oracle-augmented variants, the oracle is called most five times, consistent with our training on the final five expansions. We invoke the oracle at ratios of 0.7, 0.750, 0.8, 0.85, 0.9, 0.95, 0.975 of the relative border gap [
[E]
Results. Table shows that the state-of-the-art BB BA for systems with five variables, with smaller gains for three and four variables. Notably, none of the oracle-guided variants required reverting to standard iterations, indicating that the Transformer oracle successfully predicts expansion directions and target polynomials for all cases.
algorithm achieves up 3x speedup over the
5.3.2 Out-of-distribution performance
We assess the Transformer oracle's 's -ittt--distribttion performance by evaluating on higher-degree systems, which more challenging for both the oracle to predict and the IBBA to solve. The goal is to test whether the Transformer, trained on easy instances, can generalize to harder ones, where we defer full results to Appendix E.4
Setup. We introduce 27 new datasets (i.e., three variables, three degrees, and three field orders). We increase the total degree of the sampled input system F and transformation matrix A by at each step, limiting ourselves to Fai, 127. This produces systems of total degree 3, 4, 6, and 8. To isolate the oracle's 's impact, we compare IBBA and OBBA without FGE. The average IBBA runtimes (in seconds) on these out-i--distiiiutioo instances are: 1.17, 3.21, 20.54, and 40.2 for total degree 3, 4, 6, and 8, respectively, averaged over the three fields.

---

BBA
IBBA
OBBA
IBBA+FGE
OBBA+FGE
87
5127
F31
10a
Runtime (s)
101
10
3 Total degree d
2
4
Total degree
Total degree d'
Figure 4: Runtime comparison (log scale) across increasing total degrees for polynomial systems over F7, If 127, and F311 with n = 5 variables. Bars show mean wall-clock runtimes of 100 instaces for two baselines (BBA, IBBA) and three versions of our method (OBBA, IBBA+FGE, and OBBA+FGE). Note the logarithmic y-axis, which reveals that higher-degree out-of-distribution systems are orders of magnitude harder than the degree-2 systems used for training. Despite never being trained on such hard instances, our wwethod.particulie OBBA+ maintains dramatically lower runtimes, showing strong generalization beyond the training distribution to problems that are magnitudes harder.
Results. Figure shows that the oracle generalizes to systems with n. = 4 and total degrees d = and d 8, achieving speedup factors of up 1.8x even for the hardest case (d 8). Despite being trained only on systems of total degree d = 2, it generalizes to these substantially more difficult -ut-of-distribution systems. Figure 4 further illustrates this effect for n 5; OBBA with FGE achieves significant speedups on out-of-distnn -iii--i-iitttttiionnn systems that are order of magnitude harder than those encountered during training. For the hardest instances, IBBA took on average 101 22 seconds, while our method reduces this to 5.51 seconds. Notably, the Transformer was trained only on 2 instances, for which IBBA has an average runtime of 7.16 seconds (cf. Table This highlights the model's s's strong ability to generalize beyond its training distribution, solving problems that are magnitudes more difficult than those in training. See Appendix F.4 for the full results.
Conclusion
We introduced transformer-enhancee border basis algorithm that allows for efficiently solving systems of polynomial equations. Our approach is the first to integrate deep learning into border basis computation, achieving up to 3.5x speedup while fully preserving solution correctness. The development of this oracle-guided method was based on a detailed analysis of algorithmic costs, a new framework for generating diverse training data specific border bases, and an efficient task-specific polynomial representation, investigated both empirically and theoretically. We believe our work thus provides a practical, data-efficient, and stable enhancement the symbolic computation tooliit, showcasing a promising way to combine machine learning with established mathematical algorithms.
Limitations and future work. This study focuses O-dimensional ideals over finite fields. The extension to Dositive-dimension and infinite fields is left to our future work. We note that our setup still covers the essential cases. First, any positive-dimensionall ideal over finite fields can be reduced to O-dimensional ones by including the field equations (e.g., x(x - 1) and y(y - 1) when of
K[X] F2 y)). which restricts the solution spaces to K. Nevertheless, addressing the sampling
ideals (and their Gröbner /border bases) is an independent, interesting open problem from an algebraic perspective. Second, all our technical contributions except for those about border bases are compatible with infinite fields; we selected finite fields as well-known hard case. For example, learning the parity function (i.e., the sum of binary bits with modular 2) has been Besides, the finite field case 70 to address unbounded
theoretically and empirically known to be hard to learn [22 37 57
allows us to avoid introducing extra number embedding techniques coefficients. It is also worth noting that infinite-fiele field cases have often been reduced to finite fields through modular techniques
[6] for efficient computation. For the practical utility, a scale-up to larger systems is required, although, to the best of our knowledge, our experiments handled the largest and most general class of systems among the related studies [35] 54), see Appendix E.2
10

---

Acknowledgments. This research was partially supported by the DFG Cluster of Excellence MATH+ (EXC-2046/1, project id 390685689) funded by the Deutsche Forschungsgemeinschaff (DFG) as well as by the German Federal Ministry of Education and Research (fund number 011S23025B). Hiroshi Kera was supported by JST PRESTO Grant Number JPMJPR24K4, JST BOOST Program Grant Number JPMJBY24C6 JSPS KAKENHI Grant Number JP23KK0208, Mit- subishi Electric Information Technology R&D Center, and ISPS Program for Forming Japan's ' Peak Research Universities (J-PEAKS) Grant Number JPIS00420230002. Yuki Ishihara was supported by JSPS KAKENHI Grant Number JP22KI 13901 and Institute of Mathematics for Industry, Joint Usage/Research Center in Kyushu University (FY2025 Short-term Joint Research "Speeding up of symbolic computation and its application to solving industrial problems 3" (2025a012)). Yuki Ishihara would like to thank Kazuhiro Yokoyama and Yuta Kambe for their helpful comments about backward transforms.
References
[1] Abbott, C. Fassino, and M.-L. Torrente. Stable border bases for ideals of points. Journal of Symbolic Computation, 43((1):883-88)) 8944, 2008.
[2] J. Abbott, M. Kreuzer, and L.. Robbiano. Computing zero-dimensional schemes. Journal of Symbolic Computation, 39(1):31-49, 2005.
[3] M. Abril Bucero and B. Mourrain. Border basis relaxation for polynomial optimization. Journal of Symbolic Computation, 74:378-399, 2016.
[4] A. Alfarano, F. Charton, and A. Hayat. Global Lyapunov functions: a long-standing open problem in mathematics, with symbolic transformers, 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.
[6] E. Arnold. Modular algorithms for computing Gröbner bases. Journal of Symbolic Computation, 35:403-419, 2003.
[7] M. F. Atiyah and I. G. MacDonald. Introduction To Commutative Algebra. Addison- Addison-Wesley series in mathematics. Avalon Publishing, 1994.
[8] T. Becker, V. Weispfenning, and H. Kredel. Gröbner Bases: Computational Approach to Commutative Algebra. Graduate texts in mathematics. Springer- Verlag, 1993.
[9] G. Braun and S. Pokutta. A polyhedral characterization Border Bases. SIAM Journal on Discrete Muthematics, 30(1):239-22) 265,, 2016.
[10] B. Buchberger. Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal (An Algorithm for Finding the Basis Elements the Residue Class Ring Modulo Zero Dimensional Polynomial Ideal). PhD thesis, Mathematical Institute, University of Innsbruck, Austria, 1965. English translation of Symbolic Com- putation, Special Issue Logic, Mathematics, and Computer Science: Interactions. Vol. 41, Number 3-4, Pages 475-511, 2006.
[11] Charton. Linear algebra with transformers. Transactions on Machine Learning Research, 2022.
[12] D. Cox, J. Little, and D. O'shea. Ideals, varieties, and algorithums, volume 3. Springer, 1992.
[13] D. A. Cox, J. Little, and D. O'Shea. Ideals, Varieties, and Algorithms: An Introduction Computational Algebraic Geometry and Commutative Algebra. Undergraduate Texts in Mathematics. Springer International Publishing, 2015.
[14] 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.
[15] W. Dubé. The structure of polynomial ideals and Gröbner bases. SIAM Journal on Computing, 194):750-773, 1990.

---

[16] C. Fassino. Almost vanishing polynomials for sets of limited precision points. Journal of Symbolic Computation, 45(1):19-37, 2010.
[17] J.-C. Faugère. A new efficient algorithm for computing Gröbner bases (F4). Journal of Pure and Applied Algebra, 139(1)61--8, 1999.
[18] J.-C. Faugère. A new efficient algorithm for computing Gröbner bases without reduction to zero (FS). 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.
[19] 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. Tomezak, and C. Zhang, editors, Advances in Neural Information Processing Systems, volume 37, pages 120602-120666 Curran Associates, Inc., 2024.
[20] A. Giovini, T. Mora, G. Niesi, 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. Association for Computing Machinery.
[21] G.-M. Gruel and G. Pfister. A Singular Introduction to Commutative Algebra, 2nd Edition. Sringer Verlag, 2008
[22] M. Hahn and M. Rofin. Why are sensitive functions hard for transformers? In Proceedings of the Annual Meeting of the Association for Computational Linguistics, pages 14973-15008, 2024.
[23] D. Heldt, M. Kreuzer, S. Pokutta, and H. Poulisse. Approximate computation of zero- dimensional polynomial ideals. Journal of Symbolic Computation, 44(11):1566-155) 159,, 2009.
[24] 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.
[25] C. Hou, F. Nie, and D. Tao. Discriminative vanishing component analysis. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, pages 1666-1672, Palo Alto, California, 2016. AAAI Press.
[26] 7. Huang, M. England, D. Wilson, Bridge, H. Davenport, and I.. C. Paulson. Using machine learning to improve cylindrical algebraic decomposition. Mathematics in Computer Science, 13:461 488, 2019.
[27] Y. Ikematsu, R. Perlner, D. Smith-Tone T. Takagi, and Vates. HFERP-a new multivariate encryption scheme. In Post- Dast-Quanium Cryptography: 9th International Conference, PQCrypto 2018, Fort Lauderdale, FL, USA, April 9-11, 2018, Proceedings 9, pages 396-416. Springer, 2018.
[28] A. Kehrein and M. Kreuzer. Characterizations of border bases. Journal of Pure and Applied Algebra, 196(2):251-270, 2005.
[29] A. Kehrein and M. Kreuzer. Computing border bases. Journal of Pure and Applied Algebra, 205(2):27--955, 2006.
[30] 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.
[31] H. Kera and Y. Hasegawa. Approximate vanishing ideal via data knotting. In Proceedings of the -eeooy AAAI Conference on Artificial Intelligence, pages 3399-3406, Palo Alto, California, 2018. AAAI Press.
[32] H. Kera and Y. Hasegawa. Spurious vanishing problem in approximate vanishing ideal. IEEE Access, 7:178 1-1899911181 1880661--1797777 178976, 2019.
12

---

[33] H. Kera and Y. Hasegawa. Gradient boosts the approximate vanishing ideal. In Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence, pages 4428 4425, Palo Alto, California, 2020. AAAI Press.
[34] H. Kera and Y. Hasegawa. Monomial-agnostee computation of vanishing ideals. Journal of Computational Algebra, 11:100022, 2024.
[35] H. Kera, Y. Ishihara, Y. Kambe, T. Vaccon, and K. Yokoyama. Learning to compute Gröbner bases, 2024.
[36] 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 artificial intelligence, volume 30, 2016.
[37] J. Kim and T. Suzuki. Transformers provably solve parity efficiently with chain of thought, In The Thirteenth International Conference on Learning Representations, 2025.
[38] A. Kipnis, Patarin, and L. Goubin. Unbalanced oil and vinegar signature schemes. In International Conference the Theory and Applications of Cryptographic Techniques, pages 206-222. Springer, 1999.
[39] F. J. Király, M. Kreuzer, and L. Theran. Dual-to-kernel learning with ideals. 0bs/1402.0099) 2014.
arXiv,
[40] M. Kreuzer and L. Robbiano. Computational Commutative Algebra 2, volume 2 of Algorithms and Computation in Mathematics. Springer, 2005.
[41] G. Lample and Charton. Deep learning for symbolic mathematics. In International Conference on Learning Representations, 2020.
[42] J. B. Lasserre. Global optimization with polynomials and the problem of moments. SIAM Journal on Optimization, 11(3):796-877, 2001.
[43] R. Laubenbacher and B. Stigler. A computational algebra approach to the reverse engineering of gene regulatory networks. Journal of Theoretical Biology, 22944)3333- 2004.
[44] R. Laubenbacher and B. Sturmfels. Computer algebra in systems biology. American Mathemat- ical Monthly, 116(10):882899) 19122,9991120 2009.
[45] R. Lidl and Niederreiter. Finite Fields. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2 edition, 1996.
[46] J. Limbeck. Computation of approximate border buses and applications. PhD thesis, Passau, Universität Passau, 2013.
[47] 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, USA, June 2013. PMLR.
[48] E. Lorenz. Deterministic nonperiodic flow. Journal of Atmospheric Sciences, 20(2):130- 141, 1963.
[49] I. Loshchilov and F. Hutter. Decoupled weight decay regularization. In International Conference on Learning Representations, 2019.
[50] 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-32,, 1982.
[51] M. Mitzenmacher and S. Vassilvitskii. Algorithms with predictions, 2020.
[52] H. M. Möller and B. Buchberger. The construction of multivariate polynomials with preassigned zeros. Computer Algebra. EUROCAM 1982. Lecture Notes Computer Science, pages
24 31. Springer Berlin Heidelberg, 1982.
13

---

[53] H. Park and G. Regensburger, editors. Gröbner Bases in Control Theory and Signal Processing. De Gruyter, 2007.
[54] D. Peifer, M. Stillman, and D. Halpem-Leistner. Learning selection strategies in buchberger's s algorithm. In Proceedings of the 37th International Conference on Machine Learning, ICML'20. Jorg. 2020.
[55] N. Pelleriti, M. Zimmer, E. Wirth, and S. Pokutta. Approximating latent manifolds in neural networks via vanishing ideals. 2025.
[56] S. Ross, G. Gordon, and D. Bagnell. reduction of imitation learning and structured prediction to no-regret online learning. In G. Gordon, D. Dunson, and M. Dudik, editors. Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, volume 15 of Proceedings of Machine Learning Research, pages 627-635, Fort Lauderdale, FI., USA, 11-13 Apr 2011. PMLR.
[57] 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.
[58] H. Stewenius. Gröbner Basis Methods for Minimal Problems Computer Vision. PhD thesis, Mathematics (Faculty of Engineering), 2005.
[59] W. Sun, Venkatraman, G. J. Gordon, B. Boots, and J. A. Bagnell. Deeply Aggre 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 Proceedings of Machine Learning Research, pages 3309-3318. PMLR, 06-11 Aug 2017.
[60] A. Suzuki and Sato. 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.
[61] W. Vasconcelos, D. Eisenbud, D. Grayson, J. Herzog, and M. Stillman. Computational Methods in Commutative Algebra and Algebraic Geometry. Algorithms and Computation in Mathematics. Springer Berlin Heidelberg, 2004.
[62] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. u. Kaiser, and Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[63] E. Wenger, M. Chen, Charton, and K. E. Lauter. SALSA: Attacking lattice cryptography with Transformers. In Advances in Neural Information Processing Systems, volume 35, pages 34981 -4999434994, 2022.
[64] E. S. Wirth, H. Kera, and S. Pokutta. Approximate vanishing ideal computations at scale. In International Conference on Learning Representations, 2023.
[65] 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.
[66] 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 552. IEEE, 2019.
[67] 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.
[68] 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- 7 7186, 2024.
14

---

[69] J. Zausinger, L. Pennig, K. Chlodny. V. Limbach, A. Ketteler, T. Prein, V. M. Singh, M. Danziger, and J. Born. Augmenting language models with regression loss on number tokens for arithmetic reasoning. In The 4th Workshop on Mathematical Reasoning and Al at NeurlPS 2024.
[70] T. Zhou, D. Fu, M. Soltanolkotabi, R. Jia, and V. Sharan. Fone: Precise single-token number embeddings via fourier features, 2025.
15

---

A Theory of Oracle Border Basis Algorithm
In this section we provide proofs to lemmas and theorem in Section 3 algorithm.
We begin by providing the full
Algorithm 2: Border Bases Algorithm [BAA and OBBA simplified)
Polynomial system F (J1...., [.) C K[X]
d max 1 Lo t (T,5")) )a Vo + VectonSpaceBasis((F9)..)
2 while true do
C Vi+
C; + Oraclo(L; V.)
Vi+1 < BasisExtension V4, C₁ Li)
if Vi+1 V;; then
Vi + Vi-1
continue
end
10
not Border (arderrasisCheeek44)) V:) then
11
d d- ddd+)
L++ (Tr"*)
// Update universe
13
continue
14
end
else 15
16
C + Ci
end
18
break
end
20
return FinalReduction((V,
The oracle restricted to ls consecutive non-full expansions, after which we fall back one final full expansion to ensure correctness. We continue by stating the correctness theorem of the cracle-guieed border basis algorithm.
BorderBasiscCo corresponds the check if the border of the tentative order ideal L. LT(V) already in C. FinalReduction refers to the algorithm with the same name introduced by (28)
Theorem A.1. The guided border basis algorithm terminates and the oulput is a border basis.
Proof. There are two techniques ensure the correctness of the oracle-guided border basis algorithm, one of which will be stated here. After the oracle has been invoked times, we make one more full expansion. If BasisExtension yields additional generators, we fall back the standard border basis algorithm. This ensures that the output is a border basis, as we could have started with the current iterate and applied the standard border basis algorithm. For this we know correctness, we are done.
A.1 Alternative termination criteria
To avoid computing full expansion all the time, may rely the Buchberger Criterion for Border Basis from [29]. This criteria often a lightweight alternative to the full expansion. We can directly done. If it fails,
apply it to the result of the Algorithm 2 If it yields that have border basis, we go back to the last iterate V; and obtain termination by the standard BBA. In practice, we may combine this approach with learned heuristic, that decides based the size of the tentative order ideal, whether a full expansion is necessary or we can directly proceed to check for the Buchberger Criterion.
Lemma A.2. Assume C needs no further expansion and let O be the order ideal of the border basis ultimately produced by BBA Algorithm [ |V] = |O], then no additional expansions are necessary.
16

---

Proof. Assume towards a contradiction, a further expansion of V is required for termination. Thus, in particular it holds we can add least one element V, increasing its cardinality by 1. But this contradicts the assumption that [C] D O
Setup. Throughout this section we analyse the final stage of computation, where the computational universe L is fixed. Let Vo be the first generator set in this stage and assume the vanilla BBA terminates after full expansions, yielding Vr.
Definition A.3 (Border distance). The border distance between L and generator set V is
d(c,V) "# of full BBA expansions still required for V"" Hence d(c, Vo) = T and d(c, Vr-) 0.
Why conditional error? A k-order oracle may cut the border distance by any amount 8 S min(k, d( C, v.)). I min(k, d(C, } the oracle has missed necessary expansions; if it has made no progress at all. To separate progress from waste we introduce conditional error measure.
Definition A.4 (Conditional prediction error). Invoke a k-order oracle at iteration & E {0,.... ,.....Ty) T). After its & calls let the border distance have dropped by and denote by Q the minimal number of expansions that suffice for an order oracle to make progress The s-progress prediction error is
k-1
<(s) = Σ Oracle(C, Vo-i)l - Q.
i=0
An oracle is ideal if s k and e(s) = 0.
Benchmark:
the optimal expansion sequence. Let OPT the cost (number of polynomial reductions) of an omniscient algorithm that, starting from V., chooses the minimal set of expansions for s subsequent expansions, decreasing the border distance by s.
Theorem A.5 (Cost gap to optimal). Consider final-stage instance with universe L. order ideal O and invoke a k-order oracle at iteration t. If achieves progress s with conditional error e(s). then
cost (OBBA))))) OPT
e(s) + max s, 0} -11)
Proof. We analyse the overhead by distinguishing two components: The first component is directly given by the prediction error as it determines how many more expansions done than necessary. By definition, the prediction error is e(s) Vi |Oracle [, Ve-+)l Q and Q is the cost of the optimal expansion sequence. This covers cost difference for the first iterations. Suppose now, that T- 0. Then, the algorithm terminates and no further error incurred. Otherwise, we might incur an additional cost for having expanded the generator set V too much without reducing the border distance beyond The size of constructed generator set is at most [C] - We know that from the optimal expansions, after k - expansions, the set V has at least the size of the generator set that was predicted by the oracle. Therefore, there are most incur the higher cost which are upper bounded by na (O) times per expansion.
remaining iterations that
L
The overhead therefore consists of two terms: the first grows linearly with the prediction error, while the second reflects a hidden cost for making only progress Specifically, if the oracle expands the generator set V too much without reducing the border distance beyond 8, we incur additional cost in the following T t iterations. This theorem is practically relevant, as it further justifies the use of the k-order oracle in the final stage of computation. Being conservative with the use of the oracle (i.c. such that T is smaller than k), avoids the worst case additional cost.
B Border basis sampling
B.1 Order ideal sampling
We introduced the overview of order ideal sampling in Section 4.1.1 This section presents the formal algorithm of the order ideal sampling given The extension to general n-dimensional case is based on the same idea, but it requires a more careful formalization than may expect.
17

---

Recall our idea. A finite set of terms O is called an order ideal if for any E O, its divisors are also all included O, Importantly, for any terms &, t2 E T, the term set O := fall the divisors t.) is an order ideal for each i, and their union ig = Ot U Ot, is also an order ideal. We sample order ideals based on this observation. During the iterative process, we maintain list Q of cells. At each iteration, we pop out cell C' from Q, and split it to generate new cells. The cells with sufficient size are appended to Q, and this process iterates until Q becomes empty.
We now formalize this idea. From now on, we work on the exponent vectors of terms, We denote vector v E N" with a replacement of the i-th entry with a scalar p E N by vli+pi A cell a tuple of segments and an intersecting point p E N
Definition B.1. Let a, b E N The following set is called the segment of them.
Aaa, b) (r (n))
N min(a;; b,) S r, max(a;; bi), i i= 1, ,,...,,.... n). (B.1)
The maximum point of the segment is defined by A(a, b) (max((1 b1),.... max(an bn))) and the minimum point (a b) is defined similarly.
Definition B.2. Let A....., An be some segments such that A -A. l. The cell is tuple C' = (f - ))) and is called the intersecting point. Further, the maximum point of the cell is u (ui...., un) T E N",, where u, min( (i....... A;- Aitl..... Ans) for i = 1,..., The cell is called valid if and has at least two different entries, and max;e(1.....)) 04 4 2
(),
Let d = (di...., dn) E N" be the vector of the maximum degree of variables. The initial cell defined by Co- (1 d 0), and let Q [Co]. R be lists. Then, repeat the following until Q becomes empty or the number of iterations reaches the predesignated limit (if any).
1. Select cell C ((4))_11)
Q and remove it from the list.
2. Sample vector p (p1 (P....., PT) T E N" with pt E [4, u.] for i ,,...,7h. n2
3. Append tuple (l. R.
4. For ,,,.., n. obtain new cell Crew (14 ] j='' (it- where A
A A | A for j * i and otherwise ATT A(l,p). Append C.ow to Q it
a valid cell.
We then have an order idcal
O x
a U XlI
(B.2)
(I.))E
Theorem B.3. The order ideal sampling algorithm terminates within a finite number of steps.
Proof. Termination. We prove that the order ideal sampling algorithm terminates after finite number iterations.
Let C = ((.)).)))) 1) be cell, and denote its maximum point as u (u1...., M.). In each iteration, the algorithm pops one such cell from the queue Q, samples a point p E X w.). and generates at most n new valid cells Cnew ....,Cree tnew
Case 1: * I. For any i, the new cell Cneww contains at least one segment that is strictly smaller than the corresponding one in C. In particular, its i-th segment A = Al, p). which has length zero in coordinate j if p,- 1j. and is strictly shorter otherwise. Therefore, the total number of exponent vectors C.ew is strictly less than that C.
Case 2: p p=pp2 L. For any i, the new cell Crew becomes invalid. Indeed, let u' (u(,..., 4(,) be its maximum point. Since A.ew upper bounds both equal to 4g we have u/g = l/ for all k. This violates the validity condition, which requires that 1 jf and max,(w; 4,) 2.
by construction, and for all l & the k-th segment has lower and
Therefore, either case, the number of valid cells does not increase: Case generates strictly smaller valid cells, and Case 2 generates no valid cells. Moreover, since the exponent space [0, d1]
18

---

[0, d,) is finite, and each valid cell corresponds to distinct subregion defined by its segments, the total number of distinet valid cells is finite.
Hence, the queue Q becomes empty after finitely many iterations, and the algorithm terminates.
Empirical results. Figure 5 shows gallery of randomly sampled order ideals in the two- dimensional case. As can be seen, it involves diverse order ideals.
B.2 Border basis construction from order ideals: Proof of Theorem
Definition B.4. Given set of points P ........ p K", with gentle abuse of notation, the evaluation vector of a polynomial h E [[X] is defined by
h(X)= (h(p)) h(p.))' E EK"
For set of polynomials H. = { hyd C. K[X], the evaluation matrix is defined as H(P) = (Pi(P) ... hy(P)) E K"XM.
The proof of Theorem
4.2 immediately follows from the following lemma.
Lemma B.5. Let O (o1.....0p) C Tn and G C K[X] be an order ideal and its O-border prebasis, respectively. Ler P C K be set of points. If the following hold,
1. .r K
2. 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 G is border prebasis and (obviously) generates (G), so we only need to show that K[X] (G) @ (O)x holds. The border basis division algorithm (28) allows
represent any polynomial f K[X] as f g + with some E (G) and h E (O)a, which implies K [[X] (G) + (O). Note that this algorithm only requires to be border prebasis (not necessarily a border basis). From the first assumption, or (P), ..... .P form basis of K", and thus, h (0)x has h(P) = 0 only when h = O. Noting that Vg E gG)
0 from the second assumption, we have (G') n (O) {0). Thus, we have K[X] = (G) + (O), and G' is the O-border basis of (G).. Furthermore, the fact that I(P) n (O)x = {0} implies I(P) C (G). With the second assumption, we have I(P) = (G). and thus, G is the O-border basis of I(P).
Theorem 4.2. Let (o.....,op)) and do (bi..... bu} be an order ideal and its border, respectively. Let P {PI...., pv} C K" be set of v distinct points. Let
(b(()) (pt) (p() ... or(Pi)
M(P) = (8O(P) O(P)] =
E <Kux(utU), (4.2)
b.(p)) ... (p.) op(p.) (p
If OPP) full-rank, the nullspace of M(P) is p-dimensional and spanned by (w:) where v; (0, .0,.... 1.... 0, Ca1 .... Civ) with the first μ entries being zero except for 1 in the i-th position. The set {g: = b; E/ Ci50j Vi is the O-border basis of the vanishing ideal I(P).
Proof of Theorem 4.2 The existence of such basis set (b:)i_ readily follows from the assumption that ((P) is full-rank. The second statement follows from Lemma B.5
4.2
19

---

B.3 Comparison with Buchberger--Mülle-aannii algorithms
The Buchberger-Mölle (BM) algorithm 2 52 is a method that takes as input a set of points P and computes Gröbner basis of the vanishing ideal [PP.. This algorithm has been extensively studied and adapted to a variety of scenarios, not only in computer algebra [T 2 9 16 23
34 46).
but also in machine learning 25 33 39 47 55
64 [65.
Border basis variants of the BM algorithm allow us to sample border bases from randomly generated sets of points and a term order x. However, only a restricted class of border bases can be sampled in this way. Recall that a border basis G = {g1.....50 ..) J is associated with an order ideal O, and for each border term b; 80, the corresponding border basis polynomial takes the form
9: bi Σ cet E K[X], where e K. 1E0
(B.3)
Remark B.6. The O-border basis G = (91......01 3ss produced by BM-type algorithms with a term order < is a special case satisfying (g)))) = b, for all i ,, 8. That is, the coefficients e vanish for any /. E O such that / > 6;. Due to this algebraic constraint, the collection of such border bases forms Zariski-closed (i.c., measure- zzeour subset in the set of all border bases.
Such special border bases can also be characterized as those admitting some order ideal O for which there exists an "O' Gröbner basis" G" generating the same ideal, satisfying LT( [K]] ( = O. While border bases are defined with respect to an order ideal O Gröbner bases are defined with respect to a term ordering. The former is strictly more general notion in the zero-dimensional case. For instance, one can find examples border bases for which no corresponding Gröbner basis exists [9]
C Backward transform
C.1 Proof of Theorem. 4.5
Theorem 4.5. Let K be a field of characteristic 0, I a zero-dimensional radical ideal of K[X], and d a positive integer. Let G E K[X]* be generating set of and F = AG E K[X] a set of polynomials given by a generic matrix A E K[X
1. I and G is a Gröbner basis, we have (F) + (G).
2. Ifr n1, 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 E K[X When 2 n, (F) (G) J for some ideal J. r = n, then J # K[X] for a generic matrix A E K[X] and thus (F) + (G). If r 2 then J = [[X] for generic matrix A E K[X] and thus (F) (G).
To prove (AG)- (G) for generic matrix A E K[X]Ø* we consider parametric matrix A. Let hig = =I jalgd ia.ij X be parametric polynomial of total degree d with parameters Ga,ij and A = (h2z) an r x s matrix with hu as (i,j) entry. Let A = {a be the set of all parameters of Á and D the cardinality of A. For a generating set G = (9I......h .9. of a zero dimensinali radical ideal I, let f, = Ei= hyggt for j E (I, that is, AG = {fi..... f For subset in a ring R, we also write (5) n when we emphasize that (S) is an ideal of R. Obviously, K[AX) C ([))) For a point q E KD, we denote by ag the substitution map from K[A, - K[X], where (,((( = f(1, X). Then, A = ===a(( (A) = (o,(hig) E K[X] a generie matrix for generic q E KD, Thus, it is enough show that there exists dense set C of KD such that (a,(A)G) (G) for any E C. As (A)())) c (G) always holds, the inverse inclusion implies the equality. First, we recall some fundamental notions of Commutative Algebra as follows.
20

---

Definition C.1 (Primary Decomposition), Let I be an ideal. A finite set of primary ideals {QI..... Q13 is a primary decomposition of Z if I Q1 n.... Q. A primary decomposition (Q1, Q1) of I is said to be minimal if the length / is minimum among all primary decompositions of I. For minimal primary decomposition (Q1,... , Qi} of I, each element Qi is called a primary component of I. In addition, a primary component Qi is said to be isolated if vQi & vQz for any j * i, where VQ; is the radical ideal of Q;-
Remark C.2 (7. Corollary 4.1 1). The isolated primary components of I are uniquely determined from I. In other words, they are independent of particular primary decomposition of I.
Independent sets are useful tool compute the dimension of polynomial ideal. Definition C.3 (Independent Set). Let U be subset of X. For an ideal I of K[A, U is called an independent set mod I if n K[U]- = {0}.
Remark C.4 (21). Theorem 3.5.1 (6)). The cardinality of an independent set mod I is less than or equal to the dimension of In other words, if [U] > dim(I) then U is not an independent set mod I.
Let be the inclusion map :: K|A, + K(X)[A) such that <(f) f. For a prime ideal I of ((X)[A) the inverse image=- (Z) =
IIKKA, X] is also prime as follows.
Lemma C.5 ((8), Lemma 1.123). Let I be a prime ideal of (X))AA) Then, In I[K,A is prime ideal of K[A, X].
The following lemma is simple method for determining Gröbner bases under a certain condition.
Lemma C.6 (8). Lemma 5.66 and Theorem 5.68). Let > be a term ordering and G = [gr..... gs}- If (M())) and LM(g;) are disjoint for any i + j E {1, (1,...,,)) then G is Gröbner basis of (G) with respect to >
Recall that I h = {f E K[A, fh I) is the ideal quotient of an ideal I with respect to polynomial h of K[A,X] The ideal quotient can be used to break the ideal I into two ideals as follows.
Lemma C.7 (11). Lemma 3.3.6 (Splitting tool)). Let I be an ideal of K|A, X] and h polynomial of K[A, X]. IFI : = I: : h2, then I = (I h)) (I + (h)).
Lemma C.7 is often used in conjunction with the following lemma, i.e., I = (I hmmh) n (I + ()m))) for a sufficiently large integer m.
Lemma C.8 ((11, Proposition 4.3.1 (2)). Let I be an ideal of KIA, X] and U maximal independent
set mod I, that is, U is an independent set mod I with |U| = dim (I). Let S= {TI, .., 77) C I C
K KIA,X X] be a Gröbner basis of IK(U) X) \ U] and let h = lcmm (TI),..... L,,...,,,,,,,, (T)) E
K K(U). Then, [UAA))AUUX X) NU]]K(A,A, = I: hm for a sufficiently large integer m.
Let PTD D be the set of all terms of K[A]]. Then, PTD x Ta = {A=X8 A E PT D. X e
T is the set of all terms of K X.. For term ordering >x on Tn and >1 on PT D. the product ordering > xxx is the ordering such that A X >xxA A "X", = X and A >
if X >x X or A A02". In contrast, the product ordering > Axx is the ordering such that A 8 A 2 X
A >A A or "A" = and X >x X 222, For a product ordering >Y, we denote by LCy, E K[Y2] the leading coefficient of f in [Y))) with respect to Yy for f K[Y,, Y2). We also say that > is block ordering with Yi >> Y2. Let v(J)= E KD f(4) = 0, Vʃ E J} be the variety of an ideal J of K K[A]. The following lemma is useful when considering Gröbner bases for specialized parametric ideals.
Lemma C.9 (160), Lemma 2.2). Let G be a Gröbner basis of an ideal (F) in K[A, with respect to a product ordering > XXxA- If (LCA(())) # for each g E G \ K[A), then for any q E V((Gn K{A)) c KD, (G) is a Gröbner basis of (F,(F)) in K[X] with respect to x-
We recall that the codimension of an ideal I of K[)), denoted by codim (I), is equal to Yl-dim(Z)) The following lemma can be used to check the radicalness of unmixed ideal over field of characteristic 0.
Lemma C.10 (66] Proposition 3.65). Let K be a field of characteristic 0 and I = (gi,.... 9n) an wnmixed ideal of K KIA, X), i..,, all the primary components of minimal primary decomposition of I
21

---

have the same codimension. Let be the codimension I and Jac(g).......)) ( (..))))))))) Jacobian matrix of (9 with respect to X U.A. Then, the following conditions are equivalent.
o(x.A) the
1. I is radical,
2. there exists a X e minor determinant J of J.. such that I I.
The parametric ideal (AG) (Ji,...; satisfies the following properties. Proposition C.11. Let (AG)e ((XI) and (AG) (AG) n K|A, Then,
1. (AG))e is prime ideal of K].
2. AG is Gröbner basis of (AG)" with respect to an arbitrary term ordering on [A)
3. Fix a term ordering > on [X)] For = lemmmmm (f1) LC, E K [[X] and
sufficiently large integer
(AG) = (AG) :h"
4. codim((AG)) n. and codim codim((AG))t) If 2 n. then (AG)es &f (G)KAAXI
Proof.
1. Since AG is a set of linear polynomials over K(X), (AG) is prime ideal of ((X)[A). By Lemma C.5 (AG) K[A, X] is prime ideal of K K[A,X]
2. Since and fj do not have common variables except X, LM(f)) and LM(f;) are disjoint for any + j (1....,r) r} with respect to any term ordering on K ((X)[A]. Thus, by
Lemma C.6 AG is a Gröbner basis of (AG)" with respect to an arbitrary term ordering on [A
3. Since X is a maximal independent set mod (AG) and (AG)a = (AG) =
(X)))(X)[A) we obtain the equation from Lemma C.8
4. Since (G) x[]] is zero- dero-diimnsional ideal of K[X),
codim (() = codim ([)] = n.
As (AG)xLA.X [G) codim (AA)) S (AAG) K[A.X)) codim( (AG)ec) = codim( (Ad))((AG))) and AG consists of independent r-linear polynomi- als over [A)) codim ((A))<s) = codim((AG))) = =. Assume 2 n. Then If (AG) C (G).) then (AG)ec K[) since (AG)ce is prime ideal by (1). However, this implies (AG)* contains unit 91 G in K(X) and thus (AG) K[A)[X}, which contradicts (1). Therefore, (AG)es & (G)x
n. Since
codimi (AG)EC) 2 (alim((G))AAxx))
The parametric ideal (AG) can be decomposed into two ideals as follows.
Proposition C.12. I 2 n, then there exists an ideal J of K K[A, X] such that
(AG) = (G') n.
and codim(J) 2 min(r, n + 1). Moreover, if n, then n KKA) * {0).
Proof. Let P = (AG)ec respect to a = 0 of aaagXa in ha.. For i E st.. let >; be a block ordering (d0,1;; 00.21. 0o,ri) xix fao,1e, ag.ii...... .0.rr. on (A)) For each j E (1...., r). the leading term of f; Ei Ex=I hinOk is g:a0.ji in [X)]AA] with respect to > since g: is the only term of f, that includes au.j.. Thus, LC,, (fz) 9: with respect to > for each j and lem(g.... .9) 9:- By Proposition C.Il (3) and Lemma C.7 p
(AG) n K[A, X]. Consider the parameter dn.ij with
(fi), LLC,, (C,,(f.))
a prime ideal of K[A, X] and, for each
P (AG) g. and (AG) P n ((AG) + (g."))
22

---

for sufficiently large integer m. Here, P / (AG))) since otherwise p P= --V(AG) C VG
(G) (as (G) is radical), which contradicts Proposition C.11 (4). Thus, (AG) + (, contains at least one isolated component of (AG). Let (AG) + (o Q1 n.....n n be a minimal primary decomposition of (AG) + (g Without loss of generality, we may assume that Q1.-.., Qs are isolated primary components of (AG) and QK+1,..., Qr are not for some 2 1. Since isolated primary components are uniquely determined by Remark [C. Qi...., Qk are also isolated primary components of ((AG) + +(0T)) ()o)), )..") ((AG) + (9."")) As Q1 2.n...ne NQ 3 (AG) + (gf")) for each i, (G).m, Since (AG) = n.. C (G) and P P nu.-nQu & (G). it follows that Q1 0 .... n Qk C (G). Thus, (G) (() = ((G)om C VQ n...... nQ. vQnn.... iQQ.n..-y -n Q (G), that (G) QQn...-QV is minimal primary decomposition of (G). Let H = Q1 n.... n Qs and show that H is radical. As (G)) k[X] is a zero-dimensional radical ideal of K[X] (G) is a n-coddmennsional unmixed radical ideal of K[A, By Lemma C.10 there exists such that (G) : f = (G). Since (AG) C H, there exists generating set Gи of H such that GH [fi...., Ta Tu] for some Ti,..., Tu E H.
Qi n NQx 5
a n x n minor determinant f of Jac(gi......
(Jac(AG) for some B E X[A,X]"X(++)). As (AG) 5 G for some B
Then, Jac(Gn)
E KP, there exists an X n minor determinant g of Jac(G such that a (,(g) = f. If g * H, then g E vQ; for some i E f1...., k}. However, this implies og(g) = f (v(v.) = Qi and (G) f Q1 n.... Qi-1 n Qi+1 n... n Qx * (G), which contradicts (G) f (G). Therefore
H g = H. Since H is an n-codimensional unmixed ideal of K[A, X1. H is radical by Lemma C.10
Then, H = VH= vQi n.... n....nye QyQ: (G). Letting J = P n Qx+1 n.... n Qt it follows that (AG) = (G) By Proposition C.11 (4), codim(P) = 2 Since Qu+I..... Qi are not isolated primary components of (AG), codim (++1), codim((.) 2 + 1. Therefore, the codimension of J is min(codim
(odim(Q++1) .... (Qi) 2 min(r; n 1).
r > n, then min(r, n + 1) = n 1 and dim(J) < (D + n) - (n+ D - 1. Thus, A is not an independent set of J since AA| D D-1 dim J) by Remark C.4 that is, JnK[A] # {0}.
Recall that V(J) = {q KD f()) 0, J} is the variety of an ideal J of K[A]. If J is nonzero ideal, V(J) is variety of dimension D - 1 at most and thus KD) (JJ is dense set of KD. Finally, we obtain the proof of Theorem 4.5 as follows.
proof of 4.5 case r < n, (AG)+ * (G) since codim codim((AG)) = < n = codim( for there exists an ideal J of
any K[X]<A- Thus, we assume that 2 n. By Proposition C.12
K K[A, X] such that
(AG) = nJ)
1. Assume that r = n and G is a Gröbner basis with respect to term ordering > x on K[X]. Then, for each i E (1....,n) n), there exists 9k, E G such that LC,, (9k,) xthh for some positive integer d;. For simplicity, we may assume that kj = 1,...,k, kn Let u, = (O...., 1,. ........)) be the i-th unit vector in K", Consider the parameter auq.i with respect to X': = in his for each i. Fix a term ordering > such that {1m,, (d...11...55 ...,, an.. >> A) (au,,11,., ann on K[A). Let > be the product order- ing > AxX. Then, LT~ (hx)) = LT> LT>(au,,.)))) (au, HI.g:) = aa -1 for each i E {l,...,m} n). Since LT (hI1),.... LT> (hrn) are disjoint, AG is a Gröbner basis of (AG) with respect to > by Lemma C.6 For any non-zero polynomial w(A) E K[A], w(A)g1 & (AG) as LT, (w>())))
di
LTy (W(A))LT> (01) LT, (w(A))a is not divided by any LT(H1),.... LT(hmn). Thus, such non-zero polynomial w((A) is not J; otherwise ((A)g: E J (G) C (G) JJ = -AG)). Hence, J Jnn K[A] = (P n Q++1 0 ..... n Q K[A] = (0), where P, S.Q4I....,, Qi are ideals in the proof Proposition C.12 Since codim( Qk+1).....
codiim codiiood@))). > n, Q. A {0) for each i E (K +1. J.. There-
fore, (P (PQQu1nn -nn).nn
= {0} implies Pnk [A] = {0). Let G"
{ ........ 9
be the reduced Gröbner basis of P with respect to a block ordering
لاا A. Obviously,
G' n [[A] {0}. Then, letting H = lem(LC
(C)())) # 0, og (G') is Gröbner
basis of (P) for any q V(G n K(A)) (HH) = KP (HH) by Lemma C.9 Fix
23

---

E KP (HH). Since (AG) P.
(o₂(A)G) C og(P)) + K[X].
As P P [[] there exists y E [G) \ P such that (g) & LT, ((G)) This implies (g) (g,)) & (1 (Tx = LTy,(a,(P)) since g (g(g) and (G')") is a Gröbner basis of og with respect to >' Thus, g E (G) \ (P) and (G) @ og (P). As (A)G) C (P)) we obtain (A)()) # (G). With H + 0, KD \ ((H)) is a dense set of KD.
2. Assume that r > n. Then we can take J with J Jn K[A] * (0) by Proposition C.12 Fix
q E KD) [(JnK[A) [[A). Then, for 0 o f(A) E Jnk[A, (A), it follows that 0 + f(1) E (J), that is, (J) K K[X]. Since (G) J C (G) nJ - (AG) and ((G)) (G),
(A)(A))) = og (AG)) - (G) J) = =)((()) (J( = (G).
Since (A)G) C (G') always holds, we obtain (o,(A)G) = (G). As J n K[A] # 0.
KDY ((]NK(K]]] is a dense set of KD.
Corollary 4.6. Let d and dmax be positive integers. Let K = F, be finite field of order p for prime number p and let G be a subset of F [x] Idmas such that (G) is a O-dimensional radical ideal
of F [X], Assume r >> n and let 9 = {A E 12 I (AG) = (G) }. Then, a generically sampled A E F 2X satisfies (AG) = (G) with probability
<d
2 21 d'
Pr(p) = FX
(4.4)
P
for some positive integer d', which is determined by d and dmax independent of any specific p.
Without loss of generality, we may assume that G t......, 9- C 2[X]. Ā E L[A, X]rx* AG (Ji..... (r) Z[A,X], and (G)a is a O-dimensional radical ideal
proof of Corollary 4.6
of X]. By Proposition C.12 there exists an ideal J of Q[A, X] such that (AG): = n and [ #
(0). For a subset I. of L[A, X), we simply write (L)q = (L) q[A.X] and (L), (6)(L)) [A.x] respectively, where Φ, : Σ[A, X F [A, the canonical projec- tion. Let Qu+1...., Qi be ideals in the proof of Proposition
(L)
that is, J = PnQ n..
Then
(AG)Q :
(( (Q)): (G)
= =(G)) (P: (Q++1: (...))..n)))) (G)a)
=P (G.))).... (G)a).
Fix block ordering X >>> A. For new variables T= (4,,.. ---11) } and y. let = 91 + g241 ... -../a-1 E Q A, X]. 5 = {y/1..... .ff (1 - y) C Q T, A, X]. and Gg a Gröbner basis of (8) (.. with respect an extended block ordering {/} >> T>> X >> A. It is known that G' ([T A.A.))))) x "n] A, X] is a Gröbner basis of (AG) (G) with respect to > (see Lemma 1.8.12 12 in (II).. Since an upper bound of degrees of reduced Gröbner bases can be decided from degrees of the generator, there exists d' such that d' > deg(g) for any g E G' derived from any and A E 2[X] In other words, d' is determined by d and dmax, independent of any specific p. Let E (AA)) (G)a) n (Z[A]) \ PZ[AI) then deg f < d' and (p(()) * O. Since (Qi...., Q1) is minimal primary decomposition of (AG) + (of") ). for each i E {1: + 1, ... !) (G)g nQk & Q, and thus Q, (G) is a primary ideal with VQ, (G) VQ, Hence, / (AG)a (G) (()))=)))(00
G E ZIA,
Pny((K+) (Qk+1= (G)a)..... - (Q:: : (G)) = Pn / Q n... n VQi = VJ and f E vJ, i.e., fM E J J Z[A] for some positive integer M. Let fp = 2p( E FP((A and Jz. = JNZ[A, then P.M E (2(AAnZ)))) Here, (AG), 5 -0 since (AG) 5 (G)a
JU (G)a Jz. For E F with fo(a) # 0. (e = IF [X]]] as 0 # f/ (q) E (g())( and
24

---

thus 0g (AG))) S og((G)p -
= (G)r, Fp|X] = (G),,[X)-
As the inverse inclusion obvious, we obtain og (AG) (G)r,Ix] for any q E FP (fp)) Since Sp has at most deg(Sp) (p))p- S deg(s)p S d' p solutions in IDD (see Theorem 6. 13 in
d' and this goes 1 for sufficiently large p. (FD)((D)) pd p--dp0-1 p
45 Pr(p)
C.2 Empirical results
We conduct numerical experiment to justify our backward transform based Theorem 4.5 The
border basis generation and sampling for backward transform follows the main experiment of training the Transformer oracle. See (.2 Figure shows the success rate of having F = AG such that (F)) = (G). As Theorem 4.5 and Corollary 4.6 suggest, the success rate is zero for F = n and for F improves with larger p, and [F].
D Monomial embedding
D.1 Implementation details
We here elaborate the implementation details of monomial embedding method. First, recall the definition.
Definition 4.7. (Monomial embedding)) Let Σ be the set of all tokens. Let (t, <+>) be pair consisting of a monomial & co & Ta with coefficient c E K, exponent vector a E 850 and a follow-up token <*> E Σ. Let SPe. PP., and for denote embeddings of the coefficient, exponent vector, and follow- up token into d- d-dimensional space, respectively. The monomial embedding Pm TT x E + R is given by
(m, <>>) (p(()) + (a(a))) <p((<>>)
(4.6)
Embedding maps. The embedding maps fc and yor standard token embeddings implemented using trainable embedding matrices. The former is used for coefficient tokens, while the latter is used for special tokens such as [SEP] [PAD].
The embedding map S designed to handle exponent vectors and conceptually realized using independent embedding maps, for each variable. Specifically, the i-th embedding map
pp processes the exponent token corresponding the variable z;- Given an exponent vector (a.....: an), its embedding is computed as
(i)
(a)
1
2 (1) (a:).
(D.1)
Unembedding. After processing the input embeddings, the Transformer outputs are passed through an unembedding layer before reaching the classification head. Since our tokenization scheme based on monomial embeddings reduces the number of tokens to approximately 1 1/(n+11 of that in the standard representation, the unembedding layer restores the original token structure prior to classification. RR'
Concretely, the unembedding can be implemented by linear transformation which is applied to each embedding vector to expand it back to a sequence of (n + 1) vectors. This operation reconstructs the original token alignment, making it compatible with downstream tasks such as sequence classification or generation.
The <bos> token. The Transformer decoder requires the right-shift operation. To this end, we append, e.g., <bos>, to the input sequence before monomial-tokenized. As consequence, have n + redundant tokens; these token can be simply eliminated.
D.2 Empirical validations of monomial embedding
Task. Given a list of polynomials fi,..., fr E F,lmi,..., Nn), the task compute their cumula- tive products f1, fif2. ... Ii ft.
25

---

Table 3: Comparison between baseline (infix tokenization) and proposed (monomial tokenization and embedding) methods across different numbers of variables. The success rate measures the successful generation of complete cumulative products.
# Variables
Method
Success rate (%)
GPU memory (MB)
infix
33.9
4,302
monomial
39.7
1,678
infix
37.5
11,296
monomial
44.6
2,408
infix
38.8
23,632
n1 =
monomial
47.3
3,260
infix
22.0
27,442
7==0 5
monomial
53.7
3,424
The polynomial product task requires the model understand addition and product, and thus this is a basic symbolic computation over a ring. Several studies have reported that learning symbolic tasks over finite fields is difficult [35 63 Even learning simple parity function f (Z'...., T,,)
{-1,1)m + i== Ti, which corresponds to a scalar product over F2, is theoretically known to be hard [57. However, recent work has shown that regressiee generation can overcome this
m
challenge [37 motivating our adoption of sequential formulation.
Setup. The Transformer architecture and training setup follow Section 5.2 Transformer models were trained on 100,000 samples and evaluated on 1,000 samples. For each sample, the num- ber of polynomials was uniformly sampled from {2, 3, 4). Then, polynomials fi...., fr F7|m1,...,, [x were sampled with maximum degree dmax 4 and a maximum number of terms lmax The sampling follows the strategy given in Appendix E.T except that the polynomial degree was uniformly sampled from U[1, 4max] to exclude the zero polynomial and avoid trivially easy product computations. We tested cases with n 2, 3, 5. We adopted the standard infix representation as a baseline (Equation (4.5).. Note that the Transformer model with the proposed monomial embedding predicts target sequences in the same representation via the unembedding layer. Thus, this baseline setup allows us to directly assess the impact of the proposed tokenization and embedding strategy.
Results. Figure Souree/shww shows the average number of tokens in test samples for both the baseline method and the proposed method. The shaded region indicates the range from minimum maximum. A large gap in both the average and maximum number of tokens between the infix and monomial embeddings can be observed. This gap is also reflected in the GPU memory consumption in Table Notably, the memory consumption of the monomial embedding with = 5 is lower than that of the infix embedding with as indicated by its success rate (i.e., the proportion of samples for which a complete sequence of cumulative products successfully generated). The improvement success rate becomes even more pronounced for larger values of n. Considering the correspondence between monomials is essential in symbolic computation. With infix embedding, the model must establish attention between (n + 1) tokens and another (n + 1) tokens, resulting increased complexity. In contrast, monomial embedding reduces this to one-to-one correspondence, which benefits both memory efficiency and success rate.
The monomial embedding is further advantageous for learning.
D.3 Reduction profile of the input sequences.
Figure completes Figure We analyze the input sequence reduction in the test samples used in main experiments. As mentioned in Section 4.2 we used minimal subset L' E that allows us to retrieve the universe L, which is an order ideal. Particularly, used the corner terms [40], which we define next.
Definition D.1 (Divisibility of Monomials). Let
t= == x 22 x and $ s= x
x
x
be monomials in the polynomial ring K [[X]. We say that t divides 8, written s, if and only if
a < b for all i 1, 1,...,n.
26

---

equivalently, if there exists monomial u such that = tu.
Definition D.2 (Cornr Terms), Let be an order ideal in K[X]. The corner terms L are its maximal monomials, L.e. those L such that whenever & with E L, one has t. Equivalently,
L' (1E (Vs
==
Geometrically, each L' is the "corner" of an axis-aligned hyper-box in N whose lattice points are precisely the divisors of c, and the union these boxes is the entire order ideal.
E
Experiment setup and additional results
E.1
Sampling polynomials.
Random sampling a polynomial from F Edmax with some degree bound dmax is a basic operation in our experiments. Here, random sampling be defined in several ways. The mathematically generic way uniformly sampling the coefficients of polynomial f Lailall] ca is worth noting that in such as case, f almost always dense and of degree d,max.
However, this approach is always reasonable from the practical scenario. The maximum degree dmax can only mean the limit of the highest acceptable degree, and the user-input polynomial can vary between constant to degree-dmax ones dynamically.
Taking into account this, random sampling in this paper is performed by first uniformly samlping the degree and the number of terms of polynomial. Namely, given the predesgianated maximum degree dauxx and the maximum number of terms maxx a polynomial is sampled with ~ U[0, dmax] and Imax UO, Emax), where mmax min (maxx: (*+thmma)) ) and U(a, uniform distribution with range [a, Z.
n
E.2
Comparisons of polynomial systems in literature.
To the best of our knowledge, our experiments cover the largest and the most general class of polynomial systems in the literature of deee-learning based Gröbner/border basis computation 355
54
The experiments in 54 mostly focus 3 variables and binomials (for both input systems and Gröbner bases G).
The experiments in 35 handle up to n = 5, for 1, the mixing matrix of F AG is sparsified to keep the input system size moderate (i.e., to keep the number of tokens < 5000). The design of only supports an input system of size F > |G]. Besides, the ideals are restricted to those in shape position, where G is restricted to size G| n.
Table 4 compares the scale and class of systems and idcals (n 5, numbers are rounded).
E.3 Learning successful expansions
Computational resources. Training was performed on system with 48-core CPUs, 768 GB of RAM, and NVIDIA RTX A6000 Ada GPUs. Each run completed in less than day on a single GPU.
Datasets. To construct the training set, we first generated one million border bases {G,); as described in Section 4.1.1 These were then transformed into an equal number of non-bases {F)); using the backward generator transform from Section 4.1.2 Subsequently. the Improved Border Basis
Table 4: Comparison of the scale and class of systems and ideals (n 5).
Reference
Input system size F|
Avg. #terms in F
Class of ideals/systems
10
20
binomial
42
shape position ([F)
> [G] =n)
Ours
10
130
vanishing ideal ( 2 n,
< GG] allowed)
27

---

Table 5: Evaluation results of Transformer predictions over polynomial rings F, Fp|zi, Fn Metrics are reported for different values of
Field
Variables
Precision (%)
Recall (%)
Score (%)
No Expansion
Acc. (%)
79.4
81.2
80.3
96.3
3
84.1
86.1
85.1
96.0
5
85.66
87.6
86.6
96.6
85.1
86.6
85.8
98.8
F7 = 4
88.4
89.1
88.8
98.8
89.8
91.1
90.4
98.8
91.4
91.9
91.7
99.1
11 5
93.0
93.3
93.1
99.1
93.9
94.6
94.2
98.7
84.4
86.8
85.6
99.7
T2 = 3
89.4
90.0
89.7
99.7
91.6
93.2
92.4
99.7
90.7
91.6
91.1
98.8
F3 4
92.9
93.7
93.3
98.8
94.2
94.7
94.4
98.8
92.7
93.1
92.9
99.6
12 = 5
94.3
94.6
94.4
99.6
94.8
95.3
95.1
99.6
87.8
88.3
88.1
99.7
3
91.3
91.8
91.5
99.7
93.6
93.7
93.7
99.7
92.0
93.2
92.6
99.6
F 127 11 = 4
94.5
94.9
94.7
99.6
94.9
95.5
95.2
99.6
93.1
94.7
93.9
99.6
12 5
94.4
95.8
95.1
99.6
94.8
96.0
95.4
99.6
(IBBA: (29] algorithm was executed on each F.. From each run, we collected samples only from the last five expansion calls in the final loop (cf. Algorithm [ This process yielded approximately five million samples, from which we randomly selected one million without replacement to form the training set. The test set of 1,000 samples constructed in the same manner.
Additional Results.
Table 5 is the complete version of Table The overall trend the same.
E.4 Out of Distribution Experiments
We report results the out- -ittof-disttibution performance of our approach. In Figure and Figure TO we compare the number of fallbacks and the achieved speedup, respectively, across different configurations for n variables. The columns correspond the degree of the transformation matrix A (ranging from 2 to 4), while the rows represent the total degree, increasing from 4 in the top row 6 in the bottom row. Comprehensive results on the out-of-distributin performance for varying degrees are further provided in Tables 9
E.5 Border Basis Bottleneck
To characterize the computational bottleneck of the border-bast algorithm, we measure the fraction of the total runtime spent in the final stage (i.e., the phase after the last universe enlargement) and, within that stage, the fraction attributable to the last & E {1, 2, 3, 4, 5) Gaussian-elimination steps. Our empirical results in Table|TO] indicate inddicate that the final stage overwhelmingly dominates execution time-oo on average consuming about % of the total runtime. Moreover, the last five Gaussian climinations alone account for roughly 70 %-95 % of the final-stage runtime.
28

---

Table 6: Mcan + standard deviation of the number of zero reductions for IBBA vs. OBBA. Here we see an up to 3.5 improvement the number of zero reductions for the in distribution setting with total degree 4 and degree of transformation for = 5.
Field
Total Degree
Degree Transformation
IBBA
OBBA
F7
2
1369.31 613.7
380.15 140.33
F7
1854.63 11422
638.124 200.11
F7
4
3177.67 293036
1746.99. 1992.24
F127
2
1409 00 596.12
390.36+ 155.47
F127
3
2224.25
1025,644 6
F127
4
2510.42 2006.56
1112. 15 119061
F31
2
1324.05 044.05=
361 221.22+
F31
3
2010.02 1364 c8
797.144 695.37
F31
4
3167.66 2592.95
1672.20 1555.12
Table 7: Wall-clock runtime in seconds (mean + standard deviation over 100 random dimensional systems total degree d and max degree 1 of A) for five algorithms over polynomial rings 7, I 122, and F3'1 in variables. "Baseline" comprises BBA and IBBA; "Ours" comprises OBBA, IBBA+FGE, and OBBA+FGE. OBBA+FGE is the fastest in every setting.
Baseline
Ours
Field d
BBA
IBBA
OBBA
IBBA+FGE
OBBA+FGE
2
10.49 +: 7.37
7.16 + 4.55
2.43 1.24
0.86 + 0.46
0.59 0.31
F7
3
26.45 34.13
19.61 + 27.10
8.30 + 12.60
1.88 + 2.12
1.30 1.45
4
156.64 + 581.66
101.22 + 365.21
67.82 + 282.15
7.44 +: 24.82
5,51 + 19.41
13.44 + 8.52
9.04 + 5.34
3.06 1.49
0.49
+ 0.49
0.67 0.31
RR 1227
3
49.90 + 74.57
33.86 + 47.53
20.97 + 34.87
2.75 + 3.14
2.09 2.53
77.89 + 132.87 4
53.57 + 93.82
39.91 + 87.16
4.62 + 7.55
3.47 + 6.23
2
11.44 + 8.25
7.60 + 5.13
2.58 + 1.37
0.88 + 0.49
0.60 + 0.32
Fai
3
40.65
= 76.90
27.36 + 47.71
13.87 + 26.07
2.38 + 3.32
1.66 + 2.35
4
136.68
244.07
97.84 1 173.36
68.77 + 158.72
7.42 1: 12.01
5.63 9.34
E.6 Border Gap vs Border Distance
Detecting the final stage Border Basis computation is critical for the efficiency of the proposed method. We empirically investigate the relationship between border distance, which is unknown in practice, and border gap, which can be an input parameter as we can measure To make the border gap independent of the scale of the problem, we consider the relative border gap defined as T Our results are summarised in Figures to 13 indicating that the border gap is suitable proxy for the border distance.
29

---

Table 8: Wall-clock runtime seconds (mean + standard deviation over 100 random zero- dimensional systems of total degree d S 4 and max degree 1 for each variable) for five algorithms over polynomial rings F127, 31 and 7 = variables. "Baseline" comprises BBA and IBBA: "Ours" comprises OBBA, IBBA+FGE, and OBBA+FGE. OBBA+FGE is the fastest in almost every setting.
Baseline
Ours
Field d
BBA
IBBA
OBBA
IBBA+FGE
OBBA+FGE
2
0.43 + 0.42
0.33 1 0.24
0.20 4: 0.11
0.09 1: 0.05
0.09 1 0.04
1227
3
1,71 2.35
1.29 + 1.61
0.62 1
0.23 0.21
0.24 0.25
4
2.28 = 3.66
1.76 2.56
0.81
0.29 = 0.33
0.29 0.33
0,46 0.43
0.35 0.25
0.13
0.09 = 0.05
0.09 0.05
Fai
3
1.39 1.59
+
0.53
0,21 = 0.18 0.18
0.21 + 0.18
4
4.65
3.64 6.10
2.12
0.51 = 0.66
0.50 - 0.59
2
0.36 1 0.27
0.19 - 0.09
0.08 = 0.03
0.08 - 0.03
F7
3
1.25 = 1.68
0.94
0.48 + 0.57
0.18 0.17
0.18 0.18
4.89 4
11.42
9.99
2.13 = 5.71
0.55 = 0.94
0.52 0.84
Table 9: Wall-clock runtime in seconds (mean + standard deviation 100 random dimensional systems of total degree I d < and max degree 1) for five algorithms over polynomial rings F31, F7, and F 127 for n 3 variables. "Baseline" comprises BBA and IBBA; "Ours" comprises OBBA, IBBA+FGE, and OBBA+FGE. OBBA+FGE (last column) is the fastest in every setting.
Baseline
Ours
Field
BBA
IBBA
OBBA
IBBA+FGE
OBBA+FGE
0.07
0.06 0.09
0.06 0.08
0.03 = 0.03
0.03 0.03
F31
5
0.30 0.76
+ 0.56
0.19 0.45
+ 0.12
0.07 0.11
6
0.42 + 0.77
0.36 + 0.69
0.28 + 0.53
0.10 + 0.15
0.10 + 0.14
0.09 0.14
0.07 + 0.09
- 0.07
0.03 + 0.03 0.03
0.03 0.03
F7
5
0.18 + 0.41
0.15 0.34
0.13 0.26
0.05 + 0.08
0.05 + 0.08
6
0.28 = 0.54
0.24
0.20
0.07
0.07 -07
4
0.06 - 0.08
+
0.05 + 0.07
0.02 + 0.02
0.02 + 0.02
F127
5
0.14 = 0.25
0.12
0.10 = 0.16
0.04 = 0.05
0.04 0.05
0.45 0.70
0.51
0.27 0.39
0.10 0.11
0.10 0.11
30

---

14500
resto
00002
1e500
14800
Order ideal
923
Order ideal 924
Order ideal 255
10
a0g00
expto
explo
dugoo
dight
Oedtrr ideal 025
Order :Seal #27
iSeal 920
Order Ideal 924
Ordeer Ideeal $:00
0000
10
10
expoo
explo
Dedter ideal
iSeal
Ideal #13
Orterr Ideaal #11
Crtier Itfeal $115
10
10
10
34000
rept0
Dedter: idmal #35
iSeal #37
Order Ideal #111
Order Ideeal 619
Crdder Itfeal 6:0
10
Order iScal 041
Order 15cal 042
Order (S03) 943
Order (dcal 244
Order idool N:45
1006
Order Iscal 04G
Order (Sea) 247
Order (Sea) 248
Order ideal 240
Order idool N50
Order iscal 051
Order iseal 052
Order (Ses) 853
Order ideal 254
Order Ideal N55
Order ideal 05c
Ordir ideal 057
Order (Ses) 850
Order ideal 850
Order ideal N00
Figure 5: The gallery of randomly sampled order ideals for n 2 and d (10, 10).
31

---

=3
=
1.0
0.8
Success
0.6
0.4
5
F127
0.0
Size of
Size of F
Size of F
Figure The empirical success rate the backward transform from F without changing ideals. As Theorem 4.5 and Corollary suggest,, the success rate is zero for [F] = n and close to one for [F] > n, and larger field order and number of variables increase the success rate.
Token Count vs Number Variables
3500
Representation
Monomial Reprosentation
2500
Number Tokeens
2000
1000
500
2.0
2.5
3.5
4.0
4.5
5.0
Number of Variables (n)
Figure 7: The average number of tokens with infix and the proposed embeddings.
32

---

All Terms (Infix)
Terms (Infix) TTrrms V (Infix)
Terms & (Monomial) 1 Terms V (Monomial)
All Terms V (Infix)
|=
/
Max Token Count
60351
10r
10007
10x
104
1354
129
26
203 200
407
65
35
182
70
1354
209 209
0223
35
3521
1354
634
209 209
2021
117
35
70
10
10
10
nm
n
nm5
nm
n=4
nmb
n=
n-d
omb
Number of Variables (n)
Number of Varlables (n)
Number of Variables (n)
F3 /31/==1
F5 /=3
Fi 1=5
Max Token Count
104
1434
1434
1223
1434
10a
26
202
66
35
152
70
100
209 209 204
35
489
70
126
200
117
25
70
104
10
n=4
n=5
n=4
n=5
n=4 Number Variables (n)
Number Variables (n)
Number Variables
F12n. /=1
f122. /=3
5127,
Max Token Count
104
64632
$4632
64632
10n
11981
11981
981
10R
10a
1574
129
35
414
1280
489
153
70
1574
204
489 480
1574
127
480 185
912
70
104
n-4
n=5
n-5
n-4
Number Variables
Variables
Number
Figure 8: Reduction of the maximum number of tokens of input sequences with (-leading term and monomial representation.
Hox Degroe A
Mox Dogree
Max Dogres of
Fallbacks to BBA
22
Total Degree
Fallbacke to BBA
20
Total
Fallbark to BBA
Border Gap
Border Gap
Border Gap
Fiz7
Figure 9: Out-of-distribution (OOD) experiment for 3. measured by the number of fallbacks plotted against the relative border gap. Columns correspond to the degree of the transformation matrix A (left:: degree middle: degree right: degree 4), while rows indicate the total polynomial degree, increasing from 4 in the top row to 6 in the bottom row. As the degree of the polynomials increases moving further from the training distribution the number of fallbacks also rises. Invoking the oracle at lower relative border gap increases the number of fallbacks, as the oracle must make more progress to achieve termination.
33

---

Maa Degiee oiA 2
Mai Degree of
Nax Degrue of 444
Specedl 4p0
sperdd
Tasa Degree
Spreet- ua Oil
1.6
Speet-up D4)
spees-up up [x)
spoos-up (X)
Border gap '2
Border gap
Burder gap
F21
F127
citto--distribution (OOD) experiment for 3, measured by the speedup of the proposed method over the baseline. Columns correspond to the degree of the transformation matrix (left: degree 2, middle: degree 3, right: degree 4), while rows indicate the total polynomial degree, increasing from 4 in the top row to 6 in the bottom row. Even a moderate number of fallbacks still allows for significant speedup. For the more challenging settings, the speedup peaks around relative border gap of 0.95, indicating sensitivity to this parameter and reduced oracle performance in harder configurations, while still providing a moderate overall speedup.
Figure 10:
Border Gap Border Distance
Quartiles
Whisker/Cap
0.3
Median
Mean
0.7
Border Cap
dic.
Figure 11: Border gap vs border distance for n over IF
34

---

Table 10: Proportion of total runtime spent in the final stage (FS) of Border Basis computation, and cumulative share of the last & expansions (Lk) within FS, averaged over 100 runs. The final stage typically dominates runtime (> 70%, often >95%), with the last expansions accounting for 70-90% of FS across all settings. Interestingly, the very last expansion already account for about 30% of the final stage.
Field
n
Deg
FS
L1
L2
L3
L4
L5
0.986
0.270
0.516
0.646
0.699
0.721
3
5
0.979
0.279
0.511
0.624
0.678
0.694
0.982 6
0.741
0.893
0.922
0.937
0.944
2 0.976
0.318
0.594
0.738
0.780
0.800
F7
3
0.972
0.275
0.513
0.664
0.750
0.793
0.986 4
0.321
0.558
0.687
0.757
0.785
2
0.969
0.244
0.481
0.678
0.805
0.880
0,970
0.270
0.514
0.704
0.806
0.862
4
0.963
0.301
0.573
0.768
0.852
0.889
0.986
0.285
0.527
0.652
0.705
0.721
3
5
0.973
0.309
0.532
0.638
0.683
0,693
6
0.726
0.448
0.649
0.738
0.781
0.800
0.964
0.303
0.563
0.717
0.794
0.831
F31
4
3
0.980
0.274
0.520
0.669
0.749
0.792
0.963
0.313
0.569
0.713
0.780
0.815
2 0.960
0.326
0.588
0.736
0.826
0.877
5
3
0.970
0.275
0.524
0.714
0.805
0.858
0.568
0,289
0.560
0.744
0.852
0.895
4
0.981
0.287
0.525
0.655
0.708
0.727
0.979
0.284
0.523
0.649
0.702
0.726
0.983 6
0.569
0.759
0.821
0.844
0.857
2
0.992
0.346
0.591
0.709
0.758
0.789
F127
4
0.977
0.317
0.613
0.773
0.819
0.842
0.982 4
0.284
0.546
0.692
0.760
0.786
2
0.992
0.311
0.580
0.745
0.830
0.878
5
3
0.978
0.279
0.520
0.692
0.797
0,866
0.956
0.290
0.558
0.746
0.841
0.891
35

---

Border Border
Quartiles Whisker/Cap Median
Mean
Border
0.4
0.2
Border Distance StC, 19
Figure 12: Border gap vs border distance for n = 4 over F1.1-
Border Border Distance
Quartiles
Whisker/Cap
Median
Mean
EE
Boreer Cap
Distance 6tc. 1)
Figure 13: Border gap vs border distance for n. over Fs1-
36

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and introduction present the scope of the study and its contribu- tions.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We present current limitations in Sections 4.1.1 and
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
37

---

Justification: All the assumptions and complete proofs are provided in the main text and appendix, particularly, Sections and 4 and Appendices
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide the detailed description of the experiment setups both in the main text and appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
38

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes)
Justification:
We provide the link to the code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ praips.cc/ubblic/guuueee CoodeSumeeieeeeee ssi iessonPolll mollicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All the training and test details to follow the results are provided in Section and Appendix E
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: Error bars are not provided for all cases; however, one of the main results, Table reports the runtime along with standard deviations.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
39

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
Information about our computational resources can found Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
We have confirmed the present study meets the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- cration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA].
Justification: This paper focuses on the learnability of a mathematical task, and we cannot see any urgent social impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
40

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper does not have an evident risk of misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA].
Justification:
This paper does not use existing assets.
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
41

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA].
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
42

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: LLMs were used solely as assistants for coding and manuscript editing.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.LM policy battaa///earrrrpc.cc///oooorreep for what should or should not be described.
43


Reviews:
[{"review_id": "4M2p2SsnKK", "reviewer": "Reviewer_y4oj", "summary": "The paper presents OBBA, an algorithm for solving zero‐dimensional systems, which integrates a Transformer oracle into border‐basis computations. The authors show that OBBA has reduced wall-clock runtime, while preserving nearly perfect accuracy. The speed-up is obtained by using the oracle to predict only the necessary expansions in the final steps of the border-basis algorithm.", "questions": "- Can you comment on the originality of the proof techniques used?\n- Can you explain why you chose the number of variables and degree to be up to 5 and 4, respectively, and how you would expect the runtime gain to scale?\n- Can you comment on how you chose the Transformer architecture and on whether you did any ablation about that?\n- In Figure 3, what is the OOD accuracy achieved? Can you also comment on the trend of the number of fallbacks for degree 4 versus degree 8?\n\nI believe there are small typos in line 103 (T_n missing) and in line 94 (caligraphic I?).", "limitations": "The algorithm proposed is limited to finite-sized polynomial systems, since it relies specifically on the border-basis algorithm.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: \n- The paper is well written, and contains a complete overview of the techniques used and comparison to state of the art.\n- Proposing new faster algorithms for symbolic computation is an important direction. The idea of integrating a Transformer-based oracle and analysing its complexity is nice and promising.\n\nWeaknesses:\n- My main concern is that the scope of this work might be a bit narrow.\n- To the best of my understanding, the theoretical proofs, while sound, they assemble previously known facts. I would be happy to change my assessment if the authors do not agree and can elaborate more on the originality of their proof techniques. \n- It seems therefore that the main contribution consists of the reduced wall-clock runtime presented in the experiments, along which the reduction of the input size for making the problem tractable by a Transformer. However, the experiments are for fairly small number of variables and degree. The empirical speedups, although measurable, occur on very small instances (wall-clock times on the order of 10⁻² s). It would be helpful to understand the limitations or bottlenecks when scaling to larger systems\n- It remains unclear which real-world applications benefit from these runtime improvements on such small systems; I invite the authors to elaborate more on these.", "was_revised": true, "final_justification": "The authors clarified the technical novelty and experimental results in their work during rebuttal.", "rebuttal": "We appreciate the reviewer's insightful and thorough review. We understand the main concerns are: (1) Lack of technical novelty in the proofs, (2) Limited runtime gain with our oracle-based approach, and (3) Unclear benefit in the real-world applications. \n\nWe respectfully disagree with the first two criticisms and ask the reviewer to consider the broader context of research development when evaluating the third. The short answers are as follows. \n\n---\n\n### **Key Responses**\n\n1. The theoretical results do consist of the main contributions of our work - the claims are all novel, and the proofs are **non-trivial assembly of known facts** (Any \"novel proofs in math\" assemble known facts.).\n\n2. The best empirical average runtime gain by the oracle is **approximately 30 seconds, not $10^{-2}$ as the reviewer claims**. \n\n3. We acknowledge that success in small systems may not have immediate benefits in real-world applications. Nevertheless, our oracle-based approach and novel algebraic and machine learning techniques tackle **the largest and most general systems in the literature** - a critical step toward real-world deployment.\n\nWe kindly ask the reviewer to reassess our contributions (particularly technical ones) and their position in the literature. \n\n--- \n### (1) Technical novelty in the proofs\n> [...], the theoretical proofs, while sound, they assemble previously known facts. \n\n> Can you comment on the originality of the proof techniques used?\n\nIt is unclear to us which of the proofs the reviewer finds lacking technical novelty. Our work contains three main theoretical contributions. Each of them is novel in problem formulation, and the proofs go beyond a simple assembly of known facts: a) **Analysis of the Oracle Border Basis Algorithm** (Thm 3.1 and Sec. A). b) **Border Basis Sampling** (Thm. 4.2 and App. B). c) **Ideal-Invariant Generator Transform** (Thm. 4.5 and App. C).\n\nThe reviewer probably refers to (c), as it prepares Lemma C5-8 with citations. However, these except for C8 are all textbook-level lemmas, included to ensure clarity and accessibility for readers who are less familiar with abstract algebra. Our proof technique itself is original in that it non-trivially combines the theory of parameterized ideals with primary decomposition. \n\nFor completeness, we address (a) and (b). \n\na) Our novel concepts (e.g., the *border distance*; Def. A.3) enable the definition of a *conditional error* (Def. A.4), which is pivotal in the proof to connect the prediction error and the cost relative to the optimal expansion sequence. The result is not only theoretically significant but also serves as the primary motivation for invoking the oracle only at the final stages of the border basis computations. \n\nb) Border basis sampling is a novel task, and we propose an algorithm to address this. The proof of Theorem 4.2 is its basis. While the proof is not very complex, it solidly derives the arguments by exploiting the definition and characteristics of border bases. \n\nResults (a), (b), and (c) form key contributions of this work. Particularly, (c) extends beyond border basis computation, offering a principled method for generating non-trivial random polynomial systems. \n\nWe hope the reviewer will take into account the above points in reaccessment. \n\n--- \n### (2) The empirical speedup and OOD accuracy.\n> [...] the main contribution consists of the reduced wall-clock runtime presented in the experiments, [...]. The empirical speedups, although measurable, occur on very small instances (wall-clock times on the order of 10⁻² s). \n\nThe reduced wall-clock runtime is only a part of our contributions; we have many technical contributions, partially elaborated above. \n\nBesides, it seems that the reviewer is underrating the runtime gain by the oracle. As shown in Table 6, the best average runtime gain goes up to approximately 30 seconds (IBB vs IBB+Oracle in the bottom row). Note that FGE is also our contribution and a byproduct of this work; thus, it is fair to compare the impact of the oracle independently of FGE.\n\nFurther, our empirical contributions include the generalization of the oracle to the hard, out-of-distribution instances. See below.\n\n> [...] why you chose the number of variables and degree to be up to 5 and 4, respectively, and how you would expect the runtime gain to scale?\n\n> In Figure 3, what is the OOD accuracy achieved? Can you also comment on the trend of the number of fallbacks for degree 4 versus degree 8?\n\n> It would be helpful to understand the limitations or bottlenecks when scaling to larger systems.\n\nWe appreciate these in-depth questions. \n\nWe follow the Gröbner evaluation grid of 5 variables × degree ≤ 4 in [Kera+'24].  Tab. 2 already shows that the classical IBB solver's runtime increases dramatically from 0.06 s (n = 3, d = 4) to 7.6 s (n = 5, d = 2)—an ≈100× increase for just two extra variables. To probe harder cases, we keep n = 5 but raise the degree to 4; this OOD suite pushes IBB to 97.8 s mean / +1000 s max per instance (cf. Table 6).  **OBBA still removes 30 % of those reductions, and—when paired with our fast Gaussian-elimination, the wall-clock time to 5.63 s (17× speedup / 90s speedup)**. The scaling is consistent across $n = 3, 4, 5$ and $d = 2, 3, 4, 5, 6$; see Table 6-8. We expect the runtime gain to scale similarly to larger instances, as the dataset generation would become more expensive. \n\nThe OOD accuracy in Fig. 3 depends on how aggressively we use the oracle. For degree 4, the success rate reaches 95%. For degree 8, which is further from the training data, accuracy starts around 60% but quickly rises above 95% with more conservative oracle use. For degree 4, calling the oracle earlier gives larger speedups because the oracle is highly reliable. For degree 8, the best speedup happens when the oracle is invoked near the border gap $\\frac{|\\mathcal{V}|}{|\\mathcal{L}|} = 0.9$. The lower success rate in this case implies more fallbacks, which reduces the net speed gains.\n\n--- \n### (3) Benefit in real-world applications\n> the scope of this work might be a bit narrow.\n\n> the experiments are for fairly small number of variables and degree. \n\n> It remains unclear which real-world applications benefit from these runtime improvements on such small systems.\n\nWe currently focus on relatively small systems, and the immediate real-world impact may be limited. However, we kindly ask the reviewer to evaluate our contributions within the context of prior studies on learning Gröbner and border basis computation - our study handles the largest and the most general class of polynomial systems.\n\n- [Peifer+'20] handles binomial systems (both input F and output G) with n <= 5 (mainly n = 3). \n- [Kera+'24] handles up to n = 5, the mixing matrix A in F = AG is sparsified for the manageable input size (below 5000 tokens).\n\nThe table below compares the average size of input systems F for n = 5 (numbers are rounded):\n\n|                | Input system size \\|F\\| | Avg # of terms in F | class of ideals and systems | Note                                                  |\n|----------------|-------------------------|----------------------|----------------------| -------------------------------------------------------|\n| [Peifer+’20]   | 10                      | 20                   | binomial |  Most experiments were done with n=3. \n| [Kera+'24]     | 5–7                     | 42                   | shape position (\\|F\\| >= \\|G\\| = n) | From \"Max terms in F\" in Table 6 in [Kera+'24].       |\n| Ours           | 6–10                    | 130                  | vanishing ideal (\\|G\\| >= n, OK with \\|F\\| < \\|G\\|) | Computed from our datasets, will be added in Appendix.|\n\nSolving large polynomial systems is computationally challenging, and deep learning–based approaches have recently emerged as a promising alternative. Unlike [Peifer+'20], we target general polynomial systems (not just binomials), and unlike [Kera+'24], our method guarantees correctness. \n\nMoreover, our **monomial embedding** enables efficient encoding of large polynomial systems for Transformer models, reducing input size by a factor of $n + 2$, and memory usage by $O((n + 2)^2)$. and our **ideal-invariant transform** (Thm. 4.5) provides a principled method for generating random non-trivial systems.\n\nOur work makes substantial contributions across methodology, deep learning techniques, and dataset construction - all of which we believe advance deep learning–based approaches toward solving larger and more general polynomial systems.\n\n---\n\n### Others \n> how you chose the Transformer architecture [...] any ablation about that?\n\nWe adopted a standard architecture from [Vaswani+'17], which aligns with [Kera+'24]. In our preliminary experiments, the number of layers and embedding dimensions had little impact on learning, so we decided to focus on this standard model (with monomial embedding). The ablation of monomial embedding is infeasible, as the input size is too large without it. Instead, Tab. 3 provides ablation with another task, demonstrating that monomial embedding improves training cost and final success rate significantly.\n\n> The algorithm proposed is limited to finite-sized polynomial systems. \n\nThe reviewer may intend \"finite-field.\" Note that this is not a critical limitation. From an algebraic perspective, it is common to solve infinite-field systems through finite-field ones using *modular technique* [Arnold'03]. From a learning perspective, learning in an infinite field is far easier, as many studies have reported. We kindly ask the reviewer to consult our response to Reviewer C42S (\"Finite field only\").\n\n--- \n- [Peifer+'20] Peifer et al., \"Learning Selection Strategies in Buchberger's Algorithm,\" ICML'20\n- [Kera+'24] Kera et al., \"Learning to Compute Gröbner bases,\" NeurIPS'24\n- [Vaswani+'17] Vaswani et al., \"Attention is All You Need,\" NeurIPS'17\n- [Arnold'03]  Arnold, \"Modular algorithms for computing Gröbner bases,\" JSC, 2003"}, {"review_id": "Obw37cSW8M", "reviewer": "Reviewer_CaQ9", "summary": "Solving systems of polynomial equations is a foundational problem in mathematics and many other domains. Classical methods like Gröbner and Border bases provide a way to search for solutions but are computationally intensive. The paper introduce the Oracle Border Basis Algorithm (OBBA), which provides a way to efficiently searching solutions for zero-dimensional cases. They use a lightweight Transformer oracle to predict and eliminates unhelpful polynomial reductions, which significantly reduce the computational overhead.", "questions": "please see the weakness section.", "limitations": "yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Pros\n1. The idea is novel s.t combining ML/DL with rigorous math problem is relatively new and rare in the domain.\n2. They designed an interesting way to train a Transformer with customized tokenization and embedding.\n3. The method shows a noticeable increasing in speed without compromising accuracy and can be generalized to OOD.\n\nCons\n1. The method is only constrained to zero-dimensional problems and can’t be generalized to positive-dimensional cases.\n2. The decision of when to invoke the oracle is heuristic and could benefit from theoretical analysis or learned policies.\n3. Even though the experiment shows results up to 5 variables, but the scalability to higher-dimensional or real-world symbolic problems remains unclear. Has no theoretical guarantee.\n4. It would be interesting to know if we randomly prune the search tree, how would the performance looks like.", "was_revised": true, "final_justification": "Thank you for your response. I keep my score.", "rebuttal": "We are grateful for the reviewer's thoughtful comments and the clear articulation of both strengths and limitations. Below, for clarity, we number the weaknesses (W1–W4).\n\n\n---\n**W1. Constrained to zero-dimensional problems.** \n> The method is only constrained to zero-dimensional problems and can't be generalized to positive-dimensional cases.\n\nThis study focuses on zero-dimensional ideals, and the positive-dimensional case is beyond its scope (border bases are only defined for the zero-dimensional case). We do not view this as a critical limitation, as **zero-dimensional systems are an important and broadly applicable subclass**, perhaps more than it first appears (see below). It is also worth noting that the contribution of this study includes monomial embedding, a general embedding method to feed large-scale systems to the Transformer. \n\n1. All finite-field systems (let K be the field) can be reduced to the zero-dimensional case by including *field equations* (e.g., x(x-1) and y(y-1) when K = F_2[x, y]), which restrict the solution spaces to K.\n\n2. Solving infinite-field systems is often addressed by *modular techniques* [Arnold'03] that reduce the systems to finite-field ones. While the standard modular technique assumes homogeneous systems, the homogenization trick turns any system into a homogeneous one.\n\nTherefore, **in essence, polynomial system solving can be reduced to solving zero-dimensional systems in finite fields**, although this reduction may not always be the most efficient strategy.\n\nTo the best of our knowledge, [Peifer+'20] is the only work that addressed positive-dimensional ideals in the literature of deep learning-based Gröbner/border basis computation, but they instead assume the input and output systems consist of binomials, which we believe is stronger than the zero-dimensional assumption. The following table compares the scale and class of systems and ideals (n=5, numbers are rounded) in the related studies.\n|                | Input system size \\|F\\| | Avg # of terms in F | class of ideals and systems | Note                                                  |\n|----------------|-------------------------|----------------------|----------------------| -------------------------------------------------------|\n| [Peifer+’20]   | 10                      | 20                   | binomial |  Most experiments were done with n=3. \n| [Kera+'24]     | 5–7                     | 42                   | shape position (\\|F\\| >= \\|G\\| = n) | From \"Max terms in F\" in Table 6 in [Kera+'24].       |\n| Ours           | 6–10                    | 130                  | vanishing ideal (\\|G\\| >= n, OK with \\|F\\| < \\|G\\|) | Computed from our datasets, will be added in Appendix.|\n\n\nThe extension to the positive-dimensional case is an important future work. However, this requires an efficient sampling of (non-Gröbner basis, Gröbner basis) pairs, which is an open problem. \n\n---\n**W2. Oracle invocation.**\n>The decision of when to invoke the oracle is heuristic and could benefit from theoretical analysis or learned policies.\n\nWe found that the relative border gap, defined as $\\frac{|\\mathcal{V}|}{|\\mathcal{L}|}$, is a practical indicator for when to invoke the oracle (see Figure 3). The intuition comes from Lemma A.2: when $|\\mathcal{V}|$ is close to $|\\mathcal{L}|$, only a few expansions remain. To our knowledge, there are no theoretical results that prescribe the optimal point for oracle invocation during Border basis computation. However, we tested this heuristic extensively against the actual number of remaining expansions (Figures 10–12) and consistently found a strong correlation across all setups.\n\nWhile learned policies could further improve the decision rule, we observed that a relative border gap of about $0.9$ is nearly always optimal or very close to optimal (Figures 3, 8–9). Lemma A.2 also provides a rigorous proof for the special case where no expansions are left, but the IBB still performs one costly, full expansion. In these cases, the Transformer is especially good at predicting this final expensive step (Table 4). \n\n---\n**W3. Scalability to higher dimensions and real-world cases** \n> Even though the experiment shows results up to 5 variables, but the scalability to higher-dimensional or real-world symbolic problems remains unclear. Has no theoretical guarantee.\n\nWe do scale our case of 5 variables up to degree 4, for which the SOTA requires on average 100 seconds, whereas our pipeline (Oracle + Fast Gaussian Elimination) results in speedups of roughly **17x**. We note that our improvements are orthogonal to the baseline IBB - in particular, a highly optimised version of IBB would likely still enjoy a speedup of similar magnitudes. \n\n---\n**W4. Random pruning.**\n> It would be interesting to know if we randomly prune the search tree, how would the performance looks like.\n\nWe appreciate an interesting suggestion. We examined this idea and concluded that a purely random cut will almost certainly discard at least one mandatory reduction step, it delivers essentially no speedup. \n\nIn our experiments (Table 5) the search space contains 1,000–3,000 candidates, yet only 1–15 % are needed to build a border basis. Missing even one of them derails the computation. For example, let an elimination stage produce N = 1000 candidates, with about m = 20 being mandatory (as is typically seen in the last expansion). Keeping exactly half (k = 500) succeeds only if all m survive, and the success rate P can be computed as \n\n$P=\\frac{\\binom{N-m}{k-m}}{\\binom{N}{k}}=\\frac{\\binom{980}{480}}{\\binom{1000}{500}}\\approx7.9\\times10^{-7}$. \n\n--- \n\n- [Arnold'03]  Arnold, \"Modular algorithms for computing Gröbner bases,\" J. Symb. Comput. 35, 403-419 (2003)\n- [Peifer+'20] Peifer et al. \"Learning Selection Strategies in Buchberger's Algorithm,\" ICML'20\n- [Kera+'24] Kera et al., \"Learning to Compute Gröbner bases,\" NeurIPS'24"}, {"review_id": "rEgTsXl4Bn", "reviewer": "Reviewer_C42S", "summary": "This paper introduces the Oracle Border Basis Algorithm (OBBA), the first deep learning approach that accelerates border basis computation for solving polynomial equation systems while maintaining mathematical correctness guarantees.", "questions": "See Weakness and Limitation sessions", "limitations": "This paper introducing the first deep learning approach that successfully accelerates border basis computation while maintaining mathematical correctness guarantees. The Oracle Border Basis Algorithm represents a pioneering achievement in AI-enhanced symbolic computation, demonstrating up to 3.5× speedup with rigorous mathematical proofs and novel monomial embedding techniques.\nHowever, several critical practical challenges severely limit the real-world applicability of the proposed solution. The method requires generating millions of training samples for each new problem domain, creating substantial computational overhead that may offset the runtime benefits in practice. The evaluation lacks comparison with other acceleration techniques for symbolic computation, making it difficult to assess the relative merit of the ML-based approach versus existing optimization methods. The training is limited to degree 2 systems while testing shows only modest generalization to degree 8, raising questions about scalability to higher-degree polynomial systems commonly encountered in real applications. The restriction to finite fields, \"leaving characteristic-0 arithmetic and larger arity unexplored,\" significantly constrains the method's applicability to many practical domains that require real or complex number computations. Additionally, the experimental evaluation is based on only 27 constructed datasets with limited parameter variations, providing insufficient evidence for the method's robustness across diverse problem structures and raising concerns about whether the observed performance gains will generalize to the broader landscape of polynomial system solving tasks.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\nSuccessfully combines deep learning with symbolic computation while maintaining mathematical correctness.\nMonomial embedding reduces token count by O(n) and attention memory by O(n²).\nClever insight that border basis computation's degree-by-degree structure enables more stable supervised learning vs. reinforcement learning.\n\nWeakness:\nRequires generating millions of training samples for each new problem domain.\nNo comparison with other acceleration techniques for symbolic computation.\nTraining only on degree 2 systems, though testing shows some generalization to degree 8\nFinite fields only: \"leaving characteristic-0 arithmetic and larger arity unexplored\" \nOnly 27 datasets constructed.", "was_revised": true, "final_justification": "While I find the author’s reply satisfactory, I will retain my initial score and decision, as the overall quality does not compare favorably with other papers I reviewed.", "rebuttal": "We thank the reviewer for the thoughtful assessment. We recognize the reviewer's main concern as the practical limitations that may affect the applicability of our method. We partially acknowledge these limitations but also would like the reviewer to comprehend the development of the field for assessment. Particularly, we first highlight the following. \n\n---\n### **Key Responses**\n\n- Solving polynomial systems has been a long-standing, hard task. Our experiments handle **the largest and most general class of polynomial systems in the literature** of deep learning-based Gröbner/border basis computation. We believe that this work should make large progress from prior studies toward real-world applications, **through new algebraic and machine learning techniques** (e.g., oracle-based technique with certified output, ideal-invariant transformation, monomial embedding).\n\n- Finite field systems cover broader cases than the reviewer may consider. Indeed, from an algebraic perspective, **it is common to reduce infinite-field systems (including real and complex numbers) to finite-field systems** using the modular technique. Further, from a machine learning perspective, **learning on an infinite field is well-known significantly easier**, which motivated us to focus on the finite field.\n\n- Besides 27 datasets for training and in-distribution evaluation, we have **27 out-of-distribution evaluation sets** for examining the generalizability of the trained oracles, which should possess sufficient variations to support our claim. \n\n--- \n**W1. Instance sampling for new problem domains.** \n> The method requires generating millions of training samples for each new problem domain, creating substantial computational overhead that may offset the runtime benefits in practice.\n\nWe do not consider this to be a particular weakness of our study. This criticism can be applied to various deep learning studies. While generalization is important, for new domains, it is common to collect new samples and retrain (or fine-tune) models on them. In the context of machine learning oracle-based algorithms, it is common to collect many training instances by running the algorithms. \n\nWe emphasize two overlooked aspects: (1) training data collection is less costly than it may seem, and (2) the oracle achieved significant runtime reductions on harder, out-of-distribution instances.\n\n1. Collecting one million samples does not mean running algorithms one million times. Border basis algorithms involve many expansion steps, each of which can be collected as training instances. In our case, we focus on the final k=5 calls of expansions,  which are very costly and thus benefit from the oracle. So, we need 200k runs. The value of T is selected from our analysis of algorithm runs on our problem size. This k will be set larger for harder instances because there will be more \"costly expansions\" in a single run. \n\n2. The trained oracle empirically generalized well to harder and out-of-distribution instances. Particularly, Table 6 (see the bottom row, IBB vs IBB+Oracle) presents that Oracle reduces the runtime by approximately 30 seconds on average for hard instances that are also out of distribution. Note that FGE is also our contribution, which is a byproduct of this work, and it should be fair to compare the impact of the oracle without FGE.\n\n--- \n\n**W2. Other acceleration techniques for symbolic computation**\n> The evaluation lacks comparison with other acceleration techniques for symbolic computation, making it difficult to assess the relative merit of the ML-based approach versus existing optimization methods.\n\nWe compared our method to the standard Border Basis Algorithm (BBA) as well as the SOTA Improved Border Basis Algorithm (IBB) and introduced our own acceleration technique in the form of fast Gaussian elimination. We may be able to collect more techniques from other symbolic computation algorithms to accelerate border basis algorithms, but this should form an independent work of fast border basis computation. Therefore, we consider that our choice of baselines should be reasonable.\n\n--- \n**W3. Training only on degree 2 systems.** \n>  The training is limited to degree 2 systems while testing shows only modest generalization to degree 8, raising questions about scalability to higher-degree polynomial systems commonly encountered in real applications.\n\nThis involves a misunderstanding. The input systems F in training instances range up to degree 3, as these are obtained F=AG with border bases G of degree-2 and random polynomial matrices A, which produce a wide range of degrees in F. We kept the degree low to see how the oracle generalizes to higher degrees. In Figs. 3 and 8 and Tables 6-8 show the great generalization to various maximum degrees the input systems ranging from degree 2 to 8. \n\nThe following table presents that our work addresses the largest and most general class of systems among the related studies.\n|                | Input system size \\|F\\| | Avg # of terms in F | class of ideals and systems | Note                                                  |\n|----------------|-------------------------|----------------------|----------------------| -------------------------------------------------------|\n| [Peifer+’20]   | 10                      | 20                   | binomial |  Most experiments were done with n=3. \n| [Kera+'24]     | 5–7                     | 42                   | shape position (\\|F\\| >= \\|G\\| = n) | From \"Max terms in F\" in Table 6 in [Kera+'24].       |\n| Ours           | 6–10                    | 130                  | vanishing ideal (\\|G\\| >= n, OK with \\|F\\| < \\|G\\|) | Computed from our datasets, will be added in Appendix.|\n\n\n--- \n**W4. Finite fields only.** \n> The restriction to finite fields, \"leaving characteristic-0 arithmetic and larger arity unexplored,\" significantly constrains the method's applicability to many practical domains that require real or complex number computations.\n\nWhile the reviewer suggests the restriction to finite fields is a significant constraint, we would like to emphasize that this is not, from an algebraic and machine learning perspective. We will update the line \"leaving characteristic-0 arithmetic and larger arity unexplored\" to avoid confusion.\n\n1. (Algebraic perspective). It is common to reduce the infinite-field case to the finite-field case. The technique is called *modular techniques* [Arnold'03]. While the standard modular technique assumes homogeneous systems, the homogenization trick turns any system into a homogeneous one. For example, a complex polynomial system is reduced to a real polynomial system by introducing $i = \\sqrt{-1}$ as a new variable and appending $i^2 + 1 = 0$ to the system. The new system is then homogenized and processed by the modular technique (note: we also has to replace $\\mathbb{R}$ to $\\mathbb{Q}$ as $\\mathbb{R}$ is not an algebraic field). \n\n3. (ML perspective). Learning on a finite field has been known to be significantly more challenging than on an infinite field. For example, the parity problem (input: bit strings, target: sum of bits modulo 2) has been known to be notoriously hard to learn because of the \"modulo 2\" operation [Shwartz+'17, Hahn+'24]. In a more related context, [Kera+'24] reports that learning to compute Gröbner bases is less successful with finite fields (success rate 93.7% for Q vs 46.8% for F31, Table 2 in [Kera+'24]). Thus, our results should readily extend to infinite fields. We will update the manuscript to clarify that we focus on finite fields, as it has been known as a challenging case.\n\n--- \n**W5. Only 27 datasets.**\n> Additionally, the experimental evaluation is based on only 27 constructed datasets with limited parameter variations, providing insufficient evidence for the method's robustness across diverse problem structures and raising concerns about whether the observed performance gains will generalize to the broader landscape of polynomial system solving tasks.\n\nWe believe that our 27 datasets are enough in numbers and diversity to validate the benefits from oracle, e.g., the speedups and the generalization to out-of-distribution samples. The number 27 only accounts for the training sets, and we additionally used 27 out-of-distribution sets in evaluation as shown inTables 6-8], which is from the combinations of 3 fields, 3 variable sizes (n=3,4,5), 3 max degrees in G.  (note: to be precise, these 27 have a small overlap with the original, but instead we have the same number of additional patterns used in Figs. 8. So, the total number of out-of-distribution sets is 27.)\n\nEach dataset was regenerated with many random seeds, coefficient scales, and sparsity patterns—so a single family already spans runtimes from under 10 s to over 1000 s (cf. Table 6). Despite being trained only on degree-up-to-3 systems, the oracle generalizes to degree 4 and 8 (Fig. 3) and to the 12 additional families reported in the appendix (Figures 8-9), all with the same performance trends (Table 6-8). These benchmarks therefore provide strong evidence that the method is robust across a broad spectrum of polynomial-system problems.\n\n\n--- \n- [Peifer+'20] Peifer et al., \"Learning Selection Strategies in Buchberger's Algorithm,\" ICML'20\n- [Kera+'24] Kera et al., \"Learning to Compute Gröbner bases,\" NeurIPS'24\n- [Arnold'03]  Arnold, \"Modular algorithms for computing Gröbner bases,\" JSC, 2003\n- [Shwartz+'17] Shwartz et al., \"Failures of Gradient-Based Deep Learning,\" ICML'17\n- [Hahn+'24] Hahn et al., \"Why are Sensitive Functions Hard for Transformers?,\" ACL'24"}, {"review_id": "wEghUh4R17", "reviewer": "Reviewer_ECgM", "summary": "This paper uses a Deep Learning approach to speedup existing\nBorder basis based approaches to solving systems of polynomial equations.\nThis can\n serve as a  practical enhancement to traditional computer algebra algorithms.\nIn particular, they claim to obtain  3.5x speedup compared to Border basis computer algebra algorithm which does not use AI.\nAdditionally, introduce a novel sampling based method to generate training data.", "questions": "What would be the plan going from Border bases to Grobner bases?\n\nHow does the transformer embed the polynomial input  ?\n\nEmpirical Breadth: A brief mention of the benchmarks, problem sizes, or types of systems tested would help assess practical significance.", "limitations": "Not much of a discussion", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strength:\n\n1) Natural and central problem.The problem of solving systems of polynomial equations with finitely many solutions occurs in many fields, including cryptography, computational biology, algebraic geometry, etc. And furthermore Gröbner and border bases are part of the backbone of symbolic computation systems, although they are notoriously expensive. So, using ML to help compute Border bases is very natural. \n\n2) Using ML it in conjunction with traditional methods enables efficiency improvement without sacrificing correctness. This is a stroong benefit of the approach.\n\n3) The speed up claimed will make the method useful in real computer algebra systems.\n\n4 )\nTailoring tokenization and embeddings to algebraic input seems like a novel contribution in this field.\n\n\nWeakness\nIs 3.5 factor enough theoretically, can you do better?\nhow large is the experiment - I couldn't find the answer?", "was_revised": true, "final_justification": "The problem of solving systems of polynomial equations with finitely many solutions occurs in many fields, including cryptography, computational biology, algebraic geometry, etc. And furthermore Gröbner and border bases are part of the backbone of symbolic computation systems, although they are notoriously expensive. So, using ML to help compute Border bases is very natural. \nFurthermore, using ML it in conjunction with traditional methods enables efficiency improvement without sacrificing correctness. This is a strong benefit of the approach. Finally, it seems that the speed up claimed will make the method useful in real computer algebra systems.", "rebuttal": "We appreciate the reviewer's time and effort. \n\nWhile some aspects may be outside the reviewer's core expertise (judged by the consensus score), the listed strengths accurately reflect our key contributions. As these points seem to be highly appreciated by the reviewer, and as there are weaknesses that only ask for clarification, we suspect the negative score mostly comes from the uncertainty about the impact of our work in the context of the literature. \n\nBelow, we highlight several strengths of this work that may be overlooked by the reviewer, and then also address the suggested weaknesses and questions. An overview is as follows. \n\n---\n### **Key Responses**\n\n1. (Probably overlooked technical strengths). Our technical contributions include the **dataset generation**, which is a fundamental component in the literature of learning symbolic computation. Particularly, we highlight a) the first generic border basis sampling algorithm and b) ideal-invariant generator transform (Theorem 4.2), which significantly generalizes [Kera+'24] and offers a general method of sampling non-trivial random polynomial systems. \n\n2. (Probably overlooked empirical strengths). The experiments demonstrate (e.g., Table 6) that our oracle leads to **large speedups (up to 30 seconds)** and **strong generalization to out-of-distribution samples**. \n\n3. (The experiment setup: the size and type of systems). Our experiments handle **the largest and the most general class of polynomial systems in the literature** of deep learning-based Gröbner/border basis computation. This is achieved by the technical contributions highlighted in (1) and our efficient input embedding (i.e., monomial embedding). \n\nWe kindly ask the reviewers to take these into account at the reassessment of this work.\n\n--- \n\n### **(1) Technical strengths.**\n**Border basis sampling algorithm.** To our knowledge, this is the first algorithm that allows us to sample generic border bases. Recall that border bases are a generalization of Gröbner bases in the zero-dimensional case. Only border bases in a special (measure-zero) subset have associated Gröbner bases. An existing method [Abbott+'05] only offers sampling from such a special subset, but our algorithm can sample general border bases. \n\n**Ideal-invariant generator transform (Theorem 4.2)** This offers a principled design of a polynomial matrix A that transforms the polynomial set G by F=AG without changing the ideal (i.e., \\<F\\> = \\<G\\>). [Kera+'24] only covers the extension (i.e., |F| >= |G|), but ours addtional cover the contraction (|F| < |G|). The design of A is also significantly simplified. \n\n---\n### **(2) Empirical strengths.**\nOur experiments, both in the main text and the Appendix, not only focus on the speedups but also examine the generalizability of the oracle to OOD instances. In case the reviewer judges the empirical results only from the main text, we highlight the results in Table 6 from the Appendix. As shown in Table 6 (bottom row, IBB vs. IBB+Oracle), our oracle achieves speedups of up to 30 seconds on hard, out-of-distribution instances. These results also demonstrate strong generalization to OOD inputs. \n\n\n\n> Is 3.5 factor enough theoretically, can you do better? \n\nWe appreciate the reviewer's question. As shown in Table 5 (Appendix), the observed 3.5× speedup is already close to the best achievable. A perfect oracle—one that never predicts a polynomial reducible to zero—would reduce the number of unnecessary polynomials from the IBB baseline of roughly 1300–1400 down to none. Our oracle typically predicts only 300–400 such polynomials, which matches the 3.5× improvement. Even a perfect oracle could only achieve around 5× speedup, so our result is already close to this theoretical limit.\n\n\n--- \n### **(3) The experiment setup.**\n> Empirical Breadth: A brief mention of the benchmarks, problem sizes, or types of systems tested would help assess practical significance.\n\nTo the best of our knowledge, our experiments cover the largest and the most general class of polynomial systems in the literature of deep-learning based Gröbner/border basis computation [Peifar+'20, Kera+'24]. \n- The experiments in [Peifar+'20] mostly focus on n=3 variables and binomials (for both input systems F and Gröbner bases G).\n- The experiments in [Kera+'24] handle up to n=5, but for n>1, the mixing matrix A of F=AG is sparsified to keep the input system size moderate (i.e., to keep the number of tokens < 5000). The design of A only supports an input system of size $|F| >= |G|$. Besides, the ideals are restricted to those in shape position, where G is restricted to size |G|=n. \n\nThe following table compares the scale and class of systems and ideals (n=5, numbers are rounded).\n|                | Input system size \\|F\\| | Avg # of terms in F | class of ideals and systems | Note                                                  |\n|----------------|-------------------------|----------------------|----------------------| -------------------------------------------------------|\n| [Peifer+’20]   | 10                      | 20                   | binomial |  Most experiments were done with n=3. \n| [Kera+'24]     | 5–7                     | 42                   | shape position (\\|F\\| >= \\|G\\| = n) | From \"Max terms in F\" in Table 6 in [Kera+'24].       |\n| Ours           | 6–10                    | 130                  | vanishing ideal (\\|G\\| >= n, OK with \\|F\\| < \\|G\\|) | Computed from our datasets, will be added in Appendix.|\n\nWe acknowledge that we currently focus on small systems, which may not have immediate benefits in real-world applications. However, this work should achieve large progress in the field of deep learning-based Gröbner/border basis computation through new algebraic and machine learning techniques (e.g., oracle-based technique with certified output, ideal-invariant transformation, monomial embedding), which will generalize to deep learning-based computer algebra.\n\n--- \n### **(4) Others**\n**Q1. From Border Bases to Gröbner bases.** \n> What would be the plan going from Border bases to Gröbner bases?\n\nThe adaptation of our oracle-based approach to compute Gröbner bases remains an interesting open problem. While this is beyond the scope of this work, and border basis computation already addresses the polynomial system solving task in the zero-dimensional case, we share our view on this adaptation. \n\nOne key observation in our work is that the border basis algorithm proceeds degree-by-degree, and one can determine successful/unsuccessful expansions in hindsight. This enables us to train the Transformer-oracle in a supervised manner. Thus, it is critical for the adaptation to find such computational steps in computing Gröbner bases. In preliminary analysis, such hindsight-verifiable structures do not appear in standard Gröbner basis algorithms (e.g., Buchberger's, F4), where computation cost depends heavily on reduction ordering. For future plans, one can examine less popular algorithms of Gröbner basis computation, or design a new one so that it is more straightforward to define an oracle. \n\n\n**Q2. Embedding polynomials.** \n> How does the transformer embed the polynomial input?\n\nWe here give an intuition using a polynomial $f = 2x^3 + y + 1 \\in \\mathbb{F}_7[x, y]$ as a running example. \n\nA polynomial is represented in a sum of monomials, and first tokenized as (C2, E3, E0, +, C1, E0, E1, +, C0, E0, E0, \\<\\*\\>), where Cn and Em denotes coefficient $n$ and exponent m, respectively, and \\<\\*\\> is a token that follows this polynomial (e.g., \\<sep\\>, \\<supsep\\>, \\<eos\\>). \n\nThe standard embedding method simply translates each of the 12 tokens above into the associated embedding vector in the trainable look-up matrix (implemented by `nn.Embedding` in PyTorch). Thus, the embedding of $f$ becomes a sequence of 12 embedding vectors. In essence, the proposed embedding  (i.e., monoial embedding method) sums up the embedding vectors inside each monomial and its follow-up token. Namely, (C2, E3, E0, +, C1, E0, E1, +, C0, E0, E0, \\<\\*\\>) is reduced to 3 embedding vectors, where for example, the first embedding vector is the sum of embedding vectors of (C2, E3, E0, +). Note that we use different look-up matrices for exponents of x and y so that we can distinguish (C2, E3, E0, +) and (C2, E0, E3, +) after adding up embedding vectors. Section 4.2 and Appendix D provide the full description of the proposed embedding method. \n\nTable 3 demonstrates that the monomial embedding not only reduces the number of tokens (i.e., memory cost in attention) but also improves the success rate. Table 7 shows how significantly our training benefits from this embedding. As suggested by Reviewers CaQ9 and C42S, monomial embedding is one of the key technical contributions of this work, and is useful for learning other polynomial-based tasks.\n\n---\n- [Peifer+'20] Peifer et al. \"Learning Selection Strategies in Buchberger's Algorithm,\" ICML'20\n- [Kera+'24] Kera et al., \"Learning to Compute Gröbner bases,\" NeurIPS'24"}]

Author rebuttal:

Meta-review: The paper is a borderline accept. While reviewers initially had concerns about scalability, originality, and practical applicability, the authors' detailed rebuttal successfully clarified these points. They demonstrated technical novelty, significant real-world speedups (30+ seconds), and strong generalization to out-of-distribution instances, convincing all reviewers to recommend acceptance.
Decision: Accept (poster)