A preconditioner pulled out of a transformer's inner computation: RAPID lowers the condition number at every tested step on all 31 SuiteSparse matrices
Synopsis
A softmax-attention transformer trained only to predict in-context linear systems turns out, when its layers are traced, to apply a solution-preserving congruence update that improves the conditioning of the Gram matrix. The researchers distilled this into RAPID, a standalone algorithm with no learned components: it repeatedly applies random orthogonal mixing, then lets each row pick its smallest off-diagonal entry for a sparse correction. On four synthetic spectral families and 31 SuiteSparse symmetric positive definite matrices, RAPID reduced the condition number at every tested step count and cut the conjugate gradient iterations needed to reach a target accuracy.
Interpretation
A transformer trained to predict in-context linear systems is already improving matrix conditioning inside its layer-by-layer computation, and that effect can be extracted as a numerical algorithm independent of the model. Earlier work on in-context learning showed transformers can reproduce known algorithms such as gradient descent, preconditioned gradient descent and Newton-like methods; what emerged here is a preconditioning primitive not on that list of known algorithms. In the trained deep model, the median condition number of the Gram matrix falls from roughly 104 to below 103 at the best layer, and an approximate iteration that replaces each layer's weight products with two scalars reproduces predictions with a squared Pearson correlation of 0.9999 and a test MSE change of only 0.01%.
RAPID turns that primitive into an anytime preconditioner that acts directly on arbitrary symmetric positive definite matrices, producing a valid preconditioning factor at every step. Classical preconditioners usually build incomplete Cholesky factorizations, sparse approximate inverses or algebraic multigrid hierarchies, and randomized Nyström builds a one-shot low-rank approximation; RAPID instead repeatedly mixes coordinates and applies sparse local corrections, without explicitly computing eigenvectors or matrix inverses. Experiments cover four synthetic spectral families (Chebyshev, linear, logarithmic, power-law) and 31 SuiteSparse symmetric positive definite matrices selected by dimension and post-Jacobi condition number independently of RAPID's performance, all treated as dense operators.
The conditioning gains translate into fewer conjugate gradient iterations, improving progressively as RAPID steps increase. Against the Jacobi-scaled baseline, the comparison is randomized Nyström preconditioning, which is more sensitive to spectral structure: effective on the logarithmic spectrum but much weaker on Chebyshev and linear spectra even with large sketches. At every tested step count, RAPID reduced the condition number of all 31 SuiteSparse matrices, not just the average; all solvers reached the target accuracy, and only Nyström failed on a single SuiteSparse instance.
Perspective
The experiments cover symmetric positive definite matrices from four synthetic spectral families and 31 SuiteSparse matrices, all converted to dense form, with dimensions in the hundreds to thousands and post-Jacobi condition numbers around 102 to 105; the theoretical guarantee applies only to an idealized variant using Haar mixing and block-restricted row-min selection.
The convergence theorem relies on the rotational symmetry of Haar mixing to characterize the row-min drift, and the Walsh–Hadamard mixing actually used lacks that exact invariance, so transferring the guarantee remains open; the column-load bound under global row-min selection is supported only empirically. Per-step cost matches a dense conjugate gradient iteration up to logarithmic factors, but in practice a RAPID step can be more expensive because its operations lack equally optimized GPU implementations, and a definitive runtime comparison needs optimized implementations of both. Extending to sparse and matrix-free systems will require avoiding explicitly formed dense mixed matrices.
