Learning to Compute Gröbner Bases

(Please kindly check our global response "To all reviewers" beforehand as our reply is based on it.)

We appreciate your critical reading of our paper and many positive comments on our work.

... the actual experimental results are not that good. In particular, for the popular grevlex order, the transformer-based approach is very bad.

Yes, we consider that this demonstrates the challengingness of our newly introduced learning task: addressing NP-hard math problems. The math problems addressed in the prior math transformers are of moderate level. The only exception is a line of work of attacking LWE, the accuracy of which is also far from 100%. The popularity of grevlex in computational algebra derives from its empirical efficiency. Usually, one computes a Gröbner basis with grevlex and then transforms it to lex order using FGLM. Our results suggest that it is better for Transformers to compute lex Gröbner bases directly, which we consider is an interesting observation.

It is surprising that the support accuracy is much higher than the actual accuracy for basis generation.

Support accuracy is a relaxed accuracy metric, so it is not surprising to see that the support accuracy is higher. However, yes, high support accuracy suggests a possibility of hybridization of Transformer and math algorithms, which is one of our next targets.

One can argue that the blackbox nature of transformers makes it very hard to interpret the bottleneck of this method, but I do hope other architectures are tried to obtain a better empirical result. This is essential, as the main selling point of this paper is to use machine learning blackbox method to compute Grobner bases more efficiently.

Thank you for the important suggestion. We used a vanilla transformer architecture, as in many math transformer studies, so that one can know what and to what extent Transformers can learn by comparing these studies (including ours). As the accuracy is found to be limited, yes, the next step is to design a better architecture. To this end, we have to be careful about the difference in the nature of natural languages and symbolic computations; a correct output for the former can be calculated from the part of the input, while for the latter, the whole input should be taken into account.

Even though the main motivation of this paper is to use transformers, the theoretical parts and the two problems regarding Grobner bases are intriguing to me than the experiments.

We really appreciate this comment, and we do agree with it. As presented in the global response, we consider that one of the core contributions is posing an interdisciplinary challenge from which various studies can appear.

Q1

How fast is your transformer-based approach compared to standard algorithms?

The runtime of Transformer at Table~2 for $n=2, 3, 4, 5$ is 5.879, 11.419, 14.371, 20.622 seconds, respectively. The test batch size was 500, 250, 250, 250, respectively, to fit the input to our 48GB GPU memory. The runtime of Transformer is 5-10 times slower than the math algorithms we tested. Theoretically, the runtime of a Transformer does not depend on the difficulty of the problem as math algorithms do. Shorter encoding of polynomials and better attention mechanisms are important future works. For the former, we may be able to exploit some nature of polynomials; for the latter, sparse attention may not be helpful because, unlike NLP tasks, symbolic computation cares about all the input symbols.

(Please kindly check our global response "To all reviewers" beforehand as our reply is based on it.)

We appreciate your critical reading of our paper. We first answer the questions you raised. Replies to other comments will come later or have already been addressed in the global response.

Q1

Did you try your method on "real world" problems?

No, because our focus lies on a "general case" rather than special cases that largely vary across applications (see our global response). We believe this is reasonable for the first work. Our work discovered a new challenging machine learning task and new math problems for it, proposed baseline dataset generation method, and provided the experiments using it. We can test the Transformers trained on our dataset to "real world" problems, but such an out-distribution test should result in almost zero accuracy.

Q2

I understand that learning can only be done on limited size instances. But does this limit testing as well? If not, why not report experiments?

Thank you for your suggestion. Yes, it's limited for now because the maximum sequence length of positional encoding was set based on the maximum sequence length of training samples. We retrained a few models with extended limits for $n=2, 3$. For $n=2$, we generated a new test test for which we set the maximum number of terms of polynomials in $U_1, U_2$ to 4 (previously 2). For $n=3$, we set the density $\sigma=1.0$. We observed a large accuracy drop for such out-distribution samples~(approximately 20-30% decrease). Note that the results relate to out-distribution accuracy, which is beyond the scope of current work (see global response). However, it may be true that the results will serve as a baseline for future work.

Q3

On page 6, where you say that you sample O(s^2) polynomails, how are these sampled? What distribution?

All the polynomials in this paper are sampled uniformly from the polynomials with a bounded total degree and a bounded number of terms. This is implemented by random_element function in SageMath.

Weakness 1: Limited applicability

