Agent-UCT: 트리 기반 에이전트 워크플로우 최적화를 위한 비용 인지형 상한 신뢰 구간 활용

Agent-UCT: Upper Confidence Bounds Applied to Trees for Agentic Workflow Optimization with Cost-Awareness

검색 증강 생성(RAG) 파이프라인과 같은 에이전트 기반 워크플로우를 최적화하려면 제한된 평가 예산 하에서 이산적인 구성 요소 선택에 대한 조합 공간을 탐색해야 합니다. 기존의 휴리스틱 검색, 블랙박스 최적화 및 표준 트리 검색 방법은 이러한 워크플로우의 구조적 특성을 명시적으로 활용하지 못하여 불필요한 계산과 비효율적인 예산 할당으로 이어집니다. 본 논문에서는 Agent-UCT(Agent-based Cost-Aware Upper Confidence Bounds Applied to Trees)라는 트리 검색 알고리즘을 제안합니다. Agent-UCT는 UCT를 확장하며, 양방향 접두사 재사용 그래프에서 파생된 재사용 인지 정규화 항을 활용하여 선택 편향을 부여합니다. 이를 통해 불필요한 실행을 줄이면서 효과적인 탐색을 유지합니다. 본 연구에서는 RAGSpace라는 프레임워크를 개발하여 LongRAG, LightRAG 및 Self-RAG에서 제공하는 다양한 RAG 구성 요소를 5차원 구성 공간으로 통합하고 체계적인 교차 프레임워크 조합을 가능하게 합니다. 또한 WTB(Workflow Test Bench)는 결정적 재현성, 콘텐츠 주소 지정 캐싱 및 트랜잭션 일관성을 제공하여 중간 상태가 한 번만 생성되고 검색 과정에서 재사용되도록 보장합니다. HotpotQA 및 UltraDomain에 대한 실험 결과, Agent-UCT는 평가된 고정 프레임워크 설정 중에서 가장 높은 외부 샘플 성능을 보이는 구성을 식별했습니다. 전체 풀 평가 시, 양방향 접두사 재사용은 접두사 공유를 사용하지 않는 경우의 상한 값보다 논리적 검색 비용을 73.6% 절감했습니다. 또한 전체 풀 평가와 비교하여 샘플링 기반 평가는 4.2배 빠른 속도를 달성했습니다. Agent-UCT, RAGSpace 및 WTB는 함께 비용 인지형, 재현 가능하고 구조적으로 효율적인 에이전트 워크플로우 최적화를 위한 통합 프레임워크를 제공합니다.

Optimizing agentic workflows, such as retrieval-augmented generation (RAG) pipelines, requires navigating a combinatorial space of discrete component choices under tight evaluation budgets. Existing approaches - heuristic search, black-box optimization, and standard tree search methods - do not explicitly exploit the compositional structure of these workflows, leading to redundant computation and inefficient budget allocation. We introduce Agent-UCT (Agent-based Cost-Aware Upper Confidence Bounds Applied to Trees), a tree search algorithm that extends UCT with a reuse-aware regularization term derived from a bipartite prefix reuse graph. Agent-UCT biases selection toward branches that leverage previously materialized configuration prefixes, reducing redundant execution while maintaining effective exploration. Our framework, RAGSpace, unifies heterogeneous RAG components from LongRAG, LightRAG, and Self-RAG into a five-dimensional configuration space, enabling systematic cross-framework recombination. WTB (Workflow Test Bench) provides deterministic replay, content-addressable caching, and transactional consistency, ensuring that intermediate states are materialized once and reused across the search. Experiments on HotpotQA and UltraDomain demonstrate that Agent-UCT identifies configurations with the highest out-of-sample performance among the evaluated fixed framework presets. Under full-pool evaluation, bipartite prefix reuse reduces logical search cost by 73.6% relative to the no-prefix-sharing cost upper bound. Compared with full-pool evaluation, sampling-based evaluation further achieves a 4.2x wall-clock speedup. Agent-UCT, RAGSpace, and WTB together provide a unified framework for cost-aware, reproducible, and compositionally efficient agentic workflow optimization.