PaperlayerView exact revision on arXiv

Source-linked AI summary

The CLRS Algorithmic Reasoning Benchmark

Petar Veličković, Adrià Puigdomènech Badia, David Budden, Razvan Pascanu, Andrea Banino, Misha Dashevskiy, Raia Hadsell, Charles Blundell

arXiv:2205.15659v2cs.LGcs.DSstat.ML

TL;DR

Examining larger and corner-case instances can clarify whether models learned algorithms or overfit training statistics. CLRS-30 packages trajectories for 30 classical algorithms; results show strong in-distribution MPNN performance but weaker out-of-distribution performance, where PGNs lead on larger graphs.

  • Problem

    Examining larger and corner-case instances can clarify whether models learned algorithms or overfit training statistics.

    Source: §2 · p. 2

  • Method

    CLRS-30 provides trajectories for 30 classical algorithms, including inputs, outputs, and intermediate hints.

    Source: §5 · p. 9

  • Results

    MPNNs exceed 90% F1 on nearly all representative in-distribution tasks, but PGN is most performant averaged across task types on graphs four times larger; simple OOD scenarios reach about 50% micro-F1.

    Source: §4.3 · p. 8, §4.4 · p. 9

  • Takeaways & Limitations

    CLRS-30 provides a way to evaluate algorithmic reasoning learned by neural networks and test out-of-distribution generalization and transfer.

    Source: §5 · p. 9

    Max-flow is outside the current scope, though its minimum-cut decision formulation could be included in future iterations.

    Source: §3 · p. 3

Abstract

from arXiv · show

Learning representations of algorithms is an emerging area of machine learning, seeking to bridge concepts from neural networks with classical algorithms. Several important works have investigated whether neural networks can effectively reason like algorithms, typically by learning to execute them. The common trend in the area, however, is to generate targeted kinds of algorithmic data to evaluate specific hypotheses, making results hard to transfer across publications, and increasing the barrier of entry. To consolidate progress and work towards unified evaluation, we propose the CLRS Algorithmic Reasoning Benchmark, covering classical algorithms from the Introduction to Algorithms textbook. Our benchmark spans a variety of algorithmic reasoning procedures, including sorting, searching, dynamic programming, graph algorithms, string algorithms and geometric algorithms. We perform extensive experiments to demonstrate how several popular algorithmic reasoning baselines perform on these tasks, and consequently, highlight links to several open challenges. Our library is readily available at https://github.com/deepmind/clrs.

1. Introduction

The paper proposes CLRS-30 as a common benchmark for evaluating neural networks on classical algorithms. It covers 30 algorithms through trajectories spanning multiple forms of reasoning.

1. Introduction

  • Neural networks can adapt to raw inputs, but are hard to interpret, unreliable beyond training data, and require massive training datasets.Algorithms offer interpretable, verifiable steps and generalize to arbitrary input sizes, but require task-specific specifications.Source: §1 · p. 1
  • Algorithmic modeling has become a way to investigate reasoning limitations in neural-network architectures.The cited work uses algorithmic tasks to study memory capabilities and graph-network efficiency and alignment.Source: §1 · p. 1
  • CLRS-30 is proposed as a unified benchmark to help address the fragmentation of earlier algorithmic-reasoning studies.Earlier work differed in targeted algorithms, data presentation, and training and testing protocols, making direct comparisons difficult.Source: §1 · p. 1
  • The dataset contains trajectories for 30 classical algorithms covering sorting, searching, dynamic programming, geometry, graphs, and strings.A trajectory includes inputs, corresponding outputs, and optional intermediary targets.Source: §1 · p. 2

2. Motivation

The motivation is to use algorithmic tasks to probe model generalization, reuse, composition, and inductive biases. CLRS-30 is presented as an extensible first step toward a practical testbed for these questions.

2. Motivation

  • Algorithmic tasks probe inductive biases and compositionality through repeated computation, recursion, and input-conditioned computation.Prior work cited in the paper examines algorithm-aligned biases and neural components such as attention and message passing.Source: §2 · p. 2
  • Controlling instance difficulty and memory requirements enables tests of memorization and curricula with increasing memory demands.The paper also notes that data can be generated for regimes ranging from few-shot to infinite-data.Source: §2 · p. 2
  • Testing larger or corner-case instances at controlled distances from training data can clarify how far models generalize and under what conditions.This can help distinguish learning an algorithm from overfitting to training-set statistics.Source: §2 · p. 2
  • Algorithms’ shared subroutines offer a setting for formalizing and measuring reuse and composition across tasks.Task decompositions are often ambiguous, complicating comparisons of task relationships and distances.Source: §2 · p. 3
  • Algorithms are presented as a broad basis for reasoning, while this benchmark focuses on learning basic algorithms themselves.The paper describes learning those algorithms as challenging and useful, while presenting combinations and new algorithm discovery as speculation.Source: §2 · p. 3
  • CLRS-30 is intended as an expandable first-step testbed, allowing changes to training and testing setups, trajectory information, and included algorithms.The authors aim to extend it consistently over time.Source: §2 · p. 3

