🤖 AI

Exploit More, Explore Smarter for Budget-Constrained Agentic Search

이 논문은 확장을 정보 가치 결정으로 취급하는 판별적 보상 형성, 확률적 가상 자식 노드, 그리고 품질 조건부 분기를 통해 예산 제약이 있는 에이전트 탐색을 최적화함으로써, 표준 방식들과 비교하여 다양한 과업에서 일관된 성능 향상을 달성하는 새로운 트리 탐색 정책인 ExTS를 소개한다.

원저자: Haoyang Fang, Bernie Wang

게시일 2026-08-26

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Haoyang Fang, Bernie Wang

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

급변하는 인공지능의 세계에서, 단순히 질문에 답하는 것을 넘어 능동적으로 해결책을 찾아 나서는 새로운 형태의 시스템이 등장했습니다. 이러한 "에이전트형(agentic)" 시스템은 디지털 탐험가처럼 행동하며, 아이디어를 제안하고, 이를 테스트하며, 최선의 추측을 반복해서 정교하게 다듬습니다. 컴퓨터 코드를 작성하든, 화학 화합물을 설계하든, 혹은 복잡한 논리 퍼즐을 풀든, 이 에이전트들은 생성과 검증의 순환 과정에 의존합니다. 이들은 후보 솔루션을 생성하고, 그것이 얼마나 잘 작동하는지 확인하기 위해 테스트를 실행한 뒤, 그 피드백을 사용하여 더 나은 버전을 만듭니다. 하지만 이 과정은 비용이 많이 듭니다. 시스템이 새로운 아이디어를 생성하거나 테스트를 실행할 때마다, 제한된 자원인 계산 예산(computational budget)을 소비하기 때문입니다. 많은 실제 시나리오에서 이 예산은 매우 빠듯하여, 시스템이 멈추기 전까지 단 몇십 번 또는 몇백 번의 시도만을 허용합니다. 연구자들의 핵심 과제는 이 한정된 예산을 어떻게 현명하게 사용하는가 하는 점입니다. 만약 시스템이 막다른 길에 시도를 낭비한다면, 최선의 해결책을 찾는 데 실패하게 됩니다. 반대로 너무 신중하다면, 유망한 경로의 불과 몇 단계 뒤에 있을 돌파구를 놓칠 수도 있습니다.

수년 동안 이러한 탐색 트리(search trees)를 탐색하는 표준적인 방법은 게임 알고리즘에서 빌려온 전략으로, 이는 두 가지 상충하는 본능인 탐색(exploration)과 활용(exploitation) 사이의 균outs를 맞춥니다. 탐색은 새로운, 검증되지 않은 경로를 시도하여 가능성을 확인하는 것을 의미하며, 활용은 이미 좋은 결과를 보여준 경로를 더 깊게 파고드는 것을 의미합니다. 전통적인 방식은 모든 새로운 가지(branch)를 일정한 수준의 호기심으로 대하며, 종종 단 하나의 것에 전념하기 전에 사용 가능한 모든 옵션을 확장합니다. 이는 시간과 비용을 들여 모든 것을 탐색할 여유가 있을 때는 효과적입니다. 하지만 고도의 이해관계가 걸려 있고 예산이 제한된 현대 AI 에이전트의 세계에서, 이러한 "모두 시도해 보는" 방식은 종종 실패합니다. 이 방식은 제한된 자원을 넓고 얕은 트리에 너무 얇게 분산시켜, 가장 유망한 아이디어들이 충분히 발전하지 못하게 만듭니다. 결국 시스템은 몇 가지 탁월한 해결책에 대한 깊은 이해 대신, 수많은 평범한 솔루션들에 대한 넓은 지도만을 갖게 됩니다.

