ImprovEvolve: Basin-Hopping Meets LLM-Guided Evolutionary Search

Motivation

• Known: AlphaEvolve는 LLM과 MAP-Elites 같은 진화 알고리즘을 결합해 end-to-end 최적화 프로그램을 진화시킴으로써 수학적 발견 문제(예: hexagon packing, spherical codes 등)에서 뛰어난 성과를 보여왔다. FunSearch 역시 단일 함수를 진화시켜 수학적 문제를 해결하는 유사한 접근을 취한다.
• Gap: 기존 AlphaEvolve류 접근법은 LLM에게 initialization, search strategy, termination criteria를 모두 포함한 end-to-end 최적화 알고리즘을 한 번에 설계하도록 요구하는데, 이는 rugged한 landscape(예: packing 문제)에서 LLM에게 지나친 인지 부담을 주며 L-BFGS-B 같은 범용 optimizer에 의존하게 되어 non-convex·non-smooth 제약 landscape에는 부적합하다는 한계가 있다.
• Why: 복잡한 수학적 최적화 landscape에서 LLM이 생성하는 코드의 품질을 근본적으로 개선할 수 있는 새로운 프로그램 분해 방식을 제시함으로써, 전문가의 기존 구성(construction)에도 적용 가능한 범용적이고 모듈화된 최적화 서브루틴을 LLM이 더 쉽게 진화시킬 수 있게 하는 접근으로, 수학적 발견을 위한 LLM-guided evolutionary computation 분야에 실질적 기여를 한다.
• Approach: LLM이 end-to-end optimizer 대신 improve, perturb, generate_config라는 세 개의 모듈화된 메서드를 가진 클래스를 진화시키도록 하고, 이를 basin-hopping 알고리즘의 서브루틴으로 활용하여 초기화-국소개선-강도 스케줄링된 perturbation을 반복 적용하는 방식으로 최적해에 접근한다.

Achievement

Figure 2. Three packings of n = 11 unit hexagons. (a) The previ-

1. Hexagon in hexagon packing 신기록 달성: n=11, 12, 15, 16개 hexagon에 대해 새로운 state-of-the-art packing을 발견했으며, 최소한의 전문가 코드 튜닝을 거쳐 n=14, 17, 23에 대해서도 개선된 결과를 얻었다.
2. Second autocorrelation inequality 개선: 진화된 프로그램과 human-scaled 프로그램을 통해 하한을 0.96102에서 0.96258로 끌어올렸다.
3. Spherical codes 개선: 무작위로 선택된 90개의 다양한 state-of-the-art spherical codes 중 대다수에 대해 best-known maximum cosine을 낮추었고, 최대 2.4%의 상대적 개선을 달성했다.
4. 모듈화된 LLM-guided evolution 프레임워크 제시: GigaEvo 프레임워크 위에 basin-hopping 스타일의 검증 알고리즘(Algorithm 1)을 구현하여 여러 도메인에서 검증했다.

How

Figure 1. Comparison of AlphaEvolve and ImprovEvolve. Top: In AlphaEvolve, the LLM evolves a program that directly outpu

• Basin-hopping 알고리즘의 perturbation과 local-optimization 서브루틴을 고정된 일반 연산자(예: 무작위 좌표 스텝, L-BFGS) 대신 LLM이 진화시킨 improve, perturb, generate_config 메서드로 대체.
• Validation Scheme(Algorithm 1)을 Stage A(K개의 초기 후보를 생성 및 개선 후 최고 fitness 후보를 시작점으로 선택)와 Stage B(R 라운드에 걸쳐 σ를 σmax에서 σmin까지 기하급수적으로 감소시키며 perturb-improve 반복, T=0의 monotonic acceptance 사용)로 구성.
• Gemini 3 Pro로 N=5개의 초기 프로그램을 생성하고 동일 채팅에서 검증기 오류를 반복 수정한 뒤, 진화 단계에서는 더 빠른 Gemini 3 Flash Preview를 사용하는 two-tier 접근 채택.
• 오픈소스 GigaEvo 프레임워크(Redis 기반 candidate store, 비동기 DAG 실행 엔진, 구성 가능한 island topology를 가진 MAP-Elites 루프, LLM 기반 mutation operator)를 기반으로 single-island MAP-Elites 설정(fitness를 유일한 behavior descriptor로 사용, 150개 bin으로 이산화)을 채택.

Originality

• AlphaEvolve/FunSearch류의 monolithic end-to-end optimizer 진화 방식에서 벗어나, LLM이 진화시킬 프로그램을 initialization·improve·perturb의 세 개 모듈로 명시적으로 재구성(reformulate)한 최초의 시도라고 저자들이 주장.
• 고전적인 global-optimization 기법인 basin-hopping을 LLM-guided evolutionary framework에 직접 접목시켜, 두 계열(고전 최적화와 LLM 기반 진화)의 강점을 결합.
• 전문가가 제공한 기존의 정교한 구성(construction)에도 진화된 improve/perturb 연산자를 적용할 수 있다는 점을 실질적 이점으로 부각시킴(human-scaled 프로그램 활용).

Limitation & Further Study

• 상당수 결과(hexagon packing n=14, 17, 23 및 autocorrelation inequality)에서 "minimal expert tuning" 또는 "human-scaled" 개입이 필요했다고 명시되어 있어, 완전 자동화된 LLM만의 성과로 보기 어렵고 인간 개입의 정도와 재현성에 대한 구체적 정량화가 부족하다.
• Gemini 3 Pro와 Gemini 3 Flash Preview라는 특정 상용 LLM에 강하게 의존하며, 이러한 two-tier 초기화 전략의 비용 및 다른 LLM에 대한 일반화 가능성에 대한 논의가 제한적이다.
• 본문 발췌에는 hyperparameter(K, M, σmax, σmin, bin 수 150 등)가 untuned라고 언급되지만 이에 대한 민감도 분석이나 다양한 문제에 대한 robust성 검증이 충분히 제시되지 않았다.
• 후속 연구로는 multi-island MAP-Elites 등 대안적 진화 전략과의 비교, 더 넓은 범위의 수학적 문제로의 확장, 완전 자동화(전문가 튜닝 없는) 파이프라인의 성능 검증이 필요해 보인다.

Evaluation

총평: LLM에게 요구하는 진화 대상 프로그램을 basin-hopping의 서브루틴 구조로 재구성한다는 간단하지만 효과적인 아이디어로 여러 어려운 수학적 최적화 벤치마크에서 실질적인 state-of-the-art 개선을 이끌어낸 견실한 연구이며, 다만 일부 결과에서 전문가 개입이 요구된다는 점은 완전 자동화 관점에서 아쉬움으로 남는다.