기술 요약: LoHoSearch

문제 정의

BrowseComp와 같은 검색 에이전트 벤치마크는 가장 진보된 모델조차 90% 이상의 정확도를 달 기록하며 "난이도 천장(difficulty ceiling)"에 빠르게 도달했습니다. 이러한 포화 상태의 근본 원인은 인간이 작성한 질문에 의존한다는 점에 있습니다. 인간 주석가들은 엔티티 통계에 대한 전역적 관점이 부족하여, 인지도가 높고 직접적인 연결성을 가진 친숙한 엔티티를 선택하는 경향이 있습니다. 결과적으로, 이러한 벤치마크들은 검색 난이도를 결정하는 두 가지 핵심 요소인 다음을 체계적으로 극대화하지 못합니다:

1. 검색 공간 크기(Search Space Size): 단일 제약 조건을 만족하는 후보 엔티티의 수.
2. 구조적 복잡성(Structural Complexity): 정답을 유일하게 식별하기 위해 공동으로 만족해야 하는 제약 조건의 수.

추론 깊이(지식 홉, knowledge hops)는 기존 벤치마크에서 잘 다루어졌지만, 거대한 검색 공간과 높은 구조적 복잡성이 결합된 형태는 현재의 에이전트들이 어려움을 겪는 "장기적 지평(long-horizon)" 과제를 생성합니다. 그러나 인간의 구성 방식으로는 이를 신뢰성 있게 확장할 수 없습니다.

방법론

인간 저작의 한계를 극복하기 위해, 저자들은 대규모 지식 그래프(KG)에 기반한 자동화된 파이프라인을 통해 구축된 LoHoSearch(Long-Horizon Search Agents)를 소개합니다.

1. 지식 그래프 구축

파이프라인은 영어 위키피디아 전체 덤프를 활용하여 약 762만 개의 엔티티와 **2억 6,500만 개의 유향 엣지(directed edges)**를 포함하는 KG를 구축합니다.

• 노드(Nodes): 위키피디아 페이지.
• 엣지(Edges): 페이지 간의 하이퍼링크.
• 속성(Attributes): 각 엔티티에는 유형(Wikidata P31을 통해)과 인기도 지표(in-degree)가 할당됩니다.

2. 서브그래프 샘采样 (Subgraph Sampling)

시스템은 쉬운 추론을 방지하기 위해 낮은 엔티티 인기도를 보장하도록 KG에서 두 가지 유형의 서브그래프를 샘플링하여 질문의 기초로 삼습니다.

• 트리 구조 서브그래프(Tree-Structured Subgraphs): 루트 노드(정답)가 중간 노드에 연결되고, 이들이 다시 리프 노드에 연결되는 구조입니다. 제약 조건은 다음을 보장하도록 선택됩니다:
  • 각 관계가 큰 검색 공간($|S| > \tau$)을 가질 것.
  • 모든 관계에 대한 후보 집합의 교집합이 정확히 루트 노드와 일치할 것(유일성 보장).
  • 단 하나의 관계만 제거하더라도 여러 명의 후보가 남을 것(모든 관계가 필수적임을 보장).
• 그래프 구조 서브그래프(Graph-Structured Subgraphs): 이는 순환 의존성(cyclic dependencies)과 교차 제약 조건을 도입하여 문제를 비분해적(non-decomposable)으로 만듭니다. 이들은 연결성과 유형 다양성을 유지하면서 엣지 수와 검색 공간 크기를 최대화하도록 탐욕적(greedily)으로 구축됩니다.

3. QA 생성 및 검증

• 은폐(Obfuscation): 각 서브그래프의 엣지에 대해, LLM은 소스 엔티티의 위키피디아 페이지에서 관계에 대한 자연어 설명을 추출합니다. 리프 노드의 경우 추가적인 속성 설명이 더해집니다.
• 검색 검증(Search Verification): 관계들이 검색 엔진을 통해 직접 위치를 찾거나, 질문의 특정 맥락 없이 LLM에 의해 추론될 수 없음을 확인하기 위해 검증 과정을 거칩니다.
• 유일성 검증(Uniqueness Verification): 시스템은 전체 KG에 대해 철저한 백트래킹 탐색을 수행하여, 동일한 구조적 제약을 만족하는 다른 엔티티 집합이 존재하지 않음을 확인합니다.
• 인간 검토(Human Review): 최종 544개의 질문은 정답의 정확성, 유일성, 논리적 일관성 및 언어적 유창성을 검증하기 위해 전문적인 인간 검토를 거칩니다.

주요 기여

