How Well Do LLMs Perform on the Simplest Long-Chain Reasoning Tasks: An Empirical Study on the Equivalence Class Problem

📄 arXiv: 2605.06882v1 📥 PDF

作者: Chun Zheng, Lianlong Wu, Bingqian Li, Lvting Liu, Yi Zhou

分类: cs.AI

发布日期: 2026-05-07

备注: 9 pages, 5 figures

💡 一句话要点

通过等价类问题（ECP）实证评估大语言模型在长链推理任务中的性能表现

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 大语言模型 长链推理 等价类问题 图论分析 逻辑推理评估 模型鲁棒性

📋 核心要点

  1. 尽管LLMs能力不断提升，但其在长链逻辑推理任务中的鲁棒性与可靠性仍缺乏系统性的实证评估与理论支撑。
  2. 本文通过等价类问题（ECP）这一基础逻辑任务，对比分析了推理型与非推理型LLMs在不同图结构参数下的推理能力边界。
  3. 研究发现模型性能与图论特征（如相变点与直径）存在强相关性，揭示了当前LLMs在处理长链逻辑推理时的局限性与瓶颈。

📝 摘要（中文）

近年来，大语言模型（LLMs）取得了显著进展，但其在推理任务，尤其是长链推理任务中的表现仍不明确。本文评估了LLMs在最简单但属于长链推理任务——等价类问题（ECP）上的表现，即在给定一组随机生成的等价关系下判断两个变量是否相等。研究涵盖了多种推理与非推理模型，并考虑了变量数量、连接概率、提示词等多种因素。实验结果表明，非推理模型无法解决ECP，而推理模型表现显著更好，但仍难以完全解决该问题。有趣的是，在固定变量数量下，非推理模型在连接概率为ln n/(n-1)的相变点处表现最差，反映了问题的混沌性；而推理模型在图直径最大时表现最差，揭示了其推理难度的本质。

🔬 方法详解

问题定义：论文旨在探究LLMs在长链推理任务中的极限。现有模型在处理需要多步逻辑推导（如传递性推理）的任务时，往往表现出不稳定性，缺乏对推理过程复杂度的量化评估。

核心思路：通过构建等价类问题（ECP），将复杂的长链推理简化为图论中的连通性判断问题。通过控制变量（变量数、连接概率），观察模型在不同图拓扑结构下的表现，从而解构模型推理失败的深层原因。

技术框架：研究采用大规模基准测试框架，输入为一组等价关系集合及待查询的变量对。实验对比了不同参数规模、不同推理范式（如CoT）的模型，并系统性地遍历了从稀疏图到稠密图的多种连接概率分布。

关键创新：首次将图论中的“相变点”与“图直径”概念引入LLM推理评估。发现非推理模型在相变点（ln n/(n-1)）处表现最差，体现了其对随机噪声的敏感性；而推理模型在直径最大处表现最差，证明了其推理难度主要源于逻辑链条的长度与深度。

关键设计：实验设计了多种提示词策略，并精确控制图的生成参数。通过对比不同模型在特定图结构下的准确率，量化了模型在处理传递性逻辑时的性能衰减规律，为理解LLM推理机制提供了量化视角。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验表明，非推理模型在连接概率接近相变点时准确率急剧下降，呈现出混沌特征；而推理模型（如GPT-4等）虽在长链推理上表现优于基线，但在图直径较大时仍面临显著挑战。研究通过实证数据量化了模型推理能力与图论拓扑特征之间的映射关系，为理解LLM推理瓶颈提供了关键证据。

🎯 应用场景

该研究为评估LLMs的逻辑推理能力提供了基准框架，可应用于代码自动生成、形式化验证、复杂逻辑查询系统及知识图谱推理等领域。其研究结论有助于开发者针对性地优化模型架构或提示词策略，以提升模型在处理长链逻辑依赖任务时的准确性与鲁棒性。

📄 摘要（原文）

Large Language Models (LLMs) have achieved great improvements in recent years. Nevertheless, it still remains unclear how good LLMs are for reasoning tasks, especially for long-chain ones. In this paper, we evaluate LLMs' performance on the simplest yet long-chain reasoning task, namely the Equivalence Class Problem (ECP), i.e., determining whether two variables are equal given a set of randomly generated equivalence relations. We consider both reasoning and non-reasoning representative LLMs over a large variety of problem instances, ranging over different numbers of variables, connectivity probabilities, prompts, and other factors. The experimental results show that non-reasoning LLMs fail ECP, while reasoning models are significantly better but still struggle to completely solve this problem. Interestingly, considering various connectivity probabilities with a fixed number of variables, we observe that, for non-reasoning models, the hardest problem instances coincide with the phase transition point of ln n/(n-1), suggesting the chaos of the problem; in contrast, for reasoning models, the hardest ones coincide with the biggest diameter, suggesting the reasoning difficulty of the problem.