Budget-Aware Tool-Use Enables Effective Agent Scaling

Meta info.

• Authors: Liu, Zifeng Wang, Jin Miao, I-Hung Hsu, Jun Yan, Jiefeng Chen, Rujun Han, Fangyuan Xu, Yanfei Chen, Ke Jiang, Samira Daruki, Yi Liang, William Yang Wang, Tomas Pfister, Chen-Yu Lee
• Paper: https://arxiv.org/pdf/2511.17006
• Affiliation: Google Cloud AI Research, Google DeepMind, NYU, UC Santa Barbara
• Published: November 21, 2025

TL; DR

툴 호출 예산을 단순히 늘리는 것만으로는 에이전트 성능이 스케일(TTS)되지 않으며, 예산을 명시적으로 인식하도록 하는 Budget Tracker와 BATS 프레임워크를 도입하면 비용 대비 성능 스케일링과 Pareto frontier가 크게 개선된다.

Background

• TTS(Test-time Scaling)확장: 학습 파라미터 증가 없이 추론시 계산량 증가로 성능 향상
  • sequential refinement, parallel sampling, aggregation 등 TTS의 토큰 소비를 스케일링 축으로 추론 비용 확장
• Tool-augmented Agent 확대: 웹검색, 브라우징 등
  • tool call 측면에서는 외부 행동에 대한 비용이기 때문에 토큰 소비로 스케일링되지 않음

Problem States

• tool call 비용 예산을 확장하면 정말 성능이 오르지 않는가
  • 실제로 tool call 비용 예산을 확장해도 성능은 오르지 않거나 빠른 포화
    • 충분한 예산이 있어도 조기종료하거나 탐색과 검증사이 균형을 잡지 못함
• 에이전트에게 남은 예산을 이해시킬 수 있나?

Suggestions

• Search Agent로 TTS 범위 구체화
  • Search Agent: 입력에 대해 Thought > external knowledge를 검색/브라우징하여 수집> 추론(Thought)>… >답 (ReAct-style loop)
    • Search: 일반 검색엔진 쿼리를 입력으로 받고 결과에 대해 tiltie, snippet, URL 반환 (넓은탐색)
    • Browse: 특정 URL 스크래핑 (깊은탐색)
• 예산 제약 하에서 에이전트 scaling formulation: 예산 제약 하에서 기대 정확도를 최대화한다
  • 툴 t_i는 호출 횟수 c_i에 대해 예산 b_i를 초과할 수 없다.
• 공정 비교를 위한 unified cost = token cost + tool-call cost
  • 툴 호출 증가는 토큰 사용량과 비례하는 측면이 있음
    • 많이 검색할수록 결과를 받아서 처리하고 읽는 데에 토큰 소모 (강한 상관성)
  • token cost: 에이전트의 내부 인지 노력으로 해석 (internal knowledge 처리, reasoning, planning 등에 사용)
  • tool call cost: search/browse에 드는 API 호출 비용 = 외부 서비스 비용
• methods:
  • Budget Tracker: prompt-level에서 agent-loop에 삽입
    • prompt: tool 별 총 예산, 현재까지 사용한 호출 수, 남은 호출 수, 예산 상태에 따른 행동 가이드(예산이 많으면 적극적으로 찾아라,…예산이 적다면 검증 중심으로,,,)
    • react 한계 개선: 예산을 명시적인 상태변수로 관리하므로 내부 휴리스틱으로 대충 충분하다는 인식에 개입 가능
  • BATS(budget-aware tts)
    • Budget-Aware Planning: 이미 시도한 검색을 다시 하지 않도록 설계
      • 문제의 제약을 (1) Exploration clues (찾아야 할 정보)와 (2) Verification clues (정답을 검증할 조건)으로 분해
      • tree 기반으로 체크리스트(plan)을 유지하여 각 노드가 상태(완료했는지) + tool 호출 기록 관련 기록
    • Budget-Aware Self-Verification & Continue/Pivot
      • 답안에 대해 (1) 제약조건별평가; 만족했는지, 검증됐는지 (2) 예산잔여량을 고려하여 종료할지 더 탐색할지 전략을 바꿀지 등을 결정 (3) 만약 종료되지 못한다면: 기존 trajectory를 압축하여 context length 관리

Effects

• benchmarks: BrowseComp(영어 웹), BrowseComp-ZH(중국어 웹), HLE-Search (Human’s Last Exam 중 검색이 필요한 문제)
• backbone: Gemini-2.5-Pro, Claude-Sonnet-4
• tool: Google Custom Search API(Search), Jina,ai + CrawlAI(Browse)
• Results
  • tab3 동일한 툴 예산하에서 모든 모델에서 ReAct 대비 대폭 성능 개선
    • training-free임에도 불구하고 특히 BrowseComp에서 격차 큼
  • fig8 Early Stopping 분석
    • React: 예산이 있어도 성능이 오르지 않고, Browse를 거의 하지 않음
    • BATS: 예산이 늘면 는 만큼 browse를 적극적으로 수행하고, 예산이 낮더라도 baseline 이상 달성
  • tab4 ablation
    • planning이 없거나 verification이 빠지면 성능 하락, 특히 후자의 경우 검색 기반 문제에서 타격 큼

Personal note. 프롬프트와 react의 연장이라는 점이 연구적으로 흥미롭지는 않을 수도 있겠지만 확장과 편의성 측면의 이점에 대해서는 반박하기 어려워보입니다. 다음은 아마 그래서 예산은 어떻게 정해야하는지 일 것 같고, 저자들도 appendix 마지막에 언급하긴 하는데 문제의 시작이 에이전트가 스스로 이미 뭘 했고, 지금 어떤 상태에 있고, 앞으로 뭘 더 할 수 있는지를 지속적으로 유지하지 못한다로 시작했다면 관련해서 메모리 측면에 대한 고민으로 자연스럽게 연결될 것으로 보입니다. 한편으로 budget은 personalization의 가장 쉽게 접근할만한 factor라는 생각도 들고요.