진화 탐색에서의 연산 자원 할당: 깊이-너비 방식에서 다중 팔 밴딧(Multi-Armed Bandits)으로

Compute Allocation in Evolutionary Search: From Depth-Breadth to Multi-Armed Bandits

LLM(대규모 언어 모델) 기반 진화 탐색 시스템(Evolve systems)은 수학 및 조합 문제에서 최첨단 결과를 보여주었지만, 대부분의 기존 시스템은 여러 실행 중 가장 좋은 결과만 보고하고 실행 간 분포에 대한 정보는 제공하지 않습니다. 본 연구에서는 고정된 LLM 호출 예산을 어떻게 할당해야 하는지, 그리고 단일 실행이 보고된 성능 수준에 얼마나 안정적으로 도달하는지를 탐구합니다. 다섯 가지 모델과 세 가지 작업을 대상으로 깊이-너비 매개변수를 조정하여 두 가지 경험적 규칙성을 발견했습니다. 첫째, 모든 모델의 능력이 효과적인 FLOP(Floating Point Operations) 기준으로 크게 일치하는 '적합도-연산' 관계가 나타났습니다. 둘째, 작업별 상호 작용을 포함하는 양선형 깊이-너비 관계가 관찰되었으며, 이는 모델과 작업 간의 성능에 의해 제한됩니다. 이러한 규칙성에 착안하여 본 연구에서는 다중 팔 밴딧(Multi-Armed Bandit) 기반으로 LLM 호출을 병렬 경로에 할당하는 BaSE (Bandit-based Self-Evolving) 시스템을 제안합니다. 동일한 모델, 프롬프트 및 평가기를 사용하면서도, BaSE는 8개의 (모델, 작업) 조합에서 가장 강력한 '아일랜드 프로토콜' 기준 대비 평균 적합도를 12.3% 향상시켰습니다. 특히 분산이 높은 환경에서 더 큰 성능 향상을 보였으며, 이는 자원 할당만으로도 달성된 신뢰성 향상입니다.

LLM-guided evolutionary search (Evolve systems) has reached state-of-the-art results on mathematical and combinatorial tasks, yet most existing systems report only the best of many runs and leave the run-to-run distribution undocumented. We ask how a fixed budget of LLM calls should be allocated, and how reliably a single run reaches the reported numbers. Sweeping the depth-breadth grid over five models and three tasks, we identify two empirical regularities: a fitness-compute envelope along which capability ordering largely collapses on effective FLOPs, and a bilinear depth-breadth fit with task-specific interaction; both are gated by model-task capability. Motivated by these regularities, we propose BaSE (Bandit-based Self-Evolving), a multi-armed bandit that allocates LLM calls across parallel trajectories. Without changing the model, prompt, or evaluator, BaSE improves mean fitness by 12.3% over the strongest island-protocol baseline across 8 (model, task) cells, with the largest gains on high-variance settings: a reliability gain from allocation alone.