# Affine Tracing: A New Paradigm for Probabilistic Linear Solvers

arXiv: https://arxiv.org/abs/2605.10566 · HTML: https://mlsanity.com/paper/2605.10566/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 26 references that are in the map.
- First posted on arXiv 11 May 2026.

## Builds on (most cited first, 8 of 8)

- [Posterior and Computational Uncertainty in Gaussian Processes](https://mlsanity.com/paper/2205.15449/) (2022)
- [Probabilistic Interpretation of Linear Solvers](https://mlsanity.com/paper/1402.2058/) (2014)
- [Computation-Aware Gaussian Processes: Model Selection And Linear-Time Inference](https://mlsanity.com/paper/2411.01036/) (2024)
- [Probabilistic Iterative Methods for Linear Systems](https://mlsanity.com/paper/2012.12615/) (2020)
- [Calibrated Computation-Aware Gaussian Processes](https://mlsanity.com/paper/2410.08796/) (2024)
- [Online Conformal Probabilistic Numerics via Adaptive Edge-Cloud Offloading](https://mlsanity.com/paper/2503.14453/) (2025)
- [Randomised Postiterations for Calibrated BayesCG](https://mlsanity.com/paper/2504.04247/) (2025)
- [Robust and Computation-Aware Gaussian Processes](https://mlsanity.com/paper/2505.21133/) (2025)

## Abstract (arXiv)

Probabilistic linear solvers (PLSs) return probability distributions that quantify uncertainty due to limited computation in the solution of linear systems. The literature has traditionally distinguished between Bayesian PLSs, which condition a prior on information obtained from projections of the linear system, and probabilistic iterative methods (PIMs), which lift classical iterative solvers to probability space. In this work we show this dichotomy to be false: Bayesian PLSs are a special case of non-stationary affine PIMs. In addition, we prove that any realistic affine PIM is calibrated. These results motivate a focus on (non-stationary) affine PIMs, but their practical adoption has been limited by the significant manual effort required to implement them. To address this, we introduce affine tracing, an algorithmic framework that automatically constructs a PIM from a standard implementation of an affine iterative method by passing symbolic tracers through the computation to build an affine computational graph. We show how this graph can be transformed to compute posterior covariances, and how equality saturation can be used to perform algebraic simplifications required for computation under specific prior choices. We demonstrate the framework by automatically generating a probabilistic multigrid solver and evaluate its performance in the context of Gaussian process approximation.