3. CLRS Algorithmic Reasoning Benchmark

CLRS-30 turns 30 textbook algorithms into benchmark tasks with generated trajectories, graph-oriented representations, and intermediate hints. The section explains the benchmark’s selection boundaries and illustrates hint construction with insertion sort.

3. CLRS Algorithmic Reasoning Benchmark

  • The 30 selected procedures come from CLRS and span varied forms of algorithmic reasoning.Source: §3 · pp. 3–4
  • Selection excludes NP-hard tasks, numerical-output tasks, and algorithms needing memory that cannot be attached to input objects.Shortest-path tasks remain representable as finding path edges, while path lengths are not directly evaluated.Source: §3 · pp. 3–4

3.1. Implementation, probes and representation

  • Idiomatic textbook implementations generate controllable input/output data and trajectories encoded as graph probes over nodes, edges, and graph features.Probe specifications combine stage, location, type, and values; the graph-oriented data can be adapted to other architectures.Source: §3.1 · pp. 4–5

3.2. Hints

  • Hints provide intermediate targets for algorithm-like reasoning while retaining end-to-end models, unlike explicit subtask decompositions that can be hard to specify for novel tasks.Typical input/output-only training limits how much decomposition can be measured or encouraged.Source: §3.2 · p. 5

3.3. Worked example: insertion sort

  • Insertion sort hints track the iterator, insertion slot, and predecessor links instead of numeric swaps; a GNN can locate the insertion position in one step.The backward scan in the original pseudocode is omitted because the GNN can examine relevant positions together.Source: §3.3 · p. 6, Figure 2 · p. 6

4. Empirical evaluation

The evaluation compares algorithmic-reasoning baselines on CLRS-30 using shared training and model setups, then tests whether performance transfers to larger inputs.

4. Empirical evaluation

  • The evaluation investigates whether model performance forms a natural ladder as inputs grow, while also supporting studies of other generalisation and learning setups.The authors provide implementations of data generation, probing, and model training.Source: §4 · p. 7

4.1. Baseline models

  • The encode-process-decode setup encodes node, edge, and graph inputs, processes them with a processor network, and decodes stepwise predictions; hints are encoded and decoded, with noisy teacher forcing during training.At evaluation, the number of processor steps depends on hint size; training feeds back ground-truth hints with probability 0.5.Source: §4.1 · p. 7
  • Baselines vary their information flow: Deep Sets uses self-only connections, GAT uses self-attention, MPNNs use max aggregation, PGNs use hint-selected neighborhoods, and Memory Networks treat edges as memories.The authors report that sum aggregation underperformed max on all tasks.Source: §4.1 · pp. 7–8

4.2. Dataset statistics

  • The benchmark uses 16-node training and validation inputs, with 1,000 training and 32 validation trajectories, then tests on 64-node inputs.For graph-level outputs, test trajectories are increased 64-fold to equalise target counts across tasks.Source: §4.2 · p. 8

4.3. Validation (in-distribution) performance

  • In-distribution, MPNNs exceed 90% F1 on nearly all representative tasks, though their added flexibility may encourage fitting input specifics rather than reasoning rules.Figure 3 shows eight representative tasks; Appendix D contains results for all 30 algorithms.Source: §4.3 · p. 8, Figure 3 · p. 8

4.4. Test (out-of-distribution) performance

  • On graphs four times larger, PGNs become the most performant model averaged across task types, and GNNs outperform Deep Sets and Memory Networks.The table reports average test micro-F1 across algorithm classes; the prose also reports a win/tie/loss comparison.Source: Table 1 · p. 9, §4.4 · p. 9
  • OOD performance remains challenging: simple OOD scenarios reach only about 50% micro-F1, with PGNs struggling on long rollouts and recursive tasks.String matching may require more specialised inductive biases and training regimes.Source: §4.4 · p. 9

5. Conclusion

CLRS-30 offers trajectories from classical algorithms as a shared resource for evaluating neural algorithmic reasoning and out-of-distribution generalisation.

5. Conclusion

  • CLRS-30 contains trajectories from 30 classical algorithms, with input-output pairs and intermediate trajectory information called hints.The benchmark is presented as a way to evaluate algorithmic reasoning learned by neural network models, including out-of-distribution generalisation and transfer.Source: §5 · p. 9
  • The authors hope the shared benchmark will make progress easier to track and lower the barrier to entry for researchers focused on modelling.They note that prior work largely generated its own datasets and that CLRS-30 does not require theoretical-computer-science expertise to generate.Source: §5 · p. 9
  • The paper directs users to Appendix A for instructions on common ways to use the library.The library is described as under continuing development, with feedback welcomed.Source: §5 · p. 9

