Paper 2025/2219
HATSolver: Learning Groebner Bases with Hierarchical Attention Transformers
, FAIR, Meta Superintelligence Labs, Sorbonne University, Graduate School of Computer Science and Advanced Technologies, FAIR, Meta Superintelligence LabsAbstract
At NeurIPS 2024, Kera et al. introduced the use of transformers for computing Groebner bases, a central object in computer algebra with numerous practical applications. In this paper, we improve this approach by applying Hierarchical Attention Transformers (HATs) to solve systems of multivariate polynomial equations via Groebner bases computation. The HAT architecture incorporates a tree-structured inductive bias that enables the modeling of hierarchical relationships present in the data and thus achieves significant computational savings compared to conventional flat attention models. We generalize to arbitrary depths and include a detailed computational cost analysis. Combined with curriculum learning, our method solves instances that are much larger than those in Kera et al. (2024 Learning to compute Groebner bases)
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Published elsewhere. Submitted to arxiv and iclr
- Keywords
- Multivariate CryptographyGroebner Basis ComputationMachine Learning
- Contact author(s)
-
mmalhou @ meta com
ludovic perret @ epita fr
klauter @ meta com - History
- 2025-12-12: approved
- 2025-12-09: received
- See all versions
- Short URL
- https://ia.cr/2025/2219
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/2219,
author = {Mohamed Malhou and Ludovic Perret and Kristin Lauter},
title = {{HATSolver}: Learning Groebner Bases with Hierarchical Attention Transformers},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/2219},
year = {2025},
url = {https://eprint.iacr.org/2025/2219}
}
