Complexity Ceiling Benchmark：深度缩放下的多领域顺序推理评估

# 深度缩放下顺序推理的多领域评估
来源：https://arxiv.org/html/2606.29278

## 复杂度天花板基准：深度缩放下顺序推理的多领域评估

###### 摘要

我们提出复杂度天花板基准（Complexity Ceiling Benchmark，简称CCB），这是一个受控评估，用于衡量语言模型在所需顺序步骤数量增加时推理能力如何衰退。CCB固定任务的语义内容，仅改变深度N∈{5,...,50}，跨越三个结构不同的机制：具象空间状态追踪、抽象符号指针操作及传递关系推理。在五个前沿及开放权重LLM的6,000次试验中，我们观察到一致的模式：每步呈几何衰减，且领域天花板差异悬殊：在前两个机制中，最强模型在N=50时保持pd>0.92；在第三个机制中，每个模型在N=5时即崩溃，最佳模型的50%成功率视界H0.5≈4.7步，尽管pd=0.863。一项轨迹级指标（TFBC）显示，基准中14.5%的正确答案是通过错误中间推理得出的。强制详细状态追踪并未移动天花板（McNemar p=1.000），而推理首次偏离的平均步数k*比参数计数更能预测域内准确率。CCB与几何衰减模型共同将模型的长视界推理概况简化为每个任务族的一个可解释数字。

推理、基准、LLM、深度缩放、几何衰减

5515152525353545450252550507575100100
深度N
准确率(%)

D1 空间状态追踪
5515152525353545450252550507575100100
深度N
D2 符号指针追踪
5515152525353545450252550507575100100
H0.5≈4.7
深度N
D3 传递社交逻辑

Claude 3.7, Gemini 2.0 Flash, DeepSeek, GPT-4o-mini, LLaMA-3.3

图 1：复杂度天花板。三个结构不同的推理机制中准确率随深度N的变化，语义内容固定。标记点：每个单元格n=40次试验的经验准确率。D1和D2中的细实曲线：最优前沿模型（D1中Gemini，D2中Claude）的拟合几何模型100·pd^N。在D1和D2上，前沿模型遵循几何衰减，pd∈[0.92,0.99]，在N=50时仍保留有意义的准确率。在传递社交逻辑（D3）上，无论能力层级如何，每个模型在N=5之后都崩溃；即使最佳模型的50%成功率视界也仅为H0.5≈4.7步。实线：前沿或竞争性开放权重模型；虚线：较小模型。总共6,000次试验。

## 1 引言

当语言模型在长推理任务上失败时，当前基准无法告诉我们原因。模型可能缺乏知识、误读提示、耗尽上下文窗口，或者仅仅在中间步骤中丢失位置。这些失败模式有不同的补救措施，并且对将LLM部署为智能体有不同的影响，但固定难度基准上的聚合准确率只看到它们的并集：一个单一的数字说明模型答错了。这些模式中对智能体使用最关键的——即随着顺序步骤增加而累积的连贯性损失——也是此类基准最难以察觉的（3,12）。本文将深度作为受控实验变量。图1展示了这样做的核心结果。复杂度天花板基准（CCB）保持任务语义固定，并在三个结构不同的机制（具象空间状态追踪（D1）、抽象符号指针操作（D2）和传递关系推理（D3））中将所需推理步数N从5扫描到50。在五个前沿和开放权重LLM上进行的六千次试验揭示了一致的模式：每步保持概率随N呈几何衰减；并且领域之间存在显著分离。在D1和D2上，最强模型在整个深度范围内保持保持概率pd>0.92，在N=50时仍留下有意义的准确率。在D3上，无论能力层级如何，每个模型在N=5之后即崩溃；最佳评估模型的50%成功率视界仅为H0.5≈4.7步。追踪中间推理增加了聚合准确率所隐藏的第二个结果：在整个基准中，14.5%的正确答案来自偏离规范推理的轨迹，并且这一比例在最困难的领域上最高。

#### 贡献。我们引入的几何衰减模型和轨迹级指标共同让我们能用两个数字概括一对（模型，任务族）的概况：每步保持概率pd和平均轨迹偏离步数k*。两者都与部署相关：pd为Sinha等人（12）提出的视界长度框架提供输入，并决定持续准确率交叉任何选定阈值的深度；而k*比参数计数更能忠实预测域内准确率。本文的发现范围限于评估的五种模型上的标准自回归推理；评估过程监督和工具增强系统是明显的下一步，也是CCB旨在服务的一种用途。

## 2 相关工作

