FrugalEvo가 LLM 프로그램 진화의 비용당 성능을 높인다
FrugalEvo: Towards Cost-Aware LLM-Guided Program Evolution
무엇인가
LLM을 이용한 진화적 탐색 방법은 AlphaEvolve, OpenEvolve, ShinkaEvolve처럼 고성능 프로그램 풀을 유지하며 부모를 선택하고 LLM에 변이를 요청한 뒤 후보를 평가하는 방식으로 수학·시스템·알고리즘 최적화에서 성과를 냈다. 그런데 기존 연구는 주로 정해진 반복 횟수나 LLM이 생성한 후보 수, 평가 호출 수를 기준으로 성능 곡선을 그린다. 이 논문은 그 관점이 실무에서 중요한 제약인 총비용을 놓친다고 주장한다. 비용에는 LLM 추론 API 요금과 GPU 컴퓨트, 평가기 실행을 위한 CPU 컴퓨트 등이 포함된다. 테스트타임 스케일링처럼 추론 연산을 늘리면 성능이 오르는 현상이 있으므로, 높은 성능만으로 효율이 높다고 말할 수 없고 성능 대비 비용, 즉 비용당 이득으로 평가해야 한다는 것이다.
어떻게 동작하나
저자들은 고정 예산 아래에서의 품질을 측정하기 위해 Budget-Aware Area Under the Curve(BA-AUC)를 제안한다. 문제를 프로그램 공간 X, 초기 프로그램 x0, 평가기 E(x)=(s(x), a(x))로 정식화한다. s(x)는 최대화할 과제별 점수, a(x)는 보조 피드백이다. 평가된 프로그램은 데이터베이스 D_t에 쌓이고, 탐색 전략 S가 과제 설명·부모 프로그램·샘플 참조 프로그램·평가 결과·이전 시도 요약을 조합해 검색 문맥 C_S(D_t)를 만든다. LLM은 이 문맥에 조건화해 새 후보 x_{t+1}을 생성하고, 평가 결과가 다시 데이터베이스에 추가된다. 목표는 고정 비용 예산 B 아래에서 D_B 안의 최고 점수 s*를 최대화하는 것이다. BA-AUC(B)는 누적 LLM 비용 c에 대한 최고-지금까지 점수 q(c)의 적분, 즉 ∫_0^B q(c) dc로 정의한다. 실행이 예산 전에 끝나면 점수를 B까지 상수로 유지하고, 예산을 넘기면 B에서 곡선을 자른다.
무엇과 다른가
FrugalEvo의 절차는 다음과 같다. 먼저 콜드 스타트 단계에서 저비용 LLM이 초기 프로그램을 점수가 더 이상 오르지 않을 때까지 반복 개선하고, 그 결과를 첫 부모이자 인컴번트로 삼는다. 문맥 구축기는 고비용 LLM으로 문제 설명과 평가기 코드를 분석해 최적화 목표와 평가 제약을 파악하고, 인컴번트와 평가 피드백, 검색 메모리에서 가져온 이전 시도·전략·피드백을 결합해 탐색 문맥을 갱신한다. 캐시 효율적 프롬프트 구성은 공유 내용을 앞쪽에 배치해 API 프롬프트 캐싱의 접두사 재사용을 극대화한다. 고정 내용(과제 지시, 출력 요구사항)을 맨 앞에 두고, 덜 자주 바뀌는 문맥 예시(섬 최고·엘리트 프로그램을 무작위 샘플보다 앞에)를 그다음에, 자주 바뀌는 정보를 마지막에 둔다. 각 시도의 피드백은 프롬프트 끝에 덧붙여 캐시 사용을 가능하게 한다. 전략 탐색기는 고비용 LLM이 한 번의 API 호출로 여러 개의 서로 다른 설계 전략을 제안하게 한다. 각 전략은 부모 프로그램에서 무엇을 바꿀지, 왜 성능이 오를 수 있는지, 어떤 계산 한도를 지킬지를 설명한다. 해법 생성기는 저비용 LLM이 전략별로 시험 구현을 하나씩 만들고 평가 점수로 순위를 매긴 뒤, 순위에 따라 전략을 골라 개선 라운드를 진행한다. 한 라운드에서는 하나의 전략과 현재 인컴번트를 부모로 고정하고 최대 M번의 순차 구현 시도를 한다. 실패한 시도의 피드백은 부모를 바꾸지 않은 채 다음 프롬프트에 반영된다. 시도가 인컴번트를 개선하면 라운드가 끝나고 개선된 프로그램이 새 인컴번트가 되며, 같은 전략과 갱신된 부모로 다음 라운드가 시작된다. 개선이 없으면 다음 전략으로 넘어간다. 평가기는 과제별 점수 함수로 후보를 채점하고, 검색 메모리는 섬 기반 MAP-Elites로 프로그램 다양성을 유지하며 후보·평가 결과·제안 전략·시도 결과·실패 피드백을 저장한다. 남은 예산이 추가 LLM 호출을 감당하지 못하면 진화를 멈추고 최고 프로그램을 반환한다.
어떻게 쓰나
실험은 수학 최적화 5개, ADRS 벤치마크의 시스템 최적화 5개, ALE-Bench-Lite의 알고리즘 최적화 10개 등 총 20개 실제 최적화 과제에서 수행했다. 비교 대상은 OpenEvolve, ShinkaEvolve, AdaEvolve, EvoX이고, 수학 과제에서는 AlphaEvolve의 보고된 최신 결과도 함께 제시한다. 모델 구성은 두 가지다. 첫째, FrugalEvo는 전략 생성에 GPT-5.6 Terra, 코드 구현·개선에 GPT-5.6 Luna를 쓰고 베이스라인은 모두 GPT-5.6 Terra를 쓴다. 실행당 LLM 비용 예산은 수학 2달러, 시스템·알고리즘 1달러다. 둘째, FrugalEvo는 전략에 GLM-5.3, 구현·개선에 GLM-5.3 Flash를 쓰고 베이스라인은 GLM-5.3을 쓴다. 예산은 수학 1달러, 시스템 0.5달러다. 결과적으로 FrugalEvo는 두 구성 모두에서 수학 5개 과제 전부의 평균 BA-AUC가 가장 높았고, GPT 구성에서는 5개 모두, GLM 구성에서는 4개 과제에서 최고 또는 이에 준하는 평균 성능을 냈다. AlphaEvolve와 비교 가능한 4개 과제(Circle Packing, Heilbronn Convex (13), Heilbronn Triangle, Min-Max-3)에서 AlphaEvolve와 같거나 앞선다. 시스템 과제에서는 두 구성 모두 5개 과제 전부에서 최고 또는 이에 준하는 평균·최고 성능을 냈고, 4개 과제에서 평균 BA-AUC가 가장 높았다. ALE-Bench-Lite 10개 과제에서는 평균 점수 1924.9로 OpenEvolve(1887.5)와 AdaEvolve(1881.9)를 앞섰다. 모든 방법은 ALE-Agent가 만든 해법에서 출발해 비공개 점수로 평가했다.
전제와 한계
개별 해법 수치도 제시된다. Circle Packing에서 FrugalEvo는 초기 프로그램의 반지름 합 0.95976을 GPT-5.6 Terra와 Luna로 1.68달러에 2.635996까지, GLM-5.3과 Flash로 0.55달러에 2.635990까지 올렸다. 이는 평균 약 50달러를 쓰는 CORAL(2.635985)과 SwarmResearch(2.635996)에 필적하거나 앞선다. Signal Processing에서는 Savitzky–Golay, Butterworth, 스펙트럼 필터를 적응적으로 혼합해 0.78912를 달성했다. Heilbronn Convex (13)에서는 멀티스타트 힐 클라이밍, 선형계획법 개선, 볼록 껍질 면적 축소로 AlphaEvolve와 동등한 결과를 냈다. 시스템 과제 중 EPLB에서는 탐욕적 전문가 복제, 부하 인식 블록 할당, 쌍별 스왑 개선을 결합해 0.1473을, Transaction Scheduling에서는 멀티스타트 리그렛 기반 삽입, 국소 윈도 완전 재정렬, 트랜잭션 재배치로 4405.29를 기록했다. Signal Processing, Heilbronn Convex (13), Transaction Scheduling의 성능 대비 비용 곡선에서 FrugalEvo는 첫 0.2달러 안에 우위를 확보하고 이후에도 유지했다.
절제 실험은 모델 협업, 콜드 스타트, 코드 개선의 순차 피드백을 확인한다. 전략 탐색과 해법 생성을 같은 모델로 처리하면, 고비용 모델만 쓰든 저비용 모델만 쓰든 같은 예산에서 FrugalEvo보다 평균·최고 성능이 낮았다. 고비용 모델만 쓰면 구현 호출이 예산을 많이 잡아 탐색 여력이 줄어 평균 성능 하락이 더 컸고, 저비용 모델만 쓰면 특히 Signal Processing에서 최종 최고 점수가 낮아졌다. 콜드 스타트를 빼고 초기 프로그램을 바로 부모로 쓰면 두 과제 모두 평균·최고 성능이 떨어졌다. 코드 개선에서 순차 피드백을 제거하면 평균 성능이 낮아지고 실행 간 표준편차가 커졌다.
개발자 관점에서 이 논문은 LLM 에이전트로 코드를 자동 진화시키는 파이프라인을 운영할 때 모델 호출 비용을 1등 시민으로 다루라는 제안이다. 후보 프로그램을 자동 실행·채점할 수 있는 코드 기반 최적화에 적합하며, 강한 모델은 전략 탐색에, 저렴한 모델은 구현·개선에 배치하는 분업, 프롬프트 접두사 공유를 통한 캐시 재사용, 콜드 스타트로 초기 인컴번트 확보, 실패 피드백을 다음 시도에 반영하는 루프를 참고할 수 있다. 평가 지표로는 최종 점수만 보지 말고 BA-AUC처럼 예산 구간 전체의 품질을 보는 것이 좋다. 다만 저자들이 밝힌 전제와 한계가 있다. 이 설계는 해법 생성과 평가가 모두 코드 환경 안에서 이뤄져 후보를 자동 실행·채점할 수 있는 상황에 맞춰져 있다. 생물학처럼 습식 실험이 필요한 물리 세계 상호작용 도메인에는 쉽게 확장되지 않는다. 또한 효과적인 전략 탐색을 유도하는 지시문은 현재 계산 최적화 과제용으로 사람이 직접 설계한 것이며, 과제마다 자동으로 도출되지 않는다. 향후 과제로 물리 세계 상호작용이 필요한 도메인으로 확장하고 전략 탐색 지시문을 자동 생성하는 방법을 개발하는 것을 남겨 두었다.