Can Large Language Models Reinvent Foundational Algorithms?
作者: Jian Zhao, Haoren Luo, Yu Wang, Yuhan Cao, Pingyue Sheng, Tianxing He
分类: cs.AI
发布日期: 2026-04-07
💡 一句话要点
利用LLM的Unlearn-and-Reinvent流程，探索其重塑基础算法的能力
🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture) 支柱九：具身大模型 (Embodied Foundation Models)
关键词: 大型语言模型 算法重塑 Unlearn-and-Reinvent GRPO 测试时强化学习
📋 核心要点
- 现有方法难以评估LLM是否具备独立发现和重塑基础算法的能力，这阻碍了对LLM创新潜力的全面理解。
- 论文提出Unlearn-and-Reinvent流程，通过先移除LLM的特定算法知识，再测试其能否在受控环境中重新发现该算法，从而评估其创新能力。
- 实验结果表明，强大的LLM在适当提示下能够重塑部分基础算法，但复杂算法仍具挑战，生成验证器在维持推理能力方面至关重要。
📝 摘要（中文）
大型语言模型（LLMs）已展现出推动科学发现的强大潜力。然而，它们是否具备基础创新的能力仍然是一个悬而未决的问题。本文着重研究基础创新的一项先决条件：LLMs能否重塑计算机科学中的基础算法？我们提出的“Unlearn-and-Reinvent”流程首先利用LLM的unlearning能力，从模型的预训练知识中移除特定的基础算法，例如Dijkstra算法或Euclid算法，然后在一个受控环境中测试模型是否能够重新发明它。为了实现有效的unlearning，我们采用了一种基于GRPO的on-policy unlearning方法。在10个目标算法、3个强大的开源模型和3个提示级别上进行的实验表明：（1）最强的模型Qwen3-4B-Thinking-2507成功地在无提示的情况下重塑了50%的算法，在提示级别1时重塑了70%，在提示级别2时重塑了90%；（2）一些高级提示可以提高重塑成功率，但即使是逐步提示也无法帮助模型重塑那些复杂的算法；（3）测试时强化学习使得模型能够在提示级别2时成功重塑Strassen算法。通过对输出轨迹的分析和消融研究，我们发现重塑阶段的生成验证器在维持模型的推理能力方面起着关键作用，有助于避免“思维崩溃”现象。这些发现为了解LLMs的创新思维的潜力和当前局限性提供了见解。
🔬 方法详解
问题定义：论文旨在探究大型语言模型（LLMs）是否具备重新发明计算机科学领域基础算法的能力。现有方法缺乏有效手段来评估LLM的独立创新能力，尤其是在算法层面。直接测试LLM对算法的掌握程度无法区分其是简单记忆还是真正理解并能重新推导。因此，需要一种方法来剥离LLM已有的算法知识，并观察其是否能在受控环境下自主重建这些算法。
核心思路：论文的核心思路是设计一个“Unlearn-and-Reinvent”流程。首先，通过unlearning技术，从LLM的预训练知识中移除目标算法的相关信息，使其“忘记”该算法。然后，在提供不同程度提示的条件下，观察LLM是否能够重新发明该算法。如果LLM能够在unlearning后成功重塑算法，则表明其具备一定的独立创新能力。
技术框架：整体流程包含两个主要阶段：Unlearning阶段和Reinventing阶段。Unlearning阶段采用基于GRPO（Gradient Ratio Policy Optimization）的on-policy unlearning方法，旨在有效移除LLM中特定算法的知识。Reinventing阶段则在不同提示级别下，要求LLM重新生成目标算法。该阶段还引入了生成验证器，用于评估LLM生成的算法的正确性，并辅助模型进行迭代优化。对于某些复杂算法，还采用了测试时强化学习（Test-Time Reinforcement Learning）来进一步提升重塑成功率。
关键创新：论文的关键创新在于提出了Unlearn-and-Reinvent流程，这是一种新颖的评估LLM创新能力的方法。该方法通过主动移除LLM的先验知识，并观察其是否能够自主重建知识，从而更准确地评估其独立思考和创新能力。此外，论文还采用了基于GRPO的on-policy unlearning方法，并引入了生成验证器，以提高unlearning和reinventing的效率和准确性。
关键设计：在Unlearning阶段，GRPO算法用于优化策略，以减少LLM生成包含目标算法相关信息的文本的概率。Reinventing阶段，提示级别分为无提示、提示级别1（提供高级提示）和提示级别2（提供逐步提示）。生成验证器通过评估LLM生成的算法的正确性来提供反馈，并用于指导测试时强化学习过程。对于Strassen算法，使用PPO（Proximal Policy Optimization）算法进行测试时强化学习，以优化LLM的生成策略。
🖼️ 关键图片
📊 实验亮点
实验结果表明，Qwen3-4B-Thinking-2507模型在无提示的情况下成功重塑了50%的目标算法，在提示级别1时重塑了70%，在提示级别2时重塑了90%。测试时强化学习使得模型能够在提示级别2时成功重塑Strassen算法。消融研究表明，生成验证器在维持模型的推理能力方面起着关键作用，有助于避免“思维崩溃”现象。
🎯 应用场景
该研究成果可应用于评估和提升大型语言模型的创新能力，尤其是在算法设计、科学发现等领域。通过Unlearn-and-Reinvent流程，可以更好地理解LLM的知识表示和推理机制，并指导模型训练，使其具备更强的独立思考和解决问题的能力。此外，该方法还可以用于发现LLM的潜在局限性，并针对性地进行改进。
📄 摘要（原文）
LLMs have shown strong potential to advance scientific discovery. Whether they possess the capacity for foundational innovation, however, remains an open question. In this work, we focus on a prerequisite for foundational innovation: can LLMs reinvent foundational algorithms in computer science? Our \textit{Unlearn-and-Reinvent} pipeline applies LLM unlearning to remove a specific foundational algorithm, such as Dijkstra's or Euclid's algorithm, from an LLM's pretrained knowledge, and then tests whether the model can reinvent it in a controlled environment. To enable effective unlearning, we adopt a GRPO-based, on-policy unlearning method. Across 10 target algorithms, 3 strong open-weight models, and 3 hint levels, our experiments demonstrate that (1) the strongest model Qwen3-4B-Thinking-2507 successfully reinvents 50% of the algorithms with no hint, 70% at hint level 1, and 90% at hint level 2; (2) a few high-level hints can enhance the reinvention success rate, but even step-by-step hints fail for those complicated algorithms; and (3) test-time reinforcement learning enables successful reinvention for the Strassen algorithm at hint level 2. Through analyses of output trajectories and ablation studies, we find that generative verifier in the reinvention phase plays a critical role in sustaining models' reasoning strength, helping to avoid the ``thought collapse'' phenomenon. These findings offer insights into both the potential and current limits of LLMs' innovative thinking.