Affine Tracing: A New Paradigm for Probabilistic Linear Solvers

arXiv:2605.10566 · stat.ML, cs.LG, cs.NA, math.NA · Submitted 2026-05-11 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: We're looking at the paper: "Affine Tracing: A New Paradigm for Probabilistic Linear Solvers".

Jane: Here's the gist of the paper. Probabilistic linear solvers (PLSs) return probability distributions that quantify uncertainty due to limited computation in the solution of linear systems.

Tom: This work shows that Bayesian PLSs are a special case of non-stationary affine PIMs and proves that any realistic affine PIM is calibrated.

Jane: Dichotomy between solver types 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.

Tom: This paper shows this dichotomy to be false: Bayesian PLSs are a special case of non-stationary affine PIMs.

Title and authors: Tom: So we're looking at this paper by Disha Hegde and Marvin Pförtner and Jon Cockayne titled Affine Tracing: A New Paradigm for Probabilistic Linear Solvers. It looks like they are tackling something that has been a big sticking point in the field of probabilistic linear solvers.

Jane: Right, it seems like they're addressing that divide between Bayesian solvers and probabilistic iterative methods, which is a concept that’s been around for a while. What do you think the core problem they're trying to solve here is?

Tom: Basically, the literature has usually kept these two approaches separate—Bayesian ones condition a prior on the solution, and probabilistic iterative methods lift classical solvers into probability space. But this paper shows that this separation isn't real; Bayesian linear solvers are actually just a specific kind of non-stationary affine probabilistic iterative method.

Lu: That really shifts the focus because it means we can unify these ideas under one framework instead of having to choose between them when we implement things. The main thrust is showing that any realistic affine probabilistic iterative method is calibrated, which is pretty important for real applications.

Meng: Calibration sounds good in theory, but from where I'm sitting at the startup level, what does this mean for deployment? Does it mean we can finally trust the uncertainty estimates we get from these solvers when we put them into production systems?

Lalam: Based on what I've processed, the core idea is that they introduce an algorithmic framework called affine tracing to automatically build a probabilistic iterative method directly from a standard affine iterative solver implementation. This cuts out the huge manual effort required for those complex algebraic manipulations.

Jane: So, instead of us having to write all that specific probabilistic machinery ourselves, this tracing method just lets us pass symbolic tracers through the computation to build an affine computation graph automatically? That sounds like it could save a ton of time for researchers trying to prototype these solvers.

Tom: Exactly. And they show that this framework can even be used to automatically generate complex solvers, like a probabilistic multigrid solver, which usually requires a lot of manual derivation effort from the ground up.

Lu: That’s huge for experimentation because it means we don't have to spend months deriving every new algorithm just to make it probabilistic and calibrated. They show that Bayesian methods are instances of these affine PIMs and that any affine PIM is calibrated, which validates focusing on this specific class of solvers.

Meng: I'm interested in the practical side because the paper mentions some specific mathematical tricks they use, like equality saturation to do algebraic simplifications under certain prior choices. How much does that simplification actually help when we're dealing with massive systems?

Title and authors: Jane: Well, they show that this framework helps resolve problems related to implicitly defined matrices and cross-covariance terms in these solvers. And one of the interesting points is how it connects to computation-aware Gaussian processes, or CAGPs.

Tom: That connection is interesting because when the solver has a specific posterior form, N (x, A inverse minus D), there's this cancellation of terms involving A inverse in the covariance kernel that leads directly to that CAGP posterior structure.

Lalam: So they’re showing that by using affine tracing, we can explore these affine probabilistic iterative methods more straightforwardly to find ones that not only maintain those calibration guarantees but also converge quickly.

Lu: Their theoretical results are pretty solid because they prove two things: first, that (affine-Gaussian) Bayesian methods are indeed instances of PIMs, and second, that the only requirement for an affine iterative method to be calibrated is having the fixed point property.

Jane: The fixed point property sounds simple enough to check in practice, but proving that this is sufficient for calibration across all realistic affine methods is a big theoretical win here. It suggests we don't need impossibly complex priors to get reliable uncertainty estimates.

