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⊤ 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
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 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 .
Table 3
Appendix figures & tables9 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 3: Training curves for depth- 30 transformers. The loss is the squared error on the query prediction. Inputs and regression coefficients are resampled at every optimization step.
Figure 4: Prediction behavior across transformer depths. Left: Test MSE decreases with model depth, following a profile distinct from GD and CG at matched iteration budgets. Right: The fitted endpoint spectral gain approaches the OLS response 1/λ across eigendirections of X⊤X/d , including small eigenvalues.
Figure 5: Additional behavioral diagnostics. Left: Pearson correlations between centered residual-error vectors on shared test tasks. Transformer runs remain more aligned with each other than with GD or CG. Right: Squared residual fraction of the best linear query-to-prediction map for each context. The small residual at depth 30 supports the spectral-filter interpretation.
Figure 6: Fidelity of the projected iteration. Each point compares the original depth- 30 transformer prediction with the prediction from the two-scalar projected iteration on the same held-out task. The high R2 shows that the low-dimensional projection captures the dominant predictive behavior of the trained model.
Figure 7: Conditioning overview. Left: Condition number of Gℓ=XℓXℓ⊤ across layers of the trained transformer. Center: The corresponding trajectory under the two-scalar approximation. Both reduce the median condition number from above 3×103 to below 10 at the best layer. Right: Distribution of learned step sizes αℓ , most of which lie close to the sufficient invertibility threshold αℓ=1 .
Figure 8: Layerwise sign rule and conditioning. Layerwise condition numbers compared with the empirical criterion sign(αℓ)=sign(γℓ) and ∣αℓ∣<1 . Layers satisfying this rule typically decrease the condition number.
RAPID steps T
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
Appendix
Table 3: Absolute condition numbers and CG iterations. Mean values across 100 independent matrices per synthetic family and 31 SuiteSparse matrices. All RAPID runs reached the target accuracy ( 100/100 per synthetic family and 31/31 for SuiteSparse) at every tested step count. The only non-convergent run was Nyström with a 1% sketch on the SuiteSparse matrix Cylshell/s1rmt3m1 . These averages of absolute quantities differ from the averages of per-instance ratios shown in Figure 2 .
Figure 9: Empirical load scaling for the unblocked selector. Left: distribution of Sβ/m(A) versus dimension, aggregated over all retained spectra and Haar trials. Right: median Sβ/m(A) by spectral family. In all tested cases the ratio remains bounded away from zero.
d
# spectra
min mSβ
10th perc. mSβ
median mSβ
median m
90th perc. m
max m
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
Appendix
Table 4: Aggregate statistics for the unblocked load experiment. Each row aggregates over all retained spectra and Haar trials at the given dimension.
Preconditioned adaptive methods have gained significant attention for training deep neural networks, as they capture rich curvature information of the loss landscape. The central challenge in this field lies in balancing preconditioning effectiveness with computational efficiency of implementing the preconditioner. Among recent advances, Muon stands out by using Newton-Schulz iteration to obtain preconditioned updates without explicitly constructing the preconditioning matrix. Despite its advantages, the efficiency of Muon still leaves room for further improvement. In this paper, we introduce RMNP (Row Momentum Normalized Preconditioning), an optimizer that replaces Newton-Schulz iteration with a simple row-wise (din) ℓ2 normalization operation, motivated by the empirically observed diagonal block structure of the Transformer layerwise Hessian. We empirically verified that orthogonalization and row-wise (on input dim) ℓ2 normalization are asymptotically equivalent in the case of the transformer. This substitution reduces the per-iteration computational complexity from O(mn⋅min(m,n)) to O(mn) for an m×n weight matrix while maintaining comparable optimization performance. Theoretically, we establish convergence guarantees for RMNP in the non-convex setting that match recent results for Muon optimizers, achieving the minimax optimal complexity. Extensive experiments on large language model pretraining show that RMNP delivers competitive optimization performance compared with Muon while substantially reducing preconditioning wall-clock time. Our code is available at https://github.com/Dominator-Index/RMNP.
Shenyang Deng, Zhuoli Ouyang, Tianyu Pang +4
Dartmouth College · International Computer Science Institute · University of California, Berkeley +1
Central to the success of Transformers is the attention block, which effectively models global dependencies among input tokens associated to a dataset. However, we theoretically demonstrate that standard attention mechanisms in transformers often produce ill-conditioned matrices with large condition numbers. This ill-conditioning is a well-known obstacle for gradient-based optimizers, leading to inefficient training. To address this issue, we introduce preconditioned attention, a novel approach that incorporates a conditioning matrix into each attention head. Our theoretical analysis shows that this method significantly reduces the condition number of attention matrices, resulting in better-conditioned matrices that improve optimization. Conditioned attention serves as a simple drop-in replacement for a wide variety of attention mechanisms in the literature. We validate the effectiveness of preconditioned attention across a diverse set of transformer applications, including image classification, object detection, instance segmentation, long sequence modeling and language modeling.
Hemanth Saratchandran
Australian Institute for Machine Learning (AIML), Adelaide University
Interactive simulation solves Ax=b for a sparse SPD A that changes every frame, inside an 8-16 ms budget. At a few thousand unknowns, the setup of algebraic multigrid alone exceeds that budget, while Jacobi and other local preconditioners have no setup but cannot move error across the domain. We learn a preconditioner for this gap: a graph-and-attention network predicts an SPD approximate inverse in H^2-matrix format. On a spatially ordered 3D mesh, blocks of the true inverse lose rank as the clusters they couple move apart; the nested bases of the format follow that decay, so inference and apply are dominated by leaf-block work linear in N, where a dense inverse costs N^2. Our main finding concerns training. Probe losses reach M only through a product with A, so their gradient vanishes on the near-null modes that set the conjugate-gradient iteration count. A truncated Kaporin condition number has no such factor; changing only the objective cuts iterations on a held-out frame from 116 to 33. On a ladder of stiff tetrahedral diffusion problems ours alone fits an 8.3 ms (120 fps) frame from N=572 to 3,647.