[논문 리뷰] GRAPH-R1: TOWARDS AGENTIC GRAPHRAG FRAMEWORK VIA END-TO-END REINFORCEMENT LEARNING

https://arxiv.org/abs/2507.21892

Graph-R1: Towards Agentic GraphRAG Framework via End-to-end Reinforcement Learning

Graph-R1은 기존의 RAG(Retrieval Augmented Generation) 및 GraphRAG 방법론이 가진 한계점들을 해결하기 위해 제안된 프레임워크이다.

기존 한계점

• LLM의 환각 문제(hallucination problem)
• 청크 기반 RAG의 구조적 의미 부족
• 기존 GraphRAG의 한계점
  1. 높은 지식 구축 비용 및 의미 손실
  2. 고정된, 일회성 검색 과정
  3. 긴 컨텍스트 분석 및 프롬프트 품질에 대한 LLM 의존성

주요 특징

• 경량화된 지식 하이퍼그래프 구축 방법 도입
• 검색 프로세스를 다중 턴 에이전트-환경 상호 작용으로 모델링 → "think - search - rethink - generation" 추론 루프 반복 수행
• E2E 보상 메커니즘 설계 → 생성 품질, 그래프 경로의 구조적 신뢰성을 높임

Graph-R1

1. Knowledge construction and agent initializaiton

• 지식 하이퍼그래프 ($\mathcal G_H$)
  • $\mathcal G_H$는 도메인 지식 K(문서 d들의 집합)로부터 경량화된 방식으로 구축
  • 각 텍스트 단위 d를 입력으로 받아, LLM 기반 추출기($\pi_{ext}$)는 의미론적 세그먼트 $h_i$와 관련 엔티티 집합 $\mathcal V_{h_i}$로 구성된 N항 관계적 사실을 식별
  • 공유 인코더 $\phi(\cdot)$는 엔티티와 관계 모두에 대한 의미 임베딩을 생성하는 데 사용된다.
    → $\mathcal G_H = (V, E_H, \phi)$의 형태로 표현

• 에이전트 액션 공간 ($\mathcal A$)
  • Graph-R1에서 에이전트의 행동은 네 가지 하위 동작으로 구성
    1. Thinking($a_t^\mathrm{think}$): 현재 상태에서 추론을 계속/종료할지 결정
    2. Query Generation($a_t^\mathrm{query}$): 추론을 계속하기로 했을 때 실행, 지식 검색을 위한 적절한 질의 생성
    3. Graph Retrieval($a_t^\mathrm{ret}$): 생성된 질의를 기반으로 하이퍼그래프로부터 관련 지식을 검색하는 과정
    4. Answering($a_t^\mathrm{ans}$): 추론을 종료하기로 했을 때 실행되며, 최종 응답을 산출
  • 에이전트 행동의 로그 우도 (log likelihood)
    
    • 추론을 계속하는 경우: Thinking, Query Generation, Graph Retrieval 확률을 모두 포함하여 계산
    • 추론을 종료하는 경우: Thinking과 Answering의 확률에 의해 정의

 

2. Knowledge reasoning via multi-turn graph interaction

• 단계별 추론 정책 모델링
  • 매 추론 단계 t에서 LLM은 에이전트의 동작을 구조화된 출력 형태로 제어
  • 출력은 세 가지 요소로 구성
    1. Thinking reflection($a_t^\mathrm{think}$): 현재 상태를 요약하고 지식의 부족이나 잠재적 공백을 식별
    2. 조합 지시자($\alpha_t\in A^\mathrm{type}=\{(\mathrm{query}, \mathrm{retrieve}),(\mathrm{answer})\}$): 이후 동작이 검색 중심으로 진행될지, 혹은 답변 산출로 종료될지를 결정
    3. 콘텐츠 출력($a_t^\mathrm{out}\in A^\mathrm{content}$): 선택된 조합 구조에 따라 검색 질의 혹은 최종 답변을 구체적으로 산출
  • 의사결정 과정은 에이전트 상태 $s_t\in S$에 조건화된 계층적 정책으로 모델링
    ※ 상태 $s_t$: 이전 단계의 행동과 검색된 정보를 모두 포함
  • 정책($\pi_\theta$) 인수분해
    $$\pi_\theta(a_t^\mathrm{think},\alpha_t, a_t^\mathrm{out}|s_t)=\pi_\theta(a_t^\mathrm{out}|\alpha_t,a_t^\mathrm{think},s_t)\cdot\pi_\theta(\alpha_t|a_t^\mathrm{think},s_t)\cdot\pi_\theta(a_t^\mathrm{think}|s_t)$$
    → 에이전트는 지식의 충분성을 평가하고, 탐색과 종료 사이의 균형을 맞추며, 검색을 진행하거나 직접적인 답변을 생성하는 일련의 행동을 학습
