Chain-of-Thought and Compressed Looped Transformers: A Memory-Budget Separation
作者: Haozhou Zhang
分类: cs.LG
发布日期: 2026-05-29
💡 一句话要点
对比思维链与循环Transformer，揭示记忆预算对模型推理能力的限制
🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)
关键词: 思维链 循环Transformer 记忆预算 推理能力 复杂度分析
📋 核心要点
- 现有方法如思维链和循环Transformer虽然增加了计算量，但对中间状态的记忆方式不同，影响推理能力。
- 论文核心思想是持久可变记忆是测试时推理的关键，并分析了不同记忆机制下的模型性能。
- 实验结果表明，压缩循环受限于循环状态大小，无法解决P完全问题，而思维链在多项式长度下可以。
📝 摘要（中文）
思维链提示和循环Transformer都为固定模型提供了更多的测试时计算，但它们在记忆方式上有所不同。思维链将中间状态存储在生成的token中，这些token保留在上下文中，而循环Transformer通过循环隐藏激活来传递状态。本文认为，这种持久的可变记忆是测试时推理的核心资源。本文比较了三种记忆机制：压缩潜在循环、完整序列状态循环和思维链草稿纸。主要结果表明，压缩循环受到其循环状态大小的限制。延长循环时间增加了计算量，但本身并没有创建一个增长的草稿纸，因此，即使运行很多步，具有小循环状态的循环仍然是一个小空间推理器。在标准复杂度假设下，这种循环无法解决在对数空间归约下是P完全的问题，而多项式长度的思维链可以。这种分离特定于压缩循环，因为完整序列状态循环在每个输入位置都携带状态，并且生活在更接近显式草稿纸的内存丰富的环境中。受控的指针追踪和关联回忆扫描说明了这种记忆预算的观点，其性能对持久状态预算是否与任务的工作记忆需求相匹配敏感。
🔬 方法详解
问题定义：论文旨在研究在测试时增加计算量的情况下，不同记忆机制（思维链和循环Transformer）对模型推理能力的影响。现有方法，特别是压缩循环Transformer，在记忆容量有限的情况下，其推理能力受到限制，无法有效解决复杂问题。
核心思路：论文的核心思路是将模型推理能力与记忆预算联系起来。认为持久的可变记忆是测试时推理的关键资源。通过比较不同记忆机制（压缩循环、完整序列状态循环和思维链）的性能，揭示记忆容量对模型解决复杂问题的限制。
技术框架：论文主要通过理论分析和实验验证来研究不同记忆机制的性能。理论分析基于标准复杂度假设，证明了压缩循环Transformer无法解决P完全问题。实验部分，设计了受控的指针追踪和关联回忆扫描任务，用于评估不同记忆机制在不同工作记忆需求下的性能表现。
关键创新：论文的关键创新在于提出了“记忆预算”的概念，将模型推理能力与记忆容量联系起来。通过对比压缩循环、完整序列状态循环和思维链，揭示了记忆容量对模型解决复杂问题的限制。这种视角为理解和改进模型的推理能力提供了新的思路。
关键设计：论文的关键设计包括：1) 区分了压缩循环和完整序列状态循环，强调了循环状态大小对推理能力的限制；2) 设计了受控的指针追踪和关联回忆扫描任务，用于评估不同记忆机制在不同工作记忆需求下的性能表现；3) 基于标准复杂度假设，证明了压缩循环Transformer无法解决P完全问题。
🖼️ 关键图片
📊 实验亮点
实验结果表明，压缩循环Transformer的性能受到循环状态大小的限制，无法有效解决需要较大工作记忆的任务。相比之下，完整序列状态循环和思维链在这些任务中表现更好，验证了记忆预算对模型推理能力的重要性。理论分析也证明了压缩循环Transformer无法解决P完全问题。
🎯 应用场景
该研究成果可应用于提升自然语言处理模型的推理能力，尤其是在需要复杂推理和长期记忆的任务中，例如问答系统、对话系统和知识图谱推理。通过优化模型的记忆机制，可以提高模型在这些任务中的性能和效率。
📄 摘要（原文）
Chain-of-thought prompting and looped Transformers both give a fixed model more test-time computation, but they differ in what they remember. Chain-of-thought stores intermediate state in generated tokens that remain in the context, whereas a looped Transformer carries state through recurrent hidden activations. We argue that this persistent mutable memory is a central resource for test-time reasoning. We compare three memory regimes, the compressed latent loop, the full sequence-state loop, and the chain-of-thought scratchpad. Our main result shows that a compressed loop is limited by the size of its recurrent state. Running the loop longer adds computation but does not by itself create a growing scratchpad, so a loop with a small recurrent state remains a small-space reasoner even when run for many steps. Under a standard complexity assumption, such loops cannot decide problems that are P-complete under logspace reductions, whereas polynomial-length chain-of-thought can. The separation is specific to compressed loops, as full sequence-state loops carry state at every input position and live in a memory-rich regime closer to explicit scratchpads. Controlled pointer-chasing and associative-recall sweeps illustrate this memory-budget view, with performance sensitive to whether the persistent-state budget matches the task's working-memory demand.