1. 문제 정의 (Problem Definition)

현재 대규모 언어 모델 (LLM) 을 활용한 자동 프로그램 생성 및 알고리즘 발견 분야는 '일회성 생성 (One-shot generation)'에서 '추론 시간 검색 (Inference-time search)'으로 패러다임이 전환되고 있습니다. 특히 진화 알고리즘 (Evolutionary Algorithms, EAs) 을 LLM 과 결합하여 복잡한 검색 공간을 탐색하는 방식이 주류를 이루고 있습니다.

그러나 기존 시스템 (예: OpenEvolve, AlphaEvolve 등) 은 다음과 같은 중요한 한계를 가지고 있습니다:

• 정적 스케줄 (Static Schedules): 탐색 (Exploration) 과 활용 (Exploitation) 의 비율, 자원 할당, 프롬프트 템플릿 등이 사전에 고정되어 있습니다.
• 비정상적 동역학 (Non-stationary Dynamics) 무시: 검색 과정은 초기에는 급격한 개선을 보이다가 나중에는 정체 (Stagnation) 되는 등 동적인 변화를 겪는데, 고정된 정책은 이러한 변화에 적응하지 못합니다.
• 자원 낭비: 개선이 멈춘 지역 최적점 (Local Optima) 에 자원을 계속 투입하거나, 반대로 새로운 가능성을 가진 영역을 소홀히 하는 문제가 발생합니다.
• 수동 튜닝 필요: 새로운 문제에 대해 하이퍼파라미터 (변이율, 개체군 크기 등) 를 수동으로 조정해야 하며, 이는 인간의 직관에 의존합니다.

이러한 문제점을 해결하기 위해 AdaEvolve는 LLM 기반 진화를 계층적 적응 최적화 (Hierarchical Adaptive Optimization) 문제로 재정의합니다.

---

2. 방법론 (Methodology)

AdaEvolve 는 단일 **누적 개선 신호 (Accumulated Improvement Signal, $G_t$)**를 기반으로 세 가지 계층의 적응 메커니즘을 통합합니다. 이 신호는 지수 이동 평균 (Exponential Moving Average) 을 통해 정규화된 개선 크기의 제곱을 기반으로 계산됩니다.

Level 1: 로컬 적응 (Local Adaptation) - 개체군 내 탐색 강도 조절

• 목표: 각 서브-population(Island) 내부에서 탐색과 활용의 균형을 동적으로 조절합니다.
• 메커니즘:
  • 현재 개체군의 최근 개선 신호 ($G_t$) 가 높으면 (생산적임), 탐색 강도 ($I_t$) 를 낮추어 현재 경로를 활용 (Exploitation) 합니다.
  • 개선 신호가 낮아지면 (정체됨), 탐색 강도를 높여 지역 최적점을 탈출하도록 유도합니다.
  • 동적 프롬프트: 탐색 모드일 때는 무작위 부모를 선택하고 "직교적인 (orthogonal)" 솔루션을 유도하는 프롬프트를, 활용 모드일 때는 성능이 좋은 부모를 선택하고 "정제 (Refinement)"를 유도하는 프롬프트를 사용합니다.

Level 2: 글로벌 적응 (Global Adaptation) - 개체군 간 자원 할당

• 목표: 전역 컴퓨팅 예산을 가장 생산적인 개체군 (Island) 으로 라우팅합니다.
• 메커니즘:
  • 대역it 기반 선택 (Bandit-based Scheduling): 각 Island 를 하나의 "Arm"으로 간주하여 UCB(Upper Confidence Bound) 알고리즘을 사용합니다.
  • 전역 정규화 (Global Normalization): 기존 방식이 각 Island 의 로컬 개선량만 고려하여 낮은 기준점의 Island 를 선호하는 편향을 방지하기 위해, 전역 최고 성능 ($f^*_{global}$) 대비 개선량을 보상으로 사용합니다.
  • 동적 Island 생성: 모든 Island 의 개선 신호가 임계값 이하로 떨어지면 (전체적 정체), 새로운 Island 를 생성하여 새로운 탐색 영역을 확보합니다.

Level 3: 메타 가이드 (Meta-Guidance) - 솔루션 전술 생성

