대규모 언어 모델은 기본적인 알고리즘을 재창조할 수 있는가?

Can Large Language Models Reinvent Foundational Algorithms?

대규모 언어 모델(LLM)은 과학적 발견을 발전시킬 수 있는 강력한 잠재력을 보여주었습니다. 그러나 LLM이 근본적인 혁신을 수행할 수 있는 능력은 여전히 미지수입니다. 본 연구에서는 근본적인 혁신을 위한 전제 조건인, LLM이 컴퓨터 과학 분야의 기본적인 알고리즘을 재창조할 수 있는지에 초점을 맞춥니다. 저희는 "Unlearn-and-Reinvent" 파이프라인을 사용하여 LLM의 사전 학습된 지식에서 특정 기본적인 알고리즘(예: 다익스트라 알고리즘 또는 유클리드 알고리즘)을 제거하는 LLM 학습 제거(unlearning) 방법을 적용하고, 제어된 환경에서 모델이 이를 재창조할 수 있는지 테스트합니다. 효과적인 학습 제거를 위해 GRPO 기반의 온-폴리시 학습 제거 방법을 채택했습니다. 10개의 대상 알고리즘, 3개의 강력한 오픈 가중치 모델, 그리고 3가지 힌트 레벨에 대한 실험 결과, (1) 가장 강력한 모델인 Qwen3-4B-Thinking-2507은 힌트 없이 50%, 힌트 레벨 1에서 70%, 힌트 레벨 2에서 90%의 알고리즘을 성공적으로 재창조했습니다. (2) 몇 가지 고수준 힌트는 재창조 성공률을 향상시킬 수 있지만, 단계별 힌트조차도 복잡한 알고리즘의 경우 실패하는 경우가 있습니다. (3) 테스트 시간 강화 학습을 통해 힌트 레벨 2에서 Strassen 알고리즘을 성공적으로 재창조할 수 있었습니다. 출력 경로 분석 및 제거 연구를 통해, 재창조 단계에서 생성적 검증기가 모델의 추론 능력을 유지하는 데 중요한 역할을 하며, "사고 붕괴(thought collapse)" 현상을 방지하는 데 도움이 된다는 것을 발견했습니다. 이러한 결과는 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.