首个 CoT 层级定理:更多推理步可严格解锁更难的可解问题
gurtej__gill_ · x · 2026-11-12
NeurIPS 2026 论文《A Tight Hierarchyn for Chain of Thought》(Le、Pavan、Vinodchandran,内布拉斯加-林肯大学与爱荷华州立)首次为思维链建立真正的层级定理:
- 核心结论:对任意合理资源界 r(n)≥n 和 ε>0,有 CoT(r(n)) ⊆ CoT(r(n)^(1+ε)),且严格成立——给 transformer 略多一点推理步,即可证明性地解锁原本完全不可解的判定问题。
- 意义:把 CoT token 正式确立为一种基础计算资源,地位类似经典复杂性理论中的时间与空间。
- 技术路线:经典层级定理依赖对角化,但在 transformer 场景下很快失效;作者改用双向模拟将 CoT 增强 transformer 与图灵机互相关联,并把经典 padding 技巧移植到 transformer 的 CoT 模型内,得到紧的层级。
这为「多给推理预算就让模型本质上更强」的直觉提供了严格理论支撑。
所属事件:论文证更多推理token可解更难问题，引发复杂度讨论(3 条相关)→
「研究」频道最新
- Jeff Clune 演讲阐述开放式 AI 驱动研究的价值 — chris_j_paxton · 2026-11-13
- Salesforce Research 携 16 篇论文登陆 NeurIPS 2026 — msrivastav13 · 2026-11-13
- 新药设计剧本：加个方环再塞四个氟，化学家笑疯 — gleech · 2026-11-13
- Berkeley 提出 Population Serving:把推理流量变成免反向传播的训练资源 — LChoshen · 2026-11-13
- 用智能体重写分子动力学力场代码:潜在大幅提速,但评估须守住精度 — rishabh16_ · 2026-11-13
- MIT WorldParticle:一个统一模型模拟流体、流沙到蛋白质折叠 — MIT_CSAIL · 2026-11-13