26년 8월 1주차 그래프 오마카세

Use Graph When It Needs: Efficiently and Adaptively Integrating Retrieval-Augmented Generation with Graphs

Use Graph When It Needs: Efficiently and Adaptively Integrating Retrieval-Augmented Generation with Graphs

Large language models (LLMs) often struggle with knowledge-intensive tasks due to hallucinations and outdated parametric knowledge. While Retrieval-Augmented Generation (RAG) addresses this by integrating external corpora, its effectiveness is limited by fragmented information in unstructured domain documents. Graph-augmented RAG (GraphRAG) emerged to enhance contextual reasoning through structured knowledge graphs, yet paradoxically underperforms vanilla RAG in real-world scenarios, exhibiting significant accuracy drops and prohibitive latency despite gains on complex queries. We identify the rigid application of GraphRAG to all queries, regardless of complexity, as the root cause. To resolve this, we propose an efficient and adaptive GraphRAG framework called EA-GraphRAG that dynamically integrates RAG and GraphRAG paradigms through syntax-aware complexity analysis. Our approach introduces: (i) a syntactic feature constructor that parses each query and extracts a set of structural features; (ii) a lightweight complexity scorer that maps these features to a continuous complexity score; and (iii) a score-driven routing policy that selects dense RAG for low-score queries, invokes graph-based retrieval for high-score queries, and applies complexity-aware reciprocal rank fusion to handle borderline cases. Extensive experiments on a comprehensive benchmark, consisting of two single-hop and two multi-hop QA benchmarks, demonstrate that our EA-GraphRAG significantly improves accuracy, reduces latency, and achieves state-of-the-art performance in handling mixed scenarios involving both simple and complex queries.

arXiv.orgSu Dong

• 그동안 GraphRAG 계열 연구는 지식 그래프를 도입하면 다중 홉 추론이나 복잡한 관계 질의에서 더 나은 성능을 낼 것이라는 전제 위에서 발전해 왔습니다. Microsoft GraphRAG, RAPTOR, HippoRAG 등 굵직한 연구들이 이 흐름을 이어왔죠. 그런데 최근 여러 실증 연구는 다소 불편한 사실을 지적합니다.
• GraphRAG가 복잡한 멀티홉 질의에서는 확실히 강하지만, 단순한 단일 홉 질의에서는 오히려 vanilla RAG보다 성능이 떨어진다는 것입니다. 논문이 인용한 선행 연구에 따르면 Natural Questions에서 13.4%p, 시간에 민감한 질의에서는 16.6%p까지 정확도가 하락하는 사례가 보고되었습니다.
• 이러한 사실을 근거로, 해당 논문에서는 조금 근본적인 질문을 던지고 있습니다. 비슷한 내용을 25년 12월 오마카세로 전달해드렸었는데, 이번 논문에서도 "GraphRAG는 항상 vanilla RAG보다 나은가?"라는 질문에 해답을 찾고자 합니다.

• 한 문장으로 답할 수 있는 가벼운 질문에서 그래프 기반 검색은 엔티티와 관계를 경유해 정보를 모으는 과정에서 노이즈와 모호성을 함께 끌어올 수 있습니다. 높은 지연 시간까지 고려하면, 모든 질의에 동일한 검색 전략을 획일적으로 적용하는 방식은 정확도와 효율 양쪽에서 손해가 될 수 있습니다.

• 위 논문은 이러한 직관을 정량적인 라우팅 정책으로 전환합니다. 이를 위해 언어학에서 오랫동안 연구되어 온 구문 복잡도(syntactic complexity) 지표를 활용하고, 별도의 대형 언어모델 호출 없이도 질의에 적합한 검색 방식을 선택할 수 있는 가벼운 라우팅 어댑터를 설계합니다.

• 제안하는 EA-GraphRAG는 쿼리 하나가 들어올 때마다 세 갈래 길 중 하나를 선택합니다. 쉬운 질의는 RAG으로, 어려운 질의는 GraphRAG으로, 애매한 경계 사례는 가중 융합(Fusion) 모듈로 보냅니다. 그리고 이 결정을 내리는 것이 Syntax complexity 기반으로 설계된 어댑터(Adapter)입니다.

Query Complexity Measurement

