본 논문은 70년 이상 미해결 문제였던 최대 크기의 삭제 정정 부호를 찾는 문제에 대한 새로운 접근 방식을 제시합니다. 우선순위 함수에 따라 가장 높은 우선순위의 시퀀스를 탐욕적으로 추가하여 부호를 구성합니다. 좋은 우선순위 함수를 찾기 위해 Romera et al., 2024에서 제안된 대규모 언어 모델(LLM) 기반 진화적 탐색인 FunSearch를 활용합니다. FunSearch는 반복적으로 우선순위 함수를 생성, 평가 및 개선하여 큰 삭제 정정 부호를 구성합니다. 단일 삭제의 경우, 알려진 최대 크기와 일치하는 부호를 구성하는 함수를 찾고, 최대 크기가 알려지지 않은 가장 큰 (추정 최적) Varshamov-Tenengolts 부호의 크기에 도달하며, 동등한 형태로 독립적으로 재발견합니다. 두 개의 삭제의 경우, 코드 길이 n = 12, 13 및 16에 대해 새로운 최고 크기의 부호를 구성하는 함수를 찾아 개선된 하한을 설정합니다. 이러한 결과는 정보 이론 및 부호 설계에 대한 LLM 기반 탐색의 잠재력을 보여주며, 오류 정정 부호를 구성하기 위한 이러한 방법의 첫 번째 적용 사례를 나타냅니다.
