cs.LGNov 17, 2026

A Transformer-Derived Iterative Preconditioner

Authors: Patrick Lutz, Themistoklis Haris, Aditya Gangrade, Venkatesh Saligrama

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 Xw=yXw=y implicitly improves matrix conditioning. Tracing XX⊤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.

Figures & tables

Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. RMNP: Row-Momentum Normalized Preconditioning for Scalable Matrix-Based Optimization

    Mar 20, 2026Shenyang Deng, Zhuoli Ouyang, Tianyu Pang +4Neural Network OptimizationMuon Optimizer

  2. Preconditioned Attention: Enhancing Efficiency in Transformers

    Mar 28, 2026Hemanth SaratchandranAttention MechanismsNeural Network Optimization

  3. A Neural Hierarchical-Matrix Preconditioner for Real-Time GPU Solves

    May 13, 2026Carl Osborne, Minghao Guo, Crystal Owens +1Graph Neural NetworksHigh-Performance Computing