💬 NLP

Explore-on-Graph: Incentivizing Autonomous Exploration of Large Language Models on Knowledge Graphs with Path-refined Reward Modeling

이 논문은 지식 그래프 기반 질문 응답에서 LLM 의 환각을 줄이고 일반화 성능을 향상시키기 위해, 강화 학습과 경로 정제 보상 모델을 통해 LLM 이 자율적으로 다양한 추론 경로를 탐색하도록 유도하는 'Explore-on-Graph(EoG)' 프레임워크를 제안하고, 이를 통해 여러 벤치마크에서 최첨단 성능을 달성했음을 보여줍니다.

원저자: Shiqi Yan, Yubo Chen, Ruiqi Zhou, Zhengxi Yao, Shuai Chen, Tianyi Zhang, Shijie Zhang, Wei Qiang Zhang, Yongfeng Huang, Haixin Duan, Yunqi Zhang

게시일 2026-02-26

📖 3 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Shiqi Yan, Yubo Chen, Ruiqi Zhou, Zhengxi Yao, Shuai Chen, Tianyi Zhang, Shijie Zhang, Wei Qiang Zhang, Yongfeng Huang, Haixin Duan, Yunqi Zhang

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

🗺️ 지식 지도 탐험가: "EoG"가 어떻게 AI를 똑똑하게 만드는가?

이 논문은 **"지식 그래프 (Knowledge Graph)"**라는 거대한 지도 위에서 **대형 언어 모델 (LLM, AI)**이 어떻게 더 똑똑하게 추론할 수 있는지 설명하는 연구입니다.

기존의 AI들은 종종 **"망상 (Hallucination)"**이라는 병에 걸려, 사실과 다른 엉뚱한 답을 내놓곤 했습니다. 이 문제를 해결하기 위해 연구팀은 AI에게 **"자신만의 탐험가 정신"**을 심어주는 새로운 방법, **EoG (Explore-on-Graph)**를 제안했습니다.

🧩 1. 문제: AI는 왜 '정해진 길'만 걷나요?

기존의 AI 추론 방식은 두 가지 큰 단점이 있었습니다.

규칙 따르기 (Rule-based): "A 에서 B 로 가면 C 가 나온다"는 정해진 규칙만 따르게 했습니다. 마치 유치원생이 선생님이 그린 선만 따라 그리는 그림과 같습니다.
모방하기 (Imitation-based): 다른 AI 가 잘한 답을 보고 따라 하는 것입니다. 마치 유명한 요리사의 레시피를 그대로 복사하는 것과 비슷합니다.

🚨 문제점:
세상은 복잡합니다. 질문이 "구글 직원이 런던에 사는 사람은 누구인가?"일 때, 보통은 "직접적인 고용 관계"로 답하지만, 가끔은 **"동료 (Colleague)"**나 **"자회사 (Subsidiary)"**를 통해 연결된 길을 찾아야 할 때도 있습니다.
기존 AI 는 배운 적 없는 (Out-of-Distribution) 새로운 길이나 복잡한 연결고리를 만나면 당황해서 엉뚱한 답을 내놓거나, 아예 길을 잃어버립니다.

🚀 2. 해결책: EoG (지식 위 탐험)

연구팀은 AI 에게 **"정해진 길만 걷지 말고, 지도를 직접 탐험해 보라!"**고 가르쳤습니다. 이를 위해 두 단계의 훈련을 시켰습니다.

📚 1 단계: 기초 체력 다지기 (SFT - 지도 읽기 연습)

먼저 AI 에게 정답이 있는 예제를 보여주며 "지식 지도를 어떻게 읽고, 논리적으로 생각해야 하는지"를 가르쳤습니다.

비유: 마치 등산 학교에서 지도 보는 법과 등산로 기본 규칙을 배우는 단계입니다.

⚡ 2 단계: 자율 탐험과 보상 (RL - 실전 훈련)

이제 AI 를 혼자서 탐험하게 합니다. 이때 중요한 것은 **'보상 시스템 (Reward)'**입니다.

기존 방식: "정답을 맞췄으면 점수 줌" (결과만 봄).
EoG 의 방식: "정답을 맞췄을 뿐만 아니라, **어떻게 그 길을 찾았는지 (경로)**도 점수에 반영함".

✨ 핵심 아이디어: "경로 정제 보상 (Path-Refined Reward)"
AI 가 엉뚱한 길로 돌아다니면 점수를 깎고, **올바른 논리적 연결고리 (예: A→B→C)**를 따라갔다면 보너스 점수를 줍니다.

비유: 등산객이 **정답인 정상 (정답)**에 도달하는 것도 중요하지만, **올바른 등산로 (논리적 경로)**를 따라 올라갔을 때 더 큰 상금을 주는 것과 같습니다. 이렇게 하면 AI 는 헛걸음 (무의미한 탐험) 을 줄이고, 효율적이고 의미 있는 탐험을 하게 됩니다.

