CLRS Algorithmic Reasoning Benchmark

CLRS Algorithmic Reasoning Benchmark是由DeepMind创建的数据集，包含30个经典算法的轨迹，旨在评估神经网络的算法推理能力。数据集涵盖排序、搜索、动态规划、图算法等多种算法类型，提供输入/输出对及中间轨迹信息。该数据集支持对神经网络在不同算法任务上的泛化能力和推理性能进行测试，特别关注于超出训练分布的泛化能力。

CLRS Algorithmic Reasoning Benchmark is a dataset created by DeepMind, which contains trajectories of 30 classic algorithms and aims to evaluate the algorithmic reasoning capabilities of neural networks. The dataset covers multiple algorithm types including sorting, searching, dynamic programming, graph algorithms and others, providing input/output pairs as well as intermediate trajectory information. This dataset enables testing of the generalization ability and reasoning performance of neural networks across diverse algorithmic tasks, with a particular focus on generalization beyond the training distribution.

搜集汇总

数据集介绍

构建方式

CLRS算法推理基准数据集以Cormen等人所著的《算法导论》为核心蓝本，精心挑选并实现了涵盖排序、搜索、动态规划、图论、字符串与几何六大类别的30种经典算法。数据集的构建并非简单收集输入输出对，而是通过忠实还原教科书中的伪代码逻辑，自动生成每个算法在执行过程中的完整轨迹。这些轨迹不仅包含最终的输入与输出，还囊括了算法每一步的中间状态，即“提示”。为了确保数据与神经网络模型的兼容性，所有算法均被抽象为图结构，其中每个元素（如数组元素、字符串字符、图节点）都被视为独立的节点，而节点间的关系则通过边来表征。这种图导向的编码方式为后续的模型处理提供了统一且富有表现力的基础。

使用方法

使用CLRS-30基准数据集时，研究者通常采用“编码-处理-解码”的范式。首先，将图结构化的输入特征通过线性层编码为潜在表示。随后，利用图神经网络作为处理器，在完全连接的图或由提示指定的子图上进行多步的消息传递与状态更新，模拟算法的迭代执行过程。每一步处理后，模型需根据探针的类型解码出对应的预测，包括节点特征、边特征或全局特征。在训练阶段，模型会接收真实的提示信息作为监督信号，并采用带噪声的教师强制策略来稳定学习。在测试阶段，模型则依赖上一步自身的预测作为下一步的输入，从而评估其在更大规模或不同分布输入上的泛化能力。该基准库提供了完整的JAX和Haiku实现，并支持灵活的扩展，允许研究者轻松添加新算法或修改数据分布。

背景与挑战

背景概述

在机器学习领域，将神经网络与经典算法相结合的研究日益兴起，旨在弥合数据驱动模型与符号推理之间的鸿沟。然而，过往工作往往针对特定假设生成定制化算法数据，导致成果难以跨研究比较，且入门门槛较高。为统一评估标准并推动该领域发展，DeepMind研究团队（Petar Veličković等人）于2022年提出了CLRS算法推理基准（CLRS Algorithmic Reasoning Benchmark）。该基准以经典教材《算法导论》为蓝本，精心遴选出30种涵盖排序、搜索、动态规划、图论、字符串与几何等领域的经典算法，构建了包含输入、输出及中间轨迹信息的标准化数据集。CLRS-30的发布为评估神经网络在算法推理、特别是分布外泛化能力方面提供了坚实的平台，对推动可解释且强泛化能力的智能系统研究具有里程碑式的意义。

当前挑战

CLRS算法推理基准面临的核心挑战在于神经网络对算法逻辑的深层次模仿与泛化。其一，领域问题层面，神经网络在分布内数据上表现优异，但在面对更大规模或结构迥异的输入（如从16节点图泛化至64节点图）时，其推理能力急剧下降，暴露出模型在真正习得算法规则而非统计关联上的不足。其二，基准构建过程中，为确保数据质量与可比性，团队需解决多项难题：排除NP难任务以保证标签生成的可靠性；规避数值预测任务中不同编码方式（如二进制与浮点数）带来的评估歧义；审慎处理动态内存分配等复杂数据结构的表示问题。此外，如何设计有效的中间提示（hints）以引导模型学习算法的逐步操作，同时避免模型过度依赖这些提示，亦是构建过程中的一项严峻挑战。

常用场景

经典使用场景

在算法推理研究的广阔领域中，CLRS Algorithmic Reasoning Benchmark 作为一种标准化的评估平台，被广泛用于检验神经网络在执行经典算法时的能力。该数据集涵盖了来自《算法导论》教科书的三十种经典算法，包括排序、搜索、动态规划、图算法、字符串匹配和几何算法等。研究者通常利用该数据集来训练模型学习算法的执行轨迹，即通过输入、输出以及中间状态（提示）来模拟算法的逐步推理过程。这种设置使得模型不仅能够掌握算法的最终结果，还能理解其内部的动态逻辑，从而为评估和比较不同神经架构的算法推理性能提供了坚实的基础。

解决学术问题

该数据集的核心学术贡献在于解决了算法推理研究中长期存在的基准不统一问题。此前，各研究团队往往针对特定假设生成定制化的算法数据，导致结果难以跨论文比较，且新入门的研究者面临较高的门槛。CLRS-30 通过提供统一的算法轨迹集，使得研究者能够系统地评估模型在分布外泛化、迁移学习以及组合推理等方面的表现。它揭示了当前流行的图神经网络、记忆网络等架构在算法推理中的局限性，尤其是在处理长程依赖、递归计算和字符串匹配等任务时的不足，从而为设计更具泛化能力的推理模型指明了方向，推动了该领域从碎片化走向系统化。

实际应用

在实际应用中，CLRS-30 所训练的算法推理模型有望被部署到那些需要强泛化能力和可解释性的场景中。例如，在组合优化问题中，模型可以学习高效的启发式算法来求解旅行商问题或资源调度问题；在程序合成领域，模型能够基于有限的输入输出样例推断出正确的算法逻辑，从而辅助代码自动生成。此外，这类模型还可用于强化学习中的隐式规划，通过在算法预训练阶段掌握记忆访问和注意力机制，进而在复杂的模拟环境中实现更优的决策。这些应用场景的共同特点是需要模型在未见过的更大规模或不同分布的数据上保持可靠的推理能力，而这正是 CLRS-30 所着力测试和提升的方向。

数据集最近研究

最新研究方向

CLRS算法推理基准测试（CLRS Algorithmic Reasoning Benchmark）的提出标志着神经网络与经典算法融合领域迈入标准化评估的新阶段。该基准覆盖了排序、搜索、动态规划、图算法、字符串与几何算法等30种经典算法，通过提供完整的输入输出轨迹与中间提示（hints），为评估神经网络的分布外泛化能力与算法对齐特性提供了统一的平台。当前前沿研究聚焦于利用图神经网络（GNN）与指针图网络（PGN）等架构来模拟算法执行过程，并探索多任务迁移、元学习与持续学习等范式在算法推理中的应用。该基准不仅揭示了现有模型在长程推理与递归计算上的局限性，还有望推动可解释、强泛化的通用推理系统的发展，为组合优化、蛋白质折叠等复杂科学问题提供新的解决路径。

相关研究论文

• The CLRS Algorithmic Reasoning Benchmark

  DeepMind · 2022年