Tom: And on the implementation side, they show that their affine traced version is always faster than the non-traced counterpart, and that the time gap actually gets bigger as the system dimension increases. That’s a strong performance indicator for any practical application.

Meng: Speed matters when you're shipping models. If this method is genuinely faster at scale, that changes how we even think about fitting these solvers into our inference pipelines. But what about those limitations they mention?

Jane: They do mention some limitations, specifically that the equality saturation approach can sometimes lead to computational graphs that are too large and complex for easy simplification. That’s something to keep in mind when you start trying to apply it directly.

Tom: Yeah, so while the framework is powerful for building these solvers from scratch, we still have to be careful about the size of the graph they generate before we can use their algebraic simplifications effectively.

Lu: Looking ahead, they point out that a challenge remains when you try to relax the affine assumption and move toward methods like Krylov methods, because that's where tractability gets really hard again.

Jane: So it sounds like the big takeaway is that we have a much more unified and automated path to building these probabilistic solvers without getting bogged down in manual algebraic heavy lifting. We’ll keep an eye on how they tackle those affine assumptions next.

Tom: Agreed. The paper, Affine Tracing: A New Paradigm for Probabilistic Linear Solvers, gives us a way to build complex solvers by focusing on the affine structure and letting the tracing handle the probabilistic lifting automatically. That's what we have here for today.

The paper's summary: Tom: So, to wrap up what we just heard, these authors are saying that Bayesian solvers are really just a specific type of probabilistic iterative method, which is pretty important for how we think about uncertainty in these systems.

Jane: Right, it sounds like they're removing that old divide between the two approaches. Instead of choosing between Bayesian and iterative methods when you’re implementing something, they show you can treat them all under one umbrella.

Lu: The big point is that any realistic affine probabilistic iterative method is calibrated. That means if a solver meets a basic requirement, it will give you reliable uncertainty estimates for real-world problems.

Meng: Calibration sounds good in theory, but what does that mean when we’re actually shipping these models? Does it mean we don't have to worry about the priors we pick being completely wrong?

Tom: It means they prove that only one thing matters for calibration: the fixed point property of the method. If a solver has that property, it's calibrated, regardless of how complex its prior setup is.

Jane: That’s a relief because it simplifies things immensely for anyone trying to build a solver from scratch. It tells us we don't need impossibly complicated math just to get reliable results when we condition our information on projections of the system.

Lu: They introduce this new tool called affine tracing. It lets you take a standard implementation of an affine iterative method and automatically turn it into a full probabilistic iterative method by building an affine computational graph.

Tom: So, it automates the hard part—the manual effort to reimplement all that complex probabilistic machinery. No more bespoke numerical analysis just to make your solver work probabilistically.

Jane: Exactly, and they show you can use this tracing framework to automatically generate solvers like a probabilistic multigrid solver without having to do all that heavy mathematical derivation yourself.

Meng: If it can generate something like a multigrid solver automatically, that's a huge win for production deployment because those things are often slow on real traffic.

Lu: And they show that this tracing method resolves issues with implicit matrices and cross-covariance terms, which is where most people get stuck when dealing with these systems.

Tom: Plus, there’s this neat trick called equality saturation that helps simplify the math needed for computation under specific prior choices, like when you use an inverse prior. It leads to a structure they call a downdate term.

Jane: That downdate structure is what makes the computation efficient when you’re using those specific types of priors, and it shows how this framework helps us find solvers that are both fast to converge and guaranteed to be calibrated.

Lu: The paper also connects this method to computation-aware Gaussian processes, or CAGPs. When the solver has a specific type of posterior, there's a cancellation happening in the covariance kernel that makes things much simpler computationally.

Tom: It means we can explore these affine probabilistic iterative methods more easily now and identify ones that keep those calibration guarantees while also being fast enough to run at scale.

Jane: So, the big picture is that we have this automated way to build solvers from a standard starting point, focusing on the affine structure, and you get a method that’s calibrated and efficient. But they do flag one limitation: the equality saturation approach can sometimes generate graphs that are just too big for easy simplification.

