agent : 논문리뷰 : Tree Search for Language Model Agents

논문리뷰

agent : 논문리뷰 : Tree Search for Language Model Agents

AI바라기 2025. 2. 5. 16:51

Overall Summary

본 논문은 LM agents의 reasoning 및 planning 능력 향상을 위해 inference-time tree search 알고리즘을 제안하고, realistic web environments에서 best-first search가 효과적임을 최초로 입증했습니다. Model-based value function을 통해 복잡한 web tasks에서 search guidance를 제공하고, VisualWebArena benchmark에서 SOTA 성능을 달성했습니다. Search의 scalability를 실험적으로 보이고, 향후 연구 방향을 제시하여, capable agent building에 기여할 것으로 기대됩니다.

쉬운 설명

웹 에이전트가 복잡한 웹 환경에서 길을 찾는 과정을 생각해 봅시다. 기존 에이전트는 "눈 앞만 보고" 즉흥적으로 행동해서 길을 잃거나 헤매기 쉽습니다. 본 논문은 에이전트에게 "미리 여러 갈래 길을 탐색"하고 "가장 유망한 길을 선택"하는 능력을 부여하는 "tree search" 라는 "네비게이션 시스템" 을 장착해준 것과 같습니다. 이 네비게이션은 "value function" 이라는 "지도" 를 활용하여 각 갈림길의 "가치" 를 평가하고, "best-first search" 전략으로 "가장 가치 있는 길" 부터 탐색합니다. 실험 결과, 이 네비게이션 시스템은 에이전트의 웹 탐색 능력을 크게 향상시켰고, 특히 복잡한 웹 환경에서 "SOTA급 성능" 을 보여주었습니다. 이는 마치 "자동차 네비게이션" 이 운전자의 길 찾기를 돕듯이, "tree search 네비게이션" 이 웹 에이전트의 "웹 탐색" 을 획기적으로 발전시킬 수 있음을 시사합니다.

Purpose of the Paper

기존 LM agents는 natural language understanding 및 generation에 최적화되어 multi-step reasoning, planning, environmental feedback 활용에 어려움 존재
특히 open-ended web environments에서 exploration 및 multi-step planning 능력 부족은 심각한 bottleneck
본 연구는 LM agents의 exploration 및 multi-step planning 능력 향상을 위한 inference-time search algorithm 제시

Key Contributions

Realistic Web Tasks에 효과적인 Tree Search 알고리즘 최초 제시:
- 실제 web environment에서 agent가 직접 exploration하며 graph iteratively construction
- environmental feedback 기반으로 search guidance
- 기존 state-of-the-art agents와 complementary하게 작동
- Novelty: realistic web tasks에서 inference-time search 효과 입증 최초
Model-based Value Function 제안:
- diverse environments의 lack of clear cut rewards 문제 해결 위해 model-based value function 고안
- multimodal LM의 reasoning chains marginalization 통해 fine-grained score 생성, 효과적인 search guidance 제공
- Novelty: 환경 피드백 기반 value function을 통해 복잡한 web task에서 best-first search 가능하게 함
VisualWebArena 및 WebArena benchmark에서 SOTA 성능 달성:
- GPT-4o agent + search 조합으로 VisualWebArena에서 26.4% SOTA success rate 달성 (baseline 대비 39.7% relative increase)
- WebArena에서 19.2% competitive success rate 달성 (baseline 대비 28.0% relative improvement)
Test-time compute 증가에 따른 성능 scaling 입증:
- search budget 증가에 따라 성능 향상 실험적으로 입증
- search의 scalability 및 practical potential 시사

Experimental Highlights

Datasets: VisualWebArena, WebArena
Metrics: Success Rate (SR)
Baselines:
- GPT-4o agent (no search)
- Llama-3-70B-Instruct + captions (no search)
- Other published approaches (ICAL, AutoWebGLM, SteP 등)
Key Results:
- VisualWebArena: GPT-4o agent + search 26.4% SR (SOTA), baseline 대비 +39.7% relative increase
- →\rightarrow
- WebArena: GPT-4o agent + search 19.2% SR (Competitive), baseline 대비 +28.0% relative increase
- →\rightarrow
- Search budget (c) 증가에 따라 SR 지속적 향상 (c=20일 때 baseline 대비 +51% SR 향상)
- Search depth (d) 및 branching factor (b) 증가에 따라 SR 향상 (large search tree benefit)
- GPT-4o value function이 LLaVA value function보다 우수한 성능 (value function 중요성 시사)
- Self-consistency prompting이 value function 성능 향상에 기여

Limitations and Future Work

Search Speed: inference-time compute 증가로 trajectory execution time 증가 search efficiency 향상 연구 필요 (e.g., machine learning system optimization)
→\rightarrow
Destructive Actions: real-world deployment 위해 destructive actions 제어 필요 classifier 도입, world model 활용, offline setting 적용 등 연구 필요
→\rightarrow
Value Function: value function 성능 향상 여지 존재 better value functions training 연구 필요 (e.g., 더 많은 데이터, self-consistency 강화)
→\rightarrow
Future Work:
- 더 강력한 baseline agents (domain-specific techniques agents)에 search 적용 연구
- 더 큰 search budget 실험 통해 scaling trends 심층 분석
- value function 개선 및 destructive action 제어 연구

