🤖 AI

ImprovEvolve: Basin-Hopping Meets LLM-Guided Evolutionary Search

ImprovEvolve는 육각형 패킹, 자기상관 부등식, 구형 부호 문제에서 새로운 최첨단 솔루션을 성공적으로 발견하는 동시에 언어 모델의 인지 부하를 크게 줄이는, 베이신 호핑(basin-hopping) 과정을 유도하기 위해 특화된 초기화, 개선 및 섭동 연산자를 진화시키는 LLM 유도 진화 탐색을 도입한다.

원저자: Alexey Kravatskiy, Valentin Khrulkov, Ivan Oseledets

게시일 2026-06-30

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Alexey Kravatskiy, Valentin Khrulkov, Ivan Oseledets

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신이 아주 어려운 퍼즐을 풀려고 노력하고 있다고 상상해 보세요. 예를 들어, 특정한 수의 기묘한 모양의 육각형들을 겹치지 않게 용기에 끼워 넣거나, 특정 값을 최대화하는 완벽한 수학적 곡선을 찾는 것과 같은 일입니다. 이것들은 "최적화 문제"라고 불리며, 매우 까다로운데 그 이유는 가능한 해답들의 지형이 작은 언덕과 깊은 골짜기(지역 최적점)로 가득 차 있기 때문입니다. 만약 잘못된 발걸음을 내디디면, 얕은 골짜기에 갇혀서 더 깊은 곳을 영영 찾지 못할 수도 있습니다.

오랫동안 연구자들은 인공지능(특히 거대 언설 모델, LLM)에게 이 퍼즐을 풀도록 가르치기 위해, 시작은 어떻게 하고, 어떻게 움직이며, 언제 멈춰야 하는지를 한꺼번에 모두 결정하는 단 하나의 거대한 프로그램을 작성하도록 요청해 왔습니다. 이는 마치 요리사에게 요리를 할 뿐만 아니라 주방을 설계하고, 새로운 조리 도구를 발명하며, 레시피 북까지 한 번에 다 만들라고 요구하는 것과 같습니다. 이 논문은 이러한 접근 방식을 "AlphaEvolve"라고 부릅니다. 이 방식은 때때로 작동하긴 하지만, AI를 압도하여 결국 서툴거나 불완전한 해결책을 내놓게 만드는 경우가 많습니다.

새로운 아이디어: ImprovEvolve

이 논문의 저자인 알렉세이 크라바츠키(Alexey Kravatskiy)와 동료들은 ImprovEvolve라고 불리는 더 스마트한 방법을 제안합니다. AI에게 처음부터 "슈퍼 최적화 도구"를 통째로 만들라고 요구하는 대신, 작업을 세 가지 작고 관리 가능한 작업으로 나눕니다. 그들은 AI에게 세 가지 특정 도구가 포함된 "도구 상자"를 작성하도록 요청합니다.

시작 도구 (generate_config): 퍼즐을 위한 무작위의 유효한 시작점을 생성하기만 하는 도구입니다.
다듬기 도구 (improve): 엉망인 해결책을 가져와서 이를 약간 더 좋게 만들고 가장자리를 매끄럽게 다듬는 도구입니다.
흔들기 도구 (perturb): 해결책을 무작위로 흔들어, 흔드는 것이 더 깊고 더 나은 골짜기로 떨어지는 데 도움이 되는지 확인하는 도구입니다.

"베이슨 호핑(Basin-Hopping)"의 춤

AI가 이 도구 상자를 구축하고 나면, 연구자들은 이를 단순히 한 번 실행하는 데 그치지 않습니다. 그들은 베이슨 호핑이라 불리는 고전적인 수학적 전략을 사용합니다. 이것은 안개 낀 산맥에서 가장 낮은 지점을 찾으려는 등산가와 같습니다.

시작: 등산가는 무작위 지점에 착륙합니다 (시작 도구 사용).
다듬기: 그들은 가장 가까운 골짜기 바닥을 향해 아래로 내려갑니다 (다듬기 도구 사용).
흔들기: 그들은 다른 더 깊은 골짜기에 착륙하기를 바라며 새로운 지점으로 크게 무작위로 도약합니다 (흔들기 도구 사용).
반복: 만약 새로운 지점이 더 낮다면, 그 자리에 머뭅s니다. 그렇지 않다면, 다시 시도할 수도 있습니다. 이 과정을 반복하면서, 그들은 목표 지점에 가까워질수록 점점 더 작은 보폭으로 이동합니다.

