Empirical Evidence of Complexity-Induced Limits in Large Language Models on Finite Discrete State-Space Problems with Explicit Validity Constraints
作者: Md. Fahad Ullah Utsho, Mohd. Ruhul Ameen, Akif Islam, Md. Golam Rashed, Dipankar Das
分类: cs.CL
发布日期: 2026-04-15
备注: 45 pages, 36 figures, 7 tables, Journal Preprint
💡 一句话要点
提出受控基准测试框架，揭示大语言模型在复杂性增加时推理能力崩溃现象
🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)
关键词: 大语言模型 推理能力 复杂性 基准测试 鲁棒性
📋 核心要点
- 现有LLM评估侧重于固定数据集的总体准确率，忽略了任务复杂性对推理能力的影响。
- 论文提出受控基准测试框架，通过参数化经典推理任务，精确控制问题复杂性。
- 实验表明，LLM在超过特定复杂性阈值后，推理能力会急剧下降，出现“推理崩溃”现象。
📝 摘要（中文）
大型语言模型（LLM）在数学、逻辑和规划基准测试中表现出色，因此常被认为具有强大的推理能力。然而，现有评估主要依赖于固定数据集上的总体准确率，掩盖了推理行为随任务复杂性增加的演变过程。本文提出了一个受控的基准测试框架，以系统地评估大型推理模型（LRM）在问题复杂性逐步增加下的推理鲁棒性。我们构建了一套包含九个经典推理任务的测试集：布尔可满足性问题、密码算术、图着色、过河问题、汉诺塔、水壶问题、跳棋、数独和魔方。每个任务都经过参数化，以精确控制复杂性，同时保留底层语义。通过确定性验证器，我们评估了多个开放和专有的LRM在低、中、高复杂性范围内的表现，确保只接受完全有效的解决方案。结果表明，模型表现出一致的相变行为：在低复杂性下达到高精度，但在超过特定于任务的复杂性阈值后急剧下降。我们将这种现象形式化为推理崩溃。在所有任务中，我们观察到显著的精度下降（通常超过50%），伴随着不一致的推理轨迹、违反约束、状态跟踪丢失以及自信但错误的输出。推理长度的增加并不能可靠地提高正确性，并且在一个问题系列中获得的收益不能推广到其他问题。这些发现强调了评估方法需要超越静态基准，并明确衡量受控复杂性下的推理鲁棒性。
🔬 方法详解
问题定义：现有的大型语言模型（LLM）的评估方法，通常使用固定的数据集，并关注整体的准确率。这种评估方式无法揭示LLM在面对不同复杂程度的问题时的推理能力变化。特别是在问题复杂度逐渐增加时，LLM的推理能力是否能够保持稳定，是一个重要的研究问题。现有方法缺乏对LLM推理鲁棒性的系统性评估，无法有效识别LLM推理能力的瓶颈。
核心思路：本文的核心思路是通过构建一系列参数化的经典推理任务，来精确控制问题的复杂程度。通过逐步增加问题的复杂性，观察LLM在不同复杂程度下的推理表现，从而评估其推理鲁棒性。这种方法能够更细粒度地分析LLM的推理能力，并识别其推理崩溃的临界点。
技术框架：该研究的技术框架主要包括以下几个部分：首先，选择九个经典的推理任务，包括布尔可满足性问题、密码算术、图着色、过河问题、汉诺塔、水壶问题、跳棋、数独和魔方。其次，对每个任务进行参数化，以便能够精确控制问题的复杂性。然后，使用确定性的验证器来评估LLM生成的解决方案，确保只接受完全有效的解决方案。最后，通过比较LLM在不同复杂程度下的推理表现，分析其推理鲁棒性。
关键创新：该研究的关键创新在于提出了一个受控的基准测试框架，能够系统地评估LLM在不同复杂程度下的推理鲁棒性。与传统的评估方法相比，该框架能够更细粒度地分析LLM的推理能力，并识别其推理崩溃的临界点。此外，该研究还形式化了“推理崩溃”这一现象，为后续研究提供了理论基础。
关键设计：在任务参数化方面，研究者针对每个任务设计了不同的参数来控制复杂性。例如，在数独任务中，可以通过改变初始给定的数字数量来控制难度；在汉诺塔任务中，可以通过改变盘子的数量来控制难度。在验证器设计方面，研究者使用了确定性的验证器，以确保只接受完全有效的解决方案。这意味着LLM生成的解决方案必须满足所有约束条件，才能被认为是正确的。
🖼️ 关键图片
📊 实验亮点
实验结果表明，LLM在低复杂性任务中表现良好，但在超过特定复杂性阈值后，准确率会显著下降，通常超过50%。此外，研究发现推理长度的增加并不一定能提高正确性，并且在一个问题系列中获得的收益不能推广到其他问题。这些结果突出了现有LLM在复杂推理任务中的局限性。
🎯 应用场景
该研究成果可应用于评估和改进大型语言模型的推理能力，尤其是在需要高可靠性和安全性的领域，如金融、医疗和法律。通过识别LLM推理崩溃的临界点，可以帮助开发者设计更鲁棒的推理系统，并避免LLM在关键决策中产生错误。
📄 摘要（原文）
Large Language Models (LLMs) are increasingly described as possessing strong reasoning capabilities, supported by high performance on mathematical, logical, and planning benchmarks. However, most existing evaluations rely on aggregate accuracy over fixed datasets, obscuring how reasoning behavior evolves as task complexity increases. In this work, we introduce a controlled benchmarking framework to systematically evaluate the robustness of reasoning in Large Reasoning Models (LRMs) under progressively increasing problem complexity. We construct a suite of nine classical reasoning tasks: Boolean Satisfiability, Cryptarithmetic, Graph Coloring, River Crossing, Tower of Hanoi, Water Jug, Checker Jumping, Sudoku, and Rubik's Cube, each parameterized to precisely control complexity while preserving underlying semantics. Using deterministic validators, we evaluate multiple open and proprietary LRMs across low, intermediate, and high complexity regimes, ensuring that only fully valid solutions are accepted. Our results reveal a consistent phase transition like behavior: models achieve high accuracy at low complexity but degrade sharply beyond task specific complexity thresholds. We formalize this phenomenon as reasoning collapse. Across tasks, we observe substantial accuracy declines, often exceeding 50%, accompanied by inconsistent reasoning traces, constraint violations, loss of state tracking, and confidently incorrect outputs. Increased reasoning length does not reliably improve correctness, and gains in one problem family do not generalize to others. These findings highlight the need for evaluation methodologies that move beyond static benchmarks and explicitly measure reasoning robustness under controlled complexity.