通过乔姆斯基层次结构评估 大语言模型 的形式推理能力

LLM 的形式推理能力对于推进自动化软件工程至关重要。然而，现有的 LLM 基准测试缺乏基于计算和复杂性的系统评估，在理解其形式推理能力方面留下了重大差距。因此，SOTA LLM 是否能够掌握计算理论定义的形式语言的结构化、层次复杂性仍是未知数。为了解决这个问题，我们引入了 ChomskyBench，这是一个通过 Chomsky Hierarchy 的镜头系统评估 LLM 的基准。与之前使用神经网络矢量化分类的工作不同，ChomskyBench 是第一个将完整的乔姆斯基层次结构覆盖、通过自然语言进行的过程跟踪评估和确定性符号可验证性结合起来的工作。 ChomskyBench 由一套全面的语言识别和生成任务组成，旨在测试每个级别的能力。大量的实验表明，明显的性能分层与层次结构的复杂程度相关。我们的分析揭示了一种直接关系，即任务难度的增加会极大地影响推理长度和性能。此外，我们发现，虽然更大的模型和先进的推理方法提供了显着的相对收益，但它们面临着严重的效率障碍：实现实际可靠性将需要高昂的计算成本，这表明当前的限制源于效率低下而不是绝对的能力界限。时间复杂度分析进一步表明，对于这些正式任务，LLM 的效率明显低于传统算法程序。这些结果描绘了当前LLM的实际局限性，凸显了传统软件工具的必要性，并为指导未来LLM的开发提供了更强大的形式推理能力的见解。