1. 문제 정의 (Problem Statement)

기존의 웹 에이전트 (Web Agents) 는 대부분 웹사이트의 루트 URL(홈페이지) 에서 탐색을 시작합니다. 그러나 현실 세계의 웹사이트는 계층 구조가 깊고 페이지 수가 방대하여, 루트에서 시작하는 방식은 다음과 같은 비효율성을 초래합니다.

• 비효율적인 탐색: 관련 없는 하위 트리를 탐색하거나, 탐색 함정 (navigation traps) 에 빠지는 경우가 빈번함.
• 예산 낭비: 제한된 행동 예산 (navigation budget) 내에서 목표 정보에 도달하지 못하거나, 중간 페이지에 에너지를 낭비함.
• 국소적 관점: 각 단계에서의 부분적 관측 (partial observation) 만으로는 웹사이트의 전체 구조를 파악하지 못해 최적의 진입점을 찾기 어려움.

2. 제안 방법론: MANGO (Methodology)

MANGO 는 웹사이트의 **전역 구조 (Global View)**를 활용하여 최적의 시작점을 동적으로 결정하는 멀티 에이전트 웹 탐색 프레임워크입니다. 주요 구성 요소는 다음과 같습니다.

2.1 전역 구조 분석 (Global Structure Analysis)

• 가벼운 크롤링: BFS(너비 우선 탐색) 를 통해 루트 URL 로부터 도달 가능한 URL 집합을 수집하고, 도메인 내 페이지만 필터링합니다.
• 검색 기반 확장: 크롤링만으로는 모든 페이지를 커버하기 어려운 경우 (예: arXiv), LLM 을 사용하여 사용자 쿼리에 맞는 검색 키워드를 생성하고, Google Search 의 site: 연산자를 통해 추가적인 관련 URL 을 확보합니다.
• 후보군 선정: BM25 알고리즘을 사용하여 쿼리와 콘텐츠의 의미적 유사성을 점수화하고, 상위 10 개의 URL 을 후보 집합 ($U$) 으로 선정합니다.

2.2 URL 우선순위 지정 및 선택 (URL Prioritization and Selection)

• 다중 암 밴딧 (Multi-Armed Bandit, MAB) 모델링: 제한된 예산 하에서 어떤 URL 을 탐색할지 결정하는 문제를 MAB 문제로 형식화합니다.
• Thompson Sampling: 각 URL(암) 에 대한 성공 확률을 베타 분포 (Beta Distribution) 로 모델링합니다.
  • 초기화: BM25 점수를 기반으로 베타 분포의 파라미터 ($\alpha, \beta$) 를 초기화합니다.
  • 동적 업데이트: 탐색 시도 후 '반성 에이전트 (Reflection Agent)'의 피드백에 따라 성공/실패를 베르누이 보상 ($r \in \{0, 1\}$) 으로 간주하여 분포를 업데이트합니다.
  • 소진 (Exhaustion): 탐색이 막다른 길에 도달했음을 판단하면 해당 URL 을 '소진' 상태로 표시하여 재선택을 방지합니다.

2.3 웹 탐색 에이전트 (Web Navigation Agent)

• 선정된 URL 에서 브라우저 환경과 상호작용하며 작업을 수행합니다.
• ** episodic memory:** 이전 탐색 경로와 반성 (reflection) 정보를 저장하여, 동일한 URL 을 다시 방문할 때 불필요한 행동을 반복하지 않도록 합니다.

2.4 반성 에이전트 (Reflection Agent)

• 탐색 경로와 최종 출력을 분석하여 다음 단계를 결정합니다.
• 상태 평가: 작업이 완료되었는지, 예산이 소진되었는지, 혹은 추가 탐색이 필요한지 판단합니다.
• 보상 부여: 유망한 경로라면 긍정적 보상 ($r=1$) 을, 실패한 경로라면 부정적 보상 ($r=0$) 을 주어 Thompson Sampling 의 확률 분포를 갱신합니다.

