NeurIPS 2024 Rebuttal (Reviewer q3D1)

We appreciate your thorough review and valuable feedback. Below, we answer the weaknesses and questions.

On Weaknesses

Theoretical guarantees on training. Providing theoretical guarantees on global/local convergence, running time, and error bounds for the training of Transformers (or deep neural networks) is generally difficult. To our knowledge, such guarantees have been (partially) given only for simple models, e.g., two-layer networks or infinitely wide networks. Hence, this should be beyond the scope of our study. The tight page limitation forced us to send the description of Transformers and its training to the appendix, but as mentioned around [l.335], they follow a standard one. The exception is when hybrid embedding is used, where we have a small MLP at the input embedding, a regression head for predicting coefficients, and MSE loss. These are described in Section 5 and Appendix D, but we will review the manuscript to give further details.

Benchmarks and applications. Showing the superiority of using Transformers for large-scale problems in benchmarks and applications is indeed important. However, to achieve this, we need a few more fundamental steps, e.g.,

1. Designing dataset generation algorithms tailored for target applications.
2. Discovering an efficient tokenization of large polynomial systems.

On 1), since the characteristics of polynomial systems vary across applications, one needs to design a special way of generating them. Our work did this for zero-dimensional radical ideals as a first step because 0-dimensionality is common in several applications (cf. Global Response).

On 2), we need an efficient representation of polynomial systems for scale-up. The scope of this study is to establish the problem of learning to compute Gröbner bases, and thus, we tested its learnability based on a standard model and training. The tokenization of polynomials also follows a standard one; for example, $\{x^2-10, y\}$ is tokenized as $`[x, **, 2, +, -10, <sep>, y]`$, (cf. Section 5). Eventually, a single $n$-variate term requires $O(n)$ tokens, leading to a long input sequence for large $n$. As well known in Transformer literature, the space complexity of the attention mechanism scales as $O(L^2)$ with input length $L$. A potential approach to shorten the input is to embed a term by its coefficient and inject the exponent part as position vectors because this is literally a position in the term space. We are currently working on it in our follow-up paper.

It is worth noting that the current study already observed that Gröbner basis computation is computationally costly for $n=5$ in Table 1, where about 24% of the instances encountered timeout for two standard algorithms. Further, Table 22 shows that for all the algorithms, there are several instances for which Transformers run accurately and significantly faster. Thus, we have already partially observed the Transformer's supremacy.

Writing and format. We will carefully clean up our manuscript manually and systematically (e.g., using LLM). A grammar checker applied before submission does not seem to work well for sentences with latex codes. As for the placement of the proofs and limitations, in my limited experience, it is common for the NeurIPS papers to have them in Appendix. The paper checklist justifies this; see [l.947],

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 a short proof sketch to provide intuition.

In our manuscript, the intuition is provided below each theorem. About the limitations, because this study tackles a new problem, we needed a thorough discussion of open questions, which led us to send it to Appendix. The checklist does not clarify whether the limitation section should be included in the main text.

According to the submission instructions, accepted papers will get another content page, so we may be able to include the proofs and/or limitations in the main text in such a case.

On Questions

0-dimensional ideals. If an ideal is in shape position, it is also 0-dimensional. Thus, the assumption of shape-positioned ideals cannot be weaker than that of 0-dimensionality. We assume that you intend to mean "assuming 0-dim is strong; further assuming shape position is OK." As several reviewers ask about the assumption, we provide the Global Response to address it. Please kindly refer to it.

Killer applications. One of the potential killer applications is cryptanalysis. The security of cryptography is often reduced to the difficulty of solving certain mathematical problems. Recently, the SALSA project [1] has shown that a Transformer-based approach can solve the LWE (Learning With Errors) problem, which is the basis for the security of lattice-based cryptographies. The overview of their approach is as follows:

1. From the cryptosystem to be analyzed, generate samples of LWE and their solutions as training data and perform training.
2. Input the LWE corresponding to the ciphertext to be attacked into the model constructed in Step 1. If the output gives the secret, the cryptosystem is vulnerable.

The computational difficulty of the Gröbner basis problem for 0-dimensional ideals is the basis for the security of AES [2], which is currently the mainstream symmetric key encryption, and multivariate polynomial encryption [3], which provided candidates in the NIST Post-Quantum Cryptography Standardization process. Our future target is to make our proposed efficient data set generation and machine learning the basis for some security analysis in cryptography.

[1] E. Wenger, et al., SALSA: Attacking lattice cryptography with transformers, 2022.

[2] J. Buchmann, et al., Block ciphers sensitive to Gröbner basis attacks. 2005

[3] A. Kipnis, et al., Unbalanced oil and vinegar signature schemes, 1999

Thank you for your strongly positive evaluation of our work!