ABSTRACT

language models (LMs)에 의해 구동되는 Autonomous agents는 웹 자동화와 같은 의사 결정 작업을 수행하는 능력에서 가능성을 보여주었습니다. 그러나 주요 한계는 여전히 남아 있습니다. 주로 자연어 이해와 생성에 최적화된 LMs는 현실적인 컴퓨터 작업을 해결하려고 할 때 다단계 reasoning, planning, 그리고 환경적 피드백을 사용하는 데 어려움을 겪습니다. 이를 해결하기 위해, 우리는 LM agents가 interactive web 환경에서 탐색과 다단계 planning을 명시적으로 수행할 수 있는 inference-time search 알고리즘을 제안합니다. 우리의 접근 방식은 실제 환경 공간 내에서 작동하는 best-first tree search의 한 형태로, 대부분의 기존 state-of-the-art agents와 상호 보완적입니다. 이것은 현실적인 웹 작업에서 효과를 보여주는 LM agents를 위한 최초의 tree search 알고리즘입니다. 어려운 VisualWebArena 벤치마크에서, GPT-4o agent에 우리의 search 알고리즘을 적용하면 search를 사용하지 않은 동일한 baseline에 비해 성공률이 상대적으로 39.7% 향상되어 26.4%의 state-of-the-art 성공률을 기록했습니다. WebArena에서도 search는 baseline agent에 비해 상대적으로 28.0%의 개선을 가져와 19.2%의 경쟁력 있는 성공률을 기록했습니다. 우리의 실험은 web agents를 위한 search의 효과를 보여주며, 성능은 테스트 시간 컴퓨팅 증가에 따라 확장된다는 것을 보여줍니다. 우리는 search를 통한 개선 사항, 한계 및 향후 연구를 위한 유망한 방향을 강조하기 위해 결과에 대한 철저한 분석을 수행합니다.

1 INTRODUCTION

인지하고, 계획하고, 자율적으로 행동할 수 있는 agents를 구축하는 것은 artificial intelligence 연구의 오랜 목표였습니다. 최근 몇 년 동안 강력한 일반 기능을 갖춘 large language models (LMs)의 출현은 컴퓨터 작업을 자동화할 수 있는 language-guided agents를 구축하는 길을 열었습니다. 그러나 오늘날 최고의 LM agents는 여전히 인간보다 훨씬 성능이 떨어집니다. 현실적인 웹 벤치마크인 WebArena와 VisualWebArena에서 인간은 각각 78%와 89%의 작업에서 성공하지만, 최신 프론티어 models에 의해 구동되는 agents조차도 훨씬 성능이 떨어져 일반적으로 20% 미만의 성공률을 달성합니다. 기존 agents의 중요한 병목 현상 중 하나는 탐색 및 다단계 planning을 위해 테스트 시간 계산을 활용할 수 없다는 것입니다. search 및 planning은 개방형 웹 환경에서 특히 중요한데, 잠재적인 action space(즉, 웹 페이지에서 수행할 수 있는 모든 가능한 작업)가 대부분의 비디오 게임이나 텍스트 기반 시뮬레이터보다 훨씬 크기 때문입니다. 목표에 도달하기 위해 순서대로 수행해야 하는 그럴듯한 작업이 여러 개 있는 경우가 많으며, 궤적을 효율적으로 탐색하고 가지치기할 수 있는 능력이 필수적입니다.

artificial intelligence 시스템에서 테스트 컴퓨팅을 활용하여 결과를 개선하는 한 가지 효과적인 전략은 search입니다. 중간 상태와 가능한 솔루션의 그래프를 반복적으로 구성, 탐색 및 가지치기하는 것입니다. search 알고리즘의 효과는 여러 번 입증되었으며, models가 Go, 포커, Diplomacy를 포함한 다양한 게임에서 인간 수준의 성능을 달성하거나 능가할 수 있게 했습니다.

검색 공간이 크고 게임과 달리 명확한 보상과 승리 조건이 존재하지 않는 컴퓨터 작업 자동화의 맥락에서 search를 어떻게 적용할 수 있을까요? 이 목표를 향해, 우리는 autonomous web agents가 interactive web environment의 탐색을 통해 반복적으로 구성된 그래프를 search할 수 있는 방법을 제안합니다. 이 search 절차는 실제 환경 공간 내에서 이루어지며 환경적 피드백으로 안내됩니다. 우리의 접근 방식을 통해 agents는 테스트 시간에 훨씬 더 많은 수의 잠재적으로 유망한 궤적을 열거할 수 있으며, 명시적인 탐색과 다단계 planning을 통해 불확실성을 줄일 수 있습니다. 우리가 아는 한, 이것은 inference-time search가 현실적인 웹 환경에서 autonomous agents의 성공률을 향상시키는 것으로 나타난 최초의 사례입니다. 이러한 다양한 환경에서 명확한 보상이 부족한 문제를 해결하기 위해, 우리는 best-first search를 안내하는 model-based value function을 제안합니다. value function은 agent의 관찰을 조건으로 하는 multimodal LM의 reasoning chains에 대해 marginalizing하여 계산되며, search를 효과적으로 안내하기 위해 세분화된 점수를 생성합니다.

