作者介绍：本文第一作者是丰田工业大学芝加哥 PhD 学生杨晨晓，研究兴趣是机器学习理论和大模型推理，在 ICML，NeurIPS，ICLR 等顶级会议上发表过论文。
本文提出一个
交替
「推理 - 擦除
」的深度思考新范式 PENCIL
，比传统 CoT 更高效地解决更复杂的推理任务。理论上，我们证明 PENCIL 可用
最优空间
与
最优时间
下解决所有可计算问题，而这对于传统的 CoT 是不可能的！该工作已被机器学习顶会 ICML 2025 收录。
-
题目： PENCIL: Long Thoughts with Short Memory
-
链接：
https://arxiv.org/pdf/2503.14337
-
代码：
https://github.com/chr26195/PENCIL
最近的大模型（如 OpenAI 的 o1/o3、DeepSeek 的 R1）发现能通过在测试阶段
深度思考（Test-Time Scaling）
来大幅提高模型的推理能力。目前实现深度思考的关键在于使用
长链思维链（Long Chain-of-Thought，CoT）
，即让模型生成更长中间结果得到最终答案。然而，传统
「只写不擦
」的方法在处理高难度、大规模任务时面临以下瓶颈：
-
超出上下文窗口：
一旦链条过长，就会触及模型的最大上下文长度限制；
-
信息检索困难：
随着上下文不断累积，模型难以从冗长历史中 Retrieve 关键线索；
-
生成效率下降：
上下文越长，每步生成新 token 的计算量越大。
不过实际上，并非所有中间思路都后续推理有用：例如定理证明里，引理一旦验证通过，其具体推导可被丢弃；解数学题时，已知某条思路走不通就无需保留那段
「尝试
」的细节。纵观计算机科学的发展历史，这一
「随时清理
」的理念早已渗透到几乎所有计算模型之中：从最早的图灵机模型中，已读写的磁带符号可以被覆盖或重写，直到现在高级编程语言中，垃圾回收机制会自动清理不再可达的内存单元。
基于这样的动机，我们提出一个新的深度思考范式 PENCIL，迭代地执行
生成（Generation）
和
擦除（Reduction）
，即在生成的过程中动态地擦除不再需要的中间结果，直到得到最后的答案。
一、交替
「生成 - 擦除
」的深度思考范式
下图以一个简单的算术题为例展示了 PENCIL 的工作机制：
PENCIL 擦除机制的设计借鉴了逻辑学与经典自动定理证明中的重写规则（Rewriting Rule 和函数式编程语言中的栈帧内存管理（Stack Frame）。 具体地，我们引入三个特殊字符（Special Token），叫做 [CALL], [SEP], [RETURN]，并用以下的规则（Reduction Rule）来实现擦除：
其中 C（Context）表示上下文，T（Thoughts）表示中间思考，A（Answer）表示回答。每当生成的序列与左侧模式完全匹配时，PENCIL 即触发一次擦除，丢弃 T。重要的是，C、T、A 本身均可包含其他特殊标记，从而支持类似多层函数调用的递归结构。
PENCIL 的擦除机制能够灵活支撑多种推理模式，例如：
