STRUCTUREDAGENT: Planning with AND/OR Trees for Long-Horizon Web Tasks

이 논문은 긴 시간 범위의 웹 작업을 위해 동적 AND/OR 트리를 활용한 계층적 계획과 구조화된 기억 모듈을 도입하여 기존 에이전트의 계획 능력과 메모리 한계를 극복하고 성능을 향상시킨 'STRUCTUREDAGENT' 프레임워크를 제안합니다.

핵심

🌐 STRUCTUREDAGENT: 웹을 탐험하는 '지혜로운 나침반'

이 논문은 인공지능 (AI) 이 복잡한 웹 작업을 할 때 자주 겪는 실수를 해결하기 위해 개발된 새로운 방법, STRUCTUREDAGENT에 대해 설명합니다.

기존의 AI 는 웹을 돌아다니다가 길을 잃거나, 너무 성급하게 결론을 내리거나, 중요한 정보를 잊어버리는 경우가 많았습니다. 이 논문은 AI 가 인간처럼 계획을 세우고, 실패하면 다시 생각하고, 중요한 정보를 정리해두는 방식을 도입했습니다.

이 개념을 쉽게 이해할 수 있도록 세 가지 핵심 비유로 설명해 드리겠습니다.

---

1. 🌲 거대한 '의사결정 나무' (AND/OR 트리)

"한 번에 모든 길을 다 갈 수는 없지만, 나무처럼 가지치기를 하면 되잖아!"

기존의 AI 는 미로에 들어갈 때, 한 번 선택한 길을 끝까지 가다가 막히면 다시 처음부터 시작하거나, 그냥 포기하는 경우가 많았습니다. 마치 미로에서 길을 잃은 사람처럼요.

하지만 STRUCTUREDAGENT는 **'의사결정 나무 (Tree)'**를 그려갑니다.

• AND(그리고) 노드: "이 일을 하려면 A 와 B 둘 다 성공해야 해." (예: 레시피를 찾으려면 '재료 찾기'와 '조리법 보기'를 모두 해야 함)
• OR(또는) 노드: "A 가 안 되면 B 를 시도해 봐." (예: '레시피 A'가 없으면 '레시피 B'를 찾아보자)

이 나무는 동적으로 변합니다. 한 가지 길이 막히면 (실패하면), AI 는 나무의 그 가지를 잘라내고 (Pruning) 다른 가지를 시도합니다. 마치 정원사가 죽은 가지를 잘라내고 건강한 가지를 키우는 것처럼, 실수를 바로잡고 효율적으로 길을 찾는 것입니다.

2. 📝 '정리된 메모장' (Structured Memory)

"주방에 재료를 아무렇게나 던져두면 요리할 수 없잖아? 정리해두자!"

웹을 돌아다니는 동안 AI 는 수많은 정보를 접합니다. "이 제품은 50 달러야", "저 제품은 별점 4.5 점이야" 같은 정보들이죠. 기존 AI 는 이 정보를 기억하지 못해, 이미 본 제품을 다시 찾거나 조건에 맞지 않는 제품을 고르는 실수를 했습니다.

STRUCTUREDAGENT는 **'구조화된 메모장'**을 사용합니다.

• 마치 요리사가 재료를 상자별로 정리해두는 것처럼, 찾은 정보들을 '가격', '별점', '브랜드' 같은 칸에 깔끔하게 정리해 둡니다.
• 이 메모장을 보면서 "아, 이 제품은 50 달러를 넘어서서 조건에 안 맞네. 저걸 제외하고 다른 걸 찾아야지"라고 스스로 판단합니다.
• 이렇게 하면 중복 작업을 줄이고, 복잡한 조건 (예: "300 달러 이하이면서 별점 4.5 이상인 노트북 3 개") 을 정확히 충족할 수 있습니다.

3. 🛠️ '수리 가능한 지도' (동적 계획 수정)

"지도가 틀리면, 그 자리에서 고쳐서 다시 출발하자!"

기존 AI 는 계획을 세우고 나면 그 계획을 고수하다가 실패하는 경우가 많았습니다. 하지만 STRUCTUREDAGENT 는 계획을 유연하게 수정합니다.

• 만약 AI 가 "A 쇼핑몰에서 물건을 찾자"고 계획했는데, 그 쇼핑몰이 문을 닫았거나 물건을 찾지 못했다면?
• AI 는 즉시 **"아, 이 계획은 실패했구나"**라고 인정하고, 나무의 해당 부분을 고쳐서 B 쇼핑몰로 가는 새로운 가지를 추가합니다.
• 이 과정에서 사람이 개입할 수도 있습니다. AI 가 엉뚱한 방향으로 가고 있다면, 사람이 "아니, 그건 아니야. 이렇게 해봐"라고 나무의 가지를 직접 고쳐줄 수 있습니다. (인간이 AI 의 실수를 바로잡아주는 '코치' 역할)