이를 해결하기 위해, 아마존 AGI(Amazon AGI)의 연구진은 ExTS라는 새로운 탐색 정책을 도입했습니다. 모든 가지를 맹목적으로 확장하는 대신, 이 새로운 방법은 새로운 가지를 만드는 결정을 계산된 투자로 취급합니다. 이 방식은 어떤 예산을 쓰기 전에 다음과 같은 결정적인 질문을 던집니다. "새로운 경로를 만드는 데 드는 비용만큼 잠재적 가치가 있는가?" 시스템은 자신의 성공과 실패의 이력을 살펴봄으로써 이를 수행합니다. 특정 추론 방식이 많은 실패를 낳았다면, 시스템은 해당 경로의 확장을 멈추고 이미 작동하고 있는 경로를 심화시키는 데 에너지를 집중하도록 학습합니다. 이는 노이즈를 효과적으로 걸러내어, 기존 시스템에서 귀중한 자원을 소모했을 법한 막다른 길들을 무시합니다.

연구진은 이 접근 방식을 언어 모델을 위한 지시문 최적화, 컴퓨터 코드 생성, 스펙트럼 데이터를 통한 분자 구조 추론, 그리고 자동화된 워크플로우 설계라는 네 가지 매우 다른 분야에서 테스트했습니다. 각 경우에 연구진은 이전 방식들이 작업해야 했던 것과 동일한 타이트한 예산을 새 시스템에 부여했습니다. 결과는 일관적이었습니다. 더 똑똑하게 예산을 집행함으로써, 새 시스템은 각 특정 작업에 맞춰 설계된 전문적인 방법들보다 일관되게 더 나은 해결책을 찾아냈습니다. 예를 들어, 질의응답을 위한 프롬프트 최적화 작업에서, 이 새로운 방법은 기존의 최고 방식보다 정확도를 10% 이상 향상시켰습니다. 코드 생성에서는 훨씬 더 어려운 문제들을 해결하며 기존 방식들이 놓쳤던 솔루션들을 찾아냈습니다. 스펙트럼 서명으로부터 분자의 형태를 파악해야 하는 매우 기술적인 분야인 분자 구조 규명에서도, 새 방법은 동일한 횟수의 시도로 더 높은 정확도를 달ей했습니다.

이러한 성공 뒤에 숨겨진 핵심 통찰은, 새 시스템이 단일 시도의 점수만을 보는 것이 아니라 점수의 패턴을 본다는 점입니다. 이러한 많은 작업에서 좋은 솔루션과 훌륭한 솔루션 사이의 차이는 미묘하며, 점수들이 매우 밀접하게 모여 있을 수 있습니다. 기존 방식들은 이 차이를 구별하는 데 어려움을 겪으며 모든 옵션을 거의 동등하게 취급했습니다. 새 시스템은 이러한 작은 차이를 증폭시키는 기술을 사용하여, 약간 더 나은 경로와 진정으로 탁월한 경로를 구별해 냅니다. 또한, 새로운 가지를 만든다면 어떤 일이 벌어질지 시뮬레이션하기 위해 "가상 자녀(virtual child)" 개념을 사용합니다. 과거에 무엇이 효과적이었는지에 대한 샘냥플링을 통해, 실제로 예산을 들여 구축하지 않고도 새로운 경로의 가치를 추정할 수 있습니다. 만약 시뮬레이션이 새로운 경로가 결실을 맺을 가능성이 낮다고 판단하면, 시스템은 그 경로를 건너뛰고 입증된 경로로 더 깊이 들어갑니다.

또한 연구진은 모든 탐색 문제가 동일하지 않다는 것을 발견했습니다. 어떤 작업은 대부분의 시도가 오류로 이어지는 빈번한 실패를 겪는 반면, 어떤 작업은 더 안정적입니다. 어떤 작업은 새로운 발견이 이루어짐에 따라 점수가 급격히 변하는 반면, 어떤 작업은 일정하게 유지됩니다. 새 시스템은 이러한 다양한 환경에 적응할 수 있을 만큼 유연합니다. 문제의 본질을 이해하기 위한 작은 예비 테스트를 실행함으로써, 시스템은 특정 과제의 도전 과제에 맞춰 전략을 약간 조정할 수 있습니다. 이러한 적응성은 시스템이 각 작업을 위한 완전히 새로운 설계 없이도 광범위한 영역에서 잘 작동할 수 있게 합니다.