"생각하는 것"(AI가 하는 일)과 "탐색하는 것"(베이슨 호핑 루프)을 분리함으로써, AI는 한 번에 한 가지 특정한 일에만 집중할 수 있습니다. 이는 복잡한 문제를 해결할 때 전체를 한꺼번에 머릿속에 담아두려 하기보다 단계를 나누어 해결하는 것이 인간에게 더 효과적인 것과 마찬가지로, AI의 "인지 부하"를 줄여줍니다.

결과: 새로운 기록

이 논문은 이 방법을 세 가지 매우 어려운 수학적 과제에 대해 테스트했습니다.

육각형 채우기 (Hexagon Packing): 11개, 12개, 또는 심지어 23개의 육각형을 가장 작은 육각형 상자에 채우는 것을 상상해 보세요. 이 새로운 방법은 여러 경우에 대해 새로운 세계 기록적인 채우기 방식을 찾아냈으며, 이는 이전의 AI 시스템이나 심지어 인간 전문가들이 세운 기록을 경신한 것입니다.
자기상관 부등식 (Autocorrelation Inequality): 이것은 파동의 완벽한 형태를 찾는 것에 관한 복잡한 수학 문제입니다. AI는 알려진 수학적 한계(하한값)를 0.96102에서 0.96258로 개선했습니다. 이는 이전 AI가 찾은 좋은 해결책을 가져와서 "다듬기" 도구를 사용하여 더욱 정교하게 만든 결과입니다.
구면 부호 (Spherical Codes): 이것은 구 위에서 점들을 최대한 멀리 떨어지도록 배치하는 것을 포함합니다 (석류 씨앗처럼). 이 새로운 방법은 90가지 테스트 케이스 중 대다수에서 배치를 개선하여, 이전에 알려진 그 어떤 것보다 약간 더 효율적인 구성을 찾아냈습니다.

인간의 손길

흥미롭게도, 이 논문은 AI가 힘든 일을 수행하는 동안에도 인간 전문가가 코드에 몇 가지 아주 작은 수정(특정 설정을 변경하거나 수학적 도구를 교체하는 등)을 가하여 최상의 결과를 얻었다고 언급합니다. 이는 최고의 결과가 AI가 핵심 구조와 로직을 생성하고, 인간이 AI가 놓칠 수 있는 최종적인 "미세 조정"을 제공하는 파트너십에서 나온다는 것을 시사합니다.

요약하자면

이 논문은 AI에게 한 번에 전체 문제를 해결하는 "천재"가 되라고 요구하는 대신, 도구 세트를 만드는 "전문가"가 되라고 요구해야 한다고 주장합니다. 그런 다음, 이 도구들을 베이슨 호핑이라는 스마트한 반복 루프를 통해 사용하여 해결 공간을 탐색합니다. 이 방식인 ImprovEvolve는 모든 것을 한꺼번에 처리하려 했던 이전의 방법들보다 더 효과적이고 견고하며, 새로운 수학적 기록을 찾아내는 데 더 유능하다는 것을 입증했습니다.

기술 요약: ImprovEvolve: 베이신 호핑(Basin-Hopping)과 LLM 유도 진화 탐색의 만남

문제 정의

본 논문은 대규모 언어 모델(LLM)을 사용하여 복잡한 수학적 최적화 문제, 특히 험난하고 비볼록(non-convex)하며 비매끄러운(non-smooth) 지형(예: 패킹 문제, 함수 부등식, 구형 코드 등)을 해결하는 과제를 다룹니다. AlphaEvolve와 같은 기존 연구는 후보 해를 직접 출력하는 단일 구조의 프로그램을 진화시키는 데 성공했지만, 저자들은 이러한 방식이 LLM에 과도한 인지적 부하를 준다고 주장합니다. 모델은 초기화 스킴, 탐색 전략, 종료 기준을 동시에 설계해야 하며, 이로 인해 생성된 프로그램은 종종 특정 제약 조건과 비볼록성을 효과적으로 처리하지 못하는 기성 루틴(예: L-BFGS-B)에 의존하게 됩니다. 결과적으로 LLM이 생성한 솔루션은 수학적 통찰력과 휴리스틱을 결합하는 데 그치며, 엄밀하게 최적화 작업을 해결하기보다는 휴리스틱에 의존하게 되고, 보지 못한 문제 크기에 일반화하거나 전문가가 구축한 솔루션을 개선하는 데 어려움을 겪습니다.