---

🏆 왜 이것이 중요한가요? (결과)

이 방법을 적용한 결과, STRUCTUREDAGENT 는 다음과 같은 성과를 거두었습니다:

1. 오래 걸리는 복잡한 작업 (Long-Horizon Tasks) 에서 강세: 단순히 "구글 검색"을 하는 것은 쉽지만, "아마존에서 300 달러 이하인 노트북 3 개를 찾아서 비교하고, 별점 4.5 이상인 것만 추천해줘" 같은 복잡한 작업에서는 기존 AI 들보다 훨씬 잘했습니다.
2. 실수에서 빨리 회복: 길을 잃거나 실수를 해도, 나무를 고치고 메모장을 정리하며 다시 길을 찾습니다.
3. 사람이 이해하기 쉬움: AI 가 왜 그런 결정을 내렸는지, 어떤 가지를 선택하고 어떤 가지를 잘랐는지 그 '나무'를 보면 사람이 쉽게 이해하고 도와줄 수 있습니다.

💡 한 줄 요약

STRUCTUREDAGENT는 웹을 돌아다니는 AI 에게 '나무처럼 계획을 세우고', '메모장에 정보를 정리하며', '실수하면 즉시 고치는' 지혜를 심어주어, 복잡한 웹 작업을 인간처럼 똑똑하게 수행하게 만든 혁신적인 방법입니다.

기술 요약

1. 문제 정의 (Problem)

최근 대규모 언어 모델 (LLM) 의 발전으로 웹 에이전트 (Web Agents) 가 복잡한 순차적 의사결정 작업을 수행할 수 있게 되었으나, 장기적 시야 (Long-Horizon) 의 웹 탐색 작업에서는 여전히 심각한 한계를 보입니다. 기존 에이전트들이 겪는 주요 문제는 다음과 같습니다.

• 제한된 컨텍스트 메모리: 웹 페이지는 종종 20,000 토큰을 초과하는 긴 내용을 가지며, 에이전트는 현재 페이지와 행동 이력만 기억합니다. 이로 인해 여러 페이지에 걸친 대안적 해결 경로를 추적하거나 복잡한 제약 조건을 유지하는 데 실패합니다.
• 약한 계획 능력: 에이전트가 복잡한 다단계 계획을 구성하고 실행하는 능력이 부족합니다.
• 탐욕적 (Greedy) 행동: 에이전트가 모든 사용자 제약을 충족하기 전에 작업을 조기에 종료하는 경향이 있습니다.
• 오류 처리 부재: 실패 시 복구하거나 대안을 탐색하는 강력한 메커니즘이 부족하여, 작은 실수가 전체 작업 실패로 이어집니다.

2. 방법론 (Methodology)

저자들은 이러한 문제를 해결하기 위해 STRUCTUREDAGENT라는 계층적 계획 프레임워크를 제안합니다. 이 프레임워크는 LLM 을 단순히 전체 계획을 생성하는 도구로 사용하는 대신, 명시적인 AND/OR 트리 구조를 기반으로 에이전트의 사고와 행동을 구조화합니다.

핵심 구성 요소

1. AND/OR 계층적 계획 트리 (Hierarchical Planning Tree):

   • AND 노드: 하위 목표 (Subgoals) 가 모두 성공해야 부모 노드가 성공하는 논리적 결합을 나타냅니다.
   • OR 노드: 여러 대안 전략 중 하나라도 성공하면 부모 노드가 성공하는 논리적 선택을 나타냅니다.
   • ACTION 노드: 브라우저 수준의 구체적인 행동 (클릭, 입력, 스크롤 등) 을 수행하는 리프 노드입니다.
   • 이 구조는 에이전트가 작업을 재귀적으로 분해하고, 대안 경로를 명시적으로 추론하며, 실패 시 백업 계획을 가질 수 있게 합니다.

2. 동적 탐색 알고리즘 (Modified Greedy DFS):

   • 기존 DFS 를 변형하여 **ENTERING(진입), EXITING(종료), FAILED(실패)**의 세 가지 상태를 도입했습니다.
   • 에이전트는 트리를 점진적으로 확장하고, 실패 시 노드 복구 (Repair) 또는 **가지치기 (Pruning)**를 수행합니다.
   • 실패가 발생하면 오류가 상위 노드로 전파되어 전체 계획의 일관성을 유지하며 재계획을 수행합니다.

