기술 요약: 비용 보정된 프런티어 효용을 통한 예산 인식형 LLM 발견 (Budget-Aware LLM Discovery via Cost-Calibrated Frontier Utility)

문제 정식화

대규모 언어 모델(LLM)은 추론 시점 탐색(inference-time search)을 통해 후보 솔루션을 순차적으로 생성, 평가 및 정제하는 과학적 및 알고리즘적 발견 분야에 점점 더 많이 채택되고 있습니다. 수학적 최적화, 알고리즘 설계, 실행 가능한 프로그램 발견과 같은 도메인에서는 결정론적 평가자가 반복 가능한 품질 신호를 제공합니다. 그러나 기존의 적응형 발견 컨트롤러는 일반적으로 탐색 액션의 이질적인 비용을 무시하고 오직 점수 진전(score progress)에만 기반하여 액션에 대한 크레딧을 할당합니다.

토큰 기반 API 가격 책정 체제 하에서, 서로 다른 탐색 액션은 매우 다양한 비용을 발생시킵니다. 짧은 정제(refinement)는 한 번의 참조 생성 비용이 들 수 있는 반면, 긴 컨텍스트 가이드 호출이나 유효하지 않은 코드의 재시도는 6배 이상의 비용이 들 수 있습니다. 컨트롤러가 동일한 점수 향상을 가져온 고비용 액션과 저비용 액션에 동일한 크레딧을 부여한다면, 이는 남은 예산의 기회비용을 고려하지 못하는 것입니다. 본 논문은 이를 실행 가능한 후보들의 이산 공간에 대한 인구 집단 수준의 할당 문제로 정식화하며, 여기서 유효한 탐색 지평(search horizon)은 고정된 반복 횟수가 아니라 누적된 실현 토큰 예산에 의해 정의됩니다.

저자들은 (명제 1) 액션 비용이 이질적인 사례에서, 점수 이력에만 의존하고 실현된 비용에는 의존하지 않는 "비용 무관(cost-blind)" 컨트롤러는 검색 프런티어와 비용 격차가 증가함에 따라 최적의 예산 목적 함수의 극히 미미한 부분만을 달성할 수 있음을 증명합니다.

방법론: CostAda

이러한 간극을 메우기 위해, 저자들은 명시적인 탐색 측면 토큰 예산 하에서의 LLM 발견을 위해 설계된 비용 보정 적응형 컨트롤러인 CostAda를 소개합니다. CostAda는 진행 상황만을 고려하는 크레딧 대신, 로컬 프런티어 진전, 글로벌 최고 기록(global best-so-far) 개선, 실현된 액션 비용, 그리고 남은 예산을 통합한 **비용 보정된 프런티어 효용(cost-calibrated frontier utility)**을 도입합니다.

핵심 메커니즘은 세 가지 결합된 제어를 통해 작동합니다:

1. 비용 보정된 프런티어 효용 (Cost-Calibrated Frontier Utility):
   반복 $t$에서의 프런티어 $k$에 대한 효용 $u_t^{(k)}$는 다음과 같이 정의됩니다:
   $$u_t^{(k)} = \frac{\lambda_t g_t + (1 - \lambda_t) \delta_t^{(k)}}{d_t}$$
   여기서:

   • $g_t$는 글로벌 이득(글로벌 최고 기록 대비 개선량)입니다.
   • $\delta_t^{(k)}$는 로컬 이득(프런티어의 로컬 아카이브 대비 개선량)입니다.
   • $\lambda_t = 1 - \rho_t$는 글로벌 가중치이며, 남은 예산 비율 $\rho_t$에 따라 조건화됩니다. 예산이 소진됨에 따라 컨트롤러는 로컬 개발에서 글로벌 개선으로 초점을 전환합니다.
   • $d_t = 1 + \lambda_t^c \phi_t$는 정규화된 실현 단계 비용에 기반한 비용 분모입니다. 이는 동일한 이득을 낸 비싼 액션이 저렴한 액션보다 적은 크레딧을 받도록 보장합니다.