방법론: ImprovEvolve

저자들은 최적화 작업을 특화된 서브루틴으로 분해하여, 베이신 호핑(Basin-Hopping) 전역 최적화 기법과 LLM 유도 진화 탐색을 효과적으로 통합하는 알고리즘적 대안인 ImprovEvolve를 제안합니다.

핵심 분해

단일 함수를 진화시키는 대신, ImprovEvolve는 세 가지 별도의 연산자를 구현하는 파이썬 클래스를 진화시킵니다.

generate_config(seed): 무작위 시드로부터 실행 가능한 해를 초기화합니다.
improve(x): 구성 $x$ 를 정밀하게 개선하여, $x$ 보다 최소한 같거나 더 나은 성능을 가진 해 $x'$ 를 반환하는 국소 최적화(local optimization)를 수행합니다.
perturb(x, \sigma): 특정 강도 $\sigma$ 에서 탐색 공간을 무작위로 탐색합니다.

검증 체계 (Basin-Hopping)

진화된 클래스는 모노토닉 베이신 호핑( $T=0$ )을 모사하는 2단계 검증 체계(알고리즘 1) 내에서 활용됩니다.

단계 A (초기화): 여러 개의 초기 구성을 생성하고 improve를 통해 정밀화합니다. 가장 좋은 결과를 시작점 $x^*$ 로 선택합니다.
단계 B (반복 탐색): 알고리즘은 섭동(perturbation)과 개선 과정을 $R$ $R$ 번 반복합니다. 각 라운드에서 섭동 강도 $\sigma$ $σ$ 는 $\sigma_{max}$ $σ_{ma x}$ 에서 $\sigma_{min}$ $σ_{min}$ 까지 기하급수적으로 감소합니다. 과정은 다음과 같습니다:
1. 현재 최적해를 섭동: $x' = \text{perturb}(x^*, \sigma)$ .
2. 섭동된 해를 정밀화: $x'' = \text{improve}(x')$ .
3. 모노토닉 수용: $x''$ 의 적합도(fitness)가 엄격하게 개선된 경우에만 $x^*$ 를 $x''$ 로 업데이트합니다.

이러한 분해는 LLM의 과업을 엔드 투 엔드 최적화 도구를 설계하는 것에서, 초기화, 국소 탐색 및 탐색을 위한 도메인 특화 휴리스틱을 인코딩하는 것으로 전환하며, 이는 다시 고전적인 베이신 호핑 프레임워크에 의해 조율됩니다.

진화 프레임워크

시스템은 MAP-Elites 루프를 갖춘 GigaEvo 프레임워크를 사용합니다. 후보 프로그램의 적합도는 해당 프로그램에 대해 전체 2단계 검증 체계를 실행하여 결정됩니다. LLM(초기화를 위해 Gemini 3 Pro, 진화를 위해 Gemini 3 Flash 사용)은 적합도 피드백과 계보 통찰력을 바탕으로 Improv 클래스의 코드를 변이시킵니다.

주요 기여 및 결과

1. 육각형 패킹 (HEX $n$ )

과업: $n$ 개의 단위 정육각형을 가장 작은 둘레의 정육각형 안에 채우는 문제.
결과:
- $n=11$ 에 대해, ImprovEvolve는 변의 길이 $L=3.4245$ 인 새로운 SOTA(최고 수준) 패킹을 발견하여 AlphaEvolve의 $3.9301 $과 이전 인간 기록인$ 3.9434$를 경신했습니다.
- 진화된 프로그램은 재진화 없이도 보지 못한 문제 크기( $11 \le n \le 24$ )에 일반화되어 $n=12, 15, 16$ 에 대한 새로운 SOTA 패킹을 찾아냈습니다.
- ImprovEvolve+E: 약간의 인간 편집(옵티마이저 교체, 페널티 가중치 조정)을 통해, 시스템은 $n=14, 17, 23$ 에 대한 새로운 SOTA 패킹을 찾았으며, 기존 결과가 없던 $n=25-30$ 에 대한 구조적 패킹을 제공했습니다.
비교: ImprovEvolve는 단일 구조 접근 방식인 GigaEvo 베이스라인을 크게 능가했습니다. GigaEvo는 중첩 오류로 인해 $n > 11$ 로 일반화하는 데 실패했습니다.

2. 2차 자기상관 부등식 (ACI 2)

과업: 부등식 $\|f * f\|_2^2 \le C_2 \|f * f\|_1 \|f * f\|_\infty$ 에서 상수 $C_2$ 를 최대화하는 비음수 함수 $f$ 를 찾는 문제.
결과:
- 기본 ImprovEvolve 프로그램은 $C(f) = 0.9512$ 를 달성하여 오픈 소스 베이스라인을 넘어섰으나, AlphaEvolve의 $0.96102$에는 미치지 못했습니다.
- ImprovEvolve+E: AlphaEvolve의 솔루션으로부터 최적화를 재개하고 인간의 가이드가 포함된 편집(점진적 해상도 스케일링 업 최대 1.6M 단계, 하단 클리핑 제거)을 적용함으로써, 시스템은 $C(f) = 0.96258$ 이라는 새로운 SOTA 하한선을 달성했습니다.
의의: 이는 본 프레임워크가 전문가나 다른 모델이 제공한 고품질 솔루션을 정밀하게 개선할 수 있는 능력을 보여주며, 이는 단일 구조의 LLM 접근 방식이 어려워하는 부분입니다.

3. 구형 코드 (Spherical Codes)

과업: 단위 구 $S^{d-1}$ 상에 $N$ 개의 점을 배치하여 최대 쌍별 내적(coherence)을 최소화하는 문제.
결과:
- Cohn 카탈로그의 90가지 다양한 구성( $d \in [8, 16]$ )에 대해 평가되었습니다.
- ImprovEvolve++ (여러 차원에 걸쳐 캘리브레이션된 일반 개선기)는 90개 구성 중 53개에 대해 최대 코사인 값을 엄격하게 낮추었으며, 평균 상대 개선율은 **0.1765%**였습니다.
- 이는 이전 최고의 프로그램(ImprovEvolve) 대비 2.35배의 개선을 의미합니다.
- 진단(UMAP 및 내적 분포) 결과, ImivEvolve++는 점들을 탐색 공간의 서로 다른 영역으로 이동시키는 전역적 구조 재배열을 수행한 반면, 다른 변형들은 국소적 조정만을 수행했음을 보여주었습니다.

통계적 견고성

다중 실행 연구를 통해 ImprovEvolve의 개선 사항이 GigaEvo 베이스라인에 비해 통계적으로 유의미함( $p < 0.05$ )을 확인하였으며, 이는 모듈형 분해가 단일 구조의 최적화 도구보다 재현 가능한 이점을 제공함을 입증합니다.

의의 및 주장

본 논문은 최적화 과업을 모듈형 서브문제로 분해하는 것이 LLM 유도 발견을 위한 핵심 원칙이라고 주장합니다.

인지적 부하 감소: 초기화, 국소 개선, 섭동을 분리함으로써, LLM은 전체 탐색 과정을 조율하는 대신 수학적 구조와 휴리스틱을 인코딩하는 데 집중할 수 있습니다.
인간-LLM 협업: 모듈형 인터페이스를 통해 도메인 전문가가 타겟팅된 최소한의 편집(예: 옵티마이저 변경, 해상도 스케줄 조정)을 적용하여 성능을 크게 높일 수 있으며, 이는 LLM 생성 코드와 전문가 수준의 튜닝 사이의 간극을 메워줍니다.
일반화: improve/perturb 인터페이스는 진화된 프로그램이 보지 못한 문제 크기에 일반화하고, 전문가가 제공한 솔루션으로부터 최적화를 재개할 수 있게 하여, 단일 구조의 엔드 투 엔드 프로그램이 가진 취약성을 극복합니다.

저자들은 이 연구를 LLM 기반 수학적 발견을 확장하기 위한 단계로 위치시키며, 향-미래의 시스템은 이러한 맞춤형 분해와 어떤 모듈을 정밀화할지 자율적으로 결정하는 에이전트 워크플로우를 결합해야 한다고 제할합니다. 본 논문은 양적 평가가 현재 이 세 가지 특정 최적화 도메인에 국한되어 있음을 언급하며, 광범위한 일반화 가능성에 대해서는 신중한 태도를 유지하고 있습니다.