Lu: And they also noted that if you want to move beyond the affine assumption toward methods like Krylov methods, things get really hard again with tractability.

Tom: So the main thing is this unified framework for building these solvers automatically, but we still have to be careful about the size of those graphs and how well it handles those non-affine assumptions.

The paper's improvements: Tom: So, we’re talking about how they suggest improving this whole framework for building these probabilistic solvers from scratch. It seems like they aren't just stopping at tracing a graph, right?

Jane: Right, I mean the paper mentions using equality saturation more effectively to do those algebraic simplifications under certain prior choices. That sounds like a real optimization for speed.

Lu: Exactly, because that simplification leads to this specific structure they call a downdate term which is crucial for efficiency when you're using an inverse prior. It’s not just about making the graph smaller; it’s about making the math under those specific assumptions easier to handle at scale.

Meng: So what does that mean for my deployment? If I can use these simplifications, does it mean my solver runs faster on a real machine, or is it just a theoretical speedup?

Tom: It’s both. They show that the affine traced version is always faster than the non-traced version, and this simplification helps push that speed gap even wider as the system gets bigger. That’s tangible performance for us.

Jane: And they connect this to computation-aware Gaussian processes, which means when you use a specific posterior form, there's a cancellation of terms involving the inverse matrix in the covariance kernel. That makes exploring those complex models much more straightforward computationally.

Lu: They are basically showing that this framework lets you find methods that maintain those calibration guarantees while also providing fast convergence for things like computation-aware Gaussian processes. It helps select solvers that hit both performance and calibrated uncertainty quantification targets at once.

Tom: That’s a big win because we need tools where the uncertainty estimate is trustworthy, not just fast to compute. So, if I want to deploy a solver for an AI application where I need reliable error bars, this method seems like it gives me the best path forward right now.

Jane: It does feel like they’ve given us a much clearer map for how to build these things without having to reinvent the wheel on every single step of probabilistic lifting. But there are still those caveats, so we have to keep an eye on that graph size issue and the difficulty when you try to relax the affine assumption later.

Lu: That’s where they stop for now; if you want to move away from affine structures toward methods like Krylov methods, tractability becomes a huge problem again. That’s the next frontier for research in this area.

Meng: So, the immediate improvement is speed and reliability within the affine class, but the long-term challenge is moving to more general mathematical structures that aren't so restrictive. That’s a fair assessment of where we are right now at scale.

Conclusion: Tom: So we're wrapping up this look at "Affine Tracing: A New Paradigm for Probabilistic Linear Solvers." Essentially, they’ve shown that we can build these complex probabilistic solvers much more automatically by focusing on the affine structure of the problem and using tracing to handle the probabilistic lifting.

Jane: It really comes down to unifying Bayesian solvers with iterative methods so you don't have to choose between them when you're implementing something, which is a big relief for anyone trying to get uncertainty quantification working in production.

Lu: They proved that any realistic affine probabilistic iterative method is calibrated, meaning if it has that basic fixed point property, it’s reliable for real applications. That shifts the focus onto these specific solvers instead of having to worry about overly complex priors.

Meng: From an engineering standpoint, this means less manual derivation effort to generate a solver, but I still have concerns about the size of those computational graphs they build; what breaks at scale is still a risk if the tracing gets too messy.

Lalam: I'm confident in this finding because it connects Bayesian methods directly to probabilistic iterative methods, and that theoretical backing is very strong. It’s a solid foundation for moving forward with these solvers.

Tom: It's an interesting piece of work because it provides a clear path forward for people who want to build robust solvers without getting bogged down in the lowest level of numerical analysis every single time.

Jane: They also showed how this framework helps us identify solvers that are both fast and calibrated, specifically mentioning computation-aware Gaussian processes as an example where this combination really shines.

Lu: The structure they found for the downdate term is key for efficient computation under those inverse priors, which is a specific trick that makes the whole process run much smoother.

Meng: I just hope that when we try to deploy these auto-generated solvers, they aren't fragile when we introduce more complex, non-affine dynamics later on. That’s the main technical hurdle they flagged for future work.

