# SALSA-CLRS: A Sparse and Scalable Benchmark for Algorithmic Reasoning

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 37 references that are in the map.
- First posted on arXiv 21 Sep 2023.

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

- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [On the Properties of Neural Machine Translation: Encoder-Decoder Approaches](https://mlsanity.com/paper/1409.1259/) (2014)
- [Strategies for Pre-training Graph Neural Networks](https://mlsanity.com/paper/1905.12265/) (2019)
- [Neural Turing Machines](https://mlsanity.com/paper/1410.5401/) (2014)
- [How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks](https://mlsanity.com/paper/2009.11848/) (2020)
- [What graph neural networks cannot learn: depth vs width](https://mlsanity.com/paper/1907.03199/) (2019)
- [Learning a SAT Solver from Single-Bit Supervision](https://mlsanity.com/paper/1802.03685/) (2018)
- [Can You Learn an Algorithm? Generalizing from Easy to Hard Problems with Recurrent Networks](https://mlsanity.com/paper/2106.04537/) (2021)
- [The CLRS Algorithmic Reasoning Benchmark](https://mlsanity.com/paper/2205.15659/) (2022)
- [Learning the Travelling Salesperson Problem Requires Rethinking Generalization](https://mlsanity.com/paper/2006.07054/) (2020)
- [Neural Algorithmic Reasoning](https://mlsanity.com/paper/2105.02761/) (2021)
- [Recurrent Relational Networks](https://mlsanity.com/paper/1711.08028/) (2017)
- [A Generalist Neural Algorithmic Learner](https://mlsanity.com/paper/2209.11142/) (2022)
- [Graph Neural Networks are Dynamic Programmers](https://mlsanity.com/paper/2203.15544/) (2022)
- [Pointer Graph Networks](https://mlsanity.com/paper/2006.06380/) (2020)
- [Relational Attention: Generalizing Transformers for Graph-Structured Tasks](https://mlsanity.com/paper/2210.05062/) (2022)
- [End-to-end Algorithm Synthesis with Recurrent Networks: Logical Extrapolation Without Overthinking](https://mlsanity.com/paper/2202.05826/) (2022)
- [Neural Algorithmic Reasoning with Causal Regularisation](https://mlsanity.com/paper/2302.10258/) (2023)
- [Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Tasks](https://mlsanity.com/paper/2211.00692/) (2022)
- [Neural Algorithmic Reasoning for Combinatorial Optimisation](https://mlsanity.com/paper/2306.06064/) (2023)
- [Neural Algorithmic Reasoning Without Intermediate Supervision](https://mlsanity.com/paper/2306.13411/) (2023)
- [Learning Graph Algorithms With Recurrent Graph Neural Networks](https://mlsanity.com/paper/2212.04934/) (2022)
- [Parallel Algorithms Align with Neural Execution](https://mlsanity.com/paper/2307.04049/) (2023)

## Built on by (most cited first, 12 of 12)

- [The CLRS-Text Algorithmic Reasoning Language Benchmark](https://mlsanity.com/paper/2406.04229/) (2024)
- [Discrete Neural Algorithmic Reasoning](https://mlsanity.com/paper/2402.11628/) (2024)
- [Primal-Dual Neural Algorithmic Reasoning](https://mlsanity.com/paper/2505.24067/) (2025)
- [Benchmarking ChatGPT on Algorithmic Reasoning](https://mlsanity.com/paper/2404.03441/) (2024)
- [Neural Algorithmic Reasoning with Multiple Correct Solutions](https://mlsanity.com/paper/2409.06953/) (2024)
- [NAR-*ICP: Neural Execution of Classical ICP-based Pointcloud Registration Algorithms](https://mlsanity.com/paper/2410.11031/) (2024)
- [Beyond Interpolation: Extrapolative Reasoning with Reinforcement Learning and Graph Neural Networks](https://mlsanity.com/paper/2502.04402/) (2025)
- [KNARsack: Teaching Neural Algorithmic Reasoners to Solve Pseudo-Polynomial Problems](https://mlsanity.com/paper/2509.15239/) (2025)
- [FloydNet: A Learning Paradigm for Global Relational Reasoning](https://mlsanity.com/paper/2601.19094/) (2026)
- [Algorithm-Informed Graph Neural Networks for Leakage Detection and Localization in Water Distribution Networks](https://mlsanity.com/paper/2408.02797/) (2024)
- [Tackling GNARLy Problems: Graph Neural Algorithmic Reasoning Reimagined through Reinforcement Learning](https://mlsanity.com/paper/2509.18930/) (2025)
- [Fitting Every Hint Is Not Enough: Premature Floods in Recurrent Algorithmic Reasoners](https://mlsanity.com/paper/2610.14982/) (2026)

## Abstract (arXiv)

We introduce an extension to the CLRS algorithmic learning benchmark, prioritizing scalability and the utilization of sparse representations. Many algorithms in CLRS require global memory or information exchange, mirrored in its execution model, which constructs fully connected (not sparse) graphs based on the underlying problem. Despite CLRS's aim of assessing how effectively learned algorithms can generalize to larger instances, the existing execution model becomes a significant constraint due to its demanding memory requirements and runtime (hard to scale). However, many important algorithms do not demand a fully connected graph; these algorithms, primarily distributed in nature, align closely with the message-passing paradigm employed by Graph Neural Networks. Hence, we propose SALSA-CLRS, an extension of the current CLRS benchmark specifically with scalability and sparseness in mind. Our approach includes adapted algorithms from the original CLRS benchmark and introduces new problems from distributed and randomized algorithms. Moreover, we perform a thorough empirical evaluation of our benchmark. Code is publicly available at https://github.com/jkminder/SALSA-CLRS.