기술 요약: Search-on-Graph (SoG)

문제 정의

지식 그래프(KG)로 증강된 대규모 언어 모델(LLM)은 지식 집약적 추론을 위한 유망한 방안을 제공합니다. 그러나 KG 내에서 추론 경로를 선택하는 기존 방식들은 중대한 한계에 직면해 있습니다: 즉, 선택 과정이 추론 요구사항과 분리되어 있다는 점입니다. 기존의 접근 방식들은 별도의 모듈이나 독립적인 기준(예: 원래 질문과의 의미적 유사성)에 의존하여 관계를 가지치기하거나 선택합니다. 이러한 단절은 두 가지 주요 실패 모드로 이어집니다:

1. 의미적 표류 (Semantic Drift): 선택이 추론 이력이 아닌 표면적인 유사성에 기반하기 때문에, 탐색이 질문에 답하기 위해 필요한 논리적 체인에서 벗어나게 됩니다.
2. 조기 가지치기 (Premature Pruning): 논리적으로는 옳지만 어휘적으로 유사하지 않은 관계들이 조기에 제거되어 추론 과정이 실패하게 됩니다.

또한, 많은 기존 에이전트 방식들은 복잡한 다중 구성 요소 아키텍처(별도의 계획, 검색, 추론 모듈)를 채택하거나 빔 서치(beam search)를 통해 병렬 탐색 경로를 유지하는데, 이는 추론의 타당성을 보장하지 못하면서도 상당한 메모리 오버헤드와 계산 복잡성을 초래합니다.

방법론: Search-on-Graph (SoG)

저자들은 단일 LLM 내에서 경로 선택과 추론을 통합하는 Search-on-Graph (SoG) 프레임워크를 제안합니다. SoG는 관찰-사고-탐색(observe-think-navigate) 패러다임 위에서 작동하며, 여기서 LLM은 완전한 추론 이력과 현재의 로컬 그래프 구조를 바탕으로 정보에 입각한 결정을 내리며 반복적으로 KG를 탐색합니다.

핵심 구성 요소

1. 반복적 1-홉(1-Hop) 탐색:
   SoG는 LLM의 유일한 KG 탐색 인터페이스로서 정교하게 설계된 단일 Search 함수를 활용합니다. 이 함수는 지정된 방향(outgoing 또는 incoming)으로 주어진 엔티티의 1-홉 이웃을 검색합니다.

   • 입력: 엔티티 ID, 방향, 그리고 선택적 필터링을 위한 속성(properties).
   • 출력: 속성 ID, 레이블, 값 ID 및 값 레이블을 포함하는 효율적인 마크다운 테이블.

2. 고차수 노드(High-Degree Nodes) 처리:
   수천 개의 연결을 가진 엔티티(예: 국가, 유명인) 문제를 해결하기 위해, SoG는 2단계 필터링 메커니즘을 사용합니다.

   • 속성 발견 (Property Discovery): 노드가 $k$개 이상의 이웃을 가지고 있고 특정 속성이 요청되지 않은 경우, 시스템은 모든 인스턴스 대신 고유한 속성 유형만을 반환합니다.
   • 타겟형 검색 (Targeted Retrieval): LLM은 가용 속성을 분석하고, 특정 속성을 사용하여 관련 있는 이웃만을 가져오기 위한 두 번째 타겟형 Search 호출을 수행합니다.
   • 절단 (Truncation): 결과가 여전히 임계값 $p$를 초과하면, 컨텍스트 제한에 맞게 리스트를 절단합니다.

3. 컨텍스트 인식 탐색 (Context-Aware Navigation):
   병렬 경로를 유지하는 빔 서치 방식과 달리, SoG는 전체 추론 이력을 바탕으로 각 단계에서 단일 관계를 선택하도록 LLM을 유도합니다. LLM은 현재 엔티티의 이웃을 관찰하고, 어떤 경로가 정답을 진전시킬지 추론하며(예: "나는 Van Gogh로부터 Zundert에 도달했다. 이제 국가를 찾아야 하므로 'Contained by'를 찾는다"), 그에 따라 탐색합니다. 이는 병렬 탐색에서 발생하는 노이즈 누적 없이 논리적 일관성을 보장합니다.

