🔢 mathematics

Precision autotuning for linear solvers via contextual bandit-based RL

This paper proposes a contextual bandit-based reinforcement learning framework that dynamically selects optimal precision configurations for linear solvers, effectively reducing computational costs while maintaining accuracy comparable to double-precision baselines across both training and unseen datasets.

Original authors: Erin Carson, Xinye Chen

Published 2026-04-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Erin Carson, Xinye Chen

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a master chef running a high-end restaurant. You have a massive menu of complex dishes (mathematical problems) to prepare for thousands of guests.

Traditionally, to ensure every dish is perfect, you would use the most expensive, high-quality ingredients and the most precise, slow-cooking methods for every single step of every recipe. You'd use gold-plated knives to chop onions and diamond-tipped whisks to stir soup. This guarantees the food tastes amazing (high accuracy), but it takes forever, costs a fortune in energy, and your kitchen (computer) gets exhausted.

The Problem:
In the world of supercomputers, this "gold-plated" approach is called Double Precision (FP64). It's incredibly accurate but very slow and energy-hungry. Modern computers have faster, cheaper tools (like Half Precision or BF16), which are like using a regular steel knife or a plastic whisk. They are 32 to 64 times faster and use way less energy. However, if you use these cheap tools for everything, you might ruin the dish. A soup stirred with a plastic whisk might get splashed everywhere (numerical errors), or a cake might collapse (the math fails to converge).

The challenge is: How do you know exactly when to use the expensive gold tools and when it's safe to use the cheap plastic ones?

The Old Way:
Previously, experts tried to figure this out by guessing or running the same recipe a hundred times with different tools until they found a combination that worked. This is like a chef tasting the soup, adding salt, tasting again, adding more salt, and repeating it for hours. It's slow, inefficient, and doesn't work well for new, unseen recipes.

The New Solution: The "Smart Sous-Chef" (Reinforcement Learning)
This paper introduces a new method using Artificial Intelligence (specifically, a Contextual Bandit) to act as a smart, adaptive sous-chef.

Here is how it works, using our kitchen analogy:

1. Reading the Ingredients (Contextual Bandit)

Before the chef starts cooking, the AI looks at the specific ingredients for the dish. It doesn't just guess; it checks the "condition number" (how tricky the ingredients are) and the "matrix norm" (the size of the pot).

Analogy: If the ingredients are simple (like boiling water), the AI knows it's safe to use the cheap plastic whisk. If the ingredients are volatile (like a soufflé that might collapse), the AI knows it must use the gold whisk.

2. The Trial-and-Error Training (Reinforcement Learning)

The AI doesn't know the perfect answer immediately. It starts by trying different combinations of tools for different steps of the recipe.

The Reward System:
- If the dish turns out tasty (accurate) and was cooked quickly (efficient), the AI gets a Gold Star (Positive Reward).
- If the dish is ruined or takes too long, the AI gets a Red Card (Negative Reward).
The Learning: Over many practice runs (training episodes), the AI learns a pattern. It realizes, "Ah, for simple soups, I can use the cheap tools for the chopping and stirring, but I must switch to gold tools for the final simmer."

3. The "Contextual" Magic

What makes this special is that the AI doesn't just memorize one recipe. It learns a general rule.

Analogy: Once the AI learns that "Soufflés need gold tools," it can apply that logic to any new soufflé recipe it has never seen before, even if it's a different flavor. It looks at the new ingredients, assesses the risk, and instantly decides which tools to use.

4. The Results: Speed without Sacrifice

The researchers tested this "Smart Sous-Chef" on thousands of mathematical problems (linear systems).

The Outcome: The AI successfully switched between cheap and expensive tools dynamically.
- For "easy" math problems, it used the fast, low-precision tools almost exclusively, making the computer much faster and saving massive amounts of energy.
- For "hard" math problems, it automatically switched back to the slow, high-precision tools to ensure the answer was correct.
The Win: The final results were just as accurate as if they had used the expensive gold tools for the whole time, but the process was significantly faster and cheaper.

Why This Matters

Think of this as adaptive traffic control. Instead of having every car drive at the speed limit (slow but safe) or every car speeding (fast but dangerous), this AI acts like a smart traffic light system. It tells the cars (computational steps) to speed up when the road is clear and slow down when there's a curve or a hazard.

In Summary:
This paper teaches computers to be smart about their effort. Instead of blindly using the most powerful (and expensive) computing power for every single task, it uses a learning algorithm to figure out exactly how much power is needed for each specific step. This allows supercomputers to solve problems faster and with less energy, without sacrificing the accuracy of the results. It's the difference between using a sledgehammer to crack a nut and using a nutcracker.

1. Problem Statement

The rapid growth of large-scale computing and machine learning has increased the demand for energy-efficient arithmetic. While reduced-precision formats (e.g., FP16, BF16, FP8) offer significant speedups (up to 64× on modern GPUs like H100) and energy savings, they introduce rounding errors and numerical instability.

The Challenge: Designing mixed-precision algorithms that balance computational efficiency with numerical accuracy is difficult. Traditional theoretical analyses often rely on restrictive assumptions (e.g., specific condition number bounds) that are hard to verify in practice. Existing automated tuning tools (e.g., Precimonious, HiFPTuner) typically rely on trial-and-error search, which is computationally expensive, does not scale well, and often fails to generalize to unseen datasets.
The Goal: Develop a framework that can automatically and adaptively select precision configurations for specific computational steps in linear solvers based on the properties of the input matrix, without requiring extensive retraining or manual intervention for every new problem instance.