🏆 3. 결과: 왜 EoG 가 특별한가요?

이 방법을 적용한 AI 는 놀라운 성과를 냈습니다.

새로운 길 발견: 기존에 배운 적이 없는 복잡한 질문 (예: "일본에서 수입하는 국가는?"인데 중간에 숨은 연결고리가 있는 경우) 도 스스로 찾아냈습니다.
타고난 능력: 오픈소스 모델 (Qwen, Llama 등) 이지만, 구글의 Gemini나 OpenAI 의 GPT-5 같은 거대 상용 모델보다 더 좋은 성적을 냈습니다.
효율성: 엉뚱한 길을 헤매는 시간을 줄이고, 정답에 도달하는 데 필요한 노력을 최소화했습니다.

💡 4. 한 줄 요약 (비유로 정리)

기존 AI: "선생님이 알려준 길 (레시피) 만 따라가서, 새로운 길은 못 찾는다."

EoG (우리 방법): "지도는 주었지만, 정답을 찾으면 상금도 주되, 올바른 길을 걸었는지도 심사한다."

결과: AI 는 이제 스스로 새로운 길을 개척하는 탐험가가 되어, 복잡한 질문에도 정확하고 논리적인 답을 찾아냅니다.

이 연구는 AI 가 단순히 지식을 암기하는 것을 넘어, 지식 그래프 위에서 스스로 생각하고 탐험하는 능력을 키우는 새로운 기준을 제시했습니다.

Explore-on-Graph (EoG): 지식 그래프 기반 LLM 자율 탐색을 위한 경로 정제 보상 모델링

본 논문은 ICLR 2026에 발표된 "Explore-on-Graph (EoG)" 프레임워크에 대한 기술적 요약입니다. 이 연구는 대규모 언어 모델 (LLM) 의 추론 과정에서 발생하는 환각 (hallucination) 과 사실 누락 문제를 해결하기 위해, 지식 그래프 (Knowledge Graph, KG) 를 기반으로 LLM 이 자율적으로 다양한 추론 경로를 탐색하도록 유도하는 새로운 방법을 제안합니다.

1. 문제 정의 (Problem Statement)

기존의 지식 그래프 강화 추론 방법들은 주로 두 가지 패러다임에 의존합니다:

규칙 기반 (Rule-based): 사전 정의된 규칙을 통해 추론의 논리적 일관성을 강제합니다.
모방 기반 (Imitation-based): 고정된 데모 데이터셋에서 추론 패턴을 모방하도록 LLM 을 미세 조정 (Fine-tuning) 합니다.

한계점:
이러한 기존 방법들은 학습 데이터의 분포나 사전 정의된 규칙의 범위 내에서만 추론을 수행합니다. 따라서 Out-of-Distribution (O.O.D.) 인 복잡한 그래프 구조나 학습 데이터에 존재하지 않는 새로운 추론 패턴 (예: '동료'나 '자회사'를 통한 간접 연결) 을 마주했을 때 성능이 급격히 저하됩니다. LLM 이 훈련 분포를 벗어나지 않고 새로운 영역을 탐색할 수 있는 자율적 능력이 부족하다는 것이 핵심 문제입니다.

2. 방법론 (Methodology)

저자들은 Explore-on-Graph (EoG) 라는 새로운 프레임워크를 제안하며, 이는 지도 미세 조정 (SFT) 단계와 강화 학습 (RL) 단계로 구성됩니다.

2.1. 단계 1: 지도 미세 조정 (Supervised Fine-Tuning, SFT)

목적: LLM 에 지식 그래프 탐색을 위한 기초적인 구조화된 추론 능력을 부여합니다.
방식: 긴 체인 오브 씽킹 (Long Chain-of-Thought, Long CoT) 데이터를 구축하여 LLM 을 미세 조정합니다.
- 데이터 구축: Gemini 2.5 Flash 와 같은 고성능 모델을 사용하여 지식 그래프 기반의 논리적 추론 과정과 정답을 생성하고, 이를 필터링하여 고품질의 SFT 데이터셋 ( $D_{CoT}$ ) 을 만듭니다.
- 학습: 생성된 Long CoT 데이터를 사용하여 LLM 이 구조화된 추론 경로를 생성할 수 있도록 학습시킵니다.

2.2. 단계 2: 강화 학습 (Reinforcement Learning, RL)

SFT 단계만으로는 학습 데이터의 패턴에 갇히기 쉽기 때문에, RL 을 통해 모델이 새로운 추론 경로를 탐색하도록 유도합니다.

