PaperlayerView exact revision on arXiv

Source-linked AI summary

Can Large Language Models Reinvent Foundational Algorithms?

Jian Zhao, Haoren Luo, Yu Wang, Yuhan Cao, Pingyue Sheng, Tianxing He

arXiv:2604.05716v1cs.AI

TL;DR

The paper asks whether LLMs can reinvent foundational algorithms after their prior algorithmic knowledge is removed, addressing an open question about foundational innovation. It introduces an Unlearn-and-Reinvent pipeline with GRPO-based unlearning and evaluates reinvention across algorithms, models, and hint levels. The strongest model reinvents 50% of targets without hints, while hints and test-time reinforcement learning improve selected outcomes and verifier feedback mitigates thought collapse.

  • Problem

    Whether LLMs can produce foundational scientific discoveries remains open, so the paper tests foundational algorithm reinvention after prior algorithm knowledge is removed.

  • Method

    The Unlearn-and-Reinvent pipeline applies LLM unlearning, GRPO-based on-policy optimization, and interpreter-based reinvention with verifier feedback across controlled algorithm tasks.

  • Results

    Across 10 algorithms, 3 models, and 3 hint levels, the strongest model reinvents 50% of targets without hints, while hints improve success and test-time reinforcement learning enables Strassen reinvention at level 2.

  • Takeaways & Limitations

    Generative verifier feedback helps sustain reasoning and avoid thought collapse, but complex algorithms remain difficult even with step-by-step hints.

  • Takeaways & Limitations

    Post hoc unlearning does not certify complete removal of target knowledge, so the results measure reinvention after unlearning rather than discovery without prior exposure.

Abstract

from arXiv · show

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.

1 Introduction

The paper tests whether LLMs can reinvent foundational algorithms after targeted knowledge removal, using an efficient unlearning-and-reinvention pipeline. Across models, hints improve success, but difficult algorithms remain challenging and verifier feedback helps sustain reasoning.

  • Foundational algorithm reinvention is used to probe whether LLMs can achieve innovation beyond incremental improvements.The study focuses on algorithms such as Dijkstra’s and Euclid’s, which are presented as foundational contributions to computer science.
  • The Unlearn-and-Reinvent pipeline removes a target algorithm from pretrained knowledge, then tests independent reinvention through reasoning, code execution, and verifier-guided revision.The pipeline uses LLM unlearning instead of computationally prohibitive retraining from scratch.
  • The evaluation covers 3 open-weight models, 10 target algorithms, and 3 hint levels: no hint, high-level hints, and step-by-step hints.These settings quantify how external guidance affects reinvention success.
  • 50% of the algorithms are reinvented successfully by Qwen3-4B-Thinking-2507 with no hint, while less straightforward algorithms remain difficult.KMP, Manacher, and Strassen are identified as challenging examples.
  • Hints improve reinvention success, but even step-by-step hints fail to overcome the difficulty of complicated algorithms.The paper reports that hints help while remaining insufficient for algorithms requiring non-obvious structures or invariants.
  • Removing the generative verifier causes “thought collapse,” whereas natural-language verifier feedback helps sustain reasoning strength and improves reinvention success.The verifier provides diagnostic feedback after failed submissions, enabling error localization and revision.

2 Preliminaries

The preliminaries define the foundational algorithm set and frame LLM unlearning as targeted knowledge removal balanced against retained utility. They also describe common forgetting and preservation objectives.

  • The study selects 10 foundational algorithms spanning graph theory, string processing, number theory, and data structures.The targets are Dijkstra, Floyd-Warshall, Bellman-Ford, Prim, Euclidean, KMP, Manacher, Moore Vote, Gray, and Strassen.
  • Foundational algorithms are characterized by established theoretical properties, including provable time and space complexity guarantees and, for some, optimality on specific problem classes.
  • LLM unlearning aims to remove specific knowledge from a pretrained model while preserving general utility.The framework distinguishes examples to forget from examples to retain.
  • Unlearning objectives balance a forgetting loss against a utility-preserving loss using a coefficient λ.Lforget represents forgetting, Lretain represents utility preservation, and λ controls their trade-off.
  • Gradient Ascent provides a baseline forgetting objective, while preservation can use supervised fine-tuning or KL regularization toward a reference policy.

3 Unlearn-and-Reinvent Framework

