# RL4RLA: Teaching ML to Discover Randomized Linear Algebra Algorithms Through Curriculum Design and Graph-Based Search

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

## Key facts

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

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

- [AlphaEvolve: A coding agent for scientific and algorithmic discovery](https://mlsanity.com/paper/2506.13131/) (2025)
- [Learning to learn by gradient descent by gradient descent](https://mlsanity.com/paper/1606.04474/) (2016)
- [Symbolic Discovery of Optimization Algorithms](https://mlsanity.com/paper/2302.06675/) (2023)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [AutoML-Zero: Evolving Machine Learning Algorithms From Scratch](https://mlsanity.com/paper/2003.03384/) (2020)
- [Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm](https://mlsanity.com/paper/1310.5715/) (2013)
- [The CLRS Algorithmic Reasoning Benchmark](https://mlsanity.com/paper/2205.15659/) (2022)
- [Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence](https://mlsanity.com/paper/1505.02250/) (2015)
- [Learning-Based Low-Rank Approximations](https://mlsanity.com/paper/1910.13984/) (2019)
- [AlgoTune: Can Language Models Speed Up General-Purpose Numerical Programs?](https://mlsanity.com/paper/2507.15887/) (2025)
- [Neural incomplete factorization: learning preconditioners for the conjugate gradient method](https://mlsanity.com/paper/2305.16368/) (2023)
- [A Deep Conjugate Direction Method for Iteratively Solving Linear Systems](https://mlsanity.com/paper/2205.10763/) (2022)
- [Learning-Augmented Sketches for Hessians](https://mlsanity.com/paper/2102.12317/) (2021)

## Abstract (arXiv)

Randomized linear algebra (RLA) algorithms are a modern class of numerical linear algebra techniques that play an essential role in scientific computing and machine learning, with broad and growing adoption. However, their discovery remains mostly a manual process that requires deep expert knowledge and inspiration. While Reinforcement Learning (RL) offers a pathway to automation, standard approaches struggle with sparse reward landscapes and vast search spaces inherent to high-performing RLA algorithms. In this paper, we present RL4RLA, a general RL framework that automates the discovery of interpretable, symbolic RLA algorithms. Unlike black-box approaches, our method builds explicit algorithms from basic linear algebra primitives, ensuring verifiable and implementable representations. To enable efficient discovery, we introduce: (1) a numerical curriculum that progressively increments problem difficulty to encode inductive bias specific to the RLA domain; (2) Monte Carlo Graph Search, which optimizes exploration by identifying and merging equivalent partial algorithms. We demonstrate that RL4RLA rediscovers state-of-the-art methods, including sketch-and-precondition solvers, Randomized Kaczmarz, and Newton Sketch, and can be targeted to produce algorithms optimized for specific trade-offs between accuracy, speed, and stability. Code is available at https://github.com/Tim-Xiong/RL4RLA.