#### 深度缩放与组合泛化。大多数先前工作将推理失败视为任务的聚合属性。SCAN（8）和BIG-Bench（14）在近似恒定的难度上探测组合泛化，提供了分布外泛化的强有力测试，但对缩放分析提供的杠杆有限。CLUTRR（13）最接近我们的设定——亲属关系图上的多跳关系推理——并启发D3，但只提供最终答案判断和一小段固定范围的跳数。Dziri等人（3）表明Transformer会展开记忆的子图，在组合性分布外深度处发生灾难性失败；Hou等人（5）将其与累积状态追踪负载联系起来；SokoBench（11）在推箱子游戏中隔离规划深度，TopoBench（9）展示结构化状态有助于推理。CCB与所有这些不同之处在于：它将深度作为三个异质领域上的连续参数轴，并恢复出一个单一的单参数汇总统计量，使我们能够比较模型**如何**失败，而不仅仅是它们是否失败。

#### 轨迹级评估与结构不确定性。另一条并行的工作线评估推理链本身而非答案。ROSCOE（4）、ReCEval（10）和MME-CoT（6）引入了轨迹质量指标，但大多依赖于LLM作为法官或学习到的评分准则，而它们自身的可靠性存在争议（1）。CCB通过比较确定性生成的规范轨迹来避免这一问题；下面的TFBC指标不需要外部评分器。

#### 过程监督与视界连接。最后，我们的pd^N模型是Sinha等人（12）视界长度框架的经验对应物，该框架从每步准确率推导出有效任务视界Hs≈ln(s)/ln(pd)。Cobbe等人（2）表明过程级监督会改变相关量；递归脚手架（16）和快慢循环（15）通过架构针对同一瓶颈。Kim等人（7）认为自回归令牌排序本身是对何种推理模式可访问的一种归纳偏置。扩展讨论见附录C。

## 3 基准设计

CCB由三个任务域、一个生成真实推理轨迹的确定性生成器、一个严格的基于解析器的流水线以及适用于每个（模型，域）单元格的单参数衰减模型组成。这些组件共同设计：失败分类学隔离了衰减模型旨在描述的事件，解析器产生似然函数消耗的事件计数，而下面的轨迹指标作用于相同的解析结构。图2总结了端到端的评估流程，从数据集生成到严格的解析层次结构，该结构将每次试验路由到衰减模型所使用的互斥结果类别中。

数据集生成(N=5...50) → LLM推理(T=0) → 正则表达式轨迹解析 → 格式OK? → 是/否 → 答案OK? → 是/否 → 计算k*(TFBC) / 约束/推理失败

图 2：CCB评估流水线。LLM输出通过严格的解析层次结构路由，以防止推理衰减与结构性输出偏差混淆。约束违规与格式失败明确区分。

#### 域。三个域共享一个实验契约：语义内容固定，深度N在{5,10,...,50}上变化；但它们强调长视界推理的结构性不同方面，共同近似于智能体设置中最常遇到的机制的最小基础：具象空间、抽象符号和嵌套关系。

*D1 外星网格*是一个3×3的网格，经受N次离散变换（旋转、交换角、移位），受网格完整性约束防止实体碰撞；它测试具象空间状态追踪，其错误确定性累积，因为第k步放错的实体会使之后的所有状态无效。

*D2 符号指针追踪*要求模型维护七个变量A–G，持有不同的数字0–9，经受N次循环移位和模算术操作，受赋值唯一性约束；其主要失败模式是通过非法重新赋值导致的寄存器损坏，占D2失败的69.5%，反映了在长上下文中维护不相交符号映射的难度。

*D3 社交逻辑*在十个代理上运行一个外交关系图，遵循传递闭包规则：在N次更新步骤的每一步中，添加一条新的联盟或敌对边，重新计算闭包，并更新所有隐含的关系。模型以心智理论风格格式（“代理人i对代理人j的信念是什么？”）被询问最终成对状态，并且必须在每一步维护全局成对一致性。其主要失败模式是**级联崩溃**：单个错误分类的边通过传递性传播到每个可达节点，并且在上下文窗口中不可恢复，这正是使D3成为一个结构上不同的难度机制，而非D1或D2的更难版本（第4节）。我们在每个（模型，深度）单元格上评估n=40次独立种子试验，因此每个域有2,000次试验，总共6,000次。所有推理在T=0下通过OpenRouter进行，模型为claude-3.7-sonnet、gemini-2.0-flash-001、deepseek-chat、gpt-4o-mini和llama-3.3-70b-instruct。推理专用模型（o1/o3、DeepSeek-R1）在提交时不可访问，在第5节中讨论。