The Unlearn-and-Reinvent framework first removes target-algorithm knowledge while preserving general utility, then tests independent reinvention through interactive programming. It combines on-policy GRPO unlearning, verifier feedback, hierarchical hints, and test-time reinforcement learning.

  • The framework has two phases: unlearning removes target knowledge while preserving utility, and reinvention tests whether the model can independently recover the algorithm.
  • GRPO-based On-policy Unlearning: GRPO samples response groups on forget queries and uses relative rewards from an LLM judge to discourage target-knowledge disclosure, corrupted names, and unreadable outputs.
  • GRPO-based On-policy Unlearning: The unlearning objective combines a GRPO forgetting term with a retain-set utility term, while KL regularization limits excessive policy drift.
  • Environment and Framework: Reinvention uses Python-interpreter interaction, and success requires passing all tests within calibrated runtime and memory limits.
  • Hierarchical Prompt Levels: A generative verifier provides diagnostic feedback after failed submissions to guide revision, while prompts vary from no hint to high-level and step-by-step guidance.

4 Experimental Settings

The experiments use three open-weight models and evaluate forgetting, retained capabilities, and reinvention across multiple algorithms, prompt conditions, variants, and trials. Data and evaluation probes combine model-drafted, human-refined, and benchmark-sampled material.

  • Models: The study evaluates Qwen3-4B-Thinking-2507, Qwen3-4B-Instruct-2507, and Ministral-3-14B-Reasoning-2512 as unlearning and reinvention backbones.
  • Evaluation: Forgetting probes use multiple-choice and open-ended questions, with a judge labeling whether the model reveals no target-algorithm knowledge.
  • Evaluation: Reinvention Success Rate is the fraction of successful attempts for each target algorithm, evaluated across 8 problem variants and 128 trials per prompt level.
  • Evaluation: The retained-capability evaluation covers LiveCodeBench, AIME25, and BFCL-v3, using LiveCodeBench v6 [25.02–25.05].
  • Datasets: Target-specific initialization, forgetting, and probe queries are drafted by DeepSeek-V3.2 and refined by human annotators, while retain queries come from Nemotron-Post-Training-Dataset-v1.

5 Experiments

Experiments show that unlearned LLMs can reinvent some foundational algorithms, but success varies sharply with algorithmic difficulty. Hints, test-time reinforcement learning, and verifier feedback improve outcomes, while post hoc unlearning largely preserves model utility.

  • 5.1 Main Results: Qwen3-4B-Thinking-2507 reaches a 21.8% average RSR with no hint and succeeds on 5 algorithms.The three evaluated models show non-zero success on 5, 7, and 2 algorithms, respectively.
  • 5.1 Main Results: Performance is highly uneven: Gray and Euclidean are frequently reinvented without hints, whereas KMP, Manacher, and Strassen remain unsolved across models.Targets with constrained solution spaces are easier than those requiring non-obvious data structures or counterintuitive invariants.
  • 5.1 Main Results: Hints consistently improve reinvention performance, especially for Dijkstra, Bellman-Ford, and Prim from no hint to level 2.However, Strassen remains unsolved under all hint levels and KMP remains difficult even at level 2.
  • 5.2 Test-time RL: Test-time reinforcement learning yields a successful reinvention of Strassen at level 2 by optimizing toward correct solutions with lower running time.Correct solutions receive reward 1/T, while incorrect solutions receive zero reward.
  • 5.2 Implication: The results suggest that LLMs explore reachable solution spaces effectively but struggle with the counterintuitive leaps required by KMP and Strassen.Test-time RL appears to amplify exploratory signals when sufficient hints narrow the search space, rather than creating new reasoning capabilities.
  • 5.3.1 Ablation of the Generative Verifier: Verifier feedback sustains longer outputs and exploration across rounds, increases reinvention success, and helps prevent thought collapse.Without feedback, outputs shorten and models may abandon problem-solving; both self and oracle verifiers maintain longer trajectories.
  • 5.3.2 Unlearning and Robustness: Unlearning achieves average FR values from 96.0% to 100.0% while utility on LCB, AIME25, and BFCL remains stable relative to original models.The solvable target set also remains consistent after post-unlearning distillation, supporting robustness of the reinvention findings.

6 Related Work