Tom: So the big picture here is that affine tracing gives us a much more unified and automated way to build these probabilistic solvers without getting bogged down in manual algebraic heavy lifting, which is pretty exciting for model development.

Jane: It's a solid paper, "Affine Tracing: A New Paradigm for Probabilistic Linear Solvers," that sets a new standard for how we approach uncertainty quantification in linear systems.

Lu: We should keep an eye on those future works exploring Gaussian approximations to relax the affine assumption, because that’s where the real challenge lies if you want to apply this idea to more general Krylov methods.

Meng: For now, it looks like a powerful tool for getting fast and reliable solvers in place quickly, even if we still have some cleanup work on the complexity of those generated graphs.

University of Southampton · T࿏bingen AI Center, University of T࿏bingen

stat.ML, cs.LG, cs.NA, math.NA

Submitted: 2026-05-11

Updated: 2026-11-10

Comments: Accepted at the 40th Conference on Neural Information Processing Systems (NeurIPS 2026)

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 87/100

The gist: Probabilistic linear solvers (PLSs) return probability distributions that quantify uncertainty due to limited computation in the solution of linear systems.

Key concepts

Bayesian PLSs
Probabilistic Linear Solvers (PLSs) that return probability distributions to quantify uncertainty in linear system solutions. These methods condition a prior on information derived from projections of the linear system, providing a probabilistic view of the solution.
Probabilistic Iterative Methods (PIMs)
Methods that lift classical iterative solvers into a probabilistic space. They are used to solve problems by incorporating probability into the iteration process, allowing for uncertainty quantification alongside standard iterative techniques.
Affine Tracing
An algorithmic framework that automatically constructs a PIM from a standard affine iterative method. It works by passing symbolic tracers through the computation to build an affine computational graph, simplifying the manual effort needed for probabilistic implementation.
Calibration
A property of iterative methods ensuring that the uncertainty estimates provided by the solver are accurate and reliable. The paper proves that any realistic affine PIM is calibrated, meaning its uncertainty quantification is trustworthy.

Terminology

Summary

Probabilistic linear solvers (PLSs) return probability distributions that quantify uncertainty due to limited computation in the solution of linear systems. p. 0

Where the paper says it

Affine Tracing: A New Paradigm for Probabilistic Linear Solvers Disha Hegde1 Marvin Pförtner2 Jon Cockayne1 1University of Southampton 2Tübingen AI Center, University of Tübingen 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.

This work shows that Bayesian PLSs are a special case of non-stationary affine PIMs and proves that any realistic affine PIM is calibrated. p. 0
Where the paper says it

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.

Dichotomy between solver types

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. This paper shows this dichotomy to be false: Bayesian PLSs are a special case of non-stationary affine PIMs. p. 0

Where the paper says it

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.

Furthermore, it is shown that any realistic affine PIM is calibrated. p. 0
Where the paper says it

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.

Algorithmic framework

To address the manual effort required to implement these methods, the authors 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. This graph can be transformed to compute posterior covariances, and equality saturation can be used to perform algebraic simplifications required for computation under specific prior choices. p. 0

Where the paper says it

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.

The framework is demonstrated by automatically generating a probabilistic multigrid solver and evaluating its performance in the context of Gaussian process approximation. p. 0
Where the paper says it

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.

Theoretical results

The paper proves two key theoretical results that justify focusing on PIMs. First, it shows that (affine-Gaussian) Bayesian methods are instances of PIMs. p. 5

Where the paper says it

Theoretical Results We prove two key theoretical results that justify a focus on probabilistic iterative methods. First, we show that (affine-Gaussian) Bayesian methods are instances of PIMs.

Second, it proves strong calibration of essentially any affine iterative method by showing that the only requirement is the fixed point property. p. 5
Where the paper says it

Our next theoretical result proves strong calibration of essentially any affine iterative method. The only requirement is that the iterative map have the fixed point property, which is a benign requirement of an iterative method.

Implementation and performance

The affine tracing methodology resolves challenges related to implicitly defined matrices and cross-covariance terms. The paper demonstrates that the affine traced version is always faster than its counterpart, with the time gap increasing with system dimension. This is shown in synthetic CAGP problems where multigrid variants using affine tracing provide state-of-the-art performance. p. 2

