Computational Algebra with Attention: Transformer Oracles for Border Basis Algorithms

• URL: http://arxiv.org/abs/2505.23696v1
• Date: Thu, 29 May 2025 17:35:25 GMT
• Title: Computational Algebra with Attention: Transformer Oracles for Border Basis Algorithms
• Authors: Hiroshi Kera, Nico Pelleriti, Yuki Ishihara, Max Zimmer, Sebastian Pokutta,
• Abstract summary: We design and train a Transformer-based oracle that identifies and eliminates computationally expensive reduction steps.<n>We achieve substantial speedup factors of up to 3.5x compared to the base algorithm.<n>Our learning approach is data efficient, stable, and a practical enhancement to traditional computer algebra algorithms and symbolic computation.
• Score: 22.546453748805025
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Discovering Algorithms with Computational Language Processing [0.7062238472483737]
  We present a framework automating algorithm discovery by conceptualizing them as sequences of operations, represented as tokens.<n>These computational tokens are chained using a grammar, enabling the formation of increasingly sophisticated procedures.<n>Our ensemble Monte Carlo tree search (MCTS) guided by reinforcement learning (RL) explores token chaining and drives the creation of new tokens.
  arXiv  Detail & Related papers  (2025-07-03T21:45:17Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
  arXiv  Detail & Related papers  (2024-09-07T06:37:23Z)
• Algorithmic Language Models with Neurally Compiled Libraries [16.284360949127723]
  Large Language Models lack true algorithmic ability.<n>Our paper proposes augmenting LLMs with a library of fundamental operations and sophisticated differentiable programs.<n>We explore the feasability of augmenting LLaMA3 with a differentiable computer.
  arXiv  Detail & Related papers  (2024-07-06T00:27:05Z)
• From Decoding to Meta-Generation: Inference-time Algorithms for Large Language Models [63.188607839223046]
  This survey focuses on the benefits of scaling compute during inference. We explore three areas under a unified mathematical formalism: token-level generation algorithms, meta-generation algorithms, and efficient generation.
  arXiv  Detail & Related papers  (2024-06-24T17:45:59Z)
• Reverse That Number! Decoding Order Matters in Arithmetic Learning [49.5504492920404]
  Our work introduces a novel strategy that reevaluates the digit order by prioritizing output from the least significant digit. Compared to the previous state-of-the-art (SOTA) method, our findings reveal an overall improvement of in accuracy while requiring only a third of the tokens typically used during training.
  arXiv  Detail & Related papers  (2024-03-09T09:04:53Z)
• Automatic and effective discovery of quantum kernels [41.61572387137452]
  Quantum computing can empower machine learning models by enabling kernel machines to leverage quantum kernels for representing similarity measures between data.<n>We present an approach to this problem, which employs optimization techniques, similar to those used in neural architecture search and AutoML.<n>The results obtained by testing our approach on a high-energy physics problem demonstrate that, in the best-case scenario, we can either match or improve testing accuracy with respect to the manual design approach.
  arXiv  Detail & Related papers  (2022-09-22T16:42:14Z)
• Evolving Reinforcement Learning Algorithms [186.62294652057062]
  We propose a method for meta-learning reinforcement learning algorithms. The learned algorithms are domain-agnostic and can generalize to new environments not seen during training. We highlight two learned algorithms which obtain good generalization performance over other classical control tasks, gridworld type tasks, and Atari games.
  arXiv  Detail & Related papers  (2021-01-08T18:55:07Z)
• Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
  We create classical (non-quantum) dynamic data structures supporting queries for recommender systems and least-squares regression. We argue that the previous quantum-inspired algorithms for these problems are doing leverage or ridge-leverage score sampling in disguise.
  arXiv  Detail & Related papers  (2020-11-09T01:13:07Z)
• Quantum-Inspired Classical Algorithm for Principal Component Regression [1.9105479266011323]
  We develop an algorithm for principal component regression that runs in time polylogarithmic to the number of data points. This exponential speed up allows for potential applications in much larger data sets.
  arXiv  Detail & Related papers  (2020-10-16T20:50:48Z)
• Berrut Approximated Coded Computing: Straggler Resistance Beyond Polynomial Computing [34.69732430310801]
  We propose Berrut Approximated Coded Computing (BACC) as an alternative approach to deal with stragglers effect. BACC is proven to be numerically stable with low computational complexity. In particular, BACC is used to train a deep neural network on a cluster of servers.
  arXiv  Detail & Related papers  (2020-09-17T14:23:38Z)
• Approximation Algorithms for Sparse Principal Component Analysis [57.5357874512594]
  Principal component analysis (PCA) is a widely used dimension reduction technique in machine learning and statistics. Various approaches to obtain sparse principal direction loadings have been proposed, which are termed Sparse Principal Component Analysis. We present thresholding as a provably accurate, time, approximation algorithm for the SPCA problem.
  arXiv  Detail & Related papers  (2020-06-23T04:25:36Z)
• Decomposed Quadratization: Efficient QUBO Formulation for Learning Bayesian Network [0.0]
  It is essential to minimize the number of binary variables used in the objective function.<n>We propose a QUBO formulation that offers a bit capacity advantage over conventional quadratization techniques.
  arXiv  Detail & Related papers  (2020-06-12T03:19:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.