Grafy News
Try Grafy free

Researchers derive new numerical algorithm from transformer logic

Researchers have extracted a new preconditioning primitive from trained transformers to create RAPID, a standalone algorithm for solving linear systems.

Illustration for the news story: Researchers derive new numerical algorithm from transformer logicSource: Grafy Research Lab

Researchers have successfully extracted a new numerical algorithm from the internal computations of a trained transformer model. This discovery, detailed in a paper by Patrick Lutz, Themistoklis Haris, Aditya Gangrade, and Venkatesh Saligrama, leads to the creation of RAPID, a standalone preconditioning algorithm that requires no learned components to function.

How was the new algorithm discovered?

Historically, studies have shown that transformers can implement known numerical methods, such as gradient descent, through in-context learning. The researchers at Boston University took this a step further by investigating whether the internal mechanics of these models could reveal entirely new mathematical primitives.

By training a softmax-attention transformer to solve linear systems of the form Xw=yXw=y, the team monitored how the model's internal computations affected the conditioning of the Gram matrix Gℓ=XℓXℓ⊤G_{\ell} = X_{\ell}X_{\ell}^{\top}. Figure 1 shows that as data passes through the layers, the median condition number of the context Gram matrix decreases significantly, dropping from approximately 3,000 to below 10 at the most effective layer. This indicates that the transformer is implicitly performing a mathematical operation to make the system easier to solve.

Figure 1: Extracting a conditioning primitive. Left: Representative learned weight products WQK,ℓ and WVP,ℓ, showing the dominant two-scalar structure in Eq. (3). Right…
Figure 1. Extracting a conditioning primitive. Left: Representative learned weight products WQK,ℓ and WVP,ℓ, showing the dominant two-scalar structure in Eq. (3). Right: Median condition number of the context Gram matrix across layers of the trained transformer, decreasing from roughly 3,000 to below 10 at the best layer. Figure 1 of “A Transformer-Derived Iterative Preconditioner” by Patrick Lutz, Themistoklis Haris, Aditya Gangrade et al. (arXiv.org), CC BY 4.0.

What is the RAPID algorithm?

Following the discovery of this conditioning primitive, the authors developed RAPID (Randomized Anytime Preconditioning by Iterative Dynamics). Unlike the transformer that inspired it, RAPID is a standalone algorithm designed for symmetric positive definite (SPD) matrices.

According to the authors, RAPID improves global conditioning through a two-step iterative process. First, it uses random orthogonal mixing to redistribute matrix interactions without altering the spectrum. Second, it applies sparse local corrections by having each row select its smallest off-diagonal entry and applying a correction to weaken that specific coupling. This process accumulates transformations into a preconditioning factor PtP_{t}, resulting in a transformed system At=PtAPt⊤A_{t}=P_{t}AP_{t}^{\top}.

Why is an "anytime" preconditioner significant?

Most classical preconditioning methods require a complete setup phase, such as computing an approximate factorization, before they can be used. RAPID is described as an "anytime" algorithm because each individual iteration produces a valid preconditioner.

This flexibility allows users to balance the computational cost of the setup against the quality of the preconditioner. In practice, a user can stop the RAPID iterations early if they reach a sufficient level of conditioning, whereas traditional methods often require the full computation to be useful. This makes the algorithm particularly well-suited for highly parallel dense implementations.

What are the performance guarantees of RAPID?

The researchers provided both theoretical and empirical evidence for the algorithm's effectiveness. For an idealized version of RAPID using Haar mixing and block-restricted corrections, they proved that it can reach any fixed target condition number in O(dlog⁡dlog⁡κ(A))O(d\log d\log\kappa(A)) expected iterations, where dd is the dimension and κ(A)\kappa(A) is the initial condition number.

In empirical tests involving 31 SuiteSparse SPD matrices and various synthetic spectral families, RAPID consistently improved conditioning and reduced the number of iterations required by the conjugate gradient (CG) method to reach target accuracy. The authors noted that RAPID outperformed randomized Nyström preconditioning, which proved more sensitive to the specific spectral structure of the matrices.

How does this relate to modern AI research?

This work represents a shift from using AI simply as a tool for prediction to using AI as a laboratory for mathematical discovery. By analyzing the "black box" of transformer attention mechanisms, researchers can identify structured mathematical behaviors that are then translated into efficient, traditional code. This bridge between connectionist models (neural networks) and symbolic/numerical mathematics offers a new pathway for developing robust, high-performance computing tools.

For researchers looking to dive deeper into the technical specifics of this paper, such as the Haar Block-Row-Min Guarantee or the spectral inverse-kernel diagnostics, the Reader app in Grafy allows you to upload the PDF and perform deep research, asking specific questions about the mathematical proofs or experimental setups.

Frequently asked questions

What is the main purpose of the RAPID algorithm?

The RAPID algorithm serves as an anytime preconditioner for symmetric positive definite matrices. Its primary goal is to improve the conditioning of a linear system through randomized mixing and sparse local corrections, which ultimately reduces the number of iterations needed for solvers like the conjugate gradient method to reach a solution.

How does RAPID differ from the transformer that inspired it?

While the transformer uses learned weights and attention mechanisms to perform in-context learning, RAPID is a standalone numerical algorithm that requires no learned components. It translates the mathematical primitive discovered within the transformer's layers into a purely algorithmic process using randomized rotations and sparse updates.

Does RAPID require a complete setup before it can be used?

No, RAPID is an anytime algorithm, meaning that every iteration produces a valid preconditioner. This allows users to stop the process at any point to balance the time spent on preconditioning against the expected speedup in the subsequent solving phase, providing more flexibility than traditional factorization methods.


Source: Grafy Research Lab — A Transformer-Derived Iterative Preconditioner