A. Interfacing with the CLRS benchmark

The appendix introduces ways to use the CLRS library and points readers to its public code and artifacts.

A. Interfacing with the CLRS benchmark

A.1. Evaluating a new baseline on CLRS-30

The recommended way to add a baseline depends on how much it differs from the encode-process-decode GNN design.

A.1. Evaluating a new baseline on CLRS-30

  • The implementation path depends on how fundamentally the new baseline differs from an encode-process-decode GNN.Source: §A.1 · p. 13
  • When only the processor differs, implement the new processor and configure it in the existing baseline architecture.The recommended files are processors.py and baselines.py.Source: §A.1 · p. 13
  • For a fundamentally different baseline, create a class extending the Model API; the baseline code provides an implementation example.Source: §A.1 · p. 13

A.2. Modifying the data distribution of CLRS-30

Users can adapt CLRS-30 task distributions by changing graph sizes or trajectory counts directly, or by modifying and extending task-specific samplers for more elaborate changes.

A.2. Modifying the data distribution of CLRS-30

  • The key routines for modifying or evaluating different CLRS-30 task versions are located in clrs/src/samplers.py.Source: §A.2 · p. 13
  • Graph sizes and trajectory counts can be changed directly in the CLRS30 dictionary near the top of clrs/src/samplers.py.The key routines for modifying task versions are in clrs/src/samplers.py.Source: §A.2 · p. 13
  • More elaborate changes, such as altering data-sampling distributions, require modifying or extending the relevant sampler class.SortingSampler is provided as an example, and the SAMPLERS dictionary identifies the sampler used for each task.Source: §A.2 · p. 13

A.3. Adding new algorithms to CLRS

Adding an algorithm to CLRS involves specifying its inputs, hints, and outputs, implementing it, instrumenting its execution with probes, and providing a sampler. The code includes helper routines for probing and batching.

A.3. Adding new algorithms to CLRS

  • Adding an algorithm can require several potentially comprehensive steps, depending on its complexity, although helper routines for probing and batching facilitate inclusion.Source: §A.3 · p. 13
  • Specify the algorithm’s input, hint, and output structure in the SPECS dictionary in clrs/src/specs.py.Source: §A.3 · p. 13
  • Implement the algorithm in abstractified form, following examples in clrs/src/algorithms/.Source: §A.3 · p. 13
  • Use probing.push to capture inputs, outputs, and intermediate state at selected execution moments, then finalize and return the probes with the algorithm output.Source: §A.3 · p. 13
  • Implement an appropriate input sampler and add it to the SAMPLERS dictionary in clrs/src/samplers.py.Source: §A.3 · p. 13

B. Additional worked examples of algorithm trajectories

The worked examples show how algorithm trajectories are represented for matrix-chain optimization, Bellman–Ford, and naïve string matching, including stored intermediate state and pointers.

B. Additional worked examples of algorithm trajectories

  • For matrix-chain order, dynamic programming fills an upper-triangular matrix whose cells encode optimal multiplication costs and stores the optimal split point for each subsequence.For (10 × 30)(30 × 5)(5 × 60), the example’s optimal order costs 4,500 operations.Source: B. Additional worked examples of… · p. 14
  • The matrix-chain pyramid stores values and pointers as edge scalars and edge pointers over the original input nodes, avoiding O(n^2) auxiliary nodes.A binary flag indicates whether an edge has been populated.Source: B. Additional worked examples of… · p. 14
  • Bellman–Ford initializes the source distance to zero and other distances to infinity, then repeatedly relaxes edges and returns predecessor pointers forming the predicted shortest-path tree.Source: B. Additional worked examples of… · p. 14
  • The naïve string matcher scans candidate positions from left to right, tracking the candidate start and the current characters checked in the haystack and needle.The example detects "ab" in "aab" and stops at the first full match.Source: B. Additional worked examples of… · pp. 14–15
  • A separate string representation tags each character with its predecessor and a binary flag indicating which of two strings it belongs to.The accompanying sequence is shown as repeated a and b characters.Source: B. Additional worked examples of… · p. 15

C. Test results for all algorithms

Test performance for all 30 CLRS-30 algorithms is reported in Table 2, alongside a win-tie-loss metric in Table 3 that aggregates per-algorithm comparisons.

C. Test results for all algorithms

D. Validation results individual plots

The section reports validation results across all 30 CLRS-30 algorithms and provides test and early-stopped validation results for all models and algorithms.

D. Validation results individual plots

Loading 2205.15659v2…