3. 주요 기여 (Key Contributions)

1. 전역 구조 기반 진입점 최적화: 루트 URL 에서 시작하는 기존 방식과 달리, 웹사이트의 전역 구조를 분석하여 쿼리 관련성이 높은 진입점을 사전에 선별합니다.
2. 적응형 예산 할당 알고리즘: Thompson Sampling 을 활용하여 제한된 탐색 예산을 가장 유망한 URL 들에 동적으로 할당하는 메커니즘을 제안했습니다.
3. 반복 방지 메모리 시스템: episodic memory 를 도입하여 실패한 탐색 경로를 학습하고, 에이전트가 동일한 실수를 반복하는 것을 방지합니다.
4. 광범위한 실험 검증: 오픈소스 (Qwen3 시리즈) 와 폐쇄소스 (GPT-5-mini) 모델을 모두 백본으로 사용하여 다양한 환경에서 성능을 입증했습니다.

4. 실험 결과 (Results)

두 가지 벤치마크 (WebVoyager, WebWalkerQA) 에서 SOTA(SOTA) 방법론인 AgentOccam 과 WebWalker 와 비교 평가되었습니다.

• 성공률 (Success Rate, SR):
  • WebVoyager: GPT-5-mini 사용 시 **63.6%**의 성공률을 기록하여, 기존 최우수 베이스라인 (AgentOccam) 보다 7.3%p 향상되었습니다.
  • WebWalkerQA: GPT-5-mini 사용 시 **52.5%**의 성공률을 기록하여, 기존 최우수 베이스라인보다 26.8%p라는 압도적인 개선을 보였습니다. 특히 단일 소스 및 다중 소스 QA 모두에서 뛰어난 성능을 발휘했습니다.
• 효율성 (Action Count):
  • Qwen3 모델 기반 시에는 경쟁력 있거나 더 적은 행동 횟수로 높은 성공률을 달성했습니다.
  • GPT-5-mini 기반 시에는 행동 횟수가 다소 증가했으나, 이는 더 복잡하고 긴 시간 (long-horizon) 이 필요한 과제를 해결하기 위한 투자로, 전체적인 성공률 향상으로 이어졌습니다.
• Ablation Study:
  • 무작위 URL 선택, 검색 기반 선택, MCTS(Monte Carlo Tree Search) 기반 탐색 등 변형 모델과 비교하여, MANGO 의 전역 구조 분석과 Thompson Sampling 조합이 가장 효과적임을 입증했습니다.

5. 의의 및 결론 (Significance)

• 탐색 전략의 패러다임 전환: 웹 에이전트가 단순히 "어떻게 클릭할지"를 결정하는 것을 넘어, **"어디서부터 시작할지"**를 전역적 관점에서 최적화하는 새로운 접근법을 제시했습니다.
• 제한된 자원 하의 최적화: 제한된 행동 예산 (budget) 내에서 탐색 효율을 극대화하는 Thompson Sampling 기반의 의사결정 메커니즘은 실제 웹 자동화 환경에 매우 실용적입니다.
• 일반화 가능성: 다양한 크기의 LLM 백본에서 일관된 성능 향상을 보여주어, 모델 크기에 구애받지 않는 강력한 프레임워크임을 입증했습니다.

한계점: 매우 크고 동적인 웹사이트 (수십만 페이지) 의 경우 가벼운 크롤링만으로는 전 구조를 완벽하게 파악하기 어렵고, 초기 후보군 선정의 오류가 예산 낭비로 이어질 수 있다는 점이 지적되었습니다. 또한, 복잡한 추론 오류는 탐색 전략 개선만으로는 해결되지 않습니다.

결론적으로, MANGO 는 복잡한 웹사이트 구조를 가진 환경에서 웹 에이전트의 성공률을 획기적으로 높일 수 있는 효과적인 솔루션입니다.