우리의 실험은 이 search 절차가 기존 LM agents와 상호 보완적이며, 이러한 models가 더 어렵고 긴 horizon 작업에서 더 나은 성능을 발휘할 수 있게 한다는 것을 보여줍니다. VisualWebArena에서 search는 baseline GPT-4o agent의 성능을 search를 사용하지 않은 baseline에 비해 상대적으로 39.7% 향상시켜 26.4%의 새로운 state-of-the-art (SOTA) 성공률을 기록했습니다. WebArena에서도 search는 매우 효과적이며, 상대적으로 28.0%의 개선을 가져왔습니다 (19.2%의 경쟁력 있는 성공률을 달성). 우리는 또한 우리의 search 절차가 규모의 이점을 얻는다는 것을 보여줍니다. agent에게 더 많은 양의 테스트 시간 계산이 할당됨에 따라 향상된 성능을 달성합니다. 우리의 코드와 models는 jykoh.com/search-agents 에서 공개적으로 제공됩니다.

그림 1: 우리가 제안한 search 알고리즘. 각 반복에서, 우리는 frontier F에서 확장할 다음 상태 sp를 선택하고 value function을 사용하여 그것에 대한 점수 v를 계산합니다. 그런 다음, agent가 sp에서 도달할 수 있는 가능한 다음 상태들을 frontier에 추가하고 search 절차를 반복합니다. 흐리게 표시된 노드는 탐색되고 가지치기된 상태를 나타냅니다. 파란색 점선 화살표는 역추적(backtracking)을 나타냅니다.

1 INTRODUCTION 정리 노트 (AI 연구자 대상)

핵심: 본 논문은 inference-time search를 통해 autonomous web agents의 성능을 향상시키는 방법을 제안합니다. 기존 language models (LMs) 기반 agents는 현실적인 웹 환경에서 다단계 reasoning과 planning에 어려움을 겪는데, 이를 해결하기 위해 interactive web environment 탐색을 통해 구성된 그래프를 search하는 새로운 알고리즘을 제시합니다.

주요 내용:

문제 정의: 기존 LM agents는 현실적인 웹 벤치마크(WebArena, VisualWebArena)에서 인간 대비 현저히 낮은 성능을 보임 (agents < 20%, 인간 > 78%). 이는 test-time computation을 활용한 탐색 및 다단계 planning 능력 부족에서 기인함. 특히, 웹 환경은 action space가 매우 크기 때문에 search와 planning이 중요함.
해결 방안:
- Inference-time search: interactive web environment에서 반복적으로 구축된 그래프를 탐색하는 search 알고리즘 제안.
- Best-first search: 명확한 보상이 없는 환경을 고려하여 model-based value function을 사용해 best-first search를 수행.
- Multimodal LM 활용: agent의 관찰을 기반으로 multimodal LM의 reasoning chains을 marginalize하여 value function 계산.
실험 결과:
- VisualWebArena: GPT-4o agent에 search 알고리즘 적용 시, baseline 대비 39.7% 상대적 성능 향상 (SOTA 26.4%).
- WebArena: baseline 대비 28.0% 상대적 성능 향상 (19.2%).
- Scalability: test-time computation 증가에 따른 성능 향상 확인.

차별점:

현실적인 웹 환경에서 inference-time search를 적용하여 autonomous agents의 성공률을 향상시킨 최초의 연구.
Model-based value function을 사용하여 다양한 환경에서 search를 효과적으로 유도.

한계 및 향후 연구:

본문에서 명시적으로 언급되지는 않았지만, search 알고리즘의 계산 복잡도 및 실시간 적용 가능성에 대한 논의가 필요.
다양한 agent architectures와의 결합 가능성 탐구.

쉬운 설명 :

이 논문은 쉽게 말해 "웹 브라우저를 스스로 사용하는 AI" 를 더 똑똑하게 만드는 방법에 대한 이야기입니다. 기존 AI는 웹사이트에서 여러 단계를 거쳐야 하는 복잡한 작업을 잘 수행하지 못했습니다. 마치 길을 잃은 것과 같았죠.

이 논문에서는 AI가 마치 "지도를 보면서 탐험하듯이" 웹사이트를 탐색할 수 있는 새로운 방법을 제안합니다. AI는 웹사이트에서 자신이 어디에 있는지, 어디로 갈 수 있는지, 그리고 그 길이 얼마나 좋은지를 점수로 매겨서 가장 좋은 경로를 찾아 나갑니다. 마치 게임에서 이길 확률이 높은 길을 찾는 것과 비슷합니다.

실험 결과, 이 방법을 사용한 AI는 기존보다 훨씬 더 어려운 웹사이트 작업들을 잘 수행하는 것으로 나타났습니다. 또한, 더 많은 시간을 들여 탐색할수록 AI의 성능이 더욱 향상되는 것도 확인했습니다.

간단히 말해, 이 논문은 AI가 웹사이트를 탐험하고 복잡한 작업을 수행하는 능력을 크게 향상시키는 새로운 방법을 제시했다고 할 수 있습니다. 마치 AI에게 웹사이트를 탐험하는 데 필요한 지도를 제공한 것과 같습니다.

2 BACKGROUND

2.1 REALISTIC SIMULATED WEB ENVIRONMENTS

