적게 쓰고 더 잘 추론하기: LLM 에이전트를 위한 예산 인식 가치 트리 탐색

LLM 에이전트가 복잡한 문제를 풀 때 무의미하게 연산 자원을 낭비하는 문제를 해결한다. 추가 학습 없이도 남은 예산에 맞춰 탐색 전략을 실시간으로 조정하여 효율성을 극대화하며, 이는 실제 서비스 운영 비용 절감과 직결된다.

기존의 LLM 에이전트는 복잡한 문제를 풀 때 여러 경로를 동시에 시도하는 Parallel Sampling 방식을 주로 사용한다. 하지만 이 방식은 각 경로가 독립적으로 진행되므로, 이미 막다른 길에 들어섰거나 중복된 정보를 찾는 경로에도 동일한 연산 자원을 끝까지 낭비하게 된다. 이는 마치 여러 명의 탐험가가 서로 소통 없이 각자 길을 가다가 예산을 다 써버리는 것과 같다.

BAVT는 이를 해결하기 위해 추론 과정을 하나의 '트리(Tree)' 구조로 관리한다. 핵심은 '잔차 가치(Residual Value)' 개념이다. 단순히 현재 상태가 좋은지 묻는 대신, "이전 단계보다 얼마나 더 정답에 가까워졌는가?"를 평가한다. 이는 Gradient Descent에서 손실 함수의 변화량을 추적하는 것과 유사하게, 모델이 실제로 유의미한 정보 이득(Information Gain)을 얻고 있는지를 판단하는 기준이 된다.

또한, 남은 예산에 따라 탐색의 폭을 조절하는 Softmax 온도 조절과 유사한 메커니즘을 적용한다. 예산이 넉넉할 때는 다양한 경로를 탐색하도록 확률 분포를 평평하게 유지하고, 예산이 줄어들수록 가치가 높은 노드에 확률을 집중시켜 확실한 정답을 내도록 유도한다. 결과적으로 자원을 낭비하는 경로를 조기에 차단하고 유망한 경로에 집중 투자하는 지능적인 자원 관리가 가능해진다.

BAVT는 추론 과정을 상태(State)를 노드로, 행동(Action)을 에지로 하는 동적 탐색 트리로 정형화한다. LLM 백본은 생성자(Generator)와 비평가(Critic)의 역할을 번갈아 수행한다. 생성자는 현재 노드에서 가능한 다음 행동(도구 호출 또는 논리적 추론)을 제안하고, 비평가는 그 결과로 생성된 새로운 노드의 가치를 평가한다.

노드 선택 과정에서는 예산 인식 확률적 샘플링(Budget-Aware Stochastic Sampling)을 사용한다. 남은 도구 예산과 토큰 예산 중 최소 비율을 $r_t$로 정의하고, 이를 역수로 취해 지수 $\alpha_t = 1/r_t$를 계산한다. 각 노드의 가치 $V(n_i)$에 이 지수를 적용하여 가중치 $w_{n_i} = V(n_i)^{\alpha_t}$를 구한다. [$V(n_i)$와 $r_t$를 입력으로] → [가치 값에 예산 비율의 역수를 지수로 승수 연산하여] → [정규화된 선택 확률을 얻고] → [예산이 적을수록($r_t \to 0$) 높은 가치 노드의 선택 확률이 기하급수적으로 높아지는] 원리이다.

가치 업데이트에는 전역 역전파(Global Backpropagation) 메커니즘을 도입한다. 터미널 답변 노드가 발견되면 트리 전체에 신호를 보내 하위 경로의 성공 경험을 상위 노드로 전달한다. 노드 $n$의 가치는 $V(n) \leftarrow \frac{V(n) + \sum V(n_{child})}{1 + |N_{child}|}$ 식으로 갱신된다. [노드 자체의 초기 평가값과 자식 노드들의 가치 합을 입력으로] → [자식 노드 개수에 1을 더한 값으로 나누는 평균 연산을 수행해] → [업데이트된 가치 값을 얻고] → [특정 경로가 최종 정답으로 이어질 가능성을 전역적으로 반영한다].