2. 예산 인식형 제어 결정 (Budget-Aware Control Decisions):

   • 로컬 탐색 강도 (Local Exploration Intensity): 프런티어 주변의 샘플링 너비는 평활화된 효용에 따라 조정됩니다. 높은 효용은 낮은 강도의 정제로 이어지고, 낮은 효용은 더 넓은 탐색을 유발합니다. 결정적으로, 남은 예산 비율 $\rho_t$는 예산이 고갈됨에 따라 값비싼 탐색을 억제합니다.
   • 프런티어 할당 (Frontier Allocation): 컨트롤러는 실현된 비용당 글로벌 이득($r_t^{(k)} = g_t / d_t$)을 기준으로 미래 예산을 할당합니다. 약한 로컬 아카이브에 대해서만 개선을 보이는 프런티어는 할당 크레딧을 받지 못합니다. 상한 신뢰 구간(upper-confidence bound) 규칙은 고성능 프런티어의 활용(exploitation)과 샘플링이 부족한 프런티어의 탐색(exploration) 사이의 균형을 맞추며, 이는 남은 예산에 의해 게이트(gate)됩니다.
   • 예산 기반 전술 개입 (Budgeted Tactic Intervention): 상위 수준의 가이드(예: "guide" 또는 "tactic" 호출)는 특정 증거 술어(evidence predicates)가 충족될 때만 구매됩니다: (1) 남은 예산이 가이드와 테스트를 위한 예비비를 모두 감당할 수 있고, (2) 지속적인 글로벌 진전 부재(정체) 또는 누적된 저수율 지출이 있으며, (3) 통합 윈도우(consolidation window)가 활성화되지 않은 경우입니다. 이는 지평 근처에서 엄격히 필요한 경우가 아니면 값비싼 개입을 방지합니다.

주요 기여

1. 문제 정식화 및 이론적 경계: 본 논문은 명시적인 탐색 측면 토큰 예산 하에서의 LLM 발견을 정식화하고, 비용 불균형 설정에서 비용 무관 크레딧 전략이 예산 목적 함수를 포기한다는 것을 증명합니다.
2. 비용 보정된 프런티어 효용: 저자들은 진행 상황을 실현된 액션 비용 및 남은 예산에 조건화하는 크레딧 원칙을 도입하여, 각 액션의 기회비용이 명시적으로 고려되도록 합니다.
3. CostAda 컨트롤러: 이 원칙의 구체화로서, 예산 기반의 로컬 탐색, 비용 인식형 프런티어 할당, 예산 기반 전술 개입을 조정합니다.
4. 실험적 검증: CostAda가 최신 베이스라인들에 비해 우수한 예산 효율성과 최종 솔루션 품질을 달者함을 보여주는 광범위한 실험을 수행했습니다.

실험 결과

저자들은 8개의 벤치마크(기하학적 패킹, 극한 기하학, 가법 조합론, 실행 가능한 프로그램 최적화 포함)에 대해 두 가지 백본 모델인 GLM-5와 GPT-5.4를 사용하여 CostAda를 AdaEvolve(진행 상황 인식 베이스라인) 및 EvoX(전략 진화 컨트롤러)와 비교 평가했습니다.

• 효율성: CostAda는 16개의 벤치마크-백본 쌍 중 12개에서 가장 강력한 베이스라인의 전체 예산 품질에 도달하는 데 최대 절반의 예산만을 사용했습니다.
• 최종 품질: 두 백본 모두에서 CostAda는 8개 벤치마크 전체에서 가장 강력한 평균 최종 품질을 달성했습니다.
• 예산 경로: 예산의 4분의 1 시점에서 CostAda의 평균 정규화 점수는 가장 강력한 베이스라인의 전체 예산 평균을 상회합니다. 또한 16개 벤치마크-백본 쌍 중 15개에서 가장 높은 정규화 AUC(Area Under the Curve)를 달성했습니다.
• 안정성: CostAda는 특히 GLM-5를 사용한 Circle Packing Rect와 같은 벤치마크에서 베이스라인에 비해 낮은 결과 분산을 보여줍니다.

의의 및 주장

본 논문은 CostAda가 LLM 기반 발견에서 자원이 관리되는 방식을 근본적으로 변화시킨다고 주장합니다. 실현된 비용과 남은 예산을 사후 회계 변수나 단순한 중단 규칙이 아닌 능동적인 제어 입력으로 취급함으로써, CostAda는 탐색 전략을 토큰 기반 가격 책정의 경제적 현실에 정렬시킵니다.

저자들은 이 접근 방식이 최종 솔루션 품질을 유지하면서 예산 효율성을 크게 향 만큼한다고 주장합니다. 결과는 비용 보정이 LLM 발견을 확장하는 데 필수적임을 시사하는데, 이는 비용의 이질성을 무시하면 단순히 진행 신호를 매끄럽게 하는 것만으로는 회복할 수 없는 하위 최적의 자원 할당으로 이어지기 때문입니다. 이 연구는 "비용"이 액션이 만들어내는 "이득"만큼이나 가변적일 때, 컨트롤러가 탐색과 활용 사이의 트레이드오프를 효과적으로 항해할 수 있음을 입증합니다.