Global response mostly replies to this comment. We admit that our current results are not very practical; however, we'd like to emphasize that this is because the learning of Gröbner basis computation is extremely challenging compared to the math problems addressed in the prior math transformers, requiring many machine learning and mathematical problems to be resolved. Besides, we consider that our task is based more on practical motivation. There is no scalable algorithm for computing Gröbner bases, while there are for the tasks in the related studies. The only exception is the line of works for attacking LWE using Transformers, which is also currently restricted to small problems and not considering generalization.

a) The authors acknowledge that transformers may only perform well for in-distribution samples, ... nevertheless this limits the applicability of their algorithm.

Yes, and this is actually why prior studies of math transformers explored better training distributions and tested generalization liability. However, this is strongly based on the fact that for their tasks, the random generation of samples is trivial and in-distribution accuracy is already high enough. We found that this is not the case for the Gröbner basis computation and thus focus on this step.

b) [... The omitted part was answered at Q2. ...] As a side note, is the problem of finding the Grober basis also NP-hard for bounded size instances?

We are not very sure what is meant by "bounded size of instances." An instance size of an NP-hard problem is always bounded. For reference, "computing a Gröbner basis from a given $F$ of finite size" is NP-hard. For example, the polynomials in MQ challenge, a post-cryptography challenge, are degree-2 polynomials. The difficulty of solving degree-2 polynomial systems is the foundation of the multi-variate cryptosystem.

c) The authors impose additional restrictions on instances in the training set, and they claim these are realistic.

We consider that our setup is reasonable and oriented for practical scenario. Refer to the global response.

Weakness 2: Limited theory

Limited theory. although there are some theorems, they are simple and their proofs seem straightforward. The contribution from the mathematical side seems very limited.

