A Transformer-Derived Iterative Preconditioner
Organizations: Departments of Computer Science and Electrical and Computer Engineering Boston University
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 implicitly improves matrix conditioning. Tracing 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.
Figures & tables
Appendix figures & tables9 assets
Supplementary material from the paper’s appendix.
Appendix
| RAPID steps | |||||||
| Dataset | Jacobi baseline | 10 | 20 | 50 | 100 | 200 | 500 |
| Condition number | |||||||
| Chebyshev | 10,155.43 | 10,402.86 | 9,371.71 | 6,106.86 | 2,746.62 | 480.23 | 4.89 |
| Linear | 10,007.98 | 9,342.59 | 8,066.53 | 4,816.50 | 1,857.98 | 228.63 | 4.82 |
| Logarithmic | 9,978.65 | 7,429.91 | 5,697.62 | 2,983.64 | 1,316.00 | 330.48 | 6.07 |
| Power-law | 10,010.99 | 8,940.11 | 7,707.07 | 4,845.05 | 2,216.73 | 425.81 | 4.94 |
| # spectra | min | 10th perc. | median | median | 90th perc. | max | |
| 32 | 67 | 0.814 | 1.045 | 1.207 | 5 | 15 | 24 |
| 64 | 67 | 0.804 | 1.031 | 1.228 | 7 | 22 | 42 |
| 128 | 75 | 0.810 | 0.993 | 1.235 | 8 | 37 | 81 |
| 256 | 75 | 0.753 | 0.996 | 1.240 | 9 | 117 | 152 |
| 512 | 76 | 0.706 | 0.941 | 1.326 | 9 | 121 | 289 |
| 1024 | 76 | 0.706 | 0.893 | 1.320 | 9 | 265 | 561 |
Transformer
Transformers are neural architectures that use attention to model relationships among sequence elements in language, vision, and scientific data.
See all 583 papers