• 기존 연구들이 쿼리 복잡도를 판단할 때 흔히 쓰는 방식은 의미론적 분류기를 훈련하거나 LLM에게 직접 물어보는 것입니다. 정확하긴 하지만 매 쿼리마다 추가 추론 비용이 붙습니다.
• 저자들은 응용언어학에서 문장의 구조적 난이도를 측정할 때 쓰는 구문 복잡도 개념을 그대로 활용하며 이를 우회합니다.
  • 왜 언어학적 개념을 도입했을까? 이 논문의 핵심 가설로, 긴 명사구와 소유격 연쇄, 두 단계의 관계 추적이 필요한 질문에 대해 대형 의미 분류 모델에만 의존하지 않고, 문장 구조와 개체,어휘 정보를 조합한 가벼운 특징만으로도 어느 정도 예측할 수 있다는 것입니다.
  • 즉, 무거운 의미 모델 없이 난이도를 추정하려는 시도에서 비롯한 저자들의 설계 철학입니다.
• 구체적으로는 Stanza로 구문 구조 트리를 만들고 Tregex 패턴 매칭으로 절, T-unit, 종속절, 등위구, 복합 명사구 등 아홉 가지 기본 단위를 센 뒤, 문장당 단어 수(MLS), T-unit당 단어 수(MLT), 종속절 비율(DC/T) 같은 비율 지표를 뽑아냅니다. 여기에 SpaCy 의존구문 분석으로 얻은 장거리 의존 관계 수, 개체명 밀도, 어휘 다양성, 트리의 깊이, 너비 같은 특징까지 더하면 80개가 넘는 원시 특징이 만들어집니다.
• 이 중 GraphRAG가 RAG를 이길지 예측하는 데 가장 유용한 특징들만 상호정보량 기준으로 골라내 최종 벡터를 구성합니다.

MLP Adapter

• 추출된 벡터는 은닉층 256-128-64로 구성된 작은 MLP를 통과해 시그모이드로 압축된 복잡도 스코어 s(q)가 됩니다. 흥미로운 부분은 이 어댑터의 학습 데이터를 만드는 방식입니다.
• RAG와 GraphRAG 중 한쪽만 정답을 맞힌 사례(disagreement set)만 골라 학습에 사용합니다. 두 방법이 모두 맞거나 모두 틀린 경우에는 어느 경로가 더 낫다고 판별할 수 없으므로 제외하고, 한쪽은 맞고 다른 쪽은 틀린 사례에만 집중해 이진 분류기를 훈련하는 방식입니다.
• 스코어 s(q)는 두 개의 임계값(τ_L, τ_H)과 비교되어 최종 경로를 결정합니다. s(q)가 τ_H 이상이면 GraphRAG(HippoRAG2 방식의 개체 가중치 + Personalized PageRank 전파)으로, τ_L 이하이면 RAG으로 보냅니다 ㅡ 식 (2) 참조. 
• 이처럼 실제 라우팅 선택이 결과를 바꾸는 사례에 학습 신호를 집중한다는 점은 데이터 효율 측면에서 실용적인 선택으로 보입니다.

Online Retrieval

• 라우팅 이후 각 검색 경로가 어떻게 작동하는지 이해하려면, 먼저 두 경로가 어떤 검색 자원 위에서 작동하는지 살펴볼 필요가 있습니다.
• 오프라인 인덱싱 단계에서 EA-GraphRAG는 HippoRAG2의 설정을 따라 코퍼스 전체를 이종 그래프(heterogeneous graph)로 미리 구성합니다.
  • 그래프의 노드는 2단계 LLM 프롬프팅을 통해 추출한 개체 및 명사구 노드 (N)과 원본 문단 노드 (C)로 나뉩니다.
  • 엣지는 세 종류로 구성됩니다.
    • 첫째는 OpenIE 트리플의 head와 tail을 연결하는 관계 엣지입니다.
    • 둘째는 각 개체를 해당 개체가 출현한 원본 문단과 연결하는 발생 엣지입니다.
    • 셋째는 임베딩 간 코사인 유사도가 일정 임계값 이상인 개체 쌍을 연결하는 동의어 엣지입니다.
  • 이렇게 미리 구축된 그래프 위에서 쿼리 관련 신호를 확산해 관련 문단을 찾습니다.
• RAG 경로는 상대적으로 단순합니다. 쿼리와 각 문단을 동일한 인코더로 임베딩하고, 두 벡터의 내적 유사도가 높은 상위 (K)개 문단을 그대로 반환합니다. 별도의 그래프 순회나 다단계 점수 계산을 거치지 않고 쿼리와 문단 임베딩을 직접 비교하기 때문에 검색 과정이 빠릅니다.
• GraphRAG 경로는 이보다 여러 단계를 거칩니다.

사실(fact) 유사도 계산→ LLM 리랭킹→ 개체 가중치 산출→ 시드 개체 선정→ PPR 확산→ 문단 점수 추출.