We have to admit the current theorems and algorithms are simple. This is partially because that the efficiency matters in the large-scale dataset generation. We may design a sophisticated method based on the necessary and sufficient condition (i.e., Theorem 4.7 (3)). Particularly, we may utilize the sygyzy module of $G$, the representatives of which can be efficiently computed as we have an access to a Gröbner basis $G$ (Schreyer's Theorem). We believe that this approach can give a more "uniform" sampling, but it needs a few more steps and is left to our future work.

Other Weaknesses

Algorithm for randomly generating Grobner bases seems very simple, and seem to "engineer" the problem a lot. There is no analysis of the actual distribution of the instances the algorithm will generate. Is it uniform in any way?

Seems that only experiments on synthetic data was considered.

See the global response.

Contrary to what the authors claim, no real light is shed on the algebraic problems themselves.

Our work introduces a motivation for unexplored algebraic problems and also presents an algorithm and theories for a base case. The intention of this comment is unclear to us, and we would appreciate it if we could have more elaboration.

Will interest only specialist on work on computational algebra.

We believe that this work may attract interdisciplinary interests. Our new problems should encourage computational algebraists to work on a machine-learning topic. We showcase an example of math problems with difficulty in dataset generation, which should be of interest to the math transformer community. As you've pointed out, our algorithm and theory are designed simply, which may allow readers with limited knowledge of algebra to follow it. The limited in-distribution accuracy at Gröbner basis computation also provides an empirical limit of the Transformer's learnablity, which may interest the researchers in developping a better model. Futher, our work has a potential impact on the cyptography as many cryptosystems are in the scope of algebraic attack, which use Gröbner basis computation.

(Please kindly check our global response "To all reviewers" beforehand as our reply is based on it.)

We appreciate your critical reading of our paper. Your comments are quite reasonable and have been the focus of the prior studies. However, we would like to emphasize that (we found) learning of Gröbner basis computation has fundamental challenges that other math transformer papers do not have. We have already emphasized it in the global response, so please refer to it. We sincerely ask for your re-evaluation of our work by taking into account our rebuttal.

Weakness 1 : Out-distribution case

The test set seems to be randomly generated instances rather than problems arising out of some real applications. ... however it [the problem of out-of-distribution generalization] is not addressed ... .

This question is addressed in the global response. In short, the out-distribution case is beyond the scope of this study because, unlike the prior studies, the dataset generation itself is non-trivial, and in-distribution accuracy is not high enough.

Weakness 2: Standard datasets

It is usual for solvers to test their performance on some standard datasets (for ex. the SAT competition for SAT solvers), and random instances are usually considered irrelevant.

This strongly relates to our main claim --- preparing many (non-Gröbner set, Gröbner set) pairs is non-trivial. To our knowledge, there are some classical families of polynomials for benchmarking Gröbner basis computation algorithms (or polynomial system solving algorithms), but these are very far from standard datasets. One may consult this websight. The listed examples are artificial, not necessarily zero-dimensional. They are empirically found difficult and/or designed for easily generating variations in the number of variables (e.g., testing for polynomial system Katsura-4 in 4 variables, then Katsura-5 in 5 variables, and so on). Classical benchmarks are useful for math algorithms, i.e., the algorithms proved to work for all the cases (i.e., 100 % "in/out-distribution" samples) except for the timeout, but not for our current work because they are out-distribution samples.

Another benchmark can be found in cryptography challenges (e.g., MQ Challenge). As we have discussed above, the polynomials appearing there are also strongly biased.

It is not clear whether the state of the art Grobner basis tools have been optimised for random instances or practical instances, hence the comparision may not be fair.

The general purpose algorithms are Buchberger's algorithm and F4 algorithm (SoTA). We tested both of them in our experiments. Thus, the comparison must be fair as the focus of our study is oriented to the general case. Those specialized for particular "practical instances" are not discussed in this paper.

Weakness 3: Motivation of using Transformer

In the prior studies, math transformers were studied for testing the learnability of Transformers, rather than using them as practical solvers because we already have well-developed scalable algorithms for the adopted moderate-level math problems.

In contrast, the use of Transformers here is strongly motivated by the fact that there are no scalable mathematical algorithms for computing Gröbner bases. Unlike math algorithms, the runtime of the Transformer does not depend on the difficulty of the problem but on the sequence length. For a large-scale instance on which math algorithms cannot run, Transformers can return an answer with some probability or at least give a hint of the solutions (see discussion on the support accuracy of Table 2). We admit that the current results do not achieve this ultimate goal; resolving this challenge has a long way to go both in machine learning and computational algebra, and this study has initiated an essential step.

The paper does mention that transformers have been used for other math problems, including for a step in the related Buchberger algorithm;

Quick correction. Transformers have not been used for Gröbner basis computation before. The technique applied to the Buchberger algorithm is simple reinforcement learning. Further, this algorithm assumes binomials and does not work for general polynomials.

2. Justification of our current setup and real-world applications

Several reviewers mentioned that our setup appears artificial and may not be based on the practical scenario. This comment is critical, and we'd like to summarize why we reached our current setup.

Why ideals in shape position (or why zero-dimensional radical ideals)?

Non-Gröbner sets have various forms across applications. For example, in cryptography (particularly post-quantum cryptosystems), polynomials are restricted to dense degree-2 polynomials and generated by an encryption scheme. On the other hand, in systems biology (particularly, reconstruction of gene regulatory networks), they are typically assumed to be sparse. In statistics (particularly algebraic statistics), they are restricted to binomials, i.e., polynomials with two monomials.

As such, instead of focusing on a particular application, we decided to address the underlying motivations in various applications of computing Gröbner basis: Solving polynomial systems or understanding ideals associated with polynomial systems having solutions.

From this perspective, our restriction to the ideals in shape position is reasonable. Note that it is more mathematically meaningful to focus on the class of ideals than generators (or Gröbner bases). Proposition 4.5 tells us zero-dimensional radical ideals (under a mild condition) are generally in shape position.

Ideals in most practical scenarios are known to be zero-dimensional ideals, and if they are associated with polynomial systems having solutions, they are radical in general (i.e., non-radical ideals are in a zero-measure set in the Zariski topology).

We consider that it is natural to address a general but application-oriented case in the first work. Ideals in shape position (or zero-dimensional radical ideals) are a reasonable choice from this point of view. Specialized methods can come later based on our results.

On the strategy of sampling ideals.

It is also worth noting that random sampling of the generators of zero-dimensional ideal requires a specific strategy. In $k[x_1,\ldots,x_n]$ ($k$: infinite field), $s$ degree-bounded polynomials with random coefficients generate (i) (in general) the trivial ideal if $s > n$, the Gröbner basis of which is {1} and (ii) a positive-dimensional ideal with probability 1 if $s < n$. Thus, the only possible way is to consider $s=n$ first and append some combinations of these polynomials to the generators. Our strategy follows this approach. Note that these combinations have to satisfy some algebraic conditions, which is the source of the fundamental difficulty of analyzing the distributions of obtained generators.