A Transformer-Derived Iterative Preconditioner

Patrick Lutz, Themistoklis Haris, Aditya Gangrade, Venkatesh SaligramaarXiv 2026 · arXiv

TL;DR

Researchers have discovered a powerful new numerical algorithm hidden within the internal weights of a trained Transformer. By reverse-engineering how a Transformer solves linear systems, they developed RAPID, a standalone, "anytime" preconditioner that significantly speeds up matrix computations without requiring any neural network inference at runtime.

What Problem Does This Paper Address?

Solving large-scale linear systems of the form $Ax = b$ is a fundamental task in scientific computing, engineering, and machine learning. When the matrix $A$ is Symmetric Positive Definite (SPD), the Conjugate Gradient (CG) method is the gold standard for finding a solution iteratively. However, CG's speed is dictated by the "condition number" of the matrix—the ratio of its largest to smallest eigenvalues. A high condition number leads to agonizingly slow convergence.

"Preconditioning" is the process of transforming the system into an equivalent one that is better conditioned. While many classical preconditioners exist (like Incomplete Cholesky or Nyström methods), they often require expensive setup phases or are sensitive to the specific distribution of eigenvalues. The authors sought to discover if modern AI architectures, specifically Transformers, could "learn" a more robust and efficient way to handle this classic numerical challenge.

Methods

The authors took a unique "AI-to-Algorithm" approach:

  1. Algorithm Discovery: They trained a softmax-attention Transformer on "in-context" linear regression tasks. To understand what the model was actually doing, they used layerwise symmetry interventions—randomly rotating the data at each layer to ensure the model's internal logic was coordinate-independent and thus identifiable.
  2. Extraction: They observed that the Transformer was implicitly performing a specific "congruence update" on the data's Gram matrix, effectively improving its conditioning layer by layer.
  3. RAPID (Randomized Anytime Preconditioning by Iterative Dynamics): They distilled this learned behavior into a standalone algorithm. RAPID alternates between two steps:
  4. Randomized Mixing: Using fast Walsh-Hadamard transforms to "shuffle" the matrix interactions across coordinates.
  5. Sparse Local Corrections: Each row identifies its smallest off-diagonal entry and applies a simple, sparse update to "weaken" that specific coupling.

Crucially, RAPID is an anytime algorithm. Unlike traditional methods that require a complete factorization before they can be used, RAPID produces a valid (and increasingly better) preconditioner at every single iteration.

Figure 1: Extracting a conditioning primitive. Left: Representative learned weight products WQK,ℓ and WV P,ℓ, 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.

Datasets

The authors evaluated RAPID's performance far beyond the Transformer's original training distribution:

  • Synthetic Spectral Families: 100 matrices each for four distinct eigenvalue distributions: Chebyshev, linear, logarithmic, and power-law (dimension $d=1024$).
  • SuiteSparse Matrix Collection: 31 real-world SPD matrices from diverse applications (e.g., structural engineering, fluid dynamics) with dimensions up to $d=6000$.

Key Insights and Ideas

  • Transformers as "Algorithm Miners": This paper proves that Transformers don't just approximate known math; they can discover entirely new, provably correct numerical primitives that we can extract and use independently of the neural network.
  • Local Actions, Global Impact: RAPID achieves global spectral improvement through purely local, sparse row updates. By repeatedly randomizing the "view" of the matrix (mixing), these local fixes eventually smooth out the entire spectrum.
  • Spectral Robustness: A major "aha" moment was finding that RAPID is largely indifferent to the shape of the matrix's spectrum. While methods like Nyström preconditioning excel on logarithmic spectra but struggle on others, RAPID provided consistent gains across all tested families.
  • Logarithmic Dependence: Theoretically, for an idealized version of the algorithm, the authors proved that the time to reach a target condition number depends only logarithmically on the initial conditioning, making it highly effective for very "difficult" matrices.

Key Results

RAPID demonstrated broad effectiveness across both synthetic and real-world benchmarks:

  • Conditioning Improvement: On synthetic data, RAPID reduced condition numbers by orders of magnitude. For real-world SuiteSparse matrices, it improved conditioning in 100% of the tested cases.
  • CG Speedup: These conditioning gains translated directly into faster solves. As shown in Figure 2, RAPID significantly reduced the number of CG iterations required to reach a target accuracy, often outperforming various configurations of the popular Nyström preconditioner.
  • Anytime Nature: The results show "progressive gains"—the more RAPID steps you take, the better the preconditioner becomes, allowing users to trade off setup time for solve speed dynamically.
Figure 2: Conditioning and CG convergence across synthetic and real-world SPD matrices. Top: condition number relative to the Jacobi-scaled system. Bottom: CG iterations required to reach the common residual tolerance, relative to Jacobi-preconditioned CG. Lower is better in both rows. Blue curves show RAPID means and shaded bands the minimum and maximum; dashed lines show mean Nyström results at different sketch sizes. Each synthetic panel contains 100 independent matrices; SuiteSparse contains 31. The corresponding absolute values are reported in Appendix B.

Limitations and Future Work

  • Computational Overhead: While RAPID reduces the number of iterations, each RAPID step currently costs $O(d^2 \log d)$. For a single right-hand side, the total "wall-clock" time might not yet beat a highly optimized standard CG solve. The authors suggest RAPID is best suited for scenarios where the preconditioner can be amortized over many different $b$ vectors.
  • Sparsity: The current algorithm treats matrices as dense. A major future direction is adapting RAPID to preserve the sparsity of the original matrix, which is critical for massive-scale scientific simulations.
  • Theoretical Gap: The convergence proof currently relies on "Haar mixing" (perfectly random rotations), whereas the practical algorithm uses the much faster Walsh-Hadamard transform. Closing this theoretical gap remains an open challenge.

Summary updated

Abstract

Transformers trained on in-context prediction problems can learn known numerical algorithms, e.g., gradient descent. We go further, showing that their internal computations can reveal new algorithms with provable guarantees. A softmax-attention transformer trained to solve linear systems $Xw=y$ implicitly improves matrix conditioning. Tracing $XX^\top$ reveals an iterative preconditioning primitive, which we develop into RAPID, a standalone algorithm requiring no learned components. RAPID is an anytime preconditioner for symmetric positive definite (SPD) matrices, using randomized mixing and sparse local corrections to improve conditioning. Proof-of-concept experiments on synthetic and real-world problems consistently improve conditioning and reduce conjugate gradient iterations needed to reach a target accuracy. For a Haar-mixing idealization, we prove convergence to any fixed target condition number regardless of spectral distribution, with only logarithmic dependence on initial conditioning. Together, these results show how a transformer can discover a broadly applicable numerical algorithm.
BibTeX
@misc{lutz2026transformer,
  author = {Patrick Lutz and Themistoklis Haris and Aditya Gangrade and Venkatesh Saligrama},
  title = {{A Transformer-Derived Iterative Preconditioner}},
  year = {2026},
  eprint = {2611.22941},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.22941},
}
Figure