large language models에 의해 구동되는 autonomous web agents를 개발하는 목표를 향해, 여러 이전 연구들은 웹 작업에서 models의 진행 상황을 측정하기 위한 평가 벤치마크를 구축하는 데 중점을 두었습니다. Mind2Web은 정적 인터넷 페이지에서 수행된 작업을 예측하는 데 있어 프론티어 models의 능력을 측정하는 평가 벤치마크입니다. VisualWebBench는 models의 웹 콘텐츠 이해 능력을 평가하기 위한 multimodal 벤치마크를 도입했습니다. 다른 연구들은 시뮬레이터(정적 HTML 콘텐츠와 반대)를 조사했습니다. MiniWoB은 웹 작업을 위한 최초의 interactive 시뮬레이터 중 하나였지만, 실제 성능으로 직접 변환되지 않는 단순화된 환경으로 구성되었습니다. WebShop은 실제 데이터로 단순화된 전자 상거래 사이트를 시뮬레이션합니다. WebLINX는 agent와 인간 강사 간의 의사 소통을 포함하는 대화형 웹 탐색을 다루기 위한 벤치마크를 제안합니다. MMInA와 OSWorld는 여러 컴퓨터 애플리케이션을 탐색하여 작업을 수행하는 agents의 능력을 측정하기 위한 벤치마크를 제안합니다. WorkArena는 ServiceNow 플랫폼에서의 작업을 위한 시뮬레이션 환경입니다. WebArena (WA)는 실제 데이터로 채워진 인기 있는 웹사이트(쇼핑, Reddit, CMS, GitLab, 지도)의 5가지 현실적인 자체 호스팅 재구현에 걸쳐 812개의 작업으로 구성된 벤치마크입니다. VisualWebArena (VWA)는 WebArena의 multimodal 확장으로, 3개의 인기 있는 실제 사이트(Classifieds, Reddit, 쇼핑)의 현실적인 재구현에 걸쳐 910개의 새로운 작업으로 구성됩니다. VWA의 작업을 해결하려면 agents는 visual grounding을 활용하고 이미지 입력을 이해해야 하며, multimodal agents를 위한 현실적이고 도전적인 테스트를 제공해야 합니다. (V)WA 환경은 웹 작업을 위한 가장 현실적이고 포괄적인 평가 제품군 중 하나이므로, 우리는 주로 (V)WA에서 우리의 방법을 벤치마킹합니다. 여기서는 설정을 간략하게 설명하지만 추가 컨텍스트는 참고문헌을 참조하십시오. 환경 E = (S, A, Ω, T)는 상태 집합 S, 작업 A(표 1) 및 작업 조건에 따른 상태 간 전환을 정의하는 결정론적 전환 함수 T: S × A → S로 구성됩니다. 벤치마크의 각 작업은 자연어 지침 I(예: "2000달러 이하의 가장 저렴한 빨간색 Toyota 자동차를 찾아주세요.")로 지정된 목표로 구성됩니다. 각 작업에는 agent 실행이 성공적인지 여부를 측정하는 사전 정의된 보상 함수 R: S × A → {0, 1}이 있습니다. 우리는 (V)WA 웹 시뮬레이터에서 search 알고리즘을 구현하지만, 우리의 방법은 완전히 일반적이며 interactive 환경이 있는 모든 설정에 적용될 수 있습니다.

2.2 LANGUAGE-GUIDED AUTONOMOUS AGENTS

프론티어 (multimodal) language models (Google, OpenAI, Anthropic)에 의해 구동되는 Autonomous web agents는 위의 많은 벤치마크에서 SOTA 접근 방식입니다. Kim 등은 large language models가 MiniWoB++에서 컴퓨터 작업을 실행하도록 유도될 수 있으며, reinforcement learning 방법보다 훨씬 적은 demonstration이 필요하다는 것을 보여주었습니다. AutoWebGLM은 커리큘럼 training을 위한 웹 브라우징 데이터를 수집하고 WebArena에서 GPT-4보다 우수한 성능을 보이는 6B 파라미터 language model을 기반으로 한 웹 탐색 agent를 개발합니다. Patel 등은 language model agent가 자체적으로 생성된 데이터에 대한 finetuning을 통해 성능을 향상시킬 수 있음을 보여주었습니다. Pan 등은 작업 실패 또는 성공에 대한 지침을 제공하는 자동 평가자를 도입하면 baseline Reflexion agent의 성능을 향상시킬 수 있음을 보여줍니다. Fu 등은 오프라인 데이터에서 도메인 지식을 추출하고 추론 중에 language agent에 이를 제공하여 유용한 도메인 지식을 활용할 수 있도록 합니다. SteP와 AWM은 agents가 웹 작업을 해결하기 위해 동적으로 policies를 구성할 수 있도록 하는 방법을 제안합니다.