1. 자동화된 구축 파이프라인: 검색 공간 크기와 구조적 복잡성을 체계적으로 제어하여, 인간 저작 벤치마크에 내재된 난이도 천장을 깨뜨리는 지식 그래프 기반의 파이프라인을 제공합니다.
2. LoHoSearch 벤치마크: 11개의 주제 영역(예: 음악, 지리, 영화)에 걸친 544개의 인간 검증 질문 데이터셋입니다. 이는 KG로 검증된 유일한 정답을 가진 구조적으로 복잡한 서브그래프(트리 및 그래프 유형 모두)를 특징으로 합니다.
3. 문맥 관리 평가: 이 벤치마크는 장기적 추론 및 문맥 관리 전략을 평가하기 위한 엄격한 테스트베드 역할을 하며, 고난도 시나리오에서의 한계를 드러냅니다.

실험 결과

저자들은 LoHoSearch를 통해 다양한 최첨단 모델(GPT-5.5, DeepSeek-V4-Pro, Claude-Opus-4.6 포함)을 평가했습니다.

• 성능 천장: 가장 강력한 모델인 GPT-5.5조차 **34.74%**의 정확도만을 달성했습니다. 대부분의 모델은 14% 미만의 점수를 기록했으며, 일부(예: MiniMax-M2.5)는 2.29%까지 낮았습니다.
• 도구 사용(Tool Usage): LoHoSearch에서의 올바른 궤적은 BrowseComp보다 훨씬 더 많은 도구 호출을 요구했습니다. 평균 도구 호출 횟수는 BrowseComp의 35회에서 61회로 증가하여 74%의 상대적 증가를 보였습니다.
• 문맥 관리의 한계: 저자들은 DeepSeek-V4-Flash를 대상으로 다양한 문맥 관리 전략(요약, 전체 삭제, 검증)을 테스트했습니다.
  • BrowseComp에서는 이러한 전략들이 **14.03%**의 이득을 가져왔습니다.
  • LoHoSearch에서는 최적의 전략(전체 삭제 + 검증)이 겨우 **6.8%**의 이득(10.02%에서 16.82%로)만을 제공했습니다.
  • 이는 현재의 문맥 관리 기술이 LoHoSearch에서 요구되는 확장된 추론 체인에는 불충분함을 시사합니다.
• 구조적 복잡성: 그래프 구조 질문(8.01% 정확도)은 트리 구조 질문(11.89% 정확도)보다 훨씬 더 어렵다는 것이 증명되었으며, 이는 순환 의존성의 영향을 강조합니다.
• 병렬 샘플링(Parallel Sampling): 16개의 샘플을 사용하는 "best-of-N" 전략을 사용했을 때 성능이 24.6%로 향상되었으며, 이는 반복적인 샘플링을 통해 개선의 여지가 상당함을 나타내지만, 여전히 쉬운 벤치마크에서의 인간 수준 성능에는 훨씬 못 미칩니다.

의의 및 주장

본 논문은 LoHoSearch가 검색 에이전트를 평가하기 위한 더 까다롭고 변별력 있는 표준을 제공한다고 주장합니다. 지식 그래프를 활용하여 검색 공간과 구조적 복잡성을 체계적으로 극대화함으로써, LoHoSearch는 현재의 모델들이 쉽게 극복할 수 없는 난이도를 성공적으로 구축했습니다.

저자들은 LoHoSearch가 다음과 같은 이유로 중요하다고 주장합니다:

1. 기존 문맥 관리 전략의 한계를 노출하며, 이전 벤치마크에서 관찰된 이득이 고난도 장기 과제로는 전이되지 않음을 보여줍니다.
2. 인간의 주석 작업이 진정으로 어려운 질문을 만드는 데 있어 규모를 확장할 수 없음을 입증하며, 전역적인 통계적 관점의 부재로 인해 자동화된 KG 기반 구축이 필요함을 보여줍니다.
3. 가장 진보된 모델들조차 고전하는 **새로운 기준선(baseline)**을 설정하여, 장기적 추론 및 견고한 문맥 처리에 관한 미래 연구를 위한 필수적인 테스트베드를 제공합니다.

저자들은 영어로 제한된 범위, 평가 세트의 정적인 특성, 그리고 노이즈를 유발할 수 있는 LLM 판정기(judge)에 대한 의존성을 포함한 한계점을 인정합니다. 또한, 일부 질문의 경우 인간 주석가가 정답의 유일성을 확정적으로 확인할 수 없었으나, 철저한 검색을 통해서도 대안을 찾을 수 없었음을 언급했습니다.