덜 소비하고, 더 나은 판단: LLM 에이전트를 위한 예산 기반 가치 트리 탐색

Spend Less, Reason Better: Budget-Aware Value Tree Search for LLM Agents

테스트 시간 스케일링은 LLM 에이전트의 신뢰성을 향상시키는 주요 패러다임이 되었지만, 현재의 접근 방식은 컴퓨팅 자원을 풍부한 것으로 간주하여 에이전트가 토큰 및 도구 예산을 불필요한 단계 또는 잘못된 경로에 낭비하도록 허용합니다. 기존의 예산 기반 방법은 비용이 많이 드는 파인튜닝을 필요로 하거나, 세분화되지 않은 경로 수준의 휴리스틱에 의존하여 실행 중에 개입할 수 없습니다. 본 연구에서는 훈련이 필요 없는 추론 시간 프레임워크인 예산 기반 가치 트리(BAVT)를 제안합니다. BAVT는 멀티홉 추론을 단일 LLM 백본 내에서 단계 수준의 가치 추정을 통해 안내되는 동적 탐색 트리로 모델링합니다. 또 다른 핵심 혁신은 남은 자원 비율을 노드 값에 대한 자연스러운 스케일링 지수로 사용하는 예산 조건부 노드 선택 메커니즘입니다. 이를 통해 예산이 소진됨에 따라 체계적이고 파라미터가 없는 방식으로 광범위한 탐색에서 탐욕적인 활용으로의 전환이 가능합니다. LLM의 잘 알려진 과신 문제를 해결하기 위해 BAVT는 절대적인 상태 품질이 아닌 상대적인 진행 상황을 평가하는 잔여 가치 예측기를 사용하여 불필요하거나 중복된 도구 호출을 안정적으로 제거합니다. 또한, BAVT는 명시적인 유한 예산 제한 하에서 BAVT가 확률적으로 최소 $1-ε$의 확률로 최종 답변에 도달한다는 이론적 수렴 보장을 제공합니다. 두 가지 모델 패밀리에 걸쳐 네 가지 멀티홉 QA 벤치마크에 대한 광범위한 평가 결과, BAVT는 항상 병렬 샘플링 기준보다 우수한 성능을 보였습니다. 특히, BAVT는 엄격한 저예산 제약 조건 하에서 $4 imes$의 자원 할당량을 가진 기준 성능을 능가하여, 지능적인 예산 관리가 무차별적인 컴퓨팅 스케일링보다 근본적으로 우수하다는 것을 입증했습니다.

Test-time scaling has become a dominant paradigm for improving LLM agent reliability, yet current approaches treat compute as an abundant resource, allowing agents to exhaust token and tool budgets on redundant steps or dead-end trajectories. Existing budget-aware methods either require expensive fine-tuning or rely on coarse, trajectory-level heuristics that cannot intervene mid-execution. We propose the Budget-Aware Value Tree (BAVT), a training-free inference-time framework that models multi-hop reasoning as a dynamic search tree guided by step-level value estimation within a single LLM backbone. Another key innovation is a budget-conditioned node selection mechanism that uses the remaining resource ratio as a natural scaling exponent over node values, providing a principled, parameter-free transition from broad exploration to greedy exploitation as the budget depletes. To combat the well-known overconfidence of LLM self-evaluation, BAVT employs a residual value predictor that scores relative progress rather than absolute state quality, enabling reliable pruning of uninformative or redundant tool calls. We further provide a theoretical convergence guarantee, proving that BAVT reaches a terminal answer with probability at least $1-ε$ under an explicit finite budget bound. Extensive evaluations on four multi-hop QA benchmarks across two model families demonstrate that BAVT consistently outperforms parallel sampling baselines. Most notably, BAVT under strict low-budget constraints surpasses baseline performance at $4\times$ the resource allocation, establishing that intelligent budget management fundamentally outperforms brute-force compute scaling.