이 연구는 AI 에이전트가 계산 예산을 어떻게 사용하는지가 그 에이전트가 가진 지능만큼이나 중요하다는 것을 보여줍니다. 탐색 과정을 더 선택적이고 자신의 진척도에 대해 더 잘 인식하도록 재설계함으로써, 시스템은 동일한 노력으로 훨씬 더 나은 결과를 얻을 수 있습니다. 이 접근 방식은 끝없는 컴퓨팅 파워를 요구하지 않고도 복잡한 문제를 해결할 수 있는 더 효율적인 AI 에이전트를 구축하기 위한 실질적인 가이드를 제공합니다. 이 결과는 미래의 가장 효과적인 AI 시스템은 반드시 가장 많은 것을 시도하는 시스템이 아니라, 무엇을 시도할 가치가 있는지 정확히 아는 시스템이 될 것임을 시사합니다.

기술 요약: 예산 제약이 있는 에이전트 탐색을 위한 더 많은 착취(Exploit)와 더 스마트한 탐색(Explore)

문제 정의

본 논문은 예산 제약이 있는 에이전트 탐색(budget-constrained agentic search), 즉 LLM 에이전트가 엄격한 평가 예산 하에서 후보군(예: 프롬프트, 코드, 분자 구조)을 반복적으로 제안하고 정교화해야 하는 환경을 다룹니다. 이러한 시나리오에서는 검증 비용이 비싸거나, 생성을 위해 여러 번의 모델 호출이 필요하거나, 혹은 두 가지 모두에 해당합니다. 총 예산은 흔히 수십 회 또는 수백 회의 호출로 제한됩니다.

저자들은 표준 몬테카를로 트리 탐색(MCTS), 특히 UCT(Upper Confidence Bound applied to Trees) 정책이 다음과 같은 세 가지 구조적 한계로 인해 이 체제에서 성능이 저하된다는 점을 지적합니다:

탐색 보너스의 지배력(Exploration-bonus dominance): 방문 횟수가 적을 때 탐색 항이 지배적이 되어, 알고리즘이 유망하지 않은 노드를 유망한 노드만큼 매력적인 것으로 취급하게 만듭니다.
강제적 전체 확장(Forced full expansion): 표준 MCTS는 유망한 체인을 심화시키기 전에 모든 형제 노드를 강제로 확장하게 하여, 유망하지 않은 브랜치에 예산을 낭비하게 합니다.
³ 점수 불가지론적 브랜칭(Score-agnostic branching): 확장 결정이 노드의 품질과 독립적입니다. 알고리즘은 노드의 점수가 비용을 정당화하는지에 따라 브랜칭을 차단(gate)하지 않습니다.

기존 솔루션들은 대개 "하네스(harness)"(탐색을 감싸는 프레임워크)에 집중하거나 특정 작업 유형을 겨냥한 맞춤형 알고리즘(예: 코드를 위한 톰슨 샘플링, 프롬프트를 위한 파레토 최적 선택)을 목표로 하며, 다양한 에이전트 문제에 적응할 수 있는 통합된 정책이 부족합니다.

방법론: ExTS

저자들은 노드 선택과 확장 결정을 공동으로 재설계하는 트리 탐색 정책인 ExTS(Exploit More, Explore Smarter)를 소개합니다. ExTS는 확장을 정보의 가치(Value-of-Information, VOI) 결정으로 취급하며, 세 가지 핵심 메커니즘을 통해 작동합니다.

1. 차별적 보상 형성 (Discriminative Reward Shaping)

원시 검증 점수가 좁은 범위에 밀집되어 노드들이 동일하게 매력적으로 보이는 문제를 해결하기 위해, ExTS는 비선형 형성 함수 $\phi$ 를 적용합니다.

