The CLRS Algorithmic Reasoning Benchmark

Petar Veličković, Adrià Puigdomènech Badia, David Budden, Razvan Pascanu, Andrea Banino, Misha Dashevskiy, Raia Hadsell, Charles Blundell
Proceedings of the 39th International Conference on Machine Learning, PMLR 162:22084-22102, 2022.

Abstract

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.

Cite this Paper


BibTeX
@InProceedings{pmlr-v162-velickovic22a, title = {The {CLRS} Algorithmic Reasoning Benchmark}, author = {Veli{\v{c}}kovi{\'c}, Petar and Badia, Adri{\`a} Puigdom{\`e}nech and Budden, David and Pascanu, Razvan and Banino, Andrea and Dashevskiy, Misha and Hadsell, Raia and Blundell, Charles}, booktitle = {Proceedings of the 39th International Conference on Machine Learning}, pages = {22084--22102}, year = {2022}, editor = {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan}, volume = {162}, series = {Proceedings of Machine Learning Research}, month = {17--23 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v162/velickovic22a/velickovic22a.pdf}, url = {https://proceedings.mlr.press/v162/velickovic22a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T The CLRS Algorithmic Reasoning Benchmark %A Petar Veličković %A Adrià Puigdomènech Badia %A David Budden %A Razvan Pascanu %A Andrea Banino %A Misha Dashevskiy %A Raia Hadsell %A Charles Blundell %B Proceedings of the 39th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2022 %E Kamalika Chaudhuri %E Stefanie Jegelka %E Le Song %E Csaba Szepesvari %E Gang Niu %E Sivan Sabato %F pmlr-v162-velickovic22a %I PMLR %P 22084--22102 %U https://proceedings.mlr.press/v162/velickovic22a.html %V 162 %X 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.
APA
Veličković, P., Badia, A.P., Budden, D., Pascanu, R., Banino, A., Dashevskiy, M., Hadsell, R. & Blundell, C.. (2022). The CLRS Algorithmic Reasoning Benchmark. Proceedings of the 39th International Conference on Machine Learning, in Proceedings of Machine Learning Research 162:22084-22102 Available from https://proceedings.mlr.press/v162/velickovic22a.html.

Related Material