!원문 캡처 · slightlysupervised.substack.com

Ryan Xu는 대형 정사각형 안에 단위 정사각형을 겹치지 않게 넣는 문제에서 25개 값의 기존 기록을 깼다고 밝혔다. LLM 에이전트가 포장 프로그램을 반복적으로 변형하는 탐색을 2일간 진행했으며, 가장 오래된 기록은 47년간 유지된 기록이었다.

탐색 방식과 결과

기준 프로그램은 정사각형을 상자 안에 무작위로 배치한 뒤 상자를 점차 줄인다. 정사각형이 겹치면 L-BFGS 최적화기로 겹치지 않는 국소 배치를 찾는다. 각 세대에서 Claude Haiku 에이전트들이 이전 세대의 우수 프로그램을 변형하고, 여러 정사각형 수에 대한 기존 최고 포장 기록과의 차이를 기준으로 성능을 평가했다. 이 과정을 128세대 실행했다.

탐색에는 CPU 시간 7,500시간과 토큰 비용 125달러가 들었다. 세대별 후보 수를 16개에서 64개로 늘리고, 더 큰 정사각형 수를 평가에 포함하는 등 실행 중 설정도 조정했다. 큰 값에서 실행 시간이 초과되는 문제를 발견한 뒤 최대 실행 시간을 10초에서 60초로 늘렸고, 아직 기록을 깨지 못한 값이 평가 점수에 더 크게 반영되도록 했다.

프로그램이 찾아낸 전략

초기에는 무작위 배치와 상자 축소 방식을 유지하면서 배치를 다듬는 알고리즘을 추가하는 경향이 있었다. 평가 대상에 큰 정사각형 수를 포함한 뒤에는 계단형이나 대각선 열 같은 구조를 이용해 초기 배치를 만드는 프로그램도 나타났다.

다른 전략으로는 상자를 줄이는 동안 정사각형 모서리를 둥글게 했다가 다시 각지게 만들기, 겹침을 일으키는 정사각형을 덜 흔들어 가장자리를 안정시키기, 빈 공간이 큰 곳으로 정사각형을 옮기기 등이 있었다. 일부 프로그램은 불완전한 배치에 불이익을 주지 않도록 처음부터 단순한 격자 배치를 출력하기도 했다.

Ryan Xu는 탐색 프로그램과 결과를 GitHub 저장소에 공개했다. 정사각형 포장 기록은 Joshua Levy의 기록 페이지에서 확인할 수 있으며, 탐색에 영감을 준 체험 도구인 Packing Lab도 공개돼 있다. 이 결과는 기록을 개선한 포장 배치와 탐색 과정에 관한 것이며, 원문은 이를 최적해의 증명이라고 설명하지 않는다.