Organizations: Xiongan AI Institute · Beijing University of Posts and Telecommunications, Beijing, China · Institute for Interdisciplinary Information Sciences, Tsinghua University · Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China · Independent Researcher · Shanghai Qi Zhi Institute
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? We use LLM unlearning methods to suppress direct recall of the target algorithm and let the model reason with the remaining knowledge to recover it. Although unlearning does not guarantee full knowledge removal, LLMs fail to recover nearly half of the target algorithms. Notably, even suppressing the mention of the algorithm's name during decoding without unlearning makes the models' recovery rate drop dramatically (19--39%), suggesting their overreliance on memorized knowledge. We observe that recoverable algorithms tend to be simple in structure or core ideas, whereas the others are less straightforward. We also introduce a generative verifier that sustains models' reasoning strength, helping to avoid the ``thought collapse'' phenomenon. Taken together, by treating the unlearned model's recovery rate as an approximate upper bound, our empirical results suggest that current LLM systems still have limited ability to make foundational algorithm innovation. Our code is available at https://github.com/Algo-Reinvention/algo-reinvention.
Figures & tables
Figure 1: Our evaluation pipeline. (1) In the unlearning phase, a pretrained model πbase is transformed into πunlearn , which, under our tests, no longer recalls Dijkstra’s algorithm for concept-level queries. (2) In the recovery phase, the model is prompted with the task at three hint levels: No hint, level 1 (high-level hint), and level 2 (step-by-step hint). At each attempt, πunlearn reasons and submits its solution for testing. If the submission fails, a generative verifier instantiated from πunlearn itself returns diagnostic feedback, helping the model locate the error and revise its approach.
Table 1: Recovery Rate (RR, %) and Coverage (%) across algorithms, models, and hint levels. Higher is better. Level 1 uses high-level hints; level 2 uses step-by-step hints. Darker shading indicates higher value. The order is based on reference difficulty ratings of algorithms (Appendix D.2 ).
Figure 2: Two recovery trajectories for Dijkstra’s algorithm (no hint) on Qwen3-4B-Thinking. Left: the model remains stuck in suboptimal strategies and eventually fails. Right: the model comes up with a Dijkstra-like solution by round 11, corrected through verifier feedback.
Figure 3: Recovery rate (lines) and algorithm coverage (bars) before and after unlearning across hint levels. More informative hints substantially narrow the recovery gap between unlearned and original models. With level-2 hints, unlearned Qwen3-4B-Instruct even achieves a better recovery rate than its original counterparts.
Figure 4: Round-wise output tokens during recovery. Left : Across three models without verifier feedback, outputs become shorter in later rounds. Right : Three verifier settings on Qwen3-4B-Thinking. Without a verifier, the model either succeeds early or quickly abandons the task. With a verifier, the model sustains meaningful exploration over more rounds, enabling success even when the correct approach is not found initially.
Figure 5: Effect of algorithm-name suppression on four thinking models without hints. Each line links an algorithm’s original recovery rate to its rate after name suppression. Line length indicates the absolute change.
Verifier
RR (%)
Coverage (%)
No Verifier
20.5
50.0
DeepSeek-V4-Flash
36.6
50.0
Self-Verifier
30.1
50.0
Table 2: Verifier ablation on Qwen3-4B-Thinking in the no-hint setting. Recovery Rate (RR, %) and Coverage (%) are averaged across 20 algorithms.
Algorithm
Qwen3-4B-Thinking
Qwen3-4B-Instruct
Gemma-4-12B (Thinking)
FR (%)
LCB
AIME25
FR (%)
LCB
AIME25
FR (%)
LCB
AIME25
Origin
0.0
55.2
81.3
0.0
35.1
47.4
0.0
71.8
82.2
Kadane
100.0
50.4
78.9
96.6
32.1
47.8
94.9
63.4
68.9
DAG
86.7
48.1
80.0
96.7
38.9
47.8
91.7
62.6
70.0
Gray
97.1
50.4
74.4
91.4
38.9
47.8
88.6
66.4
73.3
BFS
91.7
51.1
71.1
96.7
41.2
45.6
85.0
72.5
71.1
Table 3: Unlearning results across target algorithms and models. Forgetting Rate (FR, %) measures unlearning effectiveness, while LCB and AIME25 (detailed in § 4 ) measure model utility. Origin denotes the original model before unlearning.
Appendix figures & tables8 assets
Supplementary material from the paper’s appendix.
Appendix
Table 4: Non-unlearned Recovery Rate (RR, %) and Coverage (%) across target algorithms, models, and hint levels. Higher is better. Level 1 uses high-level hints; level 2 uses step-by-step hints. Each reported cell is based on 128 samples. Darker shading indicates higher value.
Figure 6: Algorithm coverage under the no-hint setting with a self-verifier. Top: scaling the number of trials at T∈{5,10,20} . Bottom: scaling interaction turns at n∈{8,32,128} .
Figure 7: Mask construction. Comments show abridged Dijkstra rollouts from Qwen3-4B-Thinking. Blue underlines mark names; yellow marks the selected token.
Algorithm
Qwen
Gemma
Kadane
20
30
DAG
37
59
Gray
12
19
BFS
43
87
Euclidean
23
56
Moore Vote
36
53
Appendix
Table 5: Unique token IDs in the evaluated masks. Qwen denotes Qwen3-4B-Thinking; Gemma denotes Gemma-4-12B (Thinking).
ID
Token
Source mention
ID
Token
Source mention
33
B
Breadth-First Search
16536
␣DI
DIJKSTRA
35
D
Dijkstra
17250
bell
bellman-ford
36
E
Eppstein
17625
DI
DIJKSTRA
37
F
Floyd-Warshall
17884
␣Bell
Bellman-Ford
42
K
Kruskal
21387
␣DJ
DJikstra
53
V
Viterbi
21666
Bel
Belman-Ford
Appendix
Table 6: The 42 evaluated Dijkstra mask IDs for Qwen3-4B-Thinking. Each row gives one reviewed source mention, including model-generated misspellings; a token may have additional sources. ␣ marks a leading space.
Original
Names suppressed
“… all edge weights are non-negative, so Dijkstra ’s algorithm should work. … ”
“… in each step, you pick the node with the smallest current distance , then relax all edges . … ”
⬇ # … for i in range (1, n + 1): if not visited [ i ] and dist [ i ] < min_dist : min_dist = dist [ i ] u = i if u is None : break visited [ u ] = True for v , w in graph [ u ]: new_dist = dist [ u ] + w if new_dist < dist [ v ]: dist [ v ] = new_dist # …
⬇ # … for node in unprocessed : if dist [ node ] < min_dist : min_dist = dist [ node ] min_node = node if min_node is None : break unprocessed . remove ( min_node ) for neighbor , weight in graph [ min_node ]: new_dist = dist [ min_node ] + weight if new_dist < dist [ neighbor ]: dist [ neighbor ] = new_dist # …
Accepted
Accepted
“The minimum cut in an undirected graph can be found using the Stoer-Wagner algorithm. … ”
“I proposed a simple algorithm that computes the minimum sum of edges for each node. … ”
⬇ # … current_cut = max_weight if current_cut < min_cut : min_cut = current_cut # Contract the last two nodes u = order [-2] v = order [-1] active_nodes . remove ( v ) # Merge v into u for node in active_nodes : graph [ u ][ node ] += graph [ v ][ node ] graph [ node ][ u ] = graph [ u ][ node ] # …
⬇ def solve ( n , matrix ): min_cut = float ( ’inf’ ) for i in range ( n ): total = 0 for j in range ( n ): if i != j : total += matrix [ i ][ j ] if total < min_cut : min_cut = total return min_cut
Table 8: Results of Qwen-3-4B-Thinking and Gemma-4-12B after name suppression. Recovery rate (RR, %) in the no hint setting and accuracy (%) on LiveCodeBench and AIME25. Original denotes the model before name suppression.
Algorithm
Qwen3.8-27B (Thinking)
Gemma-4-31B (Thinking)
Recovery Rate
LCB
AIME25
Recovery Rate
LCB
AIME25
Original
93.8
79.4
93.3
98.6
79.4
81.7
Kadane
100.0
76.3
95.6
96.9
77.9
82.2
DAG
90.6
72.5
88.9
100.0
74.8
82.2
Gray
78.1
75.6
97.8
93.8
72.5
80.0
BFS
87.5
82.4
95.6
84.4
71.0
81.1
Appendix
Table 9: Additional results of Qwen3.8-27B and Gemma-4-31B after name suppression. Recovery rate (RR, %) in the no hint setting and accuracy (%) on LiveCodeBench and AIME25. For computational efficiency, we use n=32 recovery trials per algorithm for these two models, compared with n=128 for Qwen3-4B-Thinking and Gemma-4-12B. Original denotes the model before name suppression.