背景

根据CRANE论文 [ref] 的理论发现：约束生成将LLM的表达性限制到TC^0。

这是一个深刻的理论限制。如果TC^0 ≠ NL（这是一个开放问题），那么约束生成条件下的LLM应该无法解决NL-complete问题。

复杂度类回顾

TC^0（阈值电路，常数深度）

TC^0 是常数深度、多项式大小的阈值电路可计算的问题类 [ref]。

已知在TC^0中的问题：

问题 描述
整数加法 两个n位整数相加
整数乘法 两个n位整数相乘 [ref]
整数除法 n位整数除法 [ref]
迭代加法 n个n位整数相加
迭代乘法 n个n位整数相乘
排序 对n个数排序

NL（非确定性对数空间）

NL 是非确定性对数空间可计算的问题类 [ref]。

NL-complete问题：

问题 描述
st-connectivity（STCON） 给定有向图G和两个节点s、t，判断是否存在从s到t的路径
图可达性 判断图中的可达性关系

关键问题：TC^0 = NL？

这是一个开放问题。如果TC^0 = NL，那么约束生成不会损害LLM解决STCON的能力。但如果TC^0 ⊂ NL，那么约束生成应该限制LLM解决STCON的能力。

主流观点认为TC^0 ⊂ NL（因为STCON被认为需要递归搜索，而TC^0只能做常数深度的并行计算）。

实验设计

核心假设

假设：如果CRANE理论正确（约束生成限制LLM到TC^0），且TC^0 ⊂ NL，那么：

  • 约束生成条件下，LLM应该能解决TC^0问题，但难以解决NL-complete问题
  • 无约束条件下，LLM可能能解决NL-complete问题（因为不受TC^0限制）

任务设计

对比任务：

1
2
3
4
5
6
7
8
TC^0任务（对照组）：
  1. 多位整数加法
  2. 多位整数乘法
  3. 数组排序

NL任务（实验组）：
  1. st-connectivity（有向图可达性）
  2. 图可达性变体

约束条件：

1
2
3
4
5
6
7
8
约束生成：
  - 输出长度限制
  - 格式约束（如"输出yes/no"）
  - 步骤约束

无约束生成：
  - 自由推理
  - 允许CoT

实验矩阵

任务类型 约束条件 预期结果
TC^0（加法/乘法） 有约束 高准确率
TC^0（加法/乘法） 无约束 高准确率
NL（st-connectivity） 有约束 低准确率
NL（st-connectivity） 无约束 较高准确率（可能）

st-connectivity任务实例

1
2
3
4
5
6
7
8
9
10
11
12
13
输入：有向图 G = (V, E)，起点 s，终点 t
输出：是否存在从 s 到 t 的路径？

示例：
G = {V: [1,2,3,4,5], E: [(1,2), (2,3), (3,5), (1,4)]}
s = 1, t = 5
输出：yes（路径：1→2→3→5）

难度控制：
- 节点数 n
- 边数 m
- 最短路径长度 l
- 是否存在路径（平衡正负样本）

模型规模变量

根据TMBench [ref] 的发现，~4B是涌现能力阈值。因此：

模型规模 预期表现
< 4B 所有任务都困难
4B-8B TC^0任务较好，NL任务困难
70B+ TC^0任务很好，NL任务有提升

预期结论

如果TC^0 ⊂ NL

预期发现：

  1. 约束生成条件下，LLM在TC^0任务上表现显著优于NL任务
  2. 无约束条件下，LLM在NL任务上表现提升（如果模型规模足够大）
  3. 这验证了CRANE的理论预测

如果TC^0 = NL

预期发现：

  1. 约束生成条件下，LLM在TC^0和NL任务上表现相似
  2. 这将是一个令人惊讶的结果，可能意味着TC^0 = NL

潜在问题

批判性反思

  1. 任务难度匹配：TC^0任务和NL任务的难度如何公平比较？加法和图搜索的认知难度不同。

  2. 约束定义：什么是"约束生成"？

    • 输出格式约束？
    • 长度约束？
    • 两者都有？

  3. 模型记忆：如果LLM在训练数据中见过大量图算法，它可能"记忆"了BFS/DFS，而非真正推理。

  4. 复杂度类边界：TC^0 ⊂ NL 仍是开放问题，实验结果不能"证明"这个数学问题。

改进方向

  1. 难度匹配：设计多种难度级别的任务，控制输入规模
  2. 约束类型：系统研究不同约束类型的影响
  3. 分布外测试：使用随机生成的图，避免记忆问题
  4. 模型规模消融：测试不同规模的模型

与现有框架的关系

与TMBench的关系

TMBench使用m-Tag系统模拟来测试计算推理能力。本实验设计可以看作TMBench的扩展：

  • TMBench测试的是"规则遵循能力"
  • 本实验测试的是"复杂度类边界"

与约束生命周期框架的关系

计算推理是约束生命周期的底层能力 [ref]。如果LLM的计算能力有复杂度类限制，这将影响：

  • 阶段1（约束发现）：需要复杂的图搜索能力
  • 阶段3（约束执行）：可能受限

下一步

  1. 实现st-connectivity任务数据集
  2. 设计TC^0任务数据集
  3. 测试不同规模的LLM
  4. 分析约束生成的影响

关键引用：