4. 프롬프팅 전략:
   시스템은 에이전트의 역할을 정의하고 세 가지 단계(초기 탐색, 반복적 트래버설, 정답 추출)를 보여주는 몇 가지 퓨샷 예시(typically 5개)를 사용하는 시스템 프로프트를 사용합니다. LLM은 충분한 정보가 수집되었는지 스스로 판단하여 도구 호출을 중단하고 최종 답변을 제공합니다.

주요 기여

1. 통합된 프레임워크: SoG는 단일 LLM이 반복적인 KG 탐색을 조율하는 단순하면서도 효과적인 KGQA 프레임워크를 제안하며, 별도의 계획 또는 검색 모듈의 필요성을 제거합니다.
2. 컨텍스트 인식 탐색: 이 방법은 전체 추론 이력을 바탕으로 탐색을 수행함으로써, Think-on-Graph(ToG)와 같은 컨텍스트가 결여된 가지치기 방식에서 흔히 발생하는 의미적 표류를 방지합니다.
3. 스키마 불가지론 (Schema Agnosticism): 이 접근 방식은 수정이나 태스크별 미세 조정 없이 다양한 KG 스키마(Freebase 및 Wikidata)에 걸쳐 일반화됩니다.
4. 효율성: 병렬 경로를 유지하는 대신 홉당 단일 관계를 선택함으로써, SoG는 빔 서치 베이스라인에 비해 LLM 호출 횟수와 출력 토큰을 크게 줄입니다.

실험 결과

저자들은 Freebase(SimpleQA, WebQSP, CWQ, GrailQA)와 Wikidata(QALD-9, QALD-10)를 아우르는 6개의 KGQA 벤치마크에서 SoG를 평가했습니다.

• 성능: SoG는 태스크별 미세 조정 없이 6개 데이터셋 중 5개에서 최첨단(SOTA) 결과를 달성했습니다.
  • Wikidata 벤치마크에서 이전 최고 방법들보다 11.3% 이상의 상당한 성능 향상을 보여주었습니다.
  • Freebase 데이터셋에서는 이전 시스템들을 능가했으며, CWQ에서는 Generate-on-Graph에 단 0.1% 뒤처졌습니다.
• 백본 견고성: 이 프레임워크는 다양한 LLM 백본과 호환됩니다. GPT-4o를 사용하여 SOTA 성능을 달성했을 뿐만 아니라, 오픈 소스 모델(Qwen3 시리즈)에서도 강력한 결과를 보여주었습니다. 특히, 컴팩트한 Qwen3-4B 모델조차 Wikidata 벤치마크에서 이전 방법들을 능가하여, 모델 크기에 관계한 방법의 유효성을 입증했습니다.
• 효율성: Think-on-Graph 베이스라인과 비교했을 때, SoG는 LLM 호출을 최소 46.4% 줄이고 출력 토큰을 69.9% 줄였으나, 전체 추론 컨텍스트를 유지하기 위해 더 많은 입력 토큰을 필요로 합니다.
• 절제 연구 (Ablation Studies):
  • 퓨샷 학습 (Few-Shot Learning): 단 하나의 내비게이션 예시만으로도 성능이 극적으로 향상되었으며, 3~5개의 예시에서 정체되었습니다.
  • 모델 유형: "사고(Thinking)"에 최적화된 모델이 표준 지시 미세 조정 모델보다 특히 멀티 홉 태스크에서 일관되게 우수한 성능을 보였습니다.
  • 출력 형식: 제안된 "마크다운 + 속성 필터" 형식이 정확도와 토큰 효율성 사이에서 최적의 균형을 달성했습니다.

의의 및 주장

이 논문은 Search-on-Graph가 별도의 선택 모듈이나 사전 계획에 의존하는 방법보다 LLM 주도 탐색이 지식 그래프 추론에 있어 더 우월한 새로운 패러다임을 검증한다고 주장합니다.

저자들은 실제 추론 요구사항과 전체 컨텍스트를 바탕으로 각 단계에서 가장 적절한 관계를 선택하는 데 단일 LLM이 더 적합하다는 가정이 타당하다고 주장합니다. 이 접근 방식은 아키텍처를 단순화하고, 계산 오버헤드를 줄이며, 다양한 KG 스키마와 모델 크기에 효과적으로 일반화됩니다. 결과는 정교한 다중 구성 요소 시스템보다 세심한 컨텍스트 관리와 결합된 아키텍처의 단순성이 더 뛰어난 성능을 낼 수 있음을 시사합니다.