2. Methodology

The authors propose a Reinforcement Learning (RL) framework formulated as a Contextual Bandit problem. This approach treats precision selection as a decision-making process where an agent selects actions (precision configurations) based on the current context (matrix features) to maximize a multi-objective reward.

A. Framework Formulation

Context (State, $s$ ): A feature vector describing the linear system instance $Ax=b$. Key features include the condition number ( $\kappa(A)$ ) and the matrix norm ( $\|A\|_\infty$ ). These features are discretized into bins to create a finite state space $S_d$ .
Action ( $a$ ): A tuple of precision choices for $k$ $k$ computational steps (e.g., $a = (u_f, u, u_g, u_r)$ $a = (u_{f}, u, u_{g}, u_{r})$ for factorization, update, GMRES solve, and residual computation).
- Action Space Reduction: To avoid the exponential explosion of the action space ( $m^k$ ), the authors enforce a monotonicity constraint ( $u'_1 \le u'_2 \le \dots \le u'_k$ ) based on significand bits. This reduces the search space significantly (e.g., from 256 to 35 combinations) while preserving numerically meaningful configurations.
Reward ( $r$ ): A scalar value balancing three objectives:
1. Precision Efficiency: Encouraging lower-precision formats (weighted by significand bits).
2. Accuracy: Penalizing forward and backward errors relative to a high-precision baseline.
3. Computational Cost: Penalizing the number of iterations (convergence speed).
- The reward function is a weighted sum: $R = w_2 f_{precision} + w_1 f_{accuracy} - f_{penalty}$ .

B. Learning Algorithm

Agent: Uses a tabular Q-learning approach with an $\epsilon$ -greedy strategy.
Training: The agent interacts with a simulated environment (Gym) using a limited training set. It updates a Q-table $Q(s_d, a)$ using incremental action-value estimation (Bellman update).
Inference: For unseen test data, the agent computes the features, discretizes the state, and selects the action with the highest Q-value (greedy policy), effectively generalizing the learned strategy without retraining.

C. Case Study: GMRES-IR

The framework is applied to GMRES-based Iterative Refinement (GMRES-IR), a standard method for solving linear systems. The algorithm selects precisions for four distinct steps:

LU Factorization & Initial Solution.
Residual Computation.
GMRES Inner Solve (Working Precision).
Solution Update.

3. Key Contributions

First RL-based Precision Autotuning with Generalization: This is the first work to formally define precision selection as a contextual bandit problem and verify its ability to generalize to unseen datasets (out-of-sample data), moving beyond simple trial-and-error tuning.
Discretized State Space with Theoretical Bounds: The authors provide a theoretical justification (Proposition 1) showing that the performance loss due to discretizing the continuous state space is bounded by the bin diameter, provided the expected reward is Lipschitz continuous.
Action Space Pruning: The introduction of a monotonicity constraint on precision choices significantly reduces the combinatorial complexity of the action space, making the RL training tractable.
Reward Function Design: A novel reward function that explicitly balances accuracy, iteration count, and precision level, allowing the agent to learn trade-offs dynamically.

4. Experimental Results

The framework was tested on both dense and sparse linear systems with varying condition numbers ( $10^1$ to $10^9$ ) and matrix sizes.

Dense Systems:
- Adaptive Strategy: The RL agent successfully learned to use low-precision formats (BF16, TF32) for well-conditioned systems (low $\kappa$ ) to maximize efficiency, while automatically switching to high-precision (FP64) for ill-conditioned systems to ensure stability.
- Performance: Under a conservative weight setting ( $W_1$ ), the method achieved 100% success rate with accuracy comparable to FP64 baselines. Under an aggressive setting ( $W_2$ ), it utilized lower precisions more frequently, accepting slightly higher errors (e.g., $10^{-7}$ ) to reduce cost, while maintaining convergence.
- Iteration Trade-off: When using lower precision, the agent compensated by slightly increasing the number of inner GMRES iterations, demonstrating an intelligent trade-off between arithmetic cost and convergence speed.
Sparse Systems (Ill-Conditioned):
- Robustness: For highly ill-conditioned sparse matrices ( $\kappa \approx 10^8 - 10^9$ ), the agent correctly identified that low precision would lead to divergence. It defaulted to FP64 for all steps, achieving a 100% success rate and matching FP64 baselines in accuracy and iteration counts.
- Significance: This proves the framework does not blindly optimize for speed but prioritizes numerical stability when the problem characteristics dictate it.
Ablation Study (Iteration Penalty):
- Removing the iteration penalty from the reward function led to the agent selecting more low-precision actions but requiring significantly more iterations to converge, resulting in higher total computational cost. This confirms the necessity of modeling iteration costs in the reward function.

5. Significance and Future Work

Scientific Impact: This work bridges the gap between theoretical mixed-precision analysis and practical, automated deployment. It demonstrates that RL can learn the "survival boundary" of numerical algorithms, adapting to problem difficulty without explicit human rules.
Practicality: The framework requires only a small training set and generalizes to new data, reducing the dependency on programmer effort and expensive trial-and-error tuning.
Future Directions: The authors plan to extend the framework to Deep RL for continuous state spaces, incorporate more complex matrix features (e.g., fill-in ratio, pivot growth), and apply the method to a broader range of numerical algorithms beyond linear solvers.

In summary, the paper presents a robust, data-driven approach to precision autotuning that successfully balances the competing demands of speed/energy efficiency and numerical accuracy in scientific computing.