A Transformer-Derived Iterative Preconditioner
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.
Authors
- Patrick Lutz (ORCID: https://orcid.org/0000-0001-9930-4183)
- Aditya Gangrade
- Venkatesh Saligrama (ORCID: https://orcid.org/0000-0002-0675-2268)
- Themistoklis Haris (ORCID: https://orcid.org/0009-0009-4703-6266)
Publication Details
- Journal
- arXiv (Cornell University)
- Published
- 2026-11-17
- DOI
- https://doi.org/10.48550/arxiv.2611.22941
- Primary Topic
- Matrix Theory and Algorithms
- Type
- preprint