Can Large Language Models Reinvent Foundational Algorithms?

arXiv:2604.05716v2 Announce Type: replace Abstract: 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: \textit{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.

Title:Can Large Language Models Reinvent Foundational Algorithms?

Abstract: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: \textit{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 this https URL.

Artificial Intelligence (cs.AI)

arXiv:2604.05716 [cs.AI]

(or arXiv:2604.05716v2 [cs.AI] for this version)

https://doi.org/10.48550/arXiv.2604.05716 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

aiqbench analysis

Can Large Language Models Reinvent Foundational Algorithms?

Related coverage