#### 失败分类与解析器设计。每次试验属于六个互斥类别之一：**正确**（最终答案和每一步精确）、**推理**（解析干净但在某步k*≤N偏离规范轨迹）、**约束**（违反结构性任务规则）、**格式**（不可解析）、**截断**（输出中途结束）和**API**（网络错误，自动重试）。只有前三个携带关于每步保持率的信息；其余被视为缺失数据。解析器基于正则表达式，且是故意的：我们考虑并拒绝了基于AST的解析和LLM作为法官评分，以保持评估确定性和可重复性，并消除对外部评分模型的任何依赖，因为外部模型自身的可靠性需要辩护。解析器优先考虑精确度而非召回率；小的格式偏差被标记为格式失败而不是静默纠正，因此得到的pd估计对于输出风格特殊的模型来说是略微保守的。这是我们想要的偏置方向，因为它不能夸大报告的准确率或pd。对手动审计的150个边缘情况输出的检查发现，正确性分类中没有假阳性，并且由于非标准分隔符产生的假阴性率很小（≈2%）。六分类对无关键/值对的重新排序和空格差异是不变的，因此仅布局改变的输出不会影响报告的k*分布。

#### TFBC指标。正确的最终答案并不意味着正确的中间推理。我们定义**轨迹首次分支正确**（TFBC），用于标记任何最终答案与真实答案匹配但轨迹在某个步骤k*>0首先偏离规范推理的试验。算法1从第1步遍历轨迹并返回第一个偏离点；对于可解析的不正确试验，k*记录模型工作状态首先解相干时的深度。作为具体示例，D1上N=10时一个典型的k*=2事件，真实第2步为[[7,4,1],[8,5,2],[9,6,3]]（90°顺时针旋转），模型输出为[[3,2,1],[6,5,4],[9,8,7]]（水平翻转）；轨迹在第一次变换时立即偏离，并且错误确定性地传播贯穿余下的试验，即使最终答案偶然巧合。三名人类标注者独立地针对自动提取器在每域子集上标注轨迹，Cohen's κ分别为0.977（D1，n=50）、0.978（D2，n=50）和0.938（D3，n=65），均高于常规可辩护性阈值0.80。D3原则上允许多个有效推理路径；对20个随机抽样的D3 TFBC案例进行的定向审计未发现真正的替代路径正确性，支持“幸运猜测”的解释。约束违规和TFBC事件在不同的条件集上测量（TFBC仅定义在可解析的正确输出上；约束违规是互斥的失败类别），因此表1中D2高约束违规份额与每模型TFBC率并不矛盾。

**算法 1** TFBC和k*提取器。
1: **输入**: 模型轨迹 T，真实轨迹 G，深度 N
2: L ← ParseSteps(T); k* ← -1
3: **if** |L| < N **then return** (FormatFail, -1)
4: **for** i = 1 **to** N **do**
5:     **if** StepsMatch(L[i], G[i]) **then** continue
6:     **else** k* ← i; **break**
7: **if** k* = -1 **then return** (Correct, -1)
8: **if** FinalAnswerMatches(L[N], G[N]) **then**
9:     **return** (TFBC, k*)
10: **else return** (Incorrect, k*)

#### 衰减模型。我们假设每步保持概率是恒定的。正式地：

*假设1*。对于模型m在给定域d上的每次试验，每步正确推理的概率是常数pd,m,d ∈ (0,1)，且步骤之间独立。

因此N步试验无错误完成的概率为 (pd)^N。我们通过最大化试验级结果（正确/不正确，忽略TFBC状态）的对数似然来拟合pd，将解析失败和截断视为缺失数据（随机缺失假定）。拟合使用JAX中的scipy.optimize.minimize，参数限在(0,1)。对于所有模型-域组合，拟合在20次随机重启中收敛到相同的最大值。重要限制：假设1在已知方向上是有偏的。自回归模型在中间步骤后无法重新访问或修正先前状态；因此，如果在步骤k发生错误，则步骤k+1的条件正确概率上限为0，该步骤及所有后续步骤的错误概率增加。由于pd是常数假设，但真实错误概率在首次错误后增加（注1），因此真实衰减比pd^N预测的更快。

#### 替代衰减模型。假设1（假设1）在已知方向上存在错误（图3）。自回归模型在中间步骤后无法重新访问或修正先前状态；因此，如果在步骤k发生错误，则步骤k+1的条件正确概率上限为0，该步骤及所有后续步骤的错误概率增加。由于pd是常数假设，但真实错误概率在首次错误后增加（注1），因此真实衰减比pd^N预测的更快。

（注意：原文中“替代衰减模型”部分似乎被截断，最后一段重复了前面的内容。根据原文，我们翻译了最后一个完整段落，并如实反映了重复的部分。）

#### 致谢

（原文未提供致谢内容，故保留空位或根据实际情况补充？但原文在末尾无致谢，所以不添加。）

（注意：原文最后部分“Autoregressive tr”似乎被截断，我们按照给出的内容翻译至“Autoregressive tr”之前。）