multimodal 설정에서, WebGUM은 대규모 demonstration 코퍼스에 대해 3B 파라미터 multimodal language model을 finetuning하여 MiniWoB 및 WebShop에서 강력한 성능을 달성했습니다. Koh 등은 Set-of-Marks representation으로 multimodal language models를 prompting하는 것이 텍스트 전용 agents보다 복잡한 웹 페이지를 더 효과적으로 탐색할 수 있게 한다는 것을 보여주었습니다. SeeAct는 GPT-4V 및 Gemini와 같은 프론티어 multimodal models가 웹 작업을 해결하도록 유도되고 prompting될 수 있음을 입증했습니다. ICAL은 demonstration 및 인간 피드백에서 multimodal 통찰력의 메모리를 구축하여 VisualWebArena의 성능을 향상시킵니다. 우리의 절차는 더 나은 base agents를 개발하는 데 중점을 둔 이러한 과거 접근 방식 중 상당수와 호환되는 inference-time 접근 방식입니다.

2.3 SEARCH AND PLANNING

우리의 방법은 또한 컴퓨터 과학에서 search 및 planning 알고리즘의 풍부한 역사에서 영감을 얻었습니다. breadth first search, depth first search 및 A* search와 같은 search 알고리즘은 오랫동안 artificial intelligence 시스템에서 사용되었습니다. Newell 등과 Laird는 목표 지향적 행동을 가능한 상태 공간을 통한 search로 간주했습니다. Dean 등과 Tash & Russell은 제한된 search horizon에 대한 planning 알고리즘을 제안하고 정보 가치에 대한 휴리스틱을 기반으로 계획을 개선하기 위한 확장 전략을 사용했습니다. Tash & Russell은 이것이 agents가 시간 압박과 세계의 무작위성에 적절한 대응을 제공할 수 있게 한다는 것을 보여주었습니다. 1997년 체스 세계 챔피언 Kasparov를 물리친 체스 엔진인 Deep Blue는 대규모 병렬 tree search를 기반으로 했습니다. Pluribus는 동적 상황에 대한 더 나은 멀티플레이어 포커 전략을 찾기 위해 search를 활용합니다. deep learning에서 neural network 구성 요소가 있는 search 알고리즘은 많은 게임에서 초인적인 성능을 달성하는 데 중요한 역할을 했습니다. Monte-Carlo Tree Search (MCTS)는 lookahead search를 제공하는 데 사용되었으며, Go 게임에서 초인적인 성능을 달성한 AlphaGo 및 AlphaGo Zero 시스템에서 중추적인 역할을 했습니다. Gray 등은 one-step lookahead search를 수행하여 무압박 Diplomacy에서 SOTA를 달성합니다. 보다 최근에, 여러 논문은 search를 large language models에 적용하여 여러 reasoning 경로에 대한 탐색을 도입하여 사소하지 않은 planning이 필요한 텍스트 기반 작업의 성능을 향상시킬 가능성을 보여주었습니다. 다른 사람들은 MCTS를 수학 벤치마크 또는 단순화된 환경에서 LMs의 성능을 향상시키기 위해 적용했습니다.

이전 연구와 대조적으로, 우리의 설정은 현실적인 웹 환경에 기반을 두고 있으며 실제 환경 공간(즉, 웹)을 search합니다. 즉, search 메커니즘은 agent의 텍스트 출력뿐만 아니라 매우 복잡한 환경의 외부 환경 피드백도 통합해야 합니다.

2 BACKGROUND 정리 노트 (AI 연구자 대상)

핵심: 본 섹션은 논문에서 제안하는 search 알고리즘의 기반이 되는 현실적인 시뮬레이션 웹 환경 (Realistic Simulated Web Environments) 과 language-guided autonomous agents, 그리고 search 및 planning 에 대한 관련 연구들을 소개하고, 기존 연구와의 차별성을 강조합니다.

주요 내용:

2.1 REALISTIC SIMULATED WEB ENVIRONMENTS

기존 벤치마크: Mind2Web, VisualWebBench, MiniWoB, WebShop, WebLINX, MMInA, OSWorld, WorkArena 등 소개.
WebArena (WA) & VisualWebArena (VWA): 본 논문에서 주로 사용하는 벤치마크.
- WA: 5개의 실제 웹사이트를 재구현한 812개 태스크.
- VWA: WA의 multimodal 확장, 3개 사이트, 910개 태스크, visual grounding 및 이미지 입력 이해 필요.
환경: E = (S, A, Ω, T) 로 정의. 상태 집합(S), 액션(A), 결정론적 전이 함수(T) 포함. 각 태스크는 자연어 지시(I)와 보상 함수(R)로 구성.
핵심: 본 논문의 search 알고리즘은 (V)WA 웹 시뮬레이터에 구현되지만, interactive 환경을 가진 모든 설정에 적용 가능.

2.2 LANGUAGE-GUIDED AUTONOMOUS AGENTS

SOTA: (multimodal) language models 기반 autonomous web agents가 많은 벤치마크에서 SOTA 달성.
관련 연구: AutoWebGLM, Patel et al., Pan et al., Fu et al., SteP, AWM, WebGUM, SeeAct, ICAL 등 소개.
핵심: 본 논문의 search 알고리즘은 inference-time 접근 방식으로, 기존의 base agents 개선 연구들과 호환 가능.

2.3 SEARCH AND PLANNING