• 하이퍼그래프 검색을 통한 지식 상호작용
  • 주어진 질의($a_t^\mathrm{query}$)에 대해, 하이퍼그래프에서 관련 지식을 이중 경로(엔티티 기반 하이퍼엣지 검색 + 하이퍼엣지 직접 검색)로 검색하고, 두 결과를 순위 기반 융합을 통해 통합한다.
    
    1. 엔티티 기반 하이퍼엣지 검색
       
       • 질의에서 추출된 엔티티 집합과 하이퍼그래프 내 엔티티의 임베딩 유사도를 측정 → 상위 $k_V$개의 엔티티 선택
       • 선택된 엔티티와 연결된 하이퍼엣지들을 모아 관련된 관계 사실들을 수집
         → 질의에 포함된 엔티티와 가까운 엔티티들을 찾고, 이들과 연결된 관계들을 가져오는 방식
    2. 하이퍼엣지 직접 검색
       • 질의 전체를 하나의 임베딩으로 표현하여 하이퍼그래프의 각 하이퍼엣지 임베딩과의 임베딩 유사도를 측정 → 상위 $k_H$개의 하이퍼엣지 선택
       • 선택된 하이퍼엣지가 담고 있는 관계 사실들을 수집
  • 순위 기반 융합
    • 앞선 두 결과 집합을 합친 뒤, 역순위 점수를 활용하여 최종 순위를 매김
    • 각 관계 사실 f의 점수는 두 경로에서 얻은 순위 $r_V$, $r_H$를 바탕으로 $\mathrm{RankScore}(f)={1\over r_V}+{1\over r_H}$로 계산(만약 어떤 경로에서 검색되지 않았다면 순위는 무한대로 처리)
    • 계산된 점수를 기준으로 상위 k개의 관계 사실을 최종적으로 반환하여, 추론을 위한 지식 집합 $a_t^\mathrm{ret}$을 구성
• 에이전트 경로의 최적화 목표
  • 에이전트의 목표: 질의에 대해 신뢰할 수 있고 맥락적으로 타당한 답변($y_q$)를 산출하는 추론 경로($\tau \in T_q$)를 학습하는 것
    $$\max_\theta \mathbb{E}_{\tau\sim\pi_\theta(T_q|q;\mathcal G_H)}[\log P(y_q|\tau)]$$
  • 이를 통해 $\pi_\theta$가 정답과 일관된 추론을 수행하도록 유도하는 신호로 작동

3. Outcome-directed end-to-end reinforcement learning

• End-to-end GRPO
  • 데이터셋의 질문이 주어지면, 에이전트는 지식 하이퍼그래프 $\mathcal G_H$와 상호작용하여 다중 턴 추론 경로 집합 $\{\tau_i\}_{i=1}^N$를 생성한다. 각 경로는 환경에서 샘플링된 상태-행동 쌍의 시퀀스로 표현된다.
  • 정책 $\pi_\theta$는 GRPO 기반 목적 함수로 최적화

→ 목적함수는 높은 보상을 주는 추론 경로를 강화하면서도, 정책이 급격히 변하지 않도록 안정적으로 학습하도록 설계