• 목표: 수치적 적응 (Level 1, 2) 만으로는 해결되지 않는 개념적 지역 최적점에 갇혔을 때, 검색 방향을 질적으로 전환합니다.
• 메커니즘:
  • 전역적 정체가 감지되면 별도의 LLM 을 호출하여 문제 정의, 평가자, 최근 실패 사례를 분석합니다.
  • 새로운 전술 (Solution Tactics) 생성: "그리디 선택에서 동적 프로그래밍으로 전환"과 같은 고수준 알고리즘적 지시를 생성하여 변이 (Mutation) 프롬프트에 주입합니다.
  • 이는 단순한 코드 수정이 아닌, 문제 해결 접근법 자체를 변경하는 "System 2" 개입 역할을 합니다.

---

3. 주요 기여 (Key Contributions)

1. 적응형 진화 프레임워크: 탐색 강도, 자원 할당, 전략 생성을 단일 적응 최적기 (Adaptive Optimizer) 하에 통합했습니다. 이는 기존 작업들의 임의적 휴리스틱 (Ad-hoc heuristics) 을 대체합니다.
2. 동적 전역 정규화 자원 할당: 로컬 히스토리가 아닌 전역 최고 성능 대비 개선량을 기준으로 자원을 할당하는 새로운 밴딧 스케줄러를 제안하여, 자원이 비생산적인 지역 최적점에 낭비되는 것을 방지합니다.
3. 강력한 일반화 능력: 185 개의 다양한 최적화 및 알고리즘 발견 문제 (수학적 최적화, 시스템 최적화, 알고리즘 설계) 에서 동일한 하이퍼파라미터 설정으로 기존 오픈소스 베이스라인을 일관되게 능가했습니다.

---

4. 실험 결과 (Results)

논문은 185 개의 벤치마크에서 AdaEvolve 의 성능을 검증했습니다.

• 수학적 최적화 벤치마크 (6 개 문제):
  • Circle Packing (N=26): AdaEvolve 는 2.636 점으로 인간 최선 (SOTA, 2.634) 과 AlphaEvolve(2.635) 를 능가했습니다.
  • Heilbronn Triangle 등: 고정된 정책의 베이스라인들이 초기 개선 후 정체되는 반면, AdaEvolve 는 지속적인 개선을 보여주었습니다.
• ADRS 시스템 벤치마크 (7 개 문제):
  • 실제 시스템 최적화 (Telemetry, Cloudcast, TXN 등) 에서 AdaEvolve 는 GPT-5 와 Gemini-3-Pro 백본 모두에서 모든 7 개 과제에서 최상의 성능을 기록했습니다. 특히 희소하고 불규칙한 개선이 발생하는 과제 (TXN 등) 에서 적응형 메커니즘의 효과가 두드러졌습니다.
• Frontier-CS 벤치마크 (172 개 문제):
  • 오픈 엔디드 컴퓨터 과학 문제에서 AdaEvolve 는 평균 점수 61.33을 기록하여 OpenEvolve(50.75), ShinkaEvolve(47.79) 등을 압도했습니다. 단일 LLM 호출 (Median 0 점) 대비 검색 알고리즘의 필요성을 입증했습니다.
• Ablation Study:
  • Level 3(메타 가이드) 을 제거했을 때 성능이 가장 크게 저하되어, 정체 구간을 탈출하는 전략 생성의 중요성을 입증했습니다.

---

5. 의의 및 결론 (Significance & Conclusion)

AdaEvolve 는 LLM 기반 프로그램 생성 분야에서 고정된 규칙에서 적응형 시스템으로의 전환을 의미합니다.

• 자동화 및 효율성: 사용자는 모델 이름과 반복 횟수만 지정하면 되며, 복잡한 하이퍼파라미터 튜닝 없이도 다양한 문제에 대해 최적의 검색 전략을 자동 조정합니다.
• 자원 효율성: 정체된 영역에 자원을 낭비하지 않고, 생산적인 영역으로 자원을 집중시킴으로써 계산 비용을 절감하고 더 나은 결과를 도출합니다.
• 지적 발견의 확장: 단순한 코드 변이를 넘어, 알고리즘적 사고 (Meta-Guidance) 를 통해 인간이나 기존 AI 가 도달하지 못한 새로운 솔루션 영역 (예: Circle Packing 의 새로운 레이아웃) 을 발견할 수 있음을 증명했습니다.

결론적으로 AdaEvolve 는 추론 시간 컴퓨팅 (Inference-time Compute) 을 효과적으로 활용하여, LLM 이 단순한 생성기를 넘어 적응형 최적화 에이전트로 진화할 수 있는 강력한 프레임워크를 제시합니다.