메커니즘: 온도 조절 기능이 있는 볼록 함수 $\phi(r) = \frac{e^{\hat{r}/T} - 1}{e^{1/T} - 1}$ ( $T < 1$ )를 사용하여 낮은 점수는 압축하고 높은 점수는 증폭합니다.
성공률 가중치: 서브트리가 주로 유효하지 않은 출력(실패)을 생성하는 노드를 할인하기 위해 성공률 가중치 $(n^+_v / n_v)^\alpha$ 를 포함합니다.
결과: 이를 통해 점수가 밀집된 상황에서도 효과적인 선택 신호를 생성하여, 알고리즘이 후보군을 구별할 수 있게 합니다.

2. 가상 자식(Virtual Child)을 통한 VOI 추정

ExTS는 확장을 기존 체인을 심화시키는 것과 새로운 브랜치를 만드는 것 사이의 결정으로 재정의합니다.

메커니즘: 임의의 내부 노드에서 ExTS는 가상 자식(virtual child) 점수를 계산합니다. 이 가상 자식은 새로운 브랜치를 생성할 때의 기대 가치를 나타냅니다.
샘플링: 가상 자식의 점수는 부모의 보상 이력(부모 자신의 점수 포함)에서 $k$ 개의 점수를 샘플링하고 형성 함수를 적용하여 추정합니다. 샘플 수 $k$ 는 유한 샘플의 불확실성을 포착하기 위해 "공정 공유(fair-share)" 방문 횟수에 비례합니다.
결정: 알고리즘은 가장 좋은 실제 자식의 점수와 가상 자식의 점수를 비교합니다. 만약 가상 자식의 점수가 더 높다면, 알고리즘은 현재 노드를 확장(새로운 브랜치 생성)하기 위해 선택하며, 그렇지 않으면 가장 좋은 실제 자식으로 재귀합니다. 이를 통해 유망하지 않은 형제들을 완전히 확장하기 전에 유망한 체인을 심화할 수 있습니다.

3. 품질 조건부 브랜칭 (Quality-Conditioned Branching)

ExTS는 예산 낭비를 방지하기 위해 노드 품질에 따라 확장을 제한합니다.

확장 게이트(Expansion Gate): 루트가 아닌 노드는 검증 점수가 전체 모집단 점수의 $\tau$ -분위수를 초과하는 경우에만 확장이 허용됩니다. 임계값 미만의 노드는 여전히 방문 및 업데이트될 수는 있지만 새로운 자식을 생성할 수는 없습니다.
품질 기반 점진적 확장(Quality-Gated Progressive Widening): 최대 브랜칭 팩터는 방문 횟수가 증가함에 따라(점진적 확장) 성장하지만, 이는 비용을 정당화할 만큼의 품질(즉, 더 높은 분위수 $\gamma$ 이상)을 가진 노드에 대해서만 이루어집니다. 낮은 점수의 노드는 작은 초기 브랜칭 팩터 $M_0$ 로 제한됩니다.

주요 기여

통합된 정책: ExTS는 프롬프트 최적화, 코드 생성, 분자 구조 규명, 에이전트 워크플로우 최적화라는 네 가지 다양한 도메인에서 특정 작업별 베이스라인과 경쟁하거나 이를 능가하는 단일 고정 구성을 제공합니다.
구조적 재설계: 단순히 탐색 상수를 조정하는 기존 연구와 달리, ExTS는 '어디서' 그리고 '언제' 확장할지를 결정하기 위해 가상 자식, 품질 게이팅과 같은 구조적 메커니즘을 도입합니다.
파일럿 실행 진단(Pilot-Run Diagnostics): 저자들은 작업의 탐색 지형을 특징짓는 네 가지 진단 지표( $\hat{\sigma}_A$ , $\hat{\sigma}_f$ , $\kappa$ , $\rho$ )를 도입했습니다. 이 지표들은 왜 서로 다른 작업이 서로 다른 구성에 반응하는지를 설명하며, 하이퍼파라미터(예: 저변동 작업에 대한 온도 $T$ 조정 또는 고실패 작업에 대한 성공 지수 $\alpha$ 조정)를 적응시키기 위한 실질적인 가이드를 제공합니다.

