언어 모델이 정사각형 포장 기록 25개를 깼다

팬이 없는 작은 맥북 에어에서 탐색을 시작한 지 한 시간도 안 돼 51개 정사각형의 포장 기록이 깨졌다. 이어 103개와 105개의 기록도 넘어섰다.

글쓴이는 언어 모델을 이용한 진화적 프로그램 탐색(evolutionary program search)으로 이틀 동안 정사각형 포장 기록 25개를 깼다고 전했다. 이 방법은 수학 문제의 해를 찾는 탐색 프로그램을 자동으로 발전시키는 데 관심 있는 사람에게 참고가 된다.

진화적 프로그램 탐색은 무엇인가?

진화적 프로그램 탐색은 프로그램을 여러 후보로 만들고, 결과가 좋은 후보를 바탕으로 다음 후보를 생성하는 방식이다. 여러 조리법을 시험해 더 나은 결과를 내는 방법을 남기는 과정에 빗대면 이해하기 쉽다. 여기서는 정사각형을 배치하는 프로그램을 반복해서 바꾸고, 각 프로그램이 만든 포장을 평가했다.

문제는 한 변의 길이가 1인 정사각형 n개를 모두 담는 가장 작은 정사각형을 찾는 것이다. 글쓴이는 먼저 Claude에 기존 기록을 깨도록 요청했지만 한 시간 동안 성과가 없었다. 이후 직접 포장 실험을 하며 모서리 둥글게 하기, 흔들기 강도 조절, 흔드는 방향 제한, 상자가 작아질수록 흔들기를 줄이는 기능 등을 웹 앱에 추가했다. 이 실험 도구는 Packing Lab에서 볼 수 있다.

탐색은 어떻게 진행했나?

기준 프로그램은 정사각형 n개를 상자 안에 무작위로 놓고 상자를 서서히 줄인다. 정사각형이 겹치면 제한 메모리 BFGS 최적화법(L-BFGS)이 겹치지 않는 배치를 찾는다. 이 과정이 수렴하면 포장이 완성된다. 포장 실험용으로 만든 함수들도 후보 프로그램이 활용할 수 있도록 함께 제공했다.

각 세대에서는 Claude Haiku 에이전트들이 이전 세대의 우수 프로그램을 변형했다. 우수성은 정해진 n 값 표본에서 알려진 최고 기록과의 차이를 기준으로 매겼다. 이 진화 과정을 128세대 실행했다.

탐색 중에는 후보 수를 세대당 16개에서 64개로 늘렸다. 프로그램의 다양성이 낮아 보이자 변형 지시를 네 가지 역할로 나눴다. 기본 역할은 프로그램 개선, 교차 역할은 후보 둘을 합치는 작업, 발명 역할은 새 기본 기능을 만들고 사용하는 작업, 문샷 역할은 위험은 크지만 보상도 큰 변경을 맡았다. 이후 n이 200보다 큰 문제도 포함했고, 큰 n에서 제한 시간 초과가 발생하자 실행 시간을 10초에서 60초로 늘렸다. 아직 기록을 깨지 못한 n 값에는 점수 가중치를 높였다.

어떤 전략이 발견됐나?

초반 프로그램은 무작위 배치와 상자 축소 방식을 유지하면서 기존의 국소 탐색(basin hopping)을 보완하는 정련 알고리즘을 더했다. 이후 큰 n의 점수를 반영하자 정사각형을 더 구조적으로 배치하기 시작했다.

발견된 전략에는 상자가 줄어드는 동안 정사각형의 모서리를 둥글게 했다가 다시 각지게 만드는 방식, 불완전한 배치에 불이익이 없도록 간단한 격자를 먼저 놓는 방식이 포함됐다. 정련 과정에서는 가장 빈 공간에 정사각형을 옮기거나 두 정사각형의 각도·위치를 바꾸기도 했다. 초기 배치에 계단형 구조나 대각선 열을 쓰고, atan(1/2), atan(1/3), atan(2/3) 같은 각도를 활용하는 프로그램도 나왔다.

큰 n에서는 계단형 구조를 고정하고 나머지만 최적화하기도 했다. 위치를 흔들어 바꾸는 동안 겹침을 일으키는 정사각형은 덜 움직여 가장자리가 빠르게 안정되도록 했다. 글쓴이는 진화 에이전트가 프로그램의 코드와 복잡성을 늘리는 경향을 보였고, 탐색 지시의 종류를 넓힌 뒤 20세대 무렵 프로그램 다양성이 크게 증가했다고 설명했다.

결과를 어디까지 볼 수 있나?

전체 실행은 2일 동안 이어졌고, 7,500 CPU 시간과 토큰 비용 125달러를 사용했다. 가장 오래된 기록은 47년 된 것으로, n=295의 기록은 1979년 프리츠 괴벨(Frits Göbel)이 세웠다. n=86 기록은 1997년 에리히 프리드먼(Erich Friedman)이 세웠다. 결과와 프로그램은 GitHub 저장소에 공개됐다.

정사각형 포장 기록은 에리히 프리드먼의 기록 목록에서 관리됐고, 이후 데이비드 엘스워스(David Ellsworth)의 목록과 조슈아 레비(Joshua Levy)의 목록에도 정리됐다. 글쓴이는 접근 방식이 AlphaEvolve와 비슷하다고 설명하며 관련 논문을 연결했다.

이 결과는 기록을 깨는 배치를 찾았다는 보고다. 각 배치가 최적임을 증명했다는 뜻은 아니다. 원문은 25개 기록의 전체 목록이나 각 결과의 독립 검증 여부, 탐색을 재현하는 데 필요한 세부 조건은 밝히지 않는다.