• 먼저 쿼리와 코퍼스에서 추출된 모든 fact, 즉 OpenIE 트리플 사이의 임베딩 유사도를 계산합니다. 이 점수를 정규화한 뒤 상위 (k)개 fact를 후보로 선택하고, LLM 기반 리랭커를 이용해 쿼리와의 관련성을 다시 평가합니다.
• 다음으로 리랭킹된 fact의 head와 tail에 해당하는 개체 노드에 가중치를 부여합니다. 이때 fact의 정규화된 유사도 점수를 그대로 사용하지 않고, 그 개체가 등장하는 문단 수로 나눠 정규화합니다.
  • '왜 개체 가중치를 문단 수로 나누는가?'
  • 여러 문단에 반복해서 등장하는 허브 개체가 쿼리와의 실질적인 관련성과 무관하게 지나치게 높은 영향력을 갖는 것을 막기 위해서입니다. 이러한 정규화를 적용하면 코퍼스 전반에 흔하게 등장하는 개체보다, 이번 쿼리와 더 선택적으로 연결된 개체가 상대적으로 높은 가중치를 받을 수 있습니다.
  • 다만 논문의 구현에서는 동일한 개체가 여러 후보 fact에 등장할 때 각 fact의 점수를 합산하거나 평균내지 않습니다. fact를 순회하면서 해당 개체의 가중치를 갱신하며, 최종적으로는 가장 나중에 처리된 fact의 점수가 사용됩니다.