Search 알고리즘: breadth first search, depth first search, A* search 등 인공지능 시스템에서 오랫동안 사용.
Deep Blue, Pluribus: search 알고리즘을 활용한 성공 사례.
MCTS: AlphaGo, AlphaGo Zero 등에서 lookahead search 제공.
LMs + Search: 최근 연구들은 search를 LMs에 적용하여 텍스트 기반 태스크 성능 향상 가능성 제시.
핵심: 기존 연구와 달리, 현실적인 웹 환경에서 실제 환경 공간을 search하며, agent의 텍스트 출력뿐만 아니라 외부 환경 피드백을 통합.

차별점:

현실적인 웹 환경에 초점을 맞추고, 실제 환경 공간을 search함.
Inference-time search를 통해 기존 agent 연구와 결합하여 성능 향상 가능.
Agent의 텍스트 출력과 복잡한 환경의 외부 환경 피드백을 모두 고려.

쉬운 설명 :

이 섹션은 이 논문의 핵심 아이디어를 이해하는 데 필요한 배경 지식을 설명합니다.

1. 현실적인 웹 환경 시뮬레이터:

이 논문에서는 AI가 실제 웹사이트에서 작동하는 것처럼 훈련하고 테스트할 수 있는 "가짜 웹사이트" 환경을 사용합니다.
이 환경은 실제 웹사이트와 매우 유사하게 만들어졌으며, AI가 이미지를 이해하고 웹사이트를 탐색하는 능력을 테스트할 수 있습니다.
이러한 환경을 사용하면 AI가 실제 웹사이트에서 얼마나 잘 작동하는지 더 정확하게 측정할 수 있습니다.

2. Language-guided autonomous agents:

최근에는 "언어를 이해하는 AI" (large language models)를 사용하여 웹사이트를 스스로 탐색하는 AI를 만드는 연구가 활발히 진행되고 있습니다.
이러한 AI는 웹사이트에서 작업을 수행하는 데 점점 더 나은 성능을 보이고 있습니다.
이 논문에서 제안하는 방법은 이러한 AI의 성능을 더욱 향상시키는 데 사용될 수 있습니다.

3. Search 및 Planning:

"Search" 는 AI가 문제를 해결하기 위해 여러 가지 가능한 경로를 탐색하는 것을 말합니다.
이 논문에서는 AI가 웹사이트를 탐색할 때 search를 사용하여 가장 좋은 경로를 찾도록 합니다.
기존 연구에서는 주로 게임이나 간단한 환경에서 search를 사용했지만, 이 논문에서는 실제 웹사이트와 유사한 복잡한 환경에서 search를 사용합니다.

결론적으로, 이 섹션은 이 논문에서 다루는 AI가 실제 웹사이트에서 작동하는 것처럼 훈련하고 테스트할 수 있는 환경과, AI가 웹사이트를 탐색하는 데 사용하는 search 기술에 대한 배경 지식을 제공합니다.

3 METHOD

이 섹션에서는 search 절차(그림 1)에 대해 자세히 설명합니다. (V)WA와 같은 웹 환경에서 작업을 성공적으로 해결하는 것은 긍정적인 보상 R(s*) = 1을 제공하는 목표 상태 s*로 이동하는 것으로 해석될 수 있습니다. agent는 상태 s0(예: 홈페이지)에서 시작합니다. 자연어 작업 지시 I가 주어지면, agent의 목표는 일련의 작업 (a0, ..., at) ∈ A를 실행하여 목표 상태로 이동하는 것입니다. 각 작업은 환경에서 새로운 상태 st+1 ∈ S와 관찰 ot+1 ∈ Ω을 생성합니다. 전환 st → st+1은 결정론적 전이 함수 T: S × A → S에 의해 제어됩니다.

대부분의 접근 방식은 이를 부분적으로 관찰 가능한 Markov decision process로 취급하고, 다음 작업 at를 예측할 때 현재 관찰 ot에만 조건을 부여합니다. 이것은 심각한 한계가 있습니다. agent의 오류는 각 단계마다 누적되며, 시간 t에서 잘못된 작업이 수행되면 미래에 나쁜 상태로 이어질 경우 쉽게 수정할 수 없습니다. 우리의 접근 방식은 더 나은 궤적을 식별하기 위해 명시적으로 search와 역추적(backtracking)을 수행하여 이를 완화하는 것을 목표로 합니다. 다음 섹션에서 설명하는 관련된 여러 구성 요소가 있습니다. baseline agent model(섹션 3.1), value function(섹션 3.2), 그리고 search 알고리즘(섹션 3.3)입니다.

3.1 AGENT BACKBONE

대부분의 SOTA web agents는 large (multimodal) language models를 prompting하여 구축됩니다. pre-trained language model 또는 multimodal model fϕ는 현재 웹 페이지 관찰 ot로 prompting되고 실행될 다음 작업 at를 예측하도록 지시됩니다. ReAct, RCI 또는 Chain-of-Thought (CoT) prompting과 같은 prompting 기술을 활용하여 agent의 성능을 향상시키는 것이 일반적입니다. language model agents는 또한 search 중에 탐색할 그럴듯한 분기를 생성하는 데 필수적인 다양한 작업 집합(예: nucleus sampling 사용)을 샘플링할 수 있습니다(섹션 3.3 참조). 제안된 search 알고리즘은 원칙적으로 모든 base agent에 적용될 수 있습니다. 섹션 4에서 search가 fϕ를 재훈련하거나 finetuning하지 않고도 다양한 models에서 inference-time 성능을 향상시킨다는 것을 보여줍니다.