Benefits. In general, if the terms of the input polynomial system $f_1,\ldots,f_m$ are fixed and the coefficients $\{c_{i,\alpha}\}$, where $f_i = \sum_{\alpha} c_{i,\alpha} x^{\alpha}$, are considered as parameters, it is known that by using the comprehensive Gröbner basis theory, i.e., the parameterized Gröbner basis theory, the terms appearing in the reduced Gröbner basis $G$ of the ideal $\langle f_1,\ldots,f_m \rangle$ are identical for general coefficient values of $\{c_{i,\alpha}\}$. In other words, this means that in most cases, the combinations of terms on a reduced Gröbner basis are determined only by the combinations of terms in the input polynomial system. This can also be observed from the relatively high support accuracy in our experiments.

From the above, there is still no concrete guarantee that our method will give a correct model, including the coefficients, but it is believed that there is some guarantee that the terms will be guessed correctly. In algebra, guessing the terms of the Gröbner basis gives a global invariant of the ideal, such as the initial ideal or the Hilbert polynomial. Therefore, we can consider using our model as an oracle or heuristic to provide global invariants of ideals (initial ideals, Hilbert polynomials) for downstream tasks. Indeed, there is an accelerated Gröbner basis computation algorithm using Hilbert polynomials [1]. In future work, we can construct efficient polynomial solving and Gröbner basis computation theory by assuming further information (e.g., entire supports) given by Transformers.

Other fields. The proposed dataset generation works for other coefficient fields, including $\mathbb{Q}_p$. However, as $\mathbb{N}$ is not a field (or even a ring), the set $\mathbb{N}[x_1,\ldots, x_n]$ is beyond the scope of Gröbner basis theory. The ring $\mathbb{Q}_p[x_1, \ldots, x_n]$ is associated with a non-Archimedean geometry, so it should be interesting to see how the learning goes. In our experiments, the learning was more successful with $\mathbb{Q}$, which equips a canonical metric, than with $\mathbb{F}_p$, which has no non-trivial metrics. An experiment on $\mathbb{Q}_p[x_1, \ldots, x_n]$ may serve as the midpoint between them.

[1] C. Traverso, Hilbert functions and the Buchberger algorithm, Journal of Symbolic Computation, 1997.

We sincerely appreciate your thorough review and strongly positive assessment of our work. We are grateful that you listed many strengths of our work.

Reduced Gröbner basis. The reduced Gröbner basis is defined independently from shape position. A Gröbner basis $G$ is called reduced when i) the leading term coefficients are all one and ii) there is no redundancy (see. Definition A.13.) in that any terms of $g \in G$ is not divisible by the leading term of other polynomials in $G$. We will include a few follow-up lines to make it more friendly to readers unfamiliar with Grönber bases.

Gröbner basis definition for non-experts. It is indeed very important to broaden the scope of readers by introducing some intuition on the definition of a Gröbner basis. We prepare the paragraph at [l.118] to give such an intuition of Gröbner bases, but it is true that this does not give an intuition of Definition 3.2. The suggested explanation elegantly presents the point of the definition, and we will integrate it into our explanation. Once our paper gets accepted, there will be an additional content page. We will exploit it.

We will clean up our manuscript by taking into account your comments on missing table references and providing a more friendly introduction to Gröbner bases. Again, we thank you for your strong support of our work.

We sincerely appreciate your thorough review and insightful comments. You raise the characterization of a subclass of polynomial systems as the main concern, and our rebuttal mostly focuses on this point. We would like you to refer to the Global Response as well.

On Weaknesses

Characterization of a subclass of polynomial systems. We appreciate your fundamental remark. We acknowledge that our paper does not provide a comprehensive characterization of the subclass of polynomial systems that can be efficiently solved using our transformer-based approach. Generally speaking, it is difficult to answer what problems can be solved by Transformers or what sample distributions are learnable by Transformers.

Instead, our study currently approaches the question: for what class of polynomial systems can we prepare a dataset efficiently for Transformer training? The trainablity in this sense should come before the learnability from a practical point of view. As an initial work, we break down the trainability question into two components: Gröbner basis sampling and backward Gröbner problem. These can be answered affirmatively through the design of algorithms. For the former, we suggest ideals in shape position, Cauchy module, and potentially, ideals of points (cf. Appendix~G). For the latter, we suggest 0-dimensional ideals (Theorem 4.7).

Number of variables This is also an important point. Ultimately, we envision that Transformers will be used for large-scale problems (i.e., problems with many variables and equations) that mathematical algorithms cannot address.

However, the number of variables that Transformer can handle is currently restrictive. The restriction comes from the current simple tokenization of polynomial systems: for example, {$x^2-10, y$} is tokenized as $`[x, **, 2, +, -10, <sep>, y]`$, (cf. Section 5). Eventually, a single $n$-variate term requires $O(n)$ tokens, leading to a long input sequence for large $n$. As well known in Transformer literature, the space complexity of the attention mechanism scales in $O(L^2)$, where $L$ denotes the input length.

The scope of this study is to establish the problem of learning to compute Gröbner bases, and thus, we tested its learnability based on a standard model, including tokenization. For scale-up, one may be able to embed a term by its coefficient (i.e., single token) and inject the exponent part as a position vector because this is literally a position in the term space. We are currently working on it in our follow-up paper.