Where the paper says it

compared to existing, state-of-the-art PLSs, by applying it in Gaussian process approximation. Structure of the paper The rest of the paper is structured as follows.

Computation-Aware Gaussian Processes

The work shows that when the PLS has a posterior of the form N (x, A ˆ−1 − D), a cancellation of terms involving A−1 in the covariance kernel occurs, resulting in the CAGP posterior. This motivates interest in the downdate term D for efficient computation. p. 8

Where the paper says it

Therefore, if Σ0 = A−1 , we have the simplification: Σi = A −1 − M¯ i − M¯ ⊤ i + M¯ iAM¯ ⊤ i = A −1 − Di . (4) In most applications of the inverse prior, only the downdate term Di is required for computation.

The authors show that affine tracing enables more straightforward exploration of affine PIMs to identify methods which maintain calibration guarantees while also providing fast convergence. p. 5
Where the paper says it

Again, the Gaussian algebra that this enables is fundamental to the proof, and completely different proof techniques would be needed to study calibration of PIMs constructed from non-affine maps. Implementation: Affine Tracing There are two central challenges associated with implementation of PLSs that we aim to address in this section: 1.

Limitations and future work

Limitations include the brittleness of the equality saturation approach, which results in graphs that are too large and complex for simplification. Future research could investigate bespoke simplification algorithms for the inverse prior or explore Gaussian approximations to relax the affine assumption. p. 1

Where the paper says it

We also show that focussing on probabilistic iterative methods allows us to perform the lifting to probability space algorithmically, rather than using pen-and-paper calculations, by transforming computational graphs constructed from an implementation of the classical underlying iterative method, in an approach we refer to as affine tracing. This relieves a significant bottleneck in probabilistic linear algebra: the requirement to reimplement probabilistic algorithms requires completely new, often bespoke numerical analysis and algebraic manipulations to be performed for efficiency or to perform cancellations to use particular prior structures.

The central challenge remains tractability when relaxing the affine assumption to Krylov methods. p. 3
Where the paper says it

, 2025] and conformal approaches [Hou et al. This highlights a central challenge with Bayesian methods: the choice of search directions Si is crucial, and approaches which lead to fast convergence tend to be poorly calibrated due to incorrect application of Bayes rule.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Bayesian PLSs can be directly implemented as non-stationary affine PIMs, which allows for a more unified theoretical framework rather than a dichotomy between Bayesian and non-Bayesian methods. This means practitioners can focus on probabilistic iterative methods while retaining the benefits of prior conditioning.

  2. Affine tracing provides an automated way to construct a Probabilistic Iterative Method from standard implementations of affine iterative methods by passing symbolic tracers through the computation to build an affine computational graph. This removes the significant bottleneck in probabilistic linear algebra: the requirement to reimplement probabilistic algorithms requires completely new, often bespoke numerical analysis and algebraic manipulations.

  3. The framework can be used to automatically generate sophisticated solvers like a probabilistic multigrid solver, which would otherwise require significant mathematical derivation effort, thereby enabling researchers to experiment with complex methods without needing bespoke implementations.

  4. Equality saturation can be used to perform algebraic simplifications required for computation under specific prior choices, specifically when dealing with the inverse prior. This leads to the identification of a downdate structure like Di = S(Mi) + X i−1 j=1 Gi:j+1S(Mj)G⊤i:j+1, which is crucial for efficient computation under the inverse prior.

  5. The system can be optimized for computation-aware Gaussian processes by exploiting the fact that when the PLS has a posterior of the form N (x, A ˆ−1 − D), a cancellation of the terms involving A−1 in the covariance kernel occurs, resulting in a simplified posterior kernel without needing to compute full matrix inverses.

  6. The system can be used to identify methods that maintain the calibration guarantees provided in Hegde et al. [2025], while also providing fast convergence, allowing for the selection of solvers that offer both high performance and calibrated uncertainty quantification for applications like computation-aware Gaussian processes (CAGPs).

Abstract

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.

Sources

Related papers