Related work studies LLM unlearning, algorithmic and scientific discovery, and test-time learning. This paper differs by removing foundational algorithms through unlearning and evaluating independent reinvention across systematic experimental conditions.

  • LLM Unlearning: LLM unlearning methods seek targeted knowledge removal while preserving utility, using gradient ascent, regularization, preference optimization, or weight editing.Existing benchmarks include TOFU and WMDP, but reliable forgetting without utility degradation remains difficult.
  • AI-Driven Research: Prior AI-driven research combines language models with program search and reinforcement learning for algorithmic, scientific-law, and theorem discovery.Related studies also evaluate novelty and autonomous scientific research.
  • Positioning: This work tests reinvention after removing a foundational algorithm, unlike discovery evaluations that retain the model’s full pretrained knowledge.A concurrent study presents a conceptual unlearning probe, whereas this paper develops a concrete pipeline with systematic evaluation across algorithms, models, and hint levels.

7 Limitations

The study’s conclusions are bounded by post hoc unlearning and a narrow set of computer-science algorithm targets. These choices do not establish discovery from complete absence of prior exposure or generalize to other forms of scientific discovery.

  • Post Hoc Unlearning: Post hoc unlearning does not guarantee complete removal of target knowledge from internal representations.The results therefore measure reinvention under post hoc unlearning rather than discovery after complete absence of prior exposure.
  • Target Scope: The experiments cover only 10 foundational algorithms, representing one narrow task within scientific discovery.The study does not address hypothesis generation, empirical law discovery, or theorem proving.

8 Conclusion

The paper presents Unlearn-and-Reinvent as a framework for testing whether models can independently recreate forgotten foundational algorithms. It evaluates algorithm coverage, unlearning procedures, and judge-based assessment across a broad set of targets.

  • Conclusion: Test-time reinforcement learning enables successful reinvention of Strassen at hint level 2, while KMP and Strassen remain challenging even with step-by-step hints.The conclusion also reports that the strongest model reinvents 50% of targets without hints.
  • Conclusion: The unlearning experiments use model-specific GRPO optimization and rollout configurations, with complete settings reported in the paper’s tables and repository.The passage identifies representative hyperparameter settings in Tables 5 and 6.
  • Conclusion: GRPO-based on-policy unlearning is implemented with cold-start supervised fine-tuning, forget and retain sets, sampled responses, reward computation, and policy updates.The returned unlearned policy is produced after iterative updates over forget and retain batches.
  • Conclusion: The pipeline uses judge prompts to evaluate whether responses reveal target knowledge, corrupt algorithm names, and remain readable.The judge evaluates responses to algorithm-related queries using these three attributes.

B.3 Reward Design and Analysis of Reward Hacking

The reward design combines knowledge disclosure, name corruption, and readability to prevent unlearning from rewarding hallucinations or language collapse. Examples show that conceptual leakage is penalized even when the target name is absent.

  • Reward Design: The reward equals 1 only when knowledge disclosure and name corruption are both absent while readability is preserved.This three-dimensional criterion is intended to distinguish genuine forgetting from degenerate responses.
  • Reward Hacking: Penalizing name hallucination prevents the optimizer from replacing forgotten algorithms with fabricated terminology.The examples include invented names such as “Voros algorithm” and “V algorithm.”
  • Reward Hacking: Language collapse is treated as failure because empty, repetitive, or gibberish outputs would conceal target knowledge while destroying general language capability.The readability constraint explicitly penalizes multilingual word salad and other incoherent responses.
  • Reward Analysis: A response can receive zero reward despite omitting “Dijkstra” when it reveals the algorithm’s heap-based shortest-path mechanism.This evaluation targets conceptual removal rather than keyword filtering.
  • Additional Results: Unlearn and Unlearn (+Distill) produce consistent reinvention results across all 10 targets, indicating that distillation does not affect outcome stability.The comparison is reported for Qwen3-4B-Thinking-2507 without hints.
  • Additional Results: GRPO achieves the highest average LCB of 42.7, compared with 38.4 for NPO, 37.7 for DPO, and 41.5 for GradAscent.The comparison indicates better preservation of general performance under the reward-guided objective.

C.1 Training Configuration