It is also worth noting that even for $n=5$, we have observed a potential advantage of using machine learning. Table 22 shows that there are several instances in which Transformer models successfully compute Gröbner bases in less than a second, whereas algebraic methods take much longer (100 seconds and timeout for most cases).

Balance between theoretical and learning parts. Thank you for your fair evaluation and great writing suggestions. We indeed have a great algebraic interest in random generation of (non-Gröbner basis, Gröbner basis pair). We adopted the current structure by taking into account the potential readers (i.e., NeurIPS readers), who may be more interested in the learning part. We will reconsider the presentation. Thank you very much.

On Questions

We appreciate your insightful questions. We believe the learning approach of Gröbner bases has an advantage over algebraic algorithms for large-scale problems. However, as described above, the training on large $n$ requires an efficient input embedding of polynomial systems. We could also try larger $n$ by using a few more GPUs, but we considered this to be very interesting. It should be more reasonable to design an efficient input embedding for polynomial systems first and then see the impact of the increase in $n$ on the learning complexity. Here, we only provide quick answers to your questions below.

Largest number of variables with interesting results: We have only tested up to $n=5$. Even at this point, we have already observed interesting results, such as the contrast between infinite and finite fields (Table 2) and Transformer supremacy (Table 22).

Accuracy decay with the number of variables: The accuracy change with respect to the number of variables is given in Table 2, but the results would also change the density parameter $\sigma$. This is also a consequence of the input length restriction.

Relation between the number of variables and training time. We collected the training time from our experiment log and summarized it below. Note that the training time here can have been affected by the other processes running in parallel, so these numbers can be regarded as upper bounds. The table shows that we generally need longer training time for larger $n$. Not shown here, but we also tried longer training but we only observed a subtle improvement.

Thanks to the questions, we realize that there are two interleaving factors that affect the complexity of learning. For larger $n$, the Gröbner basis computation becomes algebraically more difficult. At the same time, dataset generation algorithms generate larger systems (i.e., longer input/target sequences), making learning more difficult from a machine learning perspective. We have to find a way to separate these factors for future discussion.

We appreciate your insightful and constructive comments and thorough review, as well as many pointers to related papers.

On Weaknesses

Choice of 0-dimensional ideals. We received several comments/questions about this assumption from several reviewers; please refer to the Global Response for the motivation for the choice.

Particular v.s. generic. You seem to find contradictive policies from our claims:

[l.178] ... focus on a particular class of ideals..."

[l.183] ..., the form of non-Gröbner sets varies across applications, and thus, we focus on the generic case and leave the specialization to future work.

The former claims the need to focus on a particular class of ideals as it is difficult to cover all the cases in a single work. The latter says that our way of particularization is more driven by a computer-algebraic viewpoint and not biased toward a single application. We will update our manuscript to avoid such confusion.

Hybrid input embedding. Thank you for completing our literature survey! In our reading, [2,4] rely on traditional discrete embedding based on mantissa (between 0 and 9999) and exponent, which requires keeping a large vocabulary and learning the numbers' relation from scratch. We found [3; Golkar+, Oct. 2023] to be close to our idea. The difference is that in their work, a real value is represented as the length of the embedding vector of the number token, while we use an MLP to find an embedding directly and have more degree of freedom (i.e., length and direction). Interestingly, Figure 1 shows that our embedding also encodes the values by the scale. We need experiments of Gröbner basis computation learning to check if their method outperforms ours and also discrete embedding. We will review and include them in our references.

In-distribution accuracy. We appreciate your pointer to an interesting work. It seems that the paper (particularly Table 2) indicates a potential generalization even for NP-hard problems. It is also very surprising to me that models trained on a 100-variable dataset perform better in a 600-variable dataset than in a 100-variable dataset. We are not sure if this is called generalization (although it is great).

As you claim here "in-distribution accuracy" is what we are after, it is important to include some experiments across different applications, to support this claim.

We don't claim that a generalization of learning is unachievable for NP-hard problems; we only present our picture of using Transformer for Gröbner basis computation. The learning approach may provide faster computation than classical algorithms, but the problem itself has been proven NP-hard, so machine learning models cannot break this.

On Questions

Dataset diversity. Table 6 provides several statistics of the datasets (we will make it cleaner in the update). The degrees and the number of terms have certain variances, which empirically shows diversity. Tables 4 and 22 also present the existence of hard samples for mathematical algorithms, which supports a certain diversity of the generated samples.

Theoretically, defining and measuring the diversity of generators is not very clear. For Gröbner basis sampling, we performed uniform sampling for degree, the number of terms, and so on, so the Gröbner bases were sampled uniformly randomly in a sense. For non-Gröbner sets computed from the Gröbner bases, a reasonable starting point would be the question on the reachability: can we sample all possible generating set $F$ such that $\langle F \rangle = \langle G \rangle$ from a Gröbner basis $G$? As of now, we suspect the answer is negative because we are based on Theorem 4.2 (2), a sufficient condition. We are now tackling designing an efficient algorithm based on Theorem 4.2 (3), a necessary and sufficient condition, but this requires a deeply algebraic discussion.

Generalization to the positive-dimensional case. Please kindly refer to the Global Response.