3. 구조화된 메모리 모듈 (Structured Memory):

   • 정보 탐색 작업 (예: 특정 조건을 만족하는 제품 찾기) 에서 에이전트가 발견한 후보 항목 (Candidate Entities) 과 해당 제약 조건 충족 상태를 동적 테이블로 관리합니다.
   • 이 모듈은 에이전트가 이전에 발견한 항목을 잊어버리거나, 조건을 만족하지 않는 항목을 반복해서 탐색하는 것을 방지합니다.

4. LLM 의 역할 분리:

   • 전체 트리 구조를 LLM 에게 맡기는 대신, 프레임워크가 트리의 관리 (탐색, 가지치기, 상태 업데이트) 를 담당합니다.
   • LLM 은 노드 확장 (Node Expansion), 복구 (Repair), 완료 확인 (Completion Check) 등 구체적이고 정의된 하위 작업에만 호출되어 추론의 해석 가능성과 견고성을 높입니다.

3. 주요 기여 (Key Contributions)

1. 순서화된 AND/OR 트리를 통한 인시던트 타임 계획 (Inference-time Planning):
   • 에이전트가 실행 중에 동적으로 계획을 구성하고 수정할 수 있는 계층적 프레임워크를 제안했습니다. 이는 구성적 추론, 동적 계획 수정, 오류 역전파를 지원하며, 인간이 개입하여 오류를 수정하거나 디버깅하기 쉬운 해석 가능한 계획을 생성합니다.
2. 정보 탐색을 위한 구조화된 메모리 모듈:
   • 정보 탐색 작업에서 후보 엔티티와 충족된 제약 조건을 추적하여 계획 및 실행 중 제약 조건 충족률을 향상시키는 모듈을 개발했습니다.
3. 광범위한 벤치마크에서의 검증:
   • WebVoyager, WebArena, 그리고 커스텀 쇼핑 벤치마크 (Amazon 쇼핑 작업) 에서 기존 LLM 기반 에이전트 (AgentOccam, SteP 등) 보다 우수한 성능을 입증했습니다.

4. 실험 결과 (Results)

• 성능 향상:
  • Amazon Easy/Hard: STRUCTUREDAGENT 는 AgentOccam 대비 Amazon Easy 에서 14%, Amazon Hard 에서 인간 평가 기준 7% 이상 높은 성공률을 기록했습니다.
  • WebArena: 쇼핑 (Shopping) 및 레딧 (Reddit) 카테고리에서 모든 베이스라인을 능가했으며, 전체 평균 성공률 (52.6%) 에서 가장 높은 성과를 보였습니다.
  • 모델 일반화: Claude 3.5, Claude 3.7, Kimi-k2 등 다양한 LLM 백본에서 일관된 성능 향상을 보여주어 프레임워크의 일반화 능력을 입증했습니다.
• 효율성 및 행동 분석:
  • 복잡한 작업 (Amazon Hard) 에서는 더 많은 행동을 취하지만, 이는 실패한 경로를 체계적으로 탐색하고 대안을 시도하는 과정으로, 단순한 무작위 탐색이 아닌 전략적 탐색을 의미합니다.
  • 구조화된 메모리를 사용할 경우, 복잡한 다중 제약 조건이 있는 작업에서 성능이 추가로 향상되었습니다.
• 오류 복구 및 인간 개입:
  • 에이전트가 잘못된 하위 목표 분해를 할 경우, 인간이 AND/OR 트리에 개입하여 수정된 하위 목표를 주입하면 에이전트가 이를 수용하여 성공적으로 작업을 완료할 수 있음을 시연했습니다.

5. 의의 (Significance)

이 논문은 웹 에이전트의 핵심적인 한계인 장기적 계획 능력과 오류 복구 능력을 해결하기 위해, LLM 의 추론 능력을 명시적인 검색 알고리즘 (AND/OR 트리) 과 결합한 새로운 패러다임을 제시합니다.

• 해석 가능성 (Interpretability): 에이전트의 내부 의사결정 과정을 트리 구조로 시각화하여, 왜 특정 행동을 취했는지, 어디서 실패했는지를 명확히 파악할 수 있게 합니다. 이는 인간과의 협업 (Human-in-the-loop) 을 용이하게 합니다.
• 견고성 (Robustness): 동적 계획 수정과 구조화된 메모리를 통해 웹 환경의 불확실성과 긴 작업 시야에 대응하는 능력을 크게 향상시켰습니다.
• 실용성: 복잡한 정보 검색, 쇼핑, 데이터 수집 등 실제 비즈니스 환경에서 요구되는 장기적 웹 태스크를 자동화하는 데 있어 기존 방법론보다 훨씬 신뢰할 수 있는 솔루션을 제공합니다.

결론적으로, STRUCTUREDAGENT 는 LLM 기반 에이전트가 단순한 반응형 시스템에서 계획적이고 적응적인 자율 에이전트로 발전하기 위한 중요한 기술적 토대를 마련했습니다.