Computational Algebra with Attention: Transformer Oracles for Border Basis Algorithms

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

REVIEW 4 major objections 5 minor 1 cited by

Computational Algebra with Attention: Transformer Oracles for Border Basis Algorithms

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

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

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

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

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

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

classification cs.LGcs.SC MSC 68W3013P1068T07

keywords borderbasistransformerpolynomialsystemsolvingalgorithmswithpredictionsmonomialembeddingzero-dimensionalidealssymboliccomputationdeeplearning

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

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

What carries the argument

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

What would settle it

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

Watch

Extended reading notes

Core claim

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

Load-bearing premise

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

Editorial extensions

If this is right

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

Reading between the lines

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

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

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

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

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

Now the soft spots, in order of size.

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

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

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

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

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

Referee Report

4 major / 5 minor

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

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

major comments (4)

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

minor comments (5)

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

Circularity Check

0 steps flagged · score 2.0 of 10

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

full rationale

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

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

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

free parameters (4)

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

assumptions (5)

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

how reviews work

0 comments

Cite this review

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

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

abstract

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

Figures

Figures reproduced from arXiv: 2505.23696 by the authors.

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

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

Figures from the paper (9 more)

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

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

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

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

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

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

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

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

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

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

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

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

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

Pith tools

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