大语言模型能否重新发明基础算法？基于遗忘-重发明两阶段探针的研究 Can Large Language Models Reinvent Foundational Algorithms?
遗忘算法后测 LLM 能否独立重发明 Dijkstra 等基础算法
前置知识
LLM 遗忘学习 (LLM Unlearning)
LLM 遗忘学习旨在从已训练模型中精准擦除特定知识而保留通用能力，形式化为双目标优化 $\mathcal{L}=\mathcal{L}_{forget}+\lambda\mathcal{L}_{retain}$，$\lambda$ 控制擦除强度。基线包括梯度上升 (GA)、NPO 等。
本文以遗忘为探针模拟'模型从未见过目标算法'的情景，必须理解 unlearning 的形式化定义、Forgetting Rate 评估指标，以及它与一般微调的本质区别，才能看懂 unlearn-and-reinvent 框架为何要专门设计 GRPO-based on-policy 遗忘。
GRPO (Group Relative Policy Optimization)
GRPO 是 PPO 的一种 on-policy 变体：对同一 prompt 采样 $G$ 条回答，每条优势 $A_j$ 定义为组内归一化奖励，最大化裁剪 surrogate 并加 KL 约束 $\beta D_{KL}(\pi_\theta\|\pi_{ref})$。
本文用 GRPO 做遗忘而非传统 GA，关键改进是 LLM-as-a-judge 给出三维奖励 (k,c,u)；理解 GRPO 的 group-relative 优势估计是看懂遗忘阶段训练目标的前提。
生成式验证器 (Generative Verifier)
生成式验证器指用一个语言模型对生成结果做开放式评估并以自然语言返回诊断反馈，区别于只输出 0/1 的判别式验证器。能解释失败原因 (如复杂度超界)，形成'生成-失败-反馈-修订'回路。
本文的关键发现在于抹除后的模型本身可作为自洽验证器，它在多轮交互中提供的诊断 (如指出 pop(0) 的 O(n) 是超时根因) 能阻止'思考坍缩'，是全文 Figure 4 的核心解释机制。
测试时强化学习 (Test-time RL)
测试时强化学习指在推理阶段直接针对测试样本用 RL 梯度更新模型参数，常用 $1/T$ (T 为运行时间) 作为奖励鼓励正确且高效的输出，本质上是短程 RL 微调。
本文对 Strassen@L2 等静态抹除模型解不出的算法使用测试时 GRPO，把成功率从 0 提到 62.5%；理解它的奖励设计是看懂 Table 2 与 Figure 3 的关键。
研究动机
近年来 FunSearch、AlphaEvolve 等 LLM 驱动的系统在特定任务上发现了超越人类已知最优解的算法，激起了'LLM 能否做出基础性科学发现'的讨论。然而 Dijkstra、欧几里得等基础算法全部出现在现代 LLM 的预训练语料中，测试时直接检索答案与真正'发明'算法难以区分，传统 on-distribution 评测无法区分发现能力与记忆能力。更糟的是，要获得一个'未见过目标算法'的干净基线，需要从预训练数据中删除算法并重新训练 4B-14B 参数量的模型，计算代价高得不可行。现有结论要么混入了检索，要么只覆盖小规模模型的玩具实验，亟需新探针独立验证 LLM 的算法原创性。
本文的目标是本文提出 Unlearn-and-Reinvent 两阶段框架：先用 LLM 遗忘学习把目标算法从预训练模型中精确抹除，模拟'模型从未见过该算法'的初始状态；再将抹除后的模型放入与 Python 解释器交互的测试环境中，通过多轮尝试+生成式验证器反馈让其独立重发明目标算法。具体目标包括：(1) 验证 Qwen3-4B-Thinking-2507 等强推理模型在无提示下能否重发明 50% 的算法；(2) 量化三档提示 (无/L1/L2) 对重发明成功率 RSR 的影响；(3) 揭示影响模型在反复失败中维持推理深度的关键机制——生成式验证器，以避免'思考坍缩'；(4) 探索测试时 RL 能否突破静态抹除模型的极限 (例如 Strassen@L2 达到 62.5%)。
与已有工作不同的是，已有研究在两个方向上都欠缺。遗忘方面，传统 GA 类遗忘在可靠性与通用能力保留之间难以两全，且评估无法证明知识是否真的从表示中清除；'AI 算法发现'方面，先前工作要么直接让模型读训练数据做搜索 (离不开记忆)，要么停留在少数任务的孤立案例，缺少跨多模型×多算法×多提示梯度的系统化探针。本文的独特切入点是：把'LLM 能否做基础性创新'这个形而上问题转化为'遗忘了目标知识后能否在测试时重发明'这个可量化、可复现的实验性问题，并首次同时引入 GRPO 遗忘、生成式验证器反馈和测试时 RL 三件套，专门提出 'thought collapse' 作为评测轴。这与同期 Yang (2025) 仅提概念性框架的工作形成鲜明对比。
核心方法
整体方法分两阶段。(1) Unlearning Phase：先用配对 (query, refusal-style response) 数据 $\mathcal{D}_{init}$ 做 SFT 冷启动，然后以 GRPO 在遗忘集 $\mathcal{D}_{forget}$ 上做 on-policy RL——由 LLM-as-a-judge 输出三维奖励 (k, c, u) 引导策略向稳定的拒绝风格收敛，同时用 KL 约束保留通用能力。(2) Reinvention Phase：抹除后的 $\pi_{unlearn}$ 与 Python 沙箱交互，每轮基于任务描述 $I_g$ (可选 0/1/2 档 hint) 生成代码、提交到测试套件 $T_g$，若失败则由同一 $\pi_{unlearn}$ 实例化出的生成式验证器返回自然语言诊断，最多 30 轮。最后对静态抹除模型解不出的 (算法, 提示) 组合用 $1/T$ 为奖励做测试时 GRPO。直觉上，整个流程构成了一种'故意致盲 → 在受控条件下观察能否重新看清' 的认知实验。
核心创新有四点。(1) **GRPO-based on-policy 遗忘**——区别于传统 GA，把遗忘重写为 RL 形式并用 LLM-as-a-judge 三维奖励 $r(x,y)=\mathbb{1}\{(k,c,u)=(0,0,1)\}$ (知识不披露+算法名无讹误+可读) 引导策略收敛。(2) **Cold start SFT**——GRPO 前用 (query, refusal) 对做监督微调，保证初始策略能给出非零奖励样本，避免全员零奖励导致的优化瘫痪。(3) **Self-instantiated generative verifier**——验证器本身就是抹除后的 $\pi_{unlearn}$，能在失败时给出比'wrong answer'更细的诊断 (如 pop(0) 的 O(n) 是超时根因)，阻止模型把失败归因于测试环境。(4) **Test-time RL with $1/T$ reward**——把'正确且高效'编码到持续奖励中，本质上是对生成器与验证器联合体的二次微调。
方法步骤详情
完整步骤：(1) **数据构造**：$\mathcal{D}_{init}$ (query, refusal)、$\mathcal{D}_{forget}$、$\mathcal{D}_{retain}$ (Nemotron)；$T_g$ 每算法 8 变体 128 trials。(2) **Cold start SFT**：在 $\mathcal{D}_{init}$ 上微调。(3) **GRPO 遗忘**：每条 forget-query 采样 $G$ 条回答，DeepSeek-V3.2 做 judge 输出 $(k,c,u)\to$ 奖励；优化 $\mathcal{L}=\mathcal{L}_{forget\text{-}GRPO}+\lambda\mathcal{L}_{retain}$，其中 $\mathcal{L}_{forget\text{-}GRPO}=-\tfrac{1}{G}\sum_j[\mathcal{J}_{clip,j}(\theta)-\beta D_{KL}(\pi_\theta\|\pi_{ref})]$。(4) **Verifier 循环**：$\pi_{unlearn}$ 实例化为 verifier 给出自然语言 hint，最多 30 轮。(5) **测试时 RL**：对 RSR=0 组合用 $1/T$ 奖励再 GRPO，最多 30 step 支持早停。
技术新颖性
技术新颖性体现在三方面。(1) **首次把 GRPO 用于基础算法的精准擦除**——现有 GA/NPO/RLHF 类 unlearning 都难以在擦除强度与通用能力之间取得平衡，本文用 on-policy RL + 三维奖励 + 冷启动 SFT，首次在 4B-14B 模型上达到 96-100% 平均遗忘率同时 LiveCodeBench/AIME25/BFCL 仅掉约 1-3 点。(2) **Self-generated verifier**——之前工作 (Zhang et al. 2025b) 用独立训练的 verifier，本文直接复用 unlearn 模型本身，使得验证器与生成器共享分布偏差，诊断反馈与生成者的推理方式天然对齐。(3) **首次提出 thought collapse 概念并把它作为评测轴**——Figure 4 揭示无验证器时模型在第 19-30 轮平均输出 token 数衰减到 round 1 的约 30%，加入验证器后能维持稳定探索；这是首次把'反复失败中的认知退化'明确量化成可观察评测信号，对多轮 agent 系统的设计有指导意义。
实验结果
Table 1 显示 Qwen3-4B-Thinking-2507 平均 RSR 为 21.8%/48.5%/80.9% (无/L1/L2)；Gray/Euclidean/Floyd-Warshall/Moore Vote 在 L2 下 92-100%，KMP/Manacher/Strassen 接近 0。Figure 2 展示 Dijkstra 双轨迹——左侧 verifier 反馈 11 轮后修正成功，右侧陷入次优 30 轮未解。Test-time RL (Table 2) 让 Strassen@L2 从 0% 升到 62.5%，reward curve (Figure 3) 4-12 步显著上升。Figure 4 揭示 thought collapse：无 verifier 时 token 衰减到 round 1 的 ~30%，self verifier 保持稳定。Table 3 显示 self verifier 把 RSR 从 9.5% 提到 21.8%，Oracle verifier 进一步至 34.8%；Table 4 显示 FR=96.3-99.8% 且 utility 仅掉 1-3 点。
查看结构化数据
| 任务 | 指标 | 本文 | 基线 | 提升 |
|---|---|---|---|---|
| 10 个基础算法在无提示下重发明 — Qwen3-4B-Thinking-2507 的 RSR | Reinvention Success Rate (RSR, %, 越高越好) | Gray 70.3, Euclidean 64.8, Floyd-Warshall 44.5, Dijkstra 22.7, Bellman-Ford 15.6, Moore Vote 0, Prim 0, Manacher 0, KMP 0, Strassen 0, 平均 21.8% | Ministral-3-14B-Reasoning-2512 平均 3.9%, Qwen3-4B-Instruct-2507 平均 0.2% | 比 Ministral 高 +17.9 pp, 比 Instruct 高 +21.6 pp |
| 重发明 Dijkstra 在三档提示下的 RSR (Qwen3-4B-Thinking-2507) | RSR (%) | 无提示 22.7%, L1 高层提示 83.6%, L2 逐步提示 98.4% | Ministral 同期 1.6%/69.9%/92.2%; Qwen3-4B-Instruct 0/14.1/80.3 | L2 比 Ministral 高 +6.2 pp, 比 Instruct 高 +18.1 pp |
| Test-time RL 在 Strassen@L2 上的最高奖励 variant 成功率 | Variant Success Rate (%, 越高越好), Time (s, 越低越好) | RL 前 0.0% / —, RL 后 62.5% / 1.35s | 无任何 RL 的静态 unlearn 模型为 0% | +62.5 pp 绝对提升，并首次在 Strassen 上达到非零成功率 |
| 生成式验证器消融 — Qwen3-4B-Thinking-2507 平均 RSR (无提示) | RSR (%) | 无 verifier 9.5%, self verifier 21.8%, oracle verifier (DeepSeek-V3.2) 34.8% | 无 verifier 设置 | self verifier +12.3 pp, oracle verifier +25.3 pp |
| 遗忘 + 通用能力保留 (Qwen3-4B-Thinking-2507 平均) | Forgetting Rate (%, 越高越彻底) / LiveCodeBench / AIME25 / BFCL (尽量不掉) | FR 99.8%, LCB 50.3, AIME25 77.0, BFCL 70.2 | Origin (unlearn 前): LCB 55.2, AIME25 81.3, BFCL 71.6 | FR 接近 100% 而 utility 仅掉约 1-4 点 (LCB -4.9, AIME25 -4.3, BFCL -1.4) |
局限与改进
作者在第 7 节坦率承认两大局限：(1) **Post-hoc 遗忘不保证彻底擦除**——本文使用 LLM 遗忘而非从头训练，因此无法证明目标知识已从表征中被完全抹除；这意味着所测的是'后置抹除下的重发明能力'而非'从零开始的真正发现'，观察到的成功可能仍有 representation-level 的残留知识协助。(2) **算法覆盖范围过窄**——10 个目标算法均为图论/字符串/数论/数据结构的 CS 基础算法，且评估完全靠自动测试用例，不适用于'假设生成'、'实验规律发现'、'定理证明'等开放性科学发现形态。我们自己的观察补充几点：(a) test-time RL 目前只针对 Qwen3-4B-Thinking-2507 跑，结论能否推广到 Ministral/Instruct 未知；(b) verifier 用 LLM-as-a-judge 评估'遗忘是否成功'，但 judge 自身的可靠性是元问题；(c) hint L2 的'逐步提示'接近把答案直接念给模型，再在这种设定下失败的算法价值最高 (Manacher/KMP)。
独立分析的弱点
独立分析有以下弱点。(1) **Judge 评价脆弱性**：unlearning 依赖 DeepSeek-V3.2 做 judge，对'伪 refusal' (用近义名如'shortest path greedy scan'代替'Dijkstra') 未做消融；若模型学会近义绕过奖励，FR 高但知识仍在。**改向**：加'语义相似度对原算法描述'作为额外奖励分量。(2) **题面数据泄漏**：'非负权图最短路'本身就是 Dijkstra 的天然描述，难以排除模型是否通过题面 hint 重新猜到正确结构；**改向**：把 8 道题换成迷宫/地铁线等隐含 SSSP 的应用题。(3) **TTRL 样本极少**：只在 Strassen@L2 展示收益，无法判断是否普适；**改向**：跨至少 3 个算法复现。(4) **Verifier 诊断真实性**：Figure 2 中 verifier 给出精准诊断本身是'事后合理化'，缺乏对抗扰动测试。
未来方向
作者在结论提到把 pipeline 扩展到'更开放的科学发现 (hypothesis generation、empirical law、theorem proving)'。基于成果自然延伸，我们认为以下方向最有价值。(1) **Hint 升级为执行轨迹**：让模型看到算法在 $n=4$ 上的执行 trace 反推程序结构，对 Strassen 这类高结构化算法意义更大。(2) **Verifier 协同进化**：让 verifier 与 generator 同时 GRPO 训练，可能解决 verifier 自身的 thought collapse。(3) **跨算法迁移**：让模型先重发明 Euclid 再尝试 BFS，观察是否出现'算法族'级可迁移启发式。(4) **Interpretability 检验**：重发明成功时 probe 内部表征是否激活与原模型相似的电路，作为'unlearning 真伪'的更严格判据。(5) **Scaling 验证**：把 backbone 推到 70B 级别，观察 thought collapse 与 RSR 的 scaling 趋势。
复现评估
代码已开源 https://github.com/Algo-Reinvention/algo-reinvention。**数据**：unlearn/retain/eval 数据由 DeepSeek-V3.2 起草、人工精修，prompt 模板在 Appendix D；$\mathcal{D}_{retain}$ 用 Nemotron-Post-Training-Dataset-v1。**模型**：3 个 4B-14B 开源模型 + DeepSeek-V3.2 (judge) + 同一 $\pi_{unlearn}$ (verifier/optimizer)。**算力**：128 trials × 10 算法 × 3 提示 ≈ 3840 次生成/模型，单卡 H100/A100 集群数天跑完，verifier 多轮交互消耗大量 token。**复现难度**：中等——遗忘率与成功率需在 judge 与 verifier 上同时对齐，且需检查 reward hacking。**风险**：未公开 judge 提示词精确表述与 GRPO 子训练步数，prompt 模板需逐字对齐以避免策略漂移。
论文图表