3.2 VALUE FUNCTION

우리는 현재 상태 st의 예상 보상 E[R(st)]을 추정하는 value function fv를 사용하여 best-first search 휴리스틱을 구현합니다. 여기서 실제 목표 상태는 완벽한 보상 1을 제공합니다. 시뮬레이터의 상태 st가 항상 agent에 액세스할 수 있는 것은 아니기 때문에(st는 사이트의 데이터베이스 항목과 같은 비공개 정보를 포함할 수 있음), value function은 현재 및 이전 관찰과 자연어 작업 지시 I를 사용하여 값 vt를 계산합니다:

vt = fv(I, {o1, ..., ot}) ∈ [0, 1]

우리의 실험에서 value function은 자연어 지시와 스크린샷으로서의 관찰로 multimodal language model을 prompting하여 구현됩니다(섹션 4.1).

3.3 SEARCH ALGORITHM

우리가 제안한 search 알고리즘은 컴퓨터 과학에서 널리 사용되는 고전적인 그래프 순회 알고리즘인 A* search에서 느슨하게 영감을 받은 best-first search 방법입니다. 우리는 language model agent를 사용하여 search tree의 후보 분기를 제안합니다. search에는 search tree의 최대 크기를 결정하는 하이퍼파라미터 depth d, branching factor b, search budget c, 그리고 종료 임계값 θ가 있습니다. search 절차는 그림 1에 요약되어 있습니다. 다음 단락에서 자세히 설명하고 부록 A.4에서 공식 알고리즘을 제공합니다.

실행 궤적의 시간 t에서, agent는 이전에 일련의 작업을 실행하여 현재 상태 st에 도달했습니다. 우리는 frontier F ← {}를 초기화하여 st에서 search 알고리즘을 시작합니다. frontier는 우리가 평가하려는 상태 집합을 보유하고(최대 우선 순위 큐로 구현됨), 지금까지 찾은 가장 좋은 상태 sˆt ← st, 가장 좋은 시퀀스의 점수 vˆt ← 0, 그리고 search 카운터 s ← 0입니다.

search 프로세스의 각 반복에서, 우리는 frontier에서 다음 상태 sp ← pop(F)를 추출합니다. 우리는 value function을 사용하여 상태 sp(관찰 op 및 이전 관찰 o1, ..., op-1 포함)에 대한 점수를 계산합니다:

vp = fv(I, {o1, ..., op})

그런 다음 search 카운터 s를 증가시키고, vp가 현재 최고 점수 vˆt보다 높으면, 그에 따라 최고 점수와 최고 상태를 업데이트합니다:

s ← s + 1

sˆt ← (vp > vˆt 이면 sp, 그렇지 않으면 sˆt)

vˆt ← max(vˆt, vp)

vp ≥ θ(즉, agent가 목표 상태를 찾았을 가능성이 높음)이거나 s ≥ c(search budget이 초과됨)이면, search를 종료하고 지금까지 찾은 가장 좋은 상태 sˆt로 이동합니다. 그렇지 않고, 현재 분기가 최대 depth를 초과하지 않으면(|(s0, ..., sp)| < d), language model agent fϕ에서 b개의 후보 작업 {a1p, ..., abp}를 얻어 분기를 위한 그럴듯한 다음 작업을 생성합니다. 각 i에 대해, 우리는 aip를 실행하고 결과 상태 sip를 현재 상태의 점수와 함께 frontier에 추가합니다:

F ← F ∪ (vp, sip) for i = 1, ..., b

이것으로 search의 한 번의 반복이 완료됩니다. 두 종료 조건 중 어느 것에도 도달하지 않으면, 역추적하고 업데이트된 frontier F에서 다음으로 가장 좋은 상태에 대해 이 프로세스를 반복합니다.

3 METHOD 정리 노트 (AI 연구자 대상)

핵심: 본 섹션은 search 절차의 핵심 구성 요소인 agent backbone, value function, search algorithm을 상세히 설명하고, best-first search를 통해 autonomous web agents의 성능을 향상시키는 방법을 제시합니다.

주요 내용:

문제 재정의: 웹 환경 태스크 해결을 목표 상태(s*)로의 이동으로 해석 (R(s*) = 1). Agent는 초기 상태(s0)에서 자연어 지시(I)에 따라 액션(a0, ..., at)을 실행하여 목표 상태로 이동. 각 액션은 새로운 상태(st+1)와 관찰(ot+1) 생성. 전이 함수(T)는 상태 전이를 제어.
기존 접근 방식의 한계: 부분 관찰 가능 Markov decision process로 취급하여 현재 관찰(ot)에만 의존. 오류 누적 및 잘못된 액션 수정 어려움.
제안 방법: Search와 역추적(backtracking)을 통해 더 나은 궤적 탐색.
- 3.1 AGENT BACKBONE:
  - Large (multimodal) language models를 prompting하여 SOTA web agents 구축.
  - ReAct, RCI, Chain-of-Thought (CoT) 등 prompting 기법 활용.
  - Nucleus sampling 등을 통해 다양한 액션 샘플링.
  - 핵심: 제안된 search 알고리즘은 모든 base agent에 적용 가능하며, inference-time 성능 향상을 보임.