• 가중치 상위 개체들(k')은 시드 집합(Q)으로 선정되고, 이 시드 노드들에만 초기 확률을 부여한 뒤 나머지 모든 노드는 0으로 두고 Personalized PageRank(PPR)를 실행합니다. PPR이 실행되면 관련성 신호가 관계 엣지와 동의어 엣지를 따라 개체 노드 사이로 확산되고, 발생 엣지를 통해 원본 문단 노드로 전달됩니다.
• 마지막으로 확산이 끝난 벡터에서 문단 노드에 해당하는 부분만 뽑아 점수가 높은 Top-K 문단을 최종 결과로 반환합니다. 초기 신호가 오직 쿼리와 관련된 시드 개체에서만 출발하기 때문에, 확산 결과는 그래프 구조를 반영하면서도 원래 쿼리와의 관련성을 잃지 않습니다.
• 라우팅이 Fusion으로 떨어지는 경계 사례에서는 RAG 경로에서 얻은 문단 순위와 GraphRAG 경로에서 얻은 문단 순위를 다음 절의 complexity-aware weighted RRF에 전달합니다. 이때 단순히 두 목록을 동일한 비중으로 결합하는 것이 아니라, 쿼리 복잡도 점수 (s(q))를 GraphRAG의 가중치로, (1-s(q))를 RAG의 가중치로 사용합니다.

• 실험은 단일 홉 QA(NQ, PopQA)와 멀티홉 QA(HotpotQA, 2Wiki), 그리고 이 넷을 고르게 섞은 Mix 벤치마크에서 진행됩니다.
• BM25, Contriever, ColBERTv2 같은 RAG 베이스라인과 RAPTOR, LightRAG, HippoRAG, HippoRAG2 같은 GraphRAG 베이스라인, 그리고 GPT-4o-mini 같은 순수 LLM까지 폭넓게 비교합니다.
• 가장 두드러지는 결과는 2Wiki(멀티홉)에서의 큰 격차입니다. 관계 추론이 핵심인 이 데이터셋에서 EA-GraphRAG는 가장 강한 RAG 베이스라인인 ColBERTv2보다 Acc. 기준 19.9%p 높은 성능을 보였습니다. HotpotQA에서도 QA 정확도 기준으로는 가장 강한 GraphRAG 베이스라인인 HippoRAG2를 근소하게 앞섰습니다(Acc. 65.9 대 65.5, GPT-Acc. 80.2 대 79.5).
• 다만 검색 재현율만 놓고 보면 HotpotQA 개별 데이터셋에서는 오히려 HippoRAG2가 더 높았고(R@3 82.7 대 80.5, R@5 89.6 대 87.2), EA-GraphRAG가 재현율에서 앞선 것은 네 데이터셋을 모두 합친 Mix 벤치마크였습니다(R@3 66.0 대 65.6, R@5 74.9 대 74.1).
• 전체 평균 검색 시간은 쿼리당 2.19초로, 그래프 검색만 사용했을 때의 3.23초보다 약 32% 낮았습니다.

• Ablation 실험에서도 각 구성 요소의 역할을 보여줍니다. 검색 없이 생성 모델만 쓰면 Acc. 39.5에 그치지만, RAG 검색을 더하면 65.1로, GraphRAG 검색을 더하면 70.5로, 마지막으로 Fusion 모듈까지 더하면 71.6으로 꾸준히 개선됩니다.
• 이 실험은 RAG → GraphRAG → 융합 순으로 구성 요소를 하나씩 누적해서 더한 것으로, 각 요소를 독립적으로 떼어내 비교한 것은 아닙니다. 다만 이 순서 안에서는 RAG 경로 검색으로 기본 근거를 확보하고, GraphRAG 경로 검색과 융합이 그 위에 추가적인 이득을 보탠다는 설계 의도를 확인할 수 있습니다.
• Table 5, Case study에서도 RAG, GraphRAG의 실패 케이스를 확인해볼 수 있습니다.
  • 단순 질의에서 GraphRAG 검색 실패 : "When is season 8 for game of thrones?"라는 질문에 그래프 기반 검색(HippoRAG)은 관련 개체는 맞지만 정작 방영일이 담긴 문장이 없는 문서를 끌어와 오답을 냅니다. 반면 덴스 검색은 "2019년 4월 방영 예정"이라는 문장을 바로 찾아냅니다.
  • 복잡 질의에서 RAG 검색 실패 : "What is the date of death of the director of film The Organization (Film)?"이라는 다단계 질문에서는 RAG 검색이 엉뚱한 감독 일대기만 반복해서 가져오지만, GraphRAG은 영화 → 감독(Don Medford) → 사망일(2012년 12월 12일)로 이어지는 관계를 추적해 정답을 찾아냅니다.

• EA-GraphRAG의 기여를 한 문장으로 요약하면, GraphRAG 연구의 질문을 언제 그래프를 쓸 것인가?로 옮겨놓았다는 것입니다. 그로부터 그래프 구조 자체를 더 정교하게 설계하는 대신, 이미 존재하는 RAG와 GraphRAG 파이프라인 위에 가벼운 라우팅 레이어를 얹어서 각 방법이 잘하는 영역에서만 일하도록 만드는 접근입니다.
• 짚고 넘어갈 한계도 존재합니다.
  • 설계한 어댑터는 특정 코퍼스와 특정 GraphRAG 구현(HippoRAG2 기반)에서 RAG와 GraphRAG 검색의 우수성을 예측하도록 학습된 이진 분류기입니다. 따라서 Disagreement-set 학습 전략은 그 학습 사례에 담긴 "무엇이 어려운 질문인가"라는 판단이 다른 도메인이나 다른 그래프 구현으로 얼마나 잘 옮겨가는지는 이 논문만으로는 확인하기 어렵습니다. 
• 학습 라벨 자체가 고정된 검색기와 생성 모델(GPT-4o-mini) 조합에서 RAG와 GraphRAG 중 어느 쪽이 정답을 냈는지를 기준으로 만들어집니다. 따라서 생성 모델이나 검색 백엔드가 달라지면 라우팅 임계값뿐 아니라 어댑터 자체를 다시 학습해야 할 가능성이 있으며, 이 부분은 논문에서 직접 검증되지 않았습니다. 
• 해당 어댑터를 고려한다면, 그대로 이식하는 방향보다 새로운 환경의 disagreement 데이터로 재학습 및 검증하는 과정을 거치는 편이 안전해보입니다.
• 무거운 semantic classifier 대신 구문 특징으로 난이도를 추정하는 발상, 두 방법이 실제로 갈리는 지점에만 학습 신호를 집중하는 disagreement-set 훈련 전략, 그리고 이진 라우팅이 아니라 연속 스코어를 융합 가중치로 그대로 재사용하는 설계는 색다른 아이디어로써 참신한 것 같습니다.
• 그래프를 정말 필요한 순간에만 꺼내 쓰자는 실용적 제안 및 복잡하고 무거운 구조를 버리고 기존 검색 방식을 연결해주는 라우터를 설계하여 성능 효율의 균형을 개선할 수 있다는 점을 논문의 핵심 인사이트로 정리해볼 수 있을 것 같습니다.

Reference

• 경량 모델 라우팅 (Adaptive-RAG): https://arxiv.org/abs/2403.14403?utm_source=chatgpt.com
• 구문 복잡도 지표: https://benjamins.com/catalog/ijcl.15.4.02lu?utm_source=chatgpt.com
• Fusion 구간의 weighted RRF 이해 : https://research.google/pubs/reciprocal-rank-fusion-outperforms-condorcet-and-individual-rank-learning-methods/?utm_source=chatgpt.com

[Contact Info]

Gmail: jhbae1184@akane.waseda.jp

Twitter (X): @jhbae1184

LinkedIn