正文
，比传统 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 的擦除机制能够灵活支撑多种推理模式，例如：
-
任务分解（Decomposition）：
通过 [CALL] 启动子任务，完成后用 [RETURN] 合并输出并擦除子任务推理细节；
-
搜索与回溯（Search and Backtrack）：
在搜索树中，用特殊字符管理探索分支，冲突或失败时擦除无效路径；
-
摘要与总结（Summarization）：
将冗长的思考片段归纳为简洁摘要，类似编程中的尾递归（Tail Recursion）：
其中 T 表示原始的复杂思考过程（或更难的问题），T' 归纳或简化后的摘要（或等价的、更易处理的问题）。
示例： 布尔可满足性（SAT）是经典的 NP-Complete 问题：给定一个 n 个变量布尔公式，判断是否存在一组变量赋值使其为真。
该问题被广泛认为需要指数时间但仅需多项式空间来解决，其中最简单的做法是构造一个深度为 n 的二叉搜索树遍历所有可能。传统 CoT 将每步计算附加到上下文，长度与搜索树节点数成正比 (O (exp (n)))，导致指数爆炸；PENCIL 在递归分支尝试时，遇到冲突立即回溯并擦除该分支所有思考，仅保留关键结果，使上下文长度仅与搜索深度成正比 (O (n))。
如图所示，对比 CoT
无擦除（蓝）
与
PENCIL 擦除（红）