HotpotQA, 2WikiMultihopQA, MuSiQue, Bamboogle 등 4개의 다단계 추론 벤치마크에서 GPT-OSS-20B와 Qwen3-30B 모델을 사용하여 성능을 검증했다. 모든 예산 수준(Low, Middle, High)에서 BAVT는 병렬 샘플링(Parallel Sampling) 베이스라인을 일관되게 압도했다. 특히 엄격한 저예산(Low Budget, 도구 호출 5회 제한) 환경에서 BAVT는 베이스라인이 4배 더 많은 자원(도구 호출 20회)을 사용했을 때보다 더 높은 정확도를 기록했다.

모델 특성에 따른 분석 결과, 추론 전용 모델(OSS-20B)에서는 예산 증가에 따른 성능 향상이 뚜렷했으나 베이스라인은 잘못된 전제에 빠졌을 때 자원을 낭비하는 취약점을 보였다. 반면 일반 지시 이행 모델(Qwen3-30B)은 베이스라인에서 성능 정체(Plateau) 현상이 나타났으나, BAVT는 '탐색 확장(Search Widening)' 메커니즘을 통해 모델이 동일한 실패 경로를 반복하는 모드 붕괴(Mode Collapse)를 강제로 깨뜨려 성능 한계를 돌파했다.

소거 연구(Ablation Study)를 통해 트리 구조, 단계별 가치 평가, 예산 인식 노드 선택의 기여도를 확인했다. 단순히 트리 구조만 사용하는 것은 무작위 탐색으로 인해 오히려 성능을 저하시켰으나(EM 0.268에서 0.215로 감소), 단계별 가치 평가를 추가하면 EM 0.309로 상승했고, 최종적으로 예산 인식 메커니즘까지 결합했을 때 최고 성능(EM 0.388)을 달성했다.

BAVT는 에이전트의 추론 과정을 자원 제약이 있는 결정론적 의사결정 프로세스(RCDP)로 모델링한다. 상태 공간 $S$는 쿼리, 행동 이력, 도구 관찰 값을 포함하며, 예산 상태 $B$는 남은 도구 호출 횟수와 토큰 수를 추적하는 동적 변수로 정의된다.

핵심 알고리즘은 '예산 어닐링(Budget Annealing)' 전략을 따른다. 탐색 초기에는 $\alpha_t \approx 1$로 설정되어 노드 가치에 비례하는 확률적 탐색을 수행하지만, 예산이 소진될수록 $\alpha_t \to \infty$가 되어 가장 가치가 높은 노드를 선택하는 결정론적(Deterministic) 탐욕 선택으로 전이된다. 이는 이론적으로 유한한 예산 내에서 터미널 노드에 도달할 확률 $1-\epsilon$을 보장하는 근거가 된다.

가치 비평가는 '잔차 정보 델타($\Delta_t$)'를 예측하도록 프롬프팅된다. 새로운 노드 $n'$의 가치는 $V(n') = \Phi(V(n) + \Delta_t)$로 계산되며, 여기서 $\Phi$는 값을 $[0.1, 1.0]$ 범위로 제한하는 바운딩 함수이다. 비평가는 정수 범위 $[-4, +4]$ 내에서 델타 값을 출력하며, 이는 모델의 과신을 방지하고 상대적인 진전만을 평가하게 한다.

예산 고갈 시점에는 '예산 백스톱(Budget Backstop)' 메커니즘이 작동한다. 도구 예산이 0이 되거나 토큰 예산 비율이 임계값 $\eta(0.2)$ 아래로 떨어지면, 현재 트리에서 가장 가치가 높은 미완성 리프 노드를 선택해 즉시 최종 답변을 생성하도록 강제 지시를 내린다.

비평가(Critic) 역할을 수행하기 위해 매 단계마다 LLM을 추가로 호출하므로 추론 오버헤드가 발생한다. 또한 현재는 웹 검색이라는 단일 도구와 균일한 비용 환경을 가정하고 있어, 비용이 서로 다른 다양한 도구를 사용하는 복잡한 환경에 대한 확장이 필요하다.