비용 인지형 LLM 탐색: 비용에 맞춰 조정된 프론티어 유틸리티를 통한 방법

Budget-Aware LLM Discovery via Cost-Calibrated Frontier Utility

최근 대규모 언어 모델(LLM)은 추론 과정에서 평가된 후보들을 검색하여 과학 및 알고리즘 연구를 지원하는 데 점점 더 많이 활용되고 있습니다. 기존의 적응형 탐색 제어기는 점수 개선만으로 가치를 부여하지만, 프롬프트 길이, 재시도 횟수, 그리고 안내 호출 등의 요소들이 검색 행동에 미치는 토큰 비용이 서로 다르다는 사실을 고려하지 않습니다. 우리는 비용을 무시한 가치 평가가 프론티어가 증가하고 비용 차이가 커질수록 달성 가능한 품질의 대부분을 손실하게 만들 수 있음을 증명합니다. 고정된 검색 측면의 토큰 예산을 고려할 때, 제어기는 어떤 프론티어가 개선되고 있는지, 그리고 그 이점이 실제로 발생하는 비용보다 얼마나 큰지 판단하여 예산이 소진되기 전에 결정을 내려야 합니다. 본 논문에서는 *비용에 맞춰 조정된 프론티어 유틸리티*를 기반으로 하는 새로운 적응형 제어기인 **CostAda**를 소개합니다. CostAda는 프론티어의 진행 상황을 실제 행동 비용과 비교하여 가치를 평가하고, 남은 예산에 따라 해당 가치에 대한 보상을 조정합니다. CostAda는 이 신호를 사용하여 로컬 탐색 강도, 프론티어 할당 및 예산 내에서의 전술적 개입을 제어합니다. 따라서 비용과 남은 예산은 단순히 회계 변수 또는 종료 규칙으로만 작용하는 것이 아니라, 검색 프로세스 자체에 영향을 미칩니다. 실험 결과, CostAda는 16개의 벤치마크-백본 쌍 중 12개에서 최대 절반의 예산만 사용했을 때 최적의 기준 성능을 달성했으며, GLM-5 및 GPT-5.4 환경에서 모든 8개의 벤치마크에서 가장 높은 평균 최종 품질을 달성했습니다.

Large language models increasingly support scientific and algorithmic discovery through inference-time search over evaluated candidates. Existing adaptive discovery controllers assign credit based only on score progress, even though prompt length, retries, and guidance calls cause search actions to incur different token costs. We prove that cost-blind credit can forfeit all but a vanishing fraction of attainable quality as frontiers multiply and costs diverge. Under a fixed search-side token budget, the controller must decide which frontier is improving and whether its gain justifies the realized cost before the budget is exhausted. We introduce \textbf{CostAda}, a cost-calibrated adaptive controller built around \emph{cost-calibrated frontier utility}. The utility values frontier progress relative to realized action cost and conditions that credit on the remaining budget. CostAda uses this signal to control local exploration intensity, frontier allocation, and budgeted tactic intervention. Cost and remaining budget therefore shape the search rather than serving only as accounting variables or a stopping rule. CostAda reaches the strongest baseline's full-budget quality with at most half the budget on twelve of sixteen benchmark--backbone pairs while achieving the strongest mean final quality on all eight benchmarks under GLM-5 and GPT-5.4.