• 결과 지향적 보상 함수
  • 형식 보상 ($R_\mathrm{format}(\tau)$)
    • 형식 보상은 에이전트가 의도된 추론 구조($a_t^\mathrm{think},\alpha_t,a_t^\mathrm{out}$)를 따르도록 함
    • 각 유효한 단계는 0.5점의 보상을 받으며, 최대 1.0점으로 제한
  • 답변 보상 ($R_\mathrm{answer}$)
    • 생성된 최종 답변의 의미론적 정확성을 측정
    • $y^*_q$와 예측 답변 간의 토큰 레벨 F1 점수를 사용하여 계산
  • 전체 결과 보상 ($R(\tau)$)
    • 추론 경로 $\tau$에 대한 총 보상은 형식 보상과 답변 보상을 결합하여 정의된다.
      $$R(\tau)=-1.0+R_\mathrm{format}(\tau)+II\{R_\mathrm{format}(\tau)=1.0\}\cdot(a_T^\mathrm{ans})$$
    • 답변 정확성에 대한 보상은 형식적으로 유효한 추론이 선행될 때만 주어짐

Experiments

RQ 1. Graph-R1 이 다른 방법론들보다 뛰어난가?

• 평가 지표
  • Exact Match (EM): 예측 답변이 정답과 정확히 일치하는지
  • F1: 예측 답변과 정답 간의 토큰 수준 오버랩
  • Retrieval Similarity (R-S): 검색된 지식과 정답 지식 간의 의미론적 유사성을 평가
  • Generation Evaluation (G-E): gpt-4o-mini가 7가지 기준에 따라 생성 품질 평가
• 주요 결과
  • Graph-R1은 다양한 기준 모델에 걸쳐 일관적으로 모든 기준 모델을 능가하는 성능을 보임 
  • 프롬프트만 사용하는 GraphRAG 방법론은 StandardRAG 보다 성능이 낮은 경우가 많음 → 그래프 구조만으론 충분하지 않음
  • 파라미터 수가 늘어날수록 성능도 향상됨

RQ 2. 제거 실험 및 비교 분석

• 제거 실험
  • Graph-R1의 세 가지 핵심 구성 요소(지식 구축 K.C., 다중 턴 상호 작용 M.I., 강화 학습 R.L.)를 제거하여 평가를 진행
  • 어떤 모듈이라도 제거하면 성능 저하가 발생
• 다양한 지식 표현과의 비교
  • 외부 지식이 없는 R1의 경우 성능이 제일 낮고, 청크 기반 검색을 사용하는 R1-Searcher, Search-R1, 경량화된 GraphRAG를 사용하는 LightRAG, 본 논문에서 제안하는 Graph-R1 순으로 성능을 비교할 수 있다.

RQ 3. Graph-R1 구축 비용

• 지식 구축에 1K 토큰당 5.69초와 2.81$ 소요 & 120K 노드와 98K 엣지 이상을 생성하면서도 높은 F1을 유지

RQ 4. Graph-R1 검색 효율성

• Graph-R1은 더 짧은 응답을 생성하고 더 많은 상호 작용 턴을 수행
• 다른 방법론에 비해 중간 정도의 평균 검색 콘텐츠 길이로 가장 높은 F1 점수 달성

RQ 5. Graph-R1 생성 품질

• Graph-R1은 모든 RL 기반 기준 모델들을 능가
• HyperGraphRAG는 StandardRAG와 유사한 성능을 보이며 그래프 구조만으로는 제한적이 이득이 있음
• Graph-R1을 통해 그래프 기반 추론이 RL과 결합될 때 효과적

RQ 6. O.O.D. 환경에서의 일반화 가능성

• 데이터셋 전반: Graph-R1이 Search-R1을 능가
• 일반화 능력: Graph-R1이 Search-R1보다 높은 O.O.D-to-I.I.D. 비율을 달성

※ O.O.D. to I.I.D. ratio: O.O.D 환경에서의 모델 성능을 I.I.D. 환경에서의 모델 성능으로 나눈 값