더 많이 선택하지 말고, 더 똑똑하게 선택하세요: 서브모듈러 보장 기능을 갖춘 프롬프트 인식 평가 스케줄링

Select Smarter, Not More: Prompt-Aware Evaluation Scheduling with Submodular Guarantees

자동 프롬프트 최적화(APO)는 평가 신호의 품질에 크게 의존하지만, 모든 프롬프트 후보에 대해 전체 훈련 세트를 사용하여 평가하는 것은 비용이 너무 많이 듭니다. 기존 방법은 최적화가 시작되기 전에 단일 평가 집합을 고정하는 방식(원칙적이지만 프롬프트에 독립적) 또는 최적화 과정에서 휴리스틱하게 이를 조정하는 방식(유연하지만 불안정하며 공식적인 보장이 부족)을 사용합니다. 우리는 APO가 온라인 적응형 테스트 문제와 본질적으로 연결된다는 것을 관찰했습니다. 여기서 프롬프트는 응시생, 훈련 예제는 시험 항목이며, 스케줄러는 가장 강력한 후보들 간의 차이를 가장 잘 보여주는 항목을 선택해야 합니다. 이러한 통찰력은 프롬프트 인식 온라인 평가 스케줄링(POES)을 개발하는 데 영감을 주었습니다. POES는 IRT(Item Response Theory) 기반의 차별성 유틸리티, 시설 위치 커버리지 항, 그리고 전환 비용을 고려한 워밍업 스왑을 통합하여 단일 목표 함수로 구성됩니다. 이 목표 함수는 증명 가능한 단조 서브모듈러 함수이며, 콜드 스타트의 경우 (1-1/e)의 탐욕적 보장을 제공하고, 워밍업 업데이트의 경우 경계가 있는 드리프트를 제공합니다. 적응형 컨트롤러는 최적화 진행 상황에 따라 탐색-활용 균형을 조절합니다. 세 가지 벤치마크 패밀리에 속하는 36개의 작업에서 POES는 가장 우수한 평균 정확도를 달성했습니다(최고의 기준보다 6.2% 향상). 이는 동일한 평가 예산 하에서 미미한 토큰 오버헤드(약 4%)를 갖습니다. 또한, k=20개의 예제를 사용하여 원칙적으로 선택하는 방법은 k=30-50개의 예제를 무작정 사용하는 방법보다 성능이 같거나 우수하며, 토큰 소비를 35-60% 줄입니다. 이는 더 똑똑하게 선택하는 것이 더 많이 선택하는 것보다 효과적임을 보여줍니다. 우리의 결과는 평가 스케줄링이 APO의 핵심 구성 요소이며, 단순한 구현 세부 사항이 아니라는 것을 보여줍니다.

Automatic prompt optimization (APO) hinges on the quality of its evaluation signal, yet scoring every prompt candidate on the full training set is prohibitively expensive. Existing methods either fix a single evaluation subset before optimization begins (principled but prompt-agnostic) or adapt it heuristically during optimization (flexible but unstable and lacking formal guarantees). We observe that APO naturally maps to an online adaptive testing problem: prompts are examinees, training examples are test items, and the scheduler should select items that best discriminate among the strongest candidates. This insight motivates Prompt-Aware Online Evaluation Scheduling (POES), which integrates an IRT-based discrimination utility, a facility-location coverage term, and switching-cost-aware warm-start swaps into a unified objective that is provably monotone submodular, yielding a (1-1/e) greedy guarantee for cold starts and bounded drift for warm-start updates. An adaptive controller modulates the exploration-exploitation balance based on optimization progress. Across 36 tasks spanning three benchmark families, POES achieves the highest overall average accuracy (6.2 percent improvement over the best baseline) with negligible token overhead (approximately 4 percent) at the same evaluation budget. Moreover, principled selection at k = 20 examples matches or exceeds the performance of naive evaluation at k = 30-50, reducing token consumption by 35-60 percent, showing that selecting smarter is more effective than selecting more. Our results demonstrate that evaluation scheduling is a first-class component of APO, not an implementation detail.