- 3.2 VALUE FUNCTION:
  - Best-first search 휴리스틱 구현을 위해 value function (fv) 사용.
  - Value function: 현재 상태(st)의 예상 보상(E[R(st)]) 추정.
  - 계산: vt = fv(I, {o1, ..., ot}) ∈ [0, 1]. 자연어 지시(I)와 관찰({o1, ..., ot})을 입력으로 사용.
  - 구현: Multimodal language model을 prompting하여 value function 구현.
  - 핵심: Model-based value function을 사용하여 search를 효과적으로 유도.
- 3.3 SEARCH ALGORITHM:
  - A* search에서 영감을 받은 best-first search 방법.
  - Language model agent를 사용하여 search tree의 후보 분기 제안.
  - 하이퍼파라미터: depth (d), branching factor (b), search budget (c), 종료 임계값 (θ).
  - 절차:
    1. 초기화: frontier (F), best state (sˆt), best score (vˆt), search counter (s) 초기화.
    2. 반복:
      - Frontier에서 다음 상태(sp) 추출.
      - Value function으로 sp의 점수(vp) 계산.
      - Search counter 증가.
      - Best score와 best state 업데이트.
      - 종료 조건(vp ≥ θ 또는 s ≥ c) 확인.
      - Depth 초과 여부 확인(|(s0, ..., sp)| < d).
      - Language model agent로 b개의 후보 액션 생성.
      - 각 액션 실행 후 결과 상태를 frontier에 추가.
    3. 종료: 종료 조건 만족 시, best state (sˆt)로 이동.
  - 핵심: Interactive web environment에서 명시적 탐색과 다단계 planning을 통해 불확실성 감소.

차별점:

현실적인 웹 환경에서 inference-time search를 통해 autonomous web agents의 성능 향상.
Model-based value function을 사용하여 search를 효과적으로 유도.
Agent의 액션과 환경의 피드백을 모두 고려한 best-first search 알고리즘.

쉬운 설명 :

이 섹션에서는 AI가 웹사이트에서 작업을 더 잘 수행하도록 돕는 "search" 방법에 대해 자세히 설명합니다. 이 방법은 마치 게임을 할 때 여러 수 앞을 내다보는 것과 비슷합니다.

1. Agent Backbone:

이 방법의 "언어를 이해하는 AI" (large language models)입니다. 이 AI는 웹사이트를 보고 다음에 어떤 행동을 해야 할지 결정합니다.
마치 게임에서 다음 수를 결정하는 것과 같습니다.

2. Value Function:

"Value function" 은 AI가 현재 상황이 얼마나 좋은지를 판단하는 데 사용하는 "점수판" 과 같습니다.
AI는 이 점수판을 보고 어떤 경로가 가장 좋은지를 결정합니다.
마치 게임에서 현재 상황이 얼마나 유리한지를 판단하는 것과 같습니다.

3. Search Algorithm:

"Search Algorithm" 은 AI가 여러 가지 가능한 경로를 탐색하고 가장 좋은 경로를 찾는 방법입니다.
AI는 value function을 사용하여 각 경로의 점수를 계산하고, 가장 높은 점수를 받은 경로를 선택합니다.
마치 게임에서 여러 가지 가능한 수 중에서 가장 좋은 수를 찾는 것과 같습니다.

이 방법의 핵심은 AI가 단순히 현재 상황만 보는 것이 아니라, 여러 수 앞을 내다보고 가장 좋은 경로를 선택하도록 하는 것입니다. 이를 통해 AI는 웹사이트에서 작업을 더 잘 수행할 수 있습니다.

간단히 말해, 이 섹션은 AI가 웹사이트에서 작업을 더 잘 수행하도록 돕는 "search" 방법에 대한 설명서라고 할 수 있습니다. 마치 게임 고수가 게임을 플레이하는 방법을 설명하는 것과 같습니다.

정리

1. 웹 태스크 수행: Agent(AI)에게 웹사이트에서 특정 작업(예: "가장 싼 빨간 차 찾기")을 수행하도록 시킵니다.

2. 프롬프팅 기법: Agent가 똑똑하게 행동하도록 "이렇게 해봐"라는 힌트(prompt)를 줍니다. (예: "단계별로 생각해봐", "이유를 설명해봐")

3. 다양한 액션 생성 (Nucleus Sampling): Agent가 다양한 선택지 중에서 골고루 탐색하도록 합니다. 한 우물만 파는 것보단 여러 우물을 파보는 것이 좋으니까요. (예: "다음" 버튼만 누르지 말고, "검색"도 해보고, 다른 항목도 클릭해 봅니다.)

4. 점수 매기기 (Value Function): 또 다른 AI(또는 같은 AI)에게 현재 상황이 얼마나 좋은지 점수를 매기게 합니다 (0~1점). "이 길이 얼마나 좋은 길인가?"를 판단하는 것입니다.

5. 탐색하기 (Best-first Search): 점수가 높은 길을 우선적으로 탐색합니다. 막다른 길이면 뒤로 돌아가(backtracking) 다른 길을 찾아봅니다. (A* 알고리즘과 유사)

6. 최적 경로 선택: 탐색이 끝나면, 가장 높은 점수를 받은 경로를 따라 이동하여 작업을 완료합니다.