결과

ExTS는 단일 고정 구성과 파일럿 진단을 바탕으로 1~2개의 하이퍼파라미터를 조정한 버전( $ExTS^*$ )을 사용하여 네 가지 도메인에서 평가되었습니다.

프롬프트 최적화 (HotpotQA, HoVeR): ExTS는 HotpotQA에서 GEPA 파레토 베이스라인 대비 +10.8% 향상된 성능(6.4배 낮은 분산)을 보였으며, HoVeR에서도 대등한 성능을 보였습니다. 적응형 $ExTS^*$ 는 HotpotQA 성능을 **66.00%**까지 끌어올렸습니다.
코드 생성 (LiveCodeBench): "Hard" 스플릿에서 ExTS는 19.1%의 pass@1을 달성하여 AB-MCTS-A(17.1%)와 표준 MCTS(18.1%)를 능가했습니다. 고정 구성은 전체 pass@1에서 46.2%를 달성했으며, 적응형 버전( $ExTS^*$ )은 47.4%에 도달했습니다.
분자 구조 규명 (K-MSE): ExTS는 정확도(exact-match accuracy) 측면에서 K-MSE 베이스라인(89.8%)보다 +1.3% 향상된 성능(91.0%)을 보였습니다.
에이전트 워크플로우 최적화 (DROP): ExTS는 CoT 및 AFlow 베이스라인과 비교하여 평균 정확도 90.96%(최저 분산 및 비용)를 기록하며 파레토 우위를 점했습니다. 적응형 버전( $ExTS^*$ )은 평균 정확도를 **91.54%**로 더욱 개선했습니다.
예산 스케일링: ExTS는 특히 반복적인 정교화가 중요한 어려운 인스턴스에서 더 효율적인 예산 대비 성능 전환을 보여줍니다. ExTS는 낮은 예산(예: $B \approx 8$ )에서 표준 MCTS를 앞지르며, 예산이 증가함에 따라 격차를 계속 벌려 나갑니다.

의의 및 주장

본 논문은 ExTS가 탐색 상수를 튜닝하는 것에서 정책의 구조적 재설계로의 전환을 나타낸다고 주장합니다. 저자들은 예산 제약이 있는 체제에서는 확장을 할지 여부를 결정하는 것이 어느 자식을 방문할지 결정하는 것만큼이나 중요하다고 주장합니다.

일반성: 단일 고정 구성이 구조적으로 다른 도메인 전반에서 작동한다는 것은, 보상 형성, 가상 자식 추정, 품질 게이팅 메커니즘이 MCTS의 근본적인 한계를 해결함을 시사합니다.
적응성: 파일럿 실행 진단은 에이전트 탐색 문제의 "형태"를 이해하기 위한 실용적인 프레임워크를 제공하며, 왜 단일 구성이 보편적으로 지배적이지 않은지를 설명하고 경량화된 적응 경로를 제시합니다.
효율성: 품질에 따라 확장을 게이팅하고 이를 VOI 결정으로 프레이밍함으로써, ExTS는 예산을 너비 우선 탐색에서 선택적 정교화로 재지정하여 동일하거나 더 낮은 계산 비용으로 우수한 성능을 달성합니다.

저자들은 API 비용으로 인한 도메인당 단일 모델 사용의 한계와, 파일럿 진단이 고유한 도메인 특성이 아닌 특정 구성에 의해 관찰된 지형을 설명한다는 점을 한계로 언급했습니다. 그러나 그들은 적응형 방식 없이도 고정된 ExTS가 전문화된 베이스라인들을 능가하거나 대등한 성능을 낸다는 것을 입증했습니다.