The training configuration combines on-policy unlearning with retained general prompts, cold-start data, and reward calibration to suppress target-algorithm knowledge while preserving useful response behavior.

  • Training Configuration: Test-time reinforcement learning uses PPO with a 32,768-token context window, temperature 1.0, batch size 64, and 30 optimization steps.The configuration includes a 0.2 clip ratio, learning rate 1.0 × 10^-5, KL coefficient 0.01, and maximum gradient norm 1.0.
  • Reward Initialization: Advantage Calibration adds a virtual maximum-reward sample when an entire batch receives zero reward, ensuring non-zero reinforcement-learning gradients.This addresses the weak optimization signal produced when no correct solution is found within a sampled group.
  • Unlearning Data: The forget set targets both algorithm-to-context and context-to-algorithm associations, while a fixed assistant prefix reduces superficial refusal-based unlearning.The prefix is designed to prevent shifting only the initial token distribution while leaving target knowledge intact.
  • Cold Start Synthesis: Cold-start synthesis replaces target algorithm names with random tokens, samples base-model responses, and filters target mentions to create “I don’t know” initialization data.This preserves the base model’s response style while steering outputs away from forgotten content.
  • Retain Set: The retain set uses general non-target prompts and original-model responses to preserve general capabilities, style, and distributional consistency.Approximately 3,000 cold-start examples and 80 on-policy queries are constructed per target, while the retain set contains approximately 20,000 examples overall.

D.3 Forget-Test Data Example (Dijkstra)

The forget-test examples probe whether models retain Dijkstra-related names, contexts, mechanics, and implementation details, alongside programming tasks that require comparable algorithmic behavior.

  • Dijkstra Forget Probes: The Dijkstra forget probes ask about its problem, edge-weight condition, characteristic relaxation logic, and naive implementation complexity.The examples include multiple-choice and recognition questions designed to test both direct recall and contextual identification.
  • Dijkstra Task: The associated task asks for a pure Python solve function for single-source shortest paths on non-negative weighted directed graphs with worst-case O(N^2) time.The prompt explicitly asks the model to derive a new approach rather than adapt an existing algorithm.
  • Dijkstra Hints: The Dijkstra hints describe greedy selection of the closest unvisited node, distance initialization, neighbor relaxation, and finalization of processed nodes.The step-by-step version specifies zero distance at the source, infinity elsewhere, and repeated updates through the selected node.
  • Strassen Task: The Strassen task asks for matrix multiplication with worst-case complexity O(n^log2 7), using divide-and-conquer over matrix quadrants.Its hints reduce recursive sub-matrix multiplications from eight to seven and provide the M1–M7 construction and recombination equations.
  • Strassen Procedure: The supplied Strassen procedure recursively multiplies seven combinations of matrix quadrants, combines them into four output blocks, and crops padding if needed.It uses standard multiplication below a base-case threshold and supports zero-padding for non-power-of-two dimensions.

E Evaluation

The evaluation varies inference settings across reinvention, benchmark, and forgetting-rate measurements, using repeated trials or judgments where specified.

  • Reinvention Evaluation: Reinvention evaluation constructs 8 variants per target and runs 128 trials at each prompt level, with up to 30 interaction rounds per trial.Ministral uses temperature 0.8 for this evaluation.
  • Benchmark Configuration: Benchmark evaluation averages repeated runs for LiveCodeBench and AIME25, while BFCL reports a single run.The benchmark temperatures differ across tasks and models, including 0.6 for most BFCL models and 0.2 for Ministral-3-14B-Reasoning-2512.
  • Forgetting-Rate Evaluation: Forgetting-rate evaluation uses approximately 50 test problems per algorithm and five DeepSeek-V3.2 judgments per response.The final forgetting rate aggregates the judgments assessing whether responses reveal prior target-algorithm knowledge.

F.1 Reinvention Trajectory Examples

The trajectory examples show reinvention emerging through repeated verifier feedback, failures, and corrections, while unsuccessful runs can remain trapped in inefficient approaches or lose exploratory reasoning.

  • Successful Trajectory: A successful 13-round trajectory reinvents Dijkstra’s core mechanism after correcting queue, complexity, and node-finalization mistakes.The final implementation processes each node once, produces the expected distances, and passes both cases in 0.284 seconds.
  • Successful Trajectory: The key correction is to remove finalized nodes so the minimum-distance source is not selected repeatedly.The verifier explains that retaining the source causes the algorithm to miss later relaxations, such as improving node 2 from 10 to 7.
  • Thought Collapse: Without verifier feedback, outputs shorten over rounds and contain fewer hypotheses, candidate ideas, and structured reasoning.In extreme cases, the model abandons problem-solving or attributes failures to the testing environment.
Loading 2604.05716v1…