기반 알고리즘: 그룹 상대 정책 최적화 (Group Relative Policy Optimization, GRPO) 를 사용합니다.
보상 설계 (Reward Modeling): 탐색의 효율성과 의미 있는 경로를 찾기 위해 두 가지 보상을 결합합니다.
1. 결과 보상 (Outcome Reward, $R_{outcome}$ ): 생성된 추론 경로의 최종 정답이 정답 (Ground Truth) 과 일치하는지 여부 (Entity-level F1 점수) 를 기반으로 계산합니다. 이는 탐색의 최종 목표 달성을 보장합니다.
2. 경로 정제 보상 (Path-refined Reward, $R_{path}$ ): 본 연구의 핵심 기여입니다. 단순히 정답만 맞추는 것이 아니라, LLM 이 생성한 추론 텍스트 내에 지식 그래프의 정답 경로 (Ground-truth reasoning path) 에 포함된 삼중항 (triples) 이 얼마나 정확하게 포함되어 있는지를 측정합니다.
  - Search-and-Verify 파이프라인: 정답 경로가 명시되지 않은 데이터셋의 경우, BFS 와 LLM 을 활용한 의미 검증 (Semantic Verification) 을 통해 정답 경로를 자동으로 추출합니다.
  - 효과: 이 보상은 LLM 이 무작위 탐색을 줄이고, 의미 있는 논리적 단계를 포함하는 효율적인 경로를 찾도록 유도합니다.
최종 보상 함수: $R_{joint}(p) = R_{outcome}(p) + \alpha R_{path}(p)$ (여기서 $\alpha$ 는 가중치 계수).

3. 주요 기여 (Key Contributions)

자율적 탐색 프레임워크 (EoG): 기존 방법들이 놓치고 있는 O.O.D. 추론 패턴을 처리하기 위해 LLM 이 지식 그래프에서 자율적으로 탐색하도록 유도하는 새로운 RL 기반 프레임워크를 제안했습니다.
경로 정제 보상 (Path-refined Reward Modeling): 단순한 정답 일치 여부가 아닌, 추론 과정의 논리적 경로 자체를 보상 신호로 활용하여 탐색의 효율성과 의미성을 극대화했습니다. 이는 무의미한 탐색을 줄이고 정확한 추론 경로를 학습하게 합니다.
성능 향상: 오픈소스 모델뿐만 아니라, 강력한 클로즈드소스 모델 (GPT-5, Gemini 2.5 Pro 등) 보다 우수한 성능을 달성했습니다.

4. 실험 결과 (Results)

다섯 가지 주요 KGQA 벤치마크 (WebQSP, CWQ, GrailQA, QALD10-en, 2WikiMultihop) 에서 실험을 수행했습니다.

SOTA 달성: EoG 는 Qwen2.5-7B 와 Llama-3.1-8B 기반 모델에서 모든 데이터셋에서 State-of-the-Art (SOTA) 성능을 기록했습니다.
클로즈드소스 모델 추월: 동일한 입력 조건에서 GPT-5, Gemini 2.5 Pro 등 상용 최상위 모델들의 성능을 능가했습니다. (예: CWQ 에서 Hit@1 82.6 vs GPT-5 의 74.1)
O.O.D. 일반화: 학습 데이터 분포를 벗어난 복잡한 추론 시나리오 (예: 3 홉 이상의 추론, 초상형 추론 등) 에서 기존 방법들 (GCR, DoG 등) 보다 월등히 높은 성능을 보여주었습니다.
탐색 효율성: 경로 보상을 도입한 모델은 탐색 효율성 (Exploration Efficiency) 이 높고, 지식 그래프의 논리적 공간 (Reasoning Space) 을 더 넓게 커버 (Coverage) 하는 것으로 확인되었습니다.
Ablation Study: 경로 보상 ( $R_{path}$ ) 을 제거할 경우 성능이 유의미하게 하락하여, 경로 기반 보상 신호의 중요성이 입증되었습니다.

5. 의의 및 결론 (Significance)

이 논문은 LLM 의 지식 그래프 기반 추론에서 자율적 탐색 (Autonomous Exploration) 의 중요성을 강조합니다. 단순히 정답을 맞추는 것을 넘어, 모델이 그래프 구조 내에서 새로운 논리적 경로를 발견하고 학습할 수 있도록 하는 경로 정제 보상 메커니즘은 추론의 신뢰성과 일반화 능력을 획기적으로 향상시킵니다.

EoG 는 제한된 계산 자원으로도 효율적으로 학습 가능하며, 복잡한 추론이 필요한 실제 QA 시스템에서 LLM 의 환각을 줄이고 사실 기반 추론을 강화하는 데 중요한 기여를 할 것으로 기대됩니다. 이는 지식 그래프와 강화 학습을 결합한 차세대 LLM 추론 기술의 새로운 방향성을 제시합니다.