70년 난제 해결! LLM이 이끄는 삭제 오류 정정 코드의 혁신

70년 이상 미해결이었던 삭제 오류 정정 코드 문제에 LLM 기반 FunSearch 알고리즘을 적용하여 단일 및 이중 삭제 오류에 대한 새로운 최고 크기의 코드를 생성, 기존의 하한선을 개선하고 LLM의 정보 이론 및 코드 설계 분야에서의 잠재력을 입증한 연구.

70년 이상 수학자들을 괴롭혀 온 난제가 드디어 해결의 실마리를 찾았습니다. 바로 삭제 오류 정정 코드(deletion-correcting codes) 의 최대 크기를 찾는 문제입니다. 데이터 전송 과정에서 발생할 수 있는 데이터 손실(삭제)을 복구하는 코드를 설계하는 것은 매우 중요한데, 가장 효율적인 코드를 찾는 것은 생각보다 훨씬 어려웠습니다.

독일 연구진 Franziska Weindel과 Reinhard Heckel은 이 문제에 LLM(대규모 언어 모델) 을 활용한 혁신적인 해결책을 제시했습니다. 그들의 논문 "LLM-Guided Search for Deletion-Correcting Codes"에서 제시된 방법은 기존의 접근 방식과는 사뭇 다릅니다.

그들은 FunSearch라는, Romera et al.(2024)이 제안한 LLM 기반 진화적 탐색 알고리즘을 사용했습니다. FunSearch는 우선순위 함수를 반복적으로 생성하고 평가하며 개선하여 최적의 코드를 찾아나갑니다. 이는 마치 LLM이 코드 설계 과정을 '지도'하는 것과 같습니다.

연구 결과는 놀랍습니다. 단일 삭제 오류의 경우, FunSearch는 기존에 알려진 최대 크기의 코드를 생성하는 우선순위 함수를 찾아냈습니다. 더욱 놀라운 것은, 최대 크기가 아직 알려지지 않은 Varshamov-Tenengolts 코드의 크기에 도달하는 코드를 생성했을 뿐만 아니라, 기존에 알려진 최적 코드와 동등한 코드를 독립적으로 재발견했다는 점입니다.

이중 삭제 오류의 경우에도 괄목할 만한 성과가 있었습니다. n = 12, 13, 16 길이의 코드에서 새로운 최고 크기를 달성하여, 기존 하한선을 개선했습니다. 이는 LLM 기반 탐색이 정보 이론 및 코드 설계 분야에서 가지는 잠재력을 보여주는 중요한 사례이며, 오류 정정 코드 생성에 LLM 기반 방법을 적용한 최초의 연구라는 점에서 큰 의의를 가집니다.

이 연구는 단순히 수학적 문제 해결을 넘어, 데이터 전송 및 저장 기술의 발전에 크게 기여할 것으로 예상됩니다. LLM의 놀라운 잠재력을 보여주는 이 연구는 앞으로 AI 기반 과학 연구의 새로운 지평을 열 것으로 기대됩니다. 향후 더욱 정교한 LLM과 알고리즘의 발전을 통해 더욱 강력하고 효율적인 오류 정정 코드를 기대할 수 있을 것입니다.