[논문 리뷰] LinearRAG: Linear Graph Retrieval Augmented Generation on Large-scale Corpora (25.10)

https://arxiv.org/abs/2510.10114

 

Retrieval-Augmented Generation(RAG)은 외부 지식을 활용해 Large Language Model(LLM)의 hallucination을 완화하는 데 널리 쓰인다. 단순한 query에는 효과적이지만, 전통적인 RAG 시스템은 정보가 파편화되어 있는 대규모 비정형 코퍼스에서는 어려움을 겪는다. 최근의 진전은 knowledge graph를 도입해 관계 구조를 포착함으로써 복잡한 multi-hop 추론 태스크에 대해 더 포괄적인 retrieval을 가능하게 한다. 그러나 기존 graph 기반 RAG(GraphRAG) 방법들은 graph 구축을 위해 불안정하고 비용이 큰 relation extraction에 의존하며, 그 결과 부정확하거나 일관성 없는 relation을 담은 noisy graph를 만들어 retrieval 품질을 떨어뜨린다. 본 논문에서는 기존 GraphRAG 시스템의 파이프라인을 재검토하고, 신뢰할 수 있는 graph 구축과 정밀한 passage retrieval을 가능하게 하는 효율적인 프레임워크인 Linear Graph-based Retrieval-Augmented Generation(LinearRAG)을 제안한다. 구체적으로 LinearRAG는 경량 entity extraction과 semantic linking만을 사용해 Tri-Graph라 부르는 relation-free hierarchical graph를 구축함으로써 불안정한 relation modeling을 회피한다. 이 새로운 graph 구축 패러다임은 코퍼스 크기에 대해 선형으로 확장되고 추가적인 token 소비가 발생하지 않아, 원본 passage에 대한 경제적이고 신뢰할 수 있는 indexing을 제공한다. retrieval에서 LinearRAG는 2단계 전략을 채택한다. (i) local semantic bridging을 통한 관련 entity activation, 이어서 (ii) global importance aggregation을 통한 passage retrieval이다. 네 개 데이터셋에 대한 광범위한 실험은 LinearRAG가 baseline 모델들을 유의하게 능가함을 보여준다. 코드와 데이터셋은 https://github.com/DEEP-PolyU/LinearRAG.git 에서 이용할 수 있다.

---

1 Introduction

• RAG는 외부 지식 베이스로 LLM을 강화하는 유망한 접근이지만, 실세계의 대규모 비정형 코퍼스에서는 관련 정보가 이질적인 문서들에 고르지 않게 분포하기 때문에 검색된 context가 방대하고 복잡하며 조직화되어 있지 않다.
• GraphRAG는 외부 구조 graph로 배경 지식의 계층 구조를 모델링하는 패러다임으로 등장했다.
  • 초기 연구인 RAPTOR(Sarthi et al., 2024)와 Microsoft의 GraphRAG(Edge et al., 2024)는 재귀적 요약과 community detection으로 지식을 조직한다.
  • GFM-RAG(Luo et al., 2025), G-Retriever(He et al., 2024), LightRAG(Guo et al., 2024)는 query-dependent GNN, Prize Collecting Steiner Tree, dual-level indexing 같은 전용 encoder와 목적함수를 통합한다.
  • HippoRAG(Gutiérrez et al., 2024)와 HippoRAG2(Gutiérrez et al., 2025)는 인지 과정에서 영감을 얻어 personalized PageRank를 multi-hop retrieval에 활용한다.
• 그러나 최근 연구들은 GraphRAG가 많은 실세계 응용에서 naive RAG보다도 못한 성능을 낸다고 보고하며, 그 원인은 자동 구축된 knowledge graph의 낮은 품질이다. 구체적으로 (i) local inaccuracy(relation extraction의 높은 오류율)와 (ii) global inconsistency(계층적 일관성과 전역 응집성을 강제하는 메커니즘의 부재)라는 두 결함이 지목된다.
• LinearRAG의 핵심 아이디어는 복잡한 relational graph를, 대상 entity와 그 근거가 되는 텍스트 passage 사이의 의미만 모델링하는 선형적이고 indexing하기 쉬운 관점으로 단순화하는 것이다. 비용이 큰 relation extraction 대신 경량 entity extraction과 semantic linking만으로 entity·sentence·passage의 hierarchical graph를 구축한다.
• 이 graph 위에서 2단계 passage retrieval을 도입한다. ❶ entity activation을 위한 local semantic bridging, ❷ passage retrieval을 위한 global importance aggregation이다. 논문의 기여는 GraphRAG 한계의 규명, indexing 시간을 77% 이상 줄이는 relation-free hierarchical graph인 Tri-Graph, 그리고 4개 벤치마크 데이터셋에서의 광범위한 실험 검증이다.

Figure 1: Three paradigms of RAG systems.

 

 

[Translated by Claude]

 

Retrieval-Augmented Generation(RAG)은 외부 지식 베이스를 활용하여 Large Language Model(LLM)을 강화하는 유망한 접근으로 등장했다(Gao et al., 2023; Lewis et al., 2020; Zhou et al., 2025a; Zhang et al., 2025c). 그러나 기존 RAG 시스템은 실세계 시나리오의 대규모 비정형 코퍼스가 갖는 복잡성에 고전하는데, 이런 환경에서는 관련 정보가 이질적인 문서들에 고르지 않게 분포하는 경우가 잦다. RAG 시스템이 검색해 오는 context는 종종 방대하고 뒤얽혀 있으며 명확한 조직이 없어, 정확성과 일관성의 변동 문제를 낳는다(Sun et al., 2024; Zhang et al., 2024). 최근의 진전은 효율적인 indexing을 위해 문서를 더 작은 chunk로 분할함으로써 이를 관리하려 시도하지만(Borgeaud et al., 2022; Izacard et al., 2023; Jiang et al., 2023), 이 전략은 결정적인 맥락 세부 정보의 손실을 초래하여 복잡한 태스크에 대한 retrieval 정확도와 추론 능력을 저해하는 경우가 많다(Han et al., 2024; Zhang et al., 2025b).

이를 해결하기 위해 Graph Retrieval-Augmented Generation(GraphRAG)(Zhang et al., 2025b; Procko & Ochoa, 2024; Xiao et al., 2025a; Xiang et al., 2025)이 최근 강력한 패러다임으로 등장했는데, 이는 외부의 구조화된 graph를 활용해 배경 지식의 계층 구조를 모델링한다(Han et al., 2024). 구체적으로 RAPTOR(Sarthi et al., 2024)와 Microsoft의 GraphRAG(Edge et al., 2024) 같은 초기 연구는 LLM이 생성한 개요를 이용한 재귀적 요약과 community detection을 통해 지식을 조직하여, 포괄적인 응답을 위한 coarse-to-fine retrieval을 가능하게 한다. 이를 기반으로 GFM-RAG(Luo et al., 2025), G-Retriever(He et al., 2024), LightRAG(Guo et al., 2024)를 포함한 최근 접근법들은 query-dependent GNN, Prize Collecting Steiner Tree, dual-level indexing 같은 전용 encoder와 목적함수를 통합하여 multi-hop 일반화, 확장성, 효율성을 개선한다. 더 최근에는 HippoRAG(Gutiérrez et al., 2024)와 그 개선판인 HippoRAG2(Gutiérrez et al., 2025)가 인지 과정에서 영감을 얻어 multi-hop retrieval에 personalized PageRank를 활용한다. 이런 전략들은 retrieval 정밀도와 맥락적 깊이를 크게 개선하여, LLM이 복잡한 multi-hop query를 더 효과적으로 처리할 수 있게 한다.

개념적 유망함과 이론적 우월성에도 불구하고, 최근 연구들은 GraphRAG 모델이 많은 실세계 응용에서 naive RAG 접근법보다도 자주 성능이 떨어진다는 사실을 드러낸다(Han et al., 2025; Zhou et al., 2025b; Xiang et al., 2025; Zhuang et al., 2025). 이 성능 저하는 주로 자동으로 구축된 knowledge graph의 낮은 품질에서 비롯된다. graph 기반 retrieval은 관련 지식의 recall을 높이지만, 동시에 graph 구축의 오류 때문에 검색된 context에 상당한 노이즈와 모호성을 끌어들인다. 구체적으로 두 가지 결정적 결함이 graph 품질을 훼손한다. (i) local inaccuracy: relation extraction 과정은 유의한 오류율을 보이며, 그 결과 entity 사이에 부정확한 semantic 관계가 만들어진다. (ii) global inconsistency: 추출 과정에서 계층적 일관성과 전역적 응집성을 강제하는 메커니즘이 없어, 구조적으로 파편화되고 연결성이 나쁜 graph가 만들어진다. 이 결함들은 knowledge graph 내부의 구조적 충돌과 의미적 모호성으로 함께 나타나며, 이는 곧 retrieval과 generation 과정을 훼손한다. 최근에는 bottom-up clustering 기반 community 요약(Edge et al., 2024; Gutiérrez et al., 2025; Wang et al., 2025)이나 topic modeling(Sarthi et al., 2024)을 통해 데이터에 대한 더 넓은 거시적 관점을 제공하여 graph 품질을 정제하려는 시도가 있었으나, 이런 비지도 방법들은 error propagation에 취약하여 entity 관계의 부정확성이 더 높은 추상 수준에서 증폭된다.

본 논문에서 우리는 기존 GraphRAG 시스템의 파이프라인을 재검토하고, 효율적이고 신뢰할 수 있는 graph 구축과 multi-hop 추론을 동반한 정밀한 코퍼스 retrieval을 가능하게 하는 프레임워크인 Linear Graph-based Retrieval-Augmented Generation(LinearRAG)을 제안한다. LinearRAG의 핵심 아이디어는 대상 entity와 그 바탕이 되는 텍스트 passage 사이의 의미만을 모델링하는 데 집중함으로써, 복잡한 relational graph를 선형적이고 indexing하기 쉬운 관점으로 단순화하는 것이다. 비용이 큰 relation extraction에 의존하는 대신, LinearRAG는 경량 entity extraction과 semantic linking만을 사용해 entity, sentence, passage로부터 hierarchical graph를 구축한다. 이 graph 위에서 LinearRAG는 2단계 passage retrieval 기법을 도입한다. ❶ entity activation을 위한 local semantic bridging은 문장 안의 semantic 유사도를 전파하여 multihop 맥락 연관을 캐냄으로써 문자적 일치를 넘어선 맥락적으로 관련 있는 entity를 식별한다. ❷ passage retrieval을 위한 global importance aggregation은 활성화된 subgraph 위에 personalized PageRank를 적용하여 전체적인 관점에서 passage의 중요도를 집계한다. 이 모듈들이 함께 작동하여 LinearRAG는 복잡한 query에 대해 확장 가능하고 정확하며 노이즈에 강한 retrieval을 달성한다. 우리의 전체 기여는 다음과 같이 요약된다.

• 우리는 기존 GraphRAG 시스템의 핵심 한계를 규명하며, 특히 불안정한 relation extraction에 대한 의존이 어떻게 노이즈와 구조적 비일관성을 도입하는지를 부각한다. 이는 선형 확장성을 유지하면서 신뢰할 수 있는 graph 구축과 정밀한 passage retrieval을 가능하게 하는 새로운 프레임워크인 LinearRAG의 설계 동기가 된다.
• LinearRAG는 경량 entity extraction과 semantic linking만을 사용해 Tri-Graph라 부르는 relation-free hierarchical graph를 구축하며, 이는 전통적인 relation modeling의 불안정성을 피하고 indexing 시간을 77% 이상 줄인다.
• 구축된 graph 위에서 우리는 정밀한 entity activation을 위한 local semantic bridging과 passage recall을 위한 global importance aggregation을 결합한 2단계 retrieval 메커니즘을 설계한다. 이 통합 전략은 더 정확하고 노이즈에 강하며 single-pass로 이루어지는 multi-hop retrieval을 가능하게 한다.
• 우리는 네 개의 벤치마크 데이터셋에 대해 광범위한 실험을 수행하여, LinearRAG가 retrieval 품질, generation 정확도, 확장성 측면에서 state-of-the-art baseline을 일관되게 능가함을 입증하고 실세계 응용에 대한 실용성을 검증한다.

2 Preliminary Study

• RAG 시스템에서 사용되는 graph의 효과를 조사하기 위해 일련의 예비 연구를 수행한다.
• 이 연구는 GraphRAG가 전통적인 태스크에서 naive RAG보다 자주 성능이 떨어지는 근본 원인을 설명하는 graph 구축의 결정적 결함을 드러낸다.
• 2.1은 GraphRAG-Bench 위에서의 성능 저하를, 2.2는 graph 품질과 오류 분석을, 2.3은 이로부터 도출되는 논의를 다룬다.

Figure 2: (a) Retrieval and generation rerformance (%) of Vanilla RAG v.s. GraphRAG Baselines. Notably, the evaluation on Medical dataset measures GPT-based accuracy, context relevance, and evidence recall across different RAG baselines. (b) Case study of relation errors in knowledge graph construction from local inaccuracy and global inconsistency perspectives.

 

[Translated by Claude]

 

이 절에서 우리는 RAG 시스템에서 사용되는 graph의 효과를 조사하기 위해 일련의 예비 연구를 수행했다. 우리의 발견은 GraphRAG가 전통적인 태스크에서 naive RAG에 비해 자주 성능이 떨어지는 근본 원인을 설명해 주는, graph 구축의 결정적 결함을 드러낸다.

2.1 Performance Degradation in GraphRAG Systems

• GraphRAG 모델은 많은 실세계 태스크에서 전통적인 RAG 접근법보다 자주 성능이 떨어진다.
• GraphRAG-Bench(Xiang et al., 2025) 실험에서 graph 구조는 더 넓은 범위의 잠재적 관련 passage를 검색해 recall을 높이지만, 그 이득은 노이즈와 모호한 맥락 정보의 상당한 유입으로 상쇄된다.
• LightRAG와 HippoRAG 같은 GraphRAG 방법은 evidence recall에서는 중간 수준의 개선을 얻지만 context relevance는 36.86%~54.61%로, 62.87%를 기록한 Vanilla RAG보다 현저히 낮다.
• 예컨대 "climate change impacts"에 대한 QA 태스크에서 GraphRAG는 빈약한 graph 링크 때문에 "economic policies" 관련 passage를 검색할 수 있는 반면, vanilla RAG는 query 맥락과의 정합을 더 단단히 유지해 더 정확하고 안정적인 출력을 낸다.

 

[Translated by Claude]

 

GraphRAG 모델은 많은 실세계 태스크에서 전통적인 RAG 접근법보다 자주 성능이 떨어진다. 구체적으로 GraphRAG-Bench(Xiang et al., 2025) 위에서 수행한 우리의 실험은, GraphRAG가 graph 구조를 활용해 잠재적으로 관련 있는 더 넓은 범위의 passage를 검색함으로써 recall을 높이는 한편 이 이득이 노이즈와 모호한 맥락 정보의 상당한 유입으로 상쇄된다는 것을 보여준다. 구체적으로 LightRAG와 HippoRAG 같은 GraphRAG 방법들은 evidence recall에서 중간 정도의 개선을 달성하지만, context relevance는 36.86%에서 54.61% 사이로, 62.87%의 성능을 기록한 Vanilla RAG에 비해 현저히 낮다. 이는 graph 기반 retrieval이 맥락 정보의 범위를 넓히기는 하지만, 생성된 답변의 관련성과 신뢰성을 훼손하는 상당한 노이즈를 도입한다는 것을 시사한다. 예를 들어 "climate change impacts"에 관한 질의응답 태스크에서 GraphRAG는 빈약한 graph 연결 때문에 "economic policies"와 관련된 passage를 검색할 수도 있다. 반면 vanilla RAG는 query 맥락과의 정합을 더 단단히 유지하여 더 정확하고 안정적인 출력을 이끌어낸다.

2.2 Graph Quality and Error Analysis

• Figure 2a에서 관찰된 성능 저하의 근본 원인을 진단하기 위해 GraphRAG에서 사용되는 knowledge graph에 대해 세밀한 오류 분석을 수행했다.
• 전통적인 GraphRAG 파이프라인은 relational graph를 구축하기 위해 명시적 relation extraction에 의존하는데, 이는 보통 두 수준의 오류를 도입한다.
• Local Inaccuracies: relation extraction 모델은 사실적으로 틀린 triple을 자주 만든다. "Einstein did not win the Nobel Prize for his theory of relativity"라는 문장이 (Einstein, won Nobel Prize for, theory of relativity)로 잘못 표현되어 사실의 의미가 근본적으로 뒤바뀔 수 있다.
• Global Inconsistencies: relation extraction이 개별 텍스트 passage 위에서 국소적으로 수행되고 코퍼스 전체에 걸쳐 연결을 검증·조정할 메커니즘이 없어 중복되거나 모순되는 relation이 발생한다. 예컨대 "AI"가 "Unsupervised Learning", "NLP", "CV"에 계층적 응집성 없이 병렬 하위 범주로 연결될 수 있다.

 

[Translated by Claude]

 

Figure 2a에서 관찰된 성능 저하의 근본 원인을 진단하기 위해, 우리는 GraphRAG에서 사용되는 knowledge graph에 대해 세밀한 오류 분석을 수행했다. 우리의 분석은 이 성능 저하가 knowledge graph 구축의 결함에서 직접 비롯된다는 것을 밝혔다. 전통적인 GraphRAG 파이프라인은 relational graph를 구축하기 위해 명시적 relation extraction에 의존하는데, 이는 대개 두 수준에서 오류를 도입한다. (i) Local Inaccuracies: relation extraction 모델은 사실적으로 부정확한 triple을 자주 생성한다. 예를 들어 Figure 2b에서 보듯 "Einstein did not win the Nobel Prize for his theory of relativity"라는 문장이 (Einstein, won Nobel Prize for, theory of relativity)로 잘못 표현되어 사실의 의미를 근본적으로 바꿔 버릴 수 있다. (ii) Global Inconsistencies: 기존의 relation extraction은 개별 텍스트 passage 위에서 국소적으로 수행되며, 코퍼스 전체에 걸친 연결을 검증하거나 조정할 메커니즘이 없어 중복되거나 모순되는 relation을 낳는다. 예를 들어 "AI"가 계층적 응집성 없이 "Unsupervised Learning", "NLP", "CV"에 병렬적인 하위 범주로 연결될 수 있다(예컨대 NLP와 CV는 AI의 하위 분야인 반면 "Unsupervised Learning"은 그 안에서 사용되는 기법이다). 이런 구조적 모호성은 retrieval 과정을 직접적으로 오도하여, 이 비일관적인 연결에 기반한 의미적 노이즈를 도입한다.

2.3 Discussion

• 전통적인 GraphRAG 파이프라인은 명시적 relation extraction과 triple 기반 지식 표현에 크게 의존하며, 여기에는 두 가지 근본적 문제가 있다.
• 첫째, 간결하고 정확한 relational triple을 추출하는 일은 계산 비용이 크고 언어학적으로 어렵다. 자연어로 표현된 relation은 복잡하고 맥락 의존적이며, 미묘하거나 합성적이어서 atomic triple로 정확히 증류되기 어렵다. "Rachel reluctantly agreed to go running with Phoebe"는 결정적인 의미적 뉘앙스를 잃지 않고서는 하나의 atomic triple로 깔끔하게 환원될 수 없다.
• 둘째, 명시적 relation extraction은 불필요하다. passage 전반에 분산된 정보를 잇는 주된 앵커는 relation이 아니라 정렬된 entity다.
• 원본 텍스트는 relational semantics를 온전한 맥락 속에 보존하며, 이는 오류에 취약한 추출에 의존하지 않고도 추론 시점에 LLM이 동적으로 해석할 수 있다.

 

[Translated by Claude]

 

전통적인 GraphRAG 파이프라인은 명시적 relation extraction과 triple 기반 지식 표현에 크게 의존한다. 이 접근은 passage를 구조화된 relational 형태로 요약하는 것을 목표로 하지만, 두 가지 근본적인 문제에 직면한다. 첫째, 간결하고 정확한 relational triple을 추출하는 일은 계산적으로 비싸고 언어학적으로 어렵다. 자연어로 표현되는 relation은 흔히 복잡하고 맥락 의존적이며, 미묘하거나 합성적인 경우가 많아 atomic triple로 정확하게 증류되기 어렵다. 예를 들어 "Rachel reluctantly agreed to go running with Phoebe"라는 문장은 결정적인 의미적 뉘앙스를 잃지 않고서는 하나의 atomic triple로 깔끔하게 환원될 수 없다. 둘째, 명시적 relation extraction은 불필요하다. relation이 아니라 정렬된 entity가 passage 전반에 분산된 정보를 잇는 주된 앵커 역할을 한다. 원본 텍스트는 relational semantics를 온전한 맥락 속에 보존하며, 이는 오류에 취약한 추출에 의존하지 않고도 추론 과정에서 large language model에 의해 동적으로 해석될 수 있다.

3 The Framework of LinearRAG

• 예비 연구의 발견은 명시적 relation extraction이 계산적으로 비쌀 뿐 아니라 대체로 불필요하다는 것을 보여준다. 이로부터 두 가지 중심 주장이 도출된다. (i) 정렬된 entity가 passage 전반에 분산된 정보를 잇는 주된 앵커다. (ii) 맥락적 relation은 원본 passage 안에 가장 잘 보존되므로 명시적 relation extraction이 필요 없다.
• 이에 따라 entity node, sentence node, passage node의 세 유형을 담은 graph를 구축하며, edge는 entity를 sentence에, entity를 passage에 연결하고 두 개의 인접행렬로 표현된다.
• retrieval은 2단계로 진행된다. ❶ entity activation 단계는 passage node를 고정한 채 entity-sentence subgraph 위에서 local semantic bridging으로 서로 다른 passage를 잇는 중간 entity를 식별한다. ❷ passage retrieval 단계는 sentence node를 고정한 채 entity-passage subgraph 위에서 personalized PageRank를 적용하며, 1단계의 활성화된 entity를 global importance aggregation의 seed로 활용한다.
• 이 프레임워크는 graph 구축과 retrieval 양쪽에서 선형 확장성을 보이며(상세 분석은 Appendix D), 우리는 이를 LinearRAG라 부른다.

Figure 3: The overall pipeline of the proposed LinearRAG framework. I. Offline Construction. Initially, we construct a Tri-graph containing entity, sentence, and passage nodes, with edges connecting entities to sentences and entities to passages. II. Online Retrieval. We first activate relevant entities via local semantic bridging on the entity-sentence subgraph while fixing passage nodes, then using the activated entities to aggregate global importance scores, finally, perform passage retrieval via personalized PageRank on the entity-passage subgraph while fixing sentence nodes.

 

[Translated by Claude]

 

예비 연구의 발견은 명시적 relation extraction이 계산적으로 비쌀 뿐 아니라 대체로 불필요하다는 것을 가리킨다. 이 통찰은 GraphRAG 구성 요소의 설계를 재검토하게 하며, 두 가지 중심 주장으로 귀결된다. (i) 정렬된 entity가 passage 전반에 분산된 정보를 잇는 주된 앵커 역할을 한다. (ii) 맥락적 relation은 원본 passage 안에 가장 잘 보존되며, 따라서 명시적 relation extraction의 필요를 없앤다.

이 아이디어에 착안하여 우리는 Figure 3과 같은 새로운 GraphRAG 패러다임을 도입한다. 이는 세 유형의 node를 담은 graph를 구축한다. entity node, sentence node, passage node다. edge는 entity를 sentence에, 그리고 entity를 passage에 연결하며 두 개의 인접행렬로 표현된다. retrieval은 두 단계로 진행된다. ❶ entity activation 단계에서는 passage node를 고정한 채 entity–sentence subgraph 위에서 local semantic bridging을 사용해 서로 다른 passage를 잇는 중간 entity를 식별한다. ❷ passage retrieval 단계에서는 sentence node를 고정한 채 entity–passage subgraph 위에서 personalized PageRank를 적용하며, 첫 단계에서 활성화된 entity를 global importance aggregation의 seed로 활용한다. 이 프레임워크는 graph 구축과 retrieval 양쪽에서 선형 확장성을 보이며(상세 분석은 Appendix D), 우리는 이를 LinearRAG라 부른다.

3.1 Token-free Graph Construction

• 유지·갱신이 효율적인 다중 granularity의 hierarchical graph인 Tri-graph를 구축한다. passage 집합 P가 주어지면 구두점(마침표, 느낌표 등)으로 각 passage를 문장으로 분할해 문장 집합 S를 얻고, spaCy(Honnibal et al., 2020) 같은 경량 모델로 NER을 수행해 entity 집합 E를 얻는다.
• passage, sentence, entity가 graph의 세 node 유형이 되며 각각 Vp, Vs, Ve로 표기한다. passage pi가 entity ej를 포함하면 edge (Vpi, Vej)를, sentence si가 ej를 언급하면 edge (Vsi, Vej)를 추가한다.
• 이는 passage-entity 사이의 contain matrix C와 sentence-entity 사이의 mention matrix M이라는 두 인접행렬에 대응한다.
  • C = [Cij] (|Vp| × |Ve|), 여기서 Cij = 1{pi contains ej} … (1)
  • M = [Mij] (|Vs| × |Ve|), 여기서 Mij = 1{si mentions ej} … (2)
• 새 passage가 들어오면 해당 passage만 문장 분할·NER·edge 구축을 거치므로 전체 복잡도가 선형이다. NER은 OpenIE 대비 정확하고 효율적이며 LLM token 비용 없이 경량 언어 모델(예: spaCy의 BERT 기반 모델)로 수행할 수 있다. 인접행렬 C와 M은 sparse 형태로 구현되고, 원본 passage를 지식 운반체로 유지하므로 information-lossless 구축이 보장된다.

 

[Translated by Claude]

 

우리는 유지와 갱신이 효율적이며 여러 granularity를 갖는 hierarchical graph, 즉 Tri-graph를 구축한다. passage 집합 P를 갖는 코퍼스가 주어지면, 우리는 먼저 구두점(예: 마침표나 느낌표)을 사용해 각 passage를 문장으로 분할하여 문장 집합 S를 얻는다. 그런 다음 named entity recognition(NER)을 위해 경량 모델(예: spaCy(Honnibal et al., 2020))을 적용하여 entity 집합 E를 도출한다. passage, sentence, entity는 graph에서 세 유형의 node를 구성하며 각각 Vp, Vs, Ve로 표기한다.

edge는 다음 규칙에 따라 구축된다. passage pi가 entity ej를 포함하면 edge (Vpi, Vej)를 추가하고, 마찬가지로 sentence si가 entity ej를 언급하면 edge (Vsi, Vej)를 추가한다. 이 관계들은 두 개의 인접행렬에 대응한다. passage와 entity 사이의 contain matrix C, 그리고 sentence와 entity 사이의 mention matrix M이다.

형식적으로 contain matrix C는 |Vp| × |Ve| 행렬로 정의된다.

C = [Cij]_{|Vp|×|Ve|}, where Cij = 1{pi contains ej} … (1)

여기서 1은 indicator function을 나타내며, pi가 ej를 포함하면 Cij = 1이고 그렇지 않으면 Cij = 0이다. 유사하게 mention matrix M은 |Vs| × |Ve| 행렬로 정의된다.

M = [Mij]_{|Vs|×|Ve|}, where Mij = 1{si mentions ej} … (2)

이 설계는 코퍼스가 커질 때 효율적인 graph 갱신을 가능하게 한다. 새로운 passage가 도착하면 그 passage들만 문장 분할, NER, edge 구축을 거치므로 전체적으로 선형 복잡도를 갖는다. 특히 NER은 OpenIE에 비해 정확하고 효율적이며, LLM token 비용을 발생시키지 않고 경량 언어 모델(예: spaCy의 BERT 기반 모델)로 수행할 수 있다. 또한 인접행렬 C와 M은 내재적 희소성을 활용해 sparse 형태로 구현되어 메모리 사용량을 선형 확장성 수준까지 더 줄인다. 마지막으로 원본 passage를 지식의 운반체로 유지함으로써, 결과 graph는 모든 맥락 정보를 보존하여 information-lossless한 구축을 보장한다.

3.2 Passage Retrieval

• 구축된 graph가 손실 없는 지식 운반체 역할을 하므로, 목표는 가장 정보량이 큰 passage를 효과적으로 식별하는 것이 된다.
• graph 기반 retrieval의 설계는 특히 multihop query의 경우 관련 context의 precision과 recall을 균형 잡아야 하므로 결정적으로 중요하다.
• retrieval 과정을 두 단계로 분해한다. local semantic bridging을 통한 정밀한 entity activation 단계(3.2.1)와, 전역적으로 중요한 passage를 recall하는 passage retrieval 단계(3.2.2)다.

 

[Translated by Claude]

 

구축된 graph가 손실 없는 지식 운반체 역할을 하므로, 목표는 가장 정보량이 많은 passage를 효과적으로 식별하는 것이 된다. graph 기반 retrieval의 설계는 결정적으로 중요한데, 특히 multihop query의 경우 관련 context의 precision과 recall을 균형 잡아야 하기 때문이다. 우리는 retrieval 과정을 두 단계로 분해한다. local semantic bridging을 통한 정밀한 entity activation 단계와, 그 뒤를 잇는, 전역적으로 중요한 passage를 recall하기 위한 passage retrieval 단계다.

3.2.1 First Stage: Relevant Entity Activation via Semantic Bridging

• 직접적인 entity 매칭은 multihop relation을 잇는 관련 중간 entity를 놓칠 수 있고, 이런 잠재적 연결자는 직접 캐낼 수 없으며 entity 수가 방대해 식별 정밀도가 떨어진다. 이를 해결하기 위해 semantic bridging을 통한 관련 entity activation을 제안한다.
• Initial entity activation: SpaCy로 query q에서 entity Eq를 추출하고, 각 추출 entity에 대해 knowledge graph에서 가장 유사한 entity를 찾아 그 유사도 점수를 초기 activation 점수로 설정한다. aq = [aq,i]_{|Ve|×1}, aq,i = 1{i = argmax_{ej∈Ve} sim(eq, ej)} · sim(eq, ei) … (3)
• Query-sentence relevance distribution: query q와 각 문장 si의 맥락적 연관을 계산한다. σq = [σq,i]_{|S|×1}, σq,i = sim(q, si) … (4)
• Semantic propagation: sentence-entity bipartite graph에서 이웃의 가중 집계로 activation vector를 갱신한다. a^t_q = MAX(M^T (σq ⊙ (M a^(t-1)_q)), a^(t-1)_q) … (5) 이 벡터화된 식은 n번의 iteration만으로 n-hop entity activation을 가능하게 하며 n은 대체로 작다(≤ 4).
• Dynamic pruning: 전파가 깊어지면 탐색 공간이 지수적으로 증가하므로, 각 전파 단계마다 임계값 δ를 도입해 relevance 점수가 δ를 넘는 entity만 다음 iteration에 남기고 나머지는 가지치기한다. 임계값을 넘는 새 entity가 없으면 과정이 자동 종료된다.

 

[Translated by Claude]

 

일반적으로 직접적인 entity 매칭은 multihop relation을 이어 주는 관련 중간 entity를 놓칠 수 있는데, 이런 entity는 multihop query에 필수적이다. 따라서 이 잠재적 연결자를 식별하는 일이 결정적으로 중요하다. 그러나 그런 중간 entity는 직접 캐낼 수 없으며, 방대한 entity 수는 이를 식별하는 정밀도를 어렵게 만든다. 이를 해결하기 위해 우리는 semantic bridging을 통한 관련 entity activation을 제안한다. 들어오는 query q에 대해 과정은 다음과 같다.

Initial entity activation. query q에 포함된 entity를 식별하고 knowledge graph 안에서의 그 활성화를 sparse vector로 표현한다. 구체적으로 우리는 먼저 SpaCy를 사용해 q에서 entity를 추출하고 이를 Eq로 표기한다. 그런 다음 추출된 각 entity에 대해 knowledge graph에서 가장 유사한 entity를 찾는다. 매칭된 entity의 초기 activation 점수는 그 유사도 점수로 설정된다.

aq = [aq,i]_{|Ve|×1}, where aq,i = 1{i = argmax_{ej∈Ve} sim(eq, ej)} · sim(eq, ei) … (3)

Query-sentence relevance distribution. query q와 코퍼스의 각 문장 si ∈ S 사이의 맥락적 연관을 계산한다. 여기서 S = {s1, s2, …, s|S|}는 코퍼스 내 문장의 집합이다. 이 유사도들을 벡터로 표현한다.

σq = [σq,i]_{|S|×1}, where σq,i = sim(q, si) … (4)

Semantic propagation. σq의 유사도를 semantic similarity extraction을 통해 전파하여 관련 중간 entity를 활성화함으로써, knowledge graph 안에서 multihop relation의 연결을 가능하게 한다. entity activation vector aq는 sentence-entity bipartite graph에서 연관된 이웃들의 가중 집계로 갱신된다.

a^t_q = MAX(M^T (σq ⊙ (M a^(t-1)_q)), a^(t-1)_q) … (5)

여기서 a^t_q는 semantic propagation의 t번째 iteration에서의 entity activation vector다. 몇 번의 iteration만으로 우리는 query의 추론 구조와 정합하는 코퍼스 내 subgraph를 고정하는 맥락적 관련 entity 집합을 식별한다. 이 해법은 multi-hop 추론을 위한 GraphRAG 알고리즘의 relation-matching 과정을 모사한다. 다만 우리의 전략은 암묵적 relation matching을 수행하며 명시적으로 구축된 relational knowledge graph에 의존하지 않는다. 주목할 만하게도 식 (5)의 벡터화된 정식화는 단 n번의 iteration만으로 n-hop entity activation을 가능하게 하며, 여기서 n은 일반적으로 작다(≤ 4). 각 iteration은 세 번의 MatMul(행렬 곱)과 한 번의 MAX 연산을 포함하며, 이는 널리 쓰이는 머신러닝 플랫폼에서 효율적으로 구현되고 병렬로 실행될 수 있다. 나아가 행렬 M과 activation vector a^t_q의 내재적 희소성 덕분에 이를 sparse 형식으로 저장해 메모리 소비를 줄이고, MatMul을 SpMM(sparse matrix multiplication)으로 대체해 계산 비용을 줄일 수 있다.

Dynamic pruning. 위의 semantic bridging은 query entity로부터 잠재적으로 관련 있는 중간 entity로의 초기 연관을 성공적으로 확립하지만, 동시에 큰 난제를 도입한다. 전파가 깊어질수록 탐색 공간이 지수적으로 증가한다는 것이다. 적절한 통제가 없으면 무관한 entity가 반복적으로 새로운 seed 역할을 하게 되어, 과정이 조합적으로 팽창하고 원래 query 의도와 무관한 의미 영역으로 표류할 수 있다. 이 문제를 해결하기 위해 우리는 확장을 고품질 semantic 경로로 제한하는 graph pruning을 수행한다. 구체적으로 각 전파 단계에서 임계값 δ를 도입한다. 새로 활성화된 entity는 그 relevance 점수가 δ를 초과할 때만 다음 iteration을 위해 유지되고, 그렇지 않으면 가지치기된다. 나아가 임계값을 넘는 새로운 entity가 없으면 과정은 자동으로 종료된다. 이 적응적 메커니즘은 전파가 가장 관련 있는 semantic 경로를 따라서만 진행되도록 보장하는 동시에, iteration 범위를 각 query의 복잡도에 맞춰 동적으로 조정한다.

3.2.2 Second Stage: Passage Retrieval via Global Importance Aggregation

• 1단계에서 sentence-entity graph의 local semantic-bridged subgraph 확장을 통해 추출된 관련 entity가, passage(Vp)와 entity(Ve)를 node로 갖는 passage-entity bipartite graph의 importance 점수를 초기화하는 데 쓰인다.
• 2단계는 passage node에 대한 hybrid initialization과 함께 global importance aggregation을 수행하며, passage-entity graph 위에서 Personalized PageRank(PPR)로 각 node의 정제된 전역 importance 점수를 계산한다. I(vi) = (1 − d) + d · Σ_{vj ∈ B(vi)} I(vj)/deg(vj) … (6)
• d는 damping factor(보통 0.85), B(vi)는 vi로 연결되는 node 집합, deg(vj)는 node vj의 outgoing link 수다. entity node의 초기 importance 점수는 1단계에서 계산된 aq로 설정한다.
• passage node의 초기 importance 점수는 I(v|v ∈ Vp) = (λ · sim(q, v) + ln(1 + Σ_{ei ∈ Ea} a_q^(i) · ln(1 + N_ei) / L_ei)) · Wp … (7) 로 주어지며, passage는 PPR 점수로 랭킹되어 상위 k개가 검색된다.

 

[Translated by Claude]

 

첫 번째 단계에서 관련 entity는 sentence-entity graph 안의 local semantic-bridged subgraph 확장을 통해 추출된다. 이 entity들은 passage-entity graph에서 importance 점수를 초기화하는 데 사용되는데, 이 graph는 node가 passage(Vp)와 entity(Ve)를 나타내고 edge가 등장 여부에 기반하여 passage를 그것이 포함하는 entity와 연결하는 bipartite graph다. 두 번째 단계는 중요한 passage를 검색하기 위해 passage node에 대한 hybrid initialization과 함께 global importance aggregation을 수행하며, passage-entity graph 위에서 Personalized PageRank(PPR)를 사용해 각 node vi ∈ Vp ∪ Ve에 대한 정제된 전역 importance 점수를 계산한다.

I(vi) = (1 − d) + d · Σ_{vj ∈ B(vi)} I(vj) / deg(vj) … (6)

여기서 d는 damping factor(보통 0.85)이고, B(vi)는 vi로 연결되는 node의 집합이며, deg(vj)는 node vj로부터의 outgoing link 수다. entity node vi ∈ Ve에 대한 초기 importance 점수는 I(vi | vi ∈ Ve) = a_q^(i)로 설정되며, 여기서 aq = (a_q^(1), a_q^(2), …)는 첫 번째 단계에서 query q에 대해 계산된 entity relevance 점수의 벡터다. passage node v ∈ Vp에 대한 초기 importance 점수는 다음과 같다.

I(v | v ∈ Vp) = ( λ · sim(q, v) + ln( 1 + Σ_{ei ∈ Ea} ( a_q^(i) · ln(1 + N_ei) / L_ei ) ) ) · Wp … (7)

여기서 sim(q, v)는 passage v와 query q 사이의 유사도를 포착하는 PPR base score이고, Ea는 첫 단계에서 활성화된 entity의 집합이며, N_ei는 passage v에서 entity ei의 등장 횟수, L_ei는 entity ei의 계층 수준, Wp는 passage node의 weight coefficient, λ는 trade-off coefficient다. passage는 그 PPR 점수 I(v | v ∈ Vp)로 랭킹되며, 가장 높은 점수를 가진 top-k passage가 retrieval 결과로 선택된다.

4 Experiments

• LinearRAG의 효과성과 효율성을 검증하기 위해 포괄적인 실험을 수행하며, 세 가지 질문에 답하는 것을 목표로 한다.
• Q1(Generation Accuracy): LinearRAG는 state-of-the-art GraphRAG 방법 대비 generation 성능에서 어떤 결과를 보이는가?
• Q2(Efficiency Analysis): LinearRAG는 기존 GraphRAG 접근법 대비 얼마나 비용 효율적이고 시간 효율적인가?
• Q3(Ablation Study): LinearRAG의 각 구성 요소는 전체 성능에 어떤 기여를 하는가?
• retrieval 품질, 파라미터 민감도, backbone 분석, 대규모 효율성 분석, 사례 연구에 대한 추가 실험은 Appendix E에 제시된다.

 

[Translated by Claude]

 

이 절에서 우리는 LinearRAG의 효과성과 효율성을 검증하기 위해 포괄적인 실험을 수행한다. 구체적으로 다음 질문들에 답하는 것을 목표로 한다. Q1(Generation Accuracy): LinearRAG는 generation 성능 측면에서 state-of-the-art GraphRAG 방법들과 비교해 어떤 성능을 내는가? Q2(Efficiency Analysis): LinearRAG는 기존 GraphRAG 접근법에 비해 얼마나 비용 효율적이고 시간 효율적인가? Q3(Ablation Study): LinearRAG의 각 구성 요소는 전체 성능에 어떤 기여를 하는가? (LinearRAG의 포괄적 평가를 위해 retrieval 품질, 파라미터 민감도, backbone 분석, 대규모 효율성 분석, 사례 연구에 관한 추가 실험은 Appendix E에 제시되어 있음을 밝힌다.)

4.1 Experimental Setting

• Datasets: 널리 쓰이는 multi-hop QA 데이터셋 3종인 HotpotQA(Yang et al., 2018), 2WikiMultiHopQA(2Wiki)(Ho et al., 2020), MuSiQue(Trivedi et al., 2022)와 GraphRAG-Bench(Xiang et al., 2025)의 domain-specific Medical 데이터셋에서 평가한다. HippoRAG와 동일한 평가 방법을 따라 동일한 코퍼스를 retrieval에 사용하고 각 validation set에서 1,000개 질문을 선택한다.
• Baselines: (i) Zero-shot LLM Inference — LLaMA3 (8B), LLaMA3 (13B)(Dubey et al., 2024), GPT-3.5-turbo, GPT-4o-mini(OpenAI, 2023). (ii) Vanilla RAG — top passage 1·3·5개를 검색하는 여러 설정과 chain-of-thought 추론 프롬프트 결합. (iii) state-of-the-art GraphRAG — KGP, G-retriever, RAPTOR, E2GraphRAG, LightRAG, HippoRAG, GFM-RAG, HippoRAG2.
• Evaluation Metrics: end-to-end QA 성능은 Contain-Match Accuracy(Contain-Acc.)와 GPT-Evaluation Accuracy(GPT-ACC.)로, retrieval 품질은 GraphRAG-Bench의 Context Relevance와 Evidence Recall로 평가한다. Medical 데이터셋은 정답이 긴 서술문이므로 GPT-ACC.만 사용한다.
• Implementations: 모든 알고리즘이 동일한 embedding model인 all-mpnet-base-v2(Xiao et al., 2023)를 사용하고, 모든 방법에서 top-k retrieval의 k = 5로 설정하며, 모든 RAG 접근법이 generation과 evaluation에 동일한 LLM(GPT-4o-mini)을 사용한다. 하드웨어 구성은 Appendix C에 상술되어 있다.

 

[Translated by Claude]

 

Datasets. 우리는 먼저 널리 사용되는 세 개의 multi-hop QA 데이터셋과 하나의 domain-specific 데이터셋에서 LinearRAG의 효과성을 평가한다. HotpotQA(Yang et al., 2018), 2WikiMultiHopQA(2Wiki)(Ho et al., 2020), MuSiQue(Trivedi et al., 2022), 그리고 GraphRAG-Bench(Xiang et al., 2025)의 Medical 데이터셋이다. 우리는 HippoRAG와 동일한 평가 방법을 따라 retrieval에 동일한 코퍼스를 사용하고 각 validation set에서 1,000개의 질문을 선택한다. 이 설정은 서로 다른 방법들 사이의 공정한 비교를 가능하게 한다. 또한 우리는 GraphRAG-Bench(Xiang et al., 2025)의 domain-specific Medical 데이터셋에서도 우리 접근법을 시험하여, LinearRAG가 generation 결과와 retrieval 품질을 모두 개선함을 보인다.

Baselines. 우리는 모든 baseline을 세 그룹으로 분류한다. (i) Zero-shot LLM Inference: LLaMA3 (8B)와 LLaMA3 (13B)(Dubey et al., 2024)를 비롯해 GPT-3.5-turbo와 GPT-4o-mini(OpenAI, 2023)를 포함한 여러 기반 모델을 평가한다. (ii) 우리는 여러 retrieval 설정(top passage를 1개, 3개, 5개 검색)에 걸쳐 Vanilla RAG 방법론을 배치하며, semantic 기반 문서 retrieval과 chain-of-thought 추론 프롬프트를 결합해 LLM의 generation 과정을 안내한다. (iii) State-of-the-art GraphRAG Systems: KGP(Wang et al., 2024), G-retriever(He et al., 2024), RAPTOR(Sarthi et al., 2024), E2GraphRAG(Zhao et al., 2025), LightRAG(Guo et al., 2024), HippoRAG(Gutiérrez et al., 2024), GFM-RAG(Luo et al., 2025), HippoRAG2(Gutiérrez et al., 2025)를 포함한 선도적인 GraphRAG 구현들과 비교한다. 이 중 RAPTOR는 코퍼스를 계층적 tree graph로 조직하고, G-Retriever, LightRAG, HippoRAG, GFM-RAG, HippoRAG2는 passage에서 triple을 추출해 구조화된 graph를 구축하며, E2GraphRAG는 두 전략을 통합한다.

Evaluation Metrics. 우리는 두 범주에 걸친 네 가지 지표로 우리 방법을 평가한다. end-to-end QA 성능에 대해서는 기존 연구(Wang et al., 2025)를 따라 다음을 사용한다. 1) Contain-Match Accuracy(Contain-Acc.)는 생성된 응답 안에 정답이 나타나는지를 확인하고, 2) GPT-Evaluation Accuracy(GPT-ACC.)는 예측된 답이 ground truth와 일치하는지를 평가하는 LLM 기반 지표다. Medical 데이터셋의 경우 정답이 긴 서술형 진술로 이루어져 있으므로 GPT-ACC.만으로 평가한다. retrieval 품질 평가에 대해서는 GraphRAG-Bench(Xiang et al., 2025)의 지표를 채택한다. 1) Context Relevance는 질문과 검색된 passage 사이의 semantic 정합을 측정하고, 2) Evidence Recall은 검색된 내용이 정답에 필요한 모든 정보를 담고 있는지를 평가한다.

Implementations. 구현의 일관성을 위해 모든 알고리즘은 동일한 embedding model, 즉 all-mpnet-base-v2(Xiao et al., 2023)를 사용한다. 모든 방법에서 top-k retrieval의 k = 5로 설정한다. 모든 RAG 접근법은 generation과 evaluation 태스크 모두에 동일한 LLM(GPT-4o-mini)을 사용한다. 모든 실험은 Appendix C에 상술된 하드웨어 구성에서 수행되었다.

4.2 Generation Accuracy (Q1)

• Obs. 1. RAG는 zero-shot LLM 성능을 크게 향상시킨다. GPT-4o-mini는 retrieval 없이 MuSiQue에서 GPT 기반 정확도 15.80%에 그치지만, top-5 context를 사용한 Vanilla RAG는 같은 데이터셋에서 29.60%로 끌어올린다.
• Obs. 2. GraphRAG 방법은 복잡한 추론에서 RAG가 놓치는 결정적 context를 제공한다. k 값을 키우면 정확도가 오르지만 높은 값에서는 이득이 감소하며, vanilla RAG는 문서 내에 언급된 entity나 키워드 검색에 지나치게 집중해 추론 사슬에 필수적인 논리 연관 문서를 놓친다. 그중 HippoRAG 2가 대부분 데이터셋에서 가장 좋은 결과를 내어 HotpotQA에서 Contain 기반 정확도 62.90%, MuSiQue에서 31.00%를 달성한다.
• Obs. 3. LinearRAG는 구축된 graph 품질에 민감한 GraphRAG 방법들 대비 우월한 성능을 보인다. LinearRAG는 비효과적인 graph 구축을 제거하고 모든 데이터셋에서 모든 baseline을 유의한 차이로 능가한다.
• 특히 LinearRAG는 2Wiki에서 GPT 기반 정확도 63.70%를 달성해 두 번째로 좋은 baseline 대비 약 3.80%p의 절대 향상을 보이며, Contain 기반 정확도를 70.20%까지 끌어올린다.

Table 1: Result (%) of baselines and LinearRAG on four benchmark datasets in terms of both Contain-Match and GPT-Evaluation Accuracy. The best result for each dataset is highlighted in bold, while the second result is indicated with an underline.

 

 

[Translated by Claude]

 

Q1을 다루기 위해 우리는 네 개의 벤치마크 데이터셋에 걸쳐 여러 baseline 방법과 LinearRAG를 비교함으로써 generation 성능에 대한 포괄적 평가를 수행한다. 상세한 실험 결과는 Table 1에 제시되어 있다. 우리의 분석에 기반하여 다음의 핵심 관찰을 도출한다.

Obs. 1. RAG는 zero-shot LLM 성능을 유의하게 향상시킨다. 외부 지식 retrieval 없이 LLM에 직접 프롬프트를 주는 방식은 모든 데이터셋에서 가장 나쁜 성능을 낸다. 예를 들어 GPT-4o-mini 같은 진보된 모델도 retrieval 증강 없이 작동할 때 MuSiQue 데이터셋에서 GPT 기반 정확도 15.80%에 그친다. 그러나 관련 코퍼스 내용을 프롬프트에 통합하면 성능이 크게 개선되어, top-5 검색 context를 사용한 Vanilla RAG는 같은 데이터셋에서 정확도를 29.60%까지 끌어올린다. 이런 유의한 성능 향상은 정보 집약적 응용에서 RAG 메커니즘이 본질적으로 필요함을 입증한다.

Obs. 2. GraphRAG 방법은 복잡한 추론에서 RAG 방법이 놓치는 결정적인 context를 제공한다. k 값을 키우면 정확도가 개선되지만 더 높은 값에서는 이득이 감소하며, 이는 multi-hop 추론에서 vanilla RAG의 핵심 한계를 드러낸다. 즉 문서 안에 언급된 entity나 키워드를 찾는 데 지나치게 집중하는 경향이 있어, 완전한 추론 사슬에 필수적인 논리 연관 문서를 놓친다는 것이다. 반면 retrieval에서 구조적 의존성을 모델링하는 방법들은 일관되게 더 좋은 성능을 낸다. 그중 HippoRAG 2가 대부분의 데이터셋에서 가장 좋은 결과를 달성하여, HotpotQA에서 62.90%, MuSiQue 데이터셋에서 31.00%의 Contain 기반 정확도를 기록한다.

Obs. 3. LinearRAG는 구축된 graph 품질에 대한 민감성을 겪는 GraphRAG 방법들에 비해 우월한 성능을 보인다. 전형적인 GraphRAG 방법들은 지식을 graph로 명시적으로 구조화함으로써 semantic 오정합을 다루지만, 그 효과성은 relation extraction에 크게 의존한다. 대신 LinearRAG는 비효과적인 graph 구축에서 벗어나며, 실증적으로 모든 데이터셋에서 모든 baseline을 유의한 폭으로 능가한다. 특히 LinearRAG는 2Wiki에서 63.70%의 GPT 기반 정확도를 달성하여 두 번째로 좋은 baseline 대비 약 3.80%의 절대적 개선을 보이고, Contain 기반 정확도를 70.20%까지 끌어올린다.

4.3 Efficiency Analysis (Q2)

• 2WikiMultiHopQA 데이터셋에서 indexing과 retrieval 단계의 token 사용량과 실행 시간을 비교하여 GraphRAG 모델별 프롬프트 통계를 분석한다.
• Obs. 4. 복잡한 graph 구축은 indexing과 retrieval 두 단계 모두에서 불가피하게 상당한 시간 비용을 초래한다. G-Retriever와 LightRAG는 정교한 schema 정의를 채택해 효율이 눈에 띄게 나쁘며, LightRAG는 indexing에 4,933.22초, retrieval에 10.963초가 필요하다.
• Obs. 5. LLM token 비용을 줄이는 것이 반드시 성능에 부정적 영향을 주지는 않는다. HippoRAG2는 프롬프트 구성에 3.05M token, completion 단계에 0.98M token만 사용하는 반면 HippoRAG2는 프롬프트 구성에 4.98M token, completion에 1.22M token을 소비한다. 이런 낮은 token 비용에도 두 모델 모두 G-Retriever와 LightRAG를 능가한다.
• Obs. 6. LinearRAG는 가장 강력한 전반적 효율성을 제공한다. 전체 파이프라인을 고려하면 LinearRAG가 가장 빠르고 token 사용량이 0이다. E2GraphRAG와 RAPTOR가 retrieval 단계에서는 LinearRAG보다 시간 효율적이지만, 이는 모델 성능의 유의한 저하를 대가로 한다.

Table 2: Efficiency and performance comparison of different GraphRAG methods. Notably, Accuracy represents the average of Contain-Acc. and GPT-Acc. metrics. Prompt tokens represent input to LLM, and completion tokens represent LLM output. Best results are highlighted in bold, and second-best results are underlined.

 

 

[Translated by Claude]

 

관련된 효율성과 비용 함의를 더 잘 이해하기 위해, 우리는 2WikiMultiHopQA 데이터셋에서 서로 다른 GraphRAG 모델들의 token 사용량과 실행 시간을 비교함으로써 indexing 및 retrieval 단계 동안의 프롬프트 통계에 대한 전용 분석을 수행한다. 결과는 Table 2에 제시되어 있으며, 우리의 핵심 관찰을 다음과 같이 요약한다.

Obs. 4. 복잡한 graph 구축은 indexing과 retrieval 단계 모두에서 불가피하게 상당한 시간 비용을 초래한다. G-Retriever와 LightRAG 같은 모델은 정교한 schema 정의를 채택하여 눈에 띄게 나쁜 효율성을 낳는다. 예를 들어 LightRAG는 indexing에 4,933.22초, retrieval에 10.963초를 필요로 한다. 이 모델들은 graph 안에 entity와 keyword를 정의하고 고수준과 저수준 retrieval을 모두 수행한다. 그 결과 LLM은 이 두 정보원에서 검색된 방대한 양의 내용을 처리하는 부담을 지게 되며, 이는 더 높은 비용과 지연으로 이어진다.

Obs. 5. LLM token 비용을 줄이는 것이 반드시 성능에 부정적 영향을 주지는 않는다. G-Retriever와 LightRAG의 복잡한 프롬프트 구성과 completion은 일관된 성능 개선을 가져오지 못한다. 예를 들어 HippoRAG2는 프롬프트 구성 동안 3.05M token만 사용하고 completion 단계에서 0.98M token을 사용하는 반면, HippoRAG2는 프롬프트 구성에 4.98M token을, completion에 1.22M token을 소비한다. 이런 더 낮은 token 비용에도 불구하고 두 모델 모두 G-Retriever와 LightRAG를 능가한다.

Obs. 6. LinearRAG는 가장 강력한 전반적 효율성을 제공한다. 전체 파이프라인을 고려할 때 LinearRAG는 가장 빠르며 token 사용량을 전혀 발생시키지 않는다. E2GraphRAG와 RAPTOR가 retrieval 단계에서는 LinearRAG보다 시간 효율적이지만, 이는 모델 성능의 유의한 저하를 대가로 한다. 이 방법들은 추론 사슬 안의 구조적 의존성을 고려하지 않고 query와 직접 관련된 문서만 검색하기 때문이다. 이에 비해 LinearRAG의 경량 파이프라인은 indexing과 retrieval 모두에서 LLM 호출을 피하여 지연을 최소화하고 token 비용을 제거한다. 속도, 확장성, 비용 통제와 함께 강력한 성능을 요구하는 배포 환경에서 LinearRAG는 가장 실용적인 선택이다.

4.4 Ablation Study (Q3)

• 네 개 데이터셋에 걸쳐 LinearRAG의 핵심 구성 요소에 대한 체계적 ablation을 수행하며, 두 모듈을 검토한다.
• ❶ Relevant Entity Activation via Semantic Bridging(w/o Entity Activation): query에서 추출한 초기 entity를 그대로 활성화 entity로 사용하고, query entity에서 관련 entity로 activation 점수를 전파하는 semantic bridging 과정을 건너뛴다.
• ❷ Passage Retrieval via Global Importance Aggregation(w/o Global Importance Aggregation): personalized PageRank를 건너뛰고 1단계에서 계산된 초기 activation 점수만으로 코퍼스에서 문서를 검색한다.
• Obs. 7. LinearRAG의 각 모듈은 최적 성능에 결정적이다. 평가 지표는 GPT-Acc.와 Contain-Acc.의 평균이며, LinearRAG는 HotpotQA 65.40%, 2WikiMultiHopQA 66.95%, MuSiQue 35.45%, Medical 63.72%를 기록한다. w/o Entity Activation은 각각 63.15%, 64.40%, 31.65%, 61.69%, w/o Global Importance Aggregation은 각각 63.35%, 64.20%, 32.05%, 61.73%로 떨어진다.

Figure 4: Ablation study on key modules of LinearRAG under four different datasets. The y-axis represents the average of GPT-Acc. and Contain-Acc.

 

[Translated by Claude]

 

Q3을 다루기 위해 우리는 네 개 데이터셋에 걸쳐 LinearRAG의 핵심 구성 요소에 대한 체계적인 ablation study를 수행한다. 우리는 두 가지 핵심 모듈을 검토한다. ❶ Relevant Entity Activation via Semantic Bridging, 즉 w/o Entity Activation은 query에서 추출된 초기 entity를 그대로 활성화된 entity로 사용하며, query entity로부터 knowledge graph 내 관련 entity로 activation 점수를 전파하는 semantic bridging 과정을 우회한다. ❷ Passage Retrieval via Global Importance Aggregation, 즉 w/o Global Importance Aggregation은 personalized PageRank 알고리즘을 건너뛰고 전역 importance 관계를 고려하지 않은 채 ❶ 단계에서 계산된 초기 activation 점수만으로 코퍼스에서 문서를 검색한다. 각 변형은 GPT-Acc.와 Contain-Acc.의 평균을 주된 평가 지표로 삼아 평가된다. 실험 결과는 Figure 4에 제시되어 있으며, 우리는 다음과 같은 발견을 얻는다.

Obs. 7. LinearRAG의 각 모듈은 최적 성능에 결정적이다. 성능 이득은 주로 두 개의 상보적 단계에 기인한다. 첫 번째 단계에서 LinearRAG는 semantic 유사도 전파를 통해 맥락적으로 관련 있는 entity를 식별하여 multi-hop 질문 안에 숨겨진 논리적 관계를 드러낸다. 두 번째 단계에서 모델은 활성화된 subgraph 위에서 personalized PageRank 알고리즘을 사용해 전역적 관점에서 문서의 중요도를 평가한다. 이 두 모듈은 서로 다르지만 상보적인 목적을 수행하여, LinearRAG가 효과성과 효율성을 모두 달성할 수 있게 한다.

5 Conclusion

• 본 연구는 비용이 크고 오류에 취약한 relation extraction을 경량 entity extraction으로 대체하여 graph 구축을 단순화하는 새로운 GraphRAG 프레임워크인 LinearRAG를 소개한다.
• LinearRAG는 entity, sentence, passage를 포괄하는 hierarchical graph를 생성한다.
• 그 위에서 local·global 구조 정보를 함께 활용해 precision-recall Pareto frontier를 전진시키는 2단계 retrieval 메커니즘을 특징으로 한다.
• 광범위한 실험은 LinearRAG가 retrieval 정밀도, generation 정확도, 확장성에서 state-of-the-art baseline을 일관되게 넘어서며 복잡한 query 처리를 위한 robust하고 효율적인 해법을 제공함을 입증한다.

 

[Translated by Claude]

 

본 연구에서 우리는 비용이 크고 오류에 취약한 relation extraction을 경량 entity extraction으로 대체함으로써 graph 구축을 단순화하는 새로운 GraphRAG 프레임워크인 LinearRAG를 소개한다. 이는 entity, sentence, passage를 포괄하는 hierarchical graph를 생성한다. 그 위에서 LinearRAG는 local 구조 정보와 global 구조 정보를 함께 활용하여 precision-recall Pareto frontier를 전진시키는 2단계 retrieval 메커니즘을 특징으로 한다. 광범위한 실험은 LinearRAG가 retrieval 정밀도, generation 정확도, 확장성에서 state-of-the-art baseline을 일관되게 능가하여, 복잡한 query를 다루기 위한 robust하고 효율적인 해법을 제공함을 입증한다.

Ethics Statement

• 실험에 사용된 앞의 세 데이터셋인 HotpotQA, 2WikiMultiHopQA, MuSiQue는 널리 쓰이는 데이터셋이다.
• medical 벤치마크 데이터셋은 공개 자원으로부터 구축되었다.
• 본 연구는 데이터 프라이버시, 투명성, 책임 있는 컴퓨팅 관행에 관해 ICLR Code of Ethics를 엄격히 준수한다.
• 참가자가 관여된 부분은 없다.

 

[Translated by Claude]

 

실험에 사용된 앞의 세 데이터셋, 즉 HotpotQA, 2WikiMultiHopQA, MuSiQue는 널리 사용되는 데이터셋이다. medical 벤치마크 데이터셋은 공개 자원으로부터 구축되었다. 우리의 연구는 특히 데이터 프라이버시, 투명성, 책임 있는 컴퓨팅 관행에 관해 ICLR Code of Ethics를 엄격히 준수한다. 그리고 관여된 참가자는 없다.

Reproducibility Statement

• 논문의 주요 실험 결과를 재현하는 데 필요한 상세 정보를 제공하며, 여기에는 데이터 분할과 hyperparameter 구성이 포함된다.
• 각 실험에 대해 메모리 사용량과 실행 시간 같은 필요 계산 자원을 개괄한다.
• 모든 baseline 모델은 공개 저장소에서 가져왔다.
• 코드와 데이터셋은 공개되어 있다.

 

[Translated by Claude]

 

우리는 데이터 분할과 hyperparameter 구성을 포함하여 논문의 주요 실험 결과를 재현하는 데 필요한 상세 정보를 제공한다. 추가로 각 실험에 대해 메모리 사용량과 실행 시간 같은 필요한 계산 자원을 개괄한다. 모든 baseline 모델은 공개 저장소에서 가져왔다. 우리의 코드와 데이터셋은 공개되어 있다.

A Datasets

• 실험 평가는 네 개 데이터셋에서 수행된다. multi-hop 질의응답을 위한 확립된 벤치마크 3종(HotpotQA, MuSiQue, 2WikiMultiHopQA)과 하나의 domain-specific 데이터셋이다.
• HotpotQA(Yang et al., 2018): multi-hop 추론 능력 평가를 위해 설계된 97k개의 질의응답 인스턴스로 구성되며, 각 질문은 최대 2개의 gold-standard supporting passage와 다수의 무관한 문서 속에서 여러 문서의 정보를 종합하도록 요구한다.
• 2WikiMultiHopQA(2Wiki)(Ho et al., 2020): 여러 Wikipedia 문서에 걸친 정보 통합을 요구하는 192k개 질문을 담은 multi-hop 추론 벤치마크로, 각 인스턴스는 2개 또는 4개의 특정 문서로부터 근거를 종합해야 한다.
• MuSiQue(Trivedi et al., 2022): 2~4단계의 순차적 추론을 요구하는 25k개 질의응답 쌍의 정교한 multi-hop QA 벤치마크다.
• Medical: GraphRAG-Bench(Xiang et al., 2025)에서 파생된 특화 부분집합으로, National Comprehensive Cancer Network(NCCN) 가이드라인의 구조화된 임상 데이터로 구축되었으며 fact retrieval, complex reasoning, contextual summarization, creative generation의 네 가지 난이도 태스크에 걸쳐 총 4,076개 질문을 포함한다.

 

[Translated by Claude]

 

우리의 실험 평가는 네 개 데이터셋에서 수행된다. multi-hop 질의응답을 위한 확립된 multi-hop 벤치마크 데이터셋 세 개인 HotpotQA(Yang et al., 2018), MuSiQue(Trivedi et al., 2022), 2WikiMultiHopQA(2Wiki)(Ho et al., 2020), 그리고 하나의 domain-specific 데이터셋이다. 아래에서 각 데이터셋의 핵심 특성을 간결하게 개괄한다.

(i) HotpotQA(Yang et al., 2018): multi-hop 추론 능력을 평가하도록 설계된 97k개의 질의응답 인스턴스로 구성된 포괄적 벤치마크다. 각 질문은 모델이 여러 문서의 정보를 종합하도록 요구하며, 최대 2개의 gold-standard supporting passage가 다수의 무관한 문서와 함께 제공된다. 이 구조는 시스템이 효과적인 문서 간 추론과 근거 선택을 수행하도록 도전한다.

(ii) 2WikiMultiHopQA(2Wiki)(Ho et al., 2020): 여러 Wikipedia 문서에 걸친 정보 통합을 필요로 하는 192k개의 질문을 담은 multi-hop 추론 벤치마크다. 각 인스턴스는 2개 또는 4개의 특정 문서로부터 근거를 종합해야 하며, 이는 모델의 구조화된 문서 간 추론 능력과 일관된 정보 흐름 유지 능력을 시험한다.

(iii) MuSiQue(Trivedi et al., 2022): 2~4단계의 순차적 추론 단계를 요구하는 25k개의 질의응답 쌍을 특징으로 하는 정교한 multi-hop QA 벤치마크다. 각 질문은 여러 문서에 걸친 일관된 다단계 논리적 추론을 요구하며, 시스템이 추론 과정 전반에서 맥락적 일관성을 유지하면서 구조화된 추론 사슬을 실행하도록 도전한다.

(iv) Medical: GraphRAG-Bench(Xiang et al., 2025)에서 파생된 특화 부분집합으로, National Comprehensive Cancer Network(NCCN) 가이드라인에서 얻은 구조화된 임상 데이터로 구축되었다. 이 가이드라인은 표준화된 치료 프로토콜, 약물 상호작용 위계, 진단 기준을 제공한다. 이 데이터셋은 복잡도가 점증하는 네 가지 태스크, 즉 fact retrieval, complex reasoning, contextual summarization, creative generation을 포괄하며 모든 난이도 수준을 합쳐 총 4,076개의 질문으로 이루어진다.

B Baseline Details

• 실험에서 우리 방법과 비교한 널리 사용되는 여러 GraphRAG 접근법의 세부를 정리한다.
• KGP는 LLM으로 여러 passage 위에 knowledge graph를 구축하고 retrieval 단계에서 LLM 기반 graph traversal agent를 도입하며, G-Retriever는 subgraph retrieval을 Prize-Collecting Steiner Tree 최적화 문제로 정식화해 GNN과 LLM을 결합한다.
• RAPTOR는 clustering과 abstractive summarization으로 계층적 tree를 만들고, E2GraphRAG는 spaCy로 entity를 추출하고 LLM으로 passage 그룹을 요약해 계층 tree를 구성한다.
• LightRAG는 텍스트 indexing 안에 graph 기반 표현을 결합한 2계층 프레임워크를, HippoRAG는 query concept을 seed로 하는 Personalized PageRank를, GFM-RAG는 graph-enhanced retriever를, HippoRAG2는 문단 통합과 contextualization을 강화한 HippoRAG 확장을 채택한다.

 

[Translated by Claude]

 

우리의 실험에서 우리는 널리 사용되는 여러 GraphRAG 접근법과 우리 방법을 비교한다.

(i) KGP(Wang et al., 2024)는 LLM으로 여러 passage 위에 knowledge graph를 구축한다. retrieval 단계에서는 LLM이 주도하는 graph traversal agent를 도입하여 graph를 탐색하고 supporting passage를 점진적으로 수집한다.

(ii) G-Retriever(He et al., 2024)는 subgraph retrieval을 Prize-Collecting Steiner Tree 최적화 문제로 정식화함으로써 graph neural network와 LLM을 결합하며, 텍스트 graph 위에서 효과적인 대화형 질의응답을 가능하게 하는 동시에 hallucination을 완화하고 확장성을 강화한다.

(iii) RAPTOR(Sarthi et al., 2024)는 clustering 알고리즘과 abstractive summarization 기법을 적용해 계층적 tree를 구성하여 여러 semantic granularity에서의 표현을 가능하게 한다.

(iv) E2GraphRAG(Zhao et al., 2025)는 indexing 단계에서 spaCy로 entity를 추출하고 LLM으로 passage 그룹을 요약하여 node가 인코딩된 계층적 tree를 만든다. retrieval 단계에서는 k-hop 이웃 안에서 관련 entity를 찾아 연관된 passage를 수집해 랭킹하며, 그렇지 않은 경우에는 tree 전체에 대해 dense retrieval을 수행한다.

(v) LightRAG(Guo et al., 2024)는 텍스트 indexing 안에 graph 기반 표현을 통합하는 2계층 프레임워크를 채택하여, 세밀한 entity-relation 매핑과 거친 주제 구조를 병합한다.

(vi) HippoRAG(Gutiérrez et al., 2024)는 학습이 필요 없는 graph 강화 retriever로, query concept을 seed로 삼는 Personalized PageRank 알고리즘을 사용해 서로 떨어진 문서들에 걸쳐 단일 단계 또는 multi-hop retrieval을 수행한다.

(vii) GFM-RAG(Luo et al., 2025)는 문서로부터 graph를 구축하고 graph 강화 retriever를 사용해 관련 문서를 검색함으로써 GraphRAG 패러다임을 구현한다.

(viii) HippoRAG2(Gutiérrez et al., 2025)는 강화된 문단 통합과 contextualization으로 HippoRAG를 확장한다. factual memory 능력을 유지하고 associative memory 성능을 개선하면서 seed node 선택과 PageRank reset probability를 최적화한다.

C Machine Configuration

• 본 연구의 모든 실험은 Table 3에 상술된 하드웨어 구성에서 수행되었다.
• GPU는 NVIDIA GeForce RTX 4090 D(24GB VRAM)를 사용했다.
• CPU는 Intel(R) Xeon(R) Gold 6426Y를 사용했다.

Table 3: Detailed machine configuration used in our experiments.

 

 

[Translated by Claude]

 

본 연구의 모든 실험은 Table 3에 상술된 하드웨어 구성에서 수행되었다.

D Efficiency Analysis of Graph Construction: All-Stage Linear Scalability

• LinearRAG의 효율성 분석을 제시하며, graph 구축과 retrieval 동안 실행 시간과 메모리 소비 모두에서 선형 확장성을 달성하여 all-stage 선형 확장성을 보장함을 입증한다.
• Graph construction stage: 문장 분할과 NER 같은 경량 연산으로 계산 복잡도는 O(|P| · T)이며 T는 각 passage의 평균 길이다. 이 단계는 LLM token 소비가 없다. 메모리는 embedding이 O(|P| · T), sparse 형태의 인접행렬 M과 C가 O(|P| + |S|) = O(|P|)이므로 전체 O(|P| · T)로 코퍼스 크기에 선형이다.
• Retrieval stage: 유사도 계산, SpMM을 사용한 semantic propagation, PPR iteration을 포함한다. 각 전파 단계는 O(nnz) 시간이 들며 nnz는 sparse 행렬의 비영(非零) 원소 수(O(|S|))이고, bipartite graph 위의 PPR은 edge 수에 대해 선형 시간(O(|P|))에 계산 가능하다. 전체 계산 복잡도는 O(|P|)다.
• Acceleration with parallel computation: graph 구조의 벡터화된 정식화 덕분에 모든 데이터 조작을 병렬 계산으로 효율적으로 가속할 수 있으며, 이는 4.3절과 E.4절의 효율성 실험에서 실증적으로 검증된다.

 

[Translated by Claude]

 

우리는 LinearRAG의 효율성 분석을 제시하고, graph 구축과 retrieval 동안 실행 시간과 메모리 소비 모두에서 선형 확장성을 달성하여 all-stage 선형 확장성을 보장함을 입증한다. 상세한 분석은 아래에 제시한다.

Graph construction stage는 코퍼스에 대한 문장 분할과 named entity recognition 같은 경량 연산을 포함한다. 그 결과 계산 복잡도는 O(|P| · T)이며, 여기서 T는 각 passage의 평균 길이를 나타낸다. 특히 이 단계는 LLM token 소비를 발생시키지 않는다. 메모리 사용량에 관해서는, 저장해야 할 첫 번째 자료구조가 passage, node, sentence의 embedding이며 이들은 모두 코퍼스 크기에 대해 선형으로, 즉 O(|P| · T)로 확장된다. 두 번째 자료구조 집합은 두 개의 인접행렬 M과 C로, 내재적 희소성을 활용해 sparse 형태로 저장된다(각 문장은 최대 약 4개의 entity를, 각 passage는 최대 약 10개의 entity를 포함한다). 따라서 메모리 소비는 O(|P| + |S|)이며, 문장 수가 passage 수에 비례하므로 O(|P|)로 단순화된다. 그러므로 전체 메모리 복잡도는 O(|P| · T + |P|) = O(|P| · T), 즉 코퍼스 크기에 대해 선형이다.

Retrieval stage는 유사도 계산, SpMM(sparse matrix multiplication)을 사용한 semantic propagation, 그리고 Personalized PageRank(PPR) iteration을 포함한다. 각 전파 단계는 O(nnz) 시간을 필요로 하는데, 여기서 nnz는 sparse 행렬의 비영 원소 수(O(|S|))이며, bipartite graph 위의 PPR은 edge 수에 대해 선형 시간(O(|P|))에 계산 가능하다. 전반적으로 계산 복잡도는 O(|P|)다. 메모리 소비는 주로 sparse graph 구조, activation vector(크기 O(|E| + |S| + |P|)), 그리고 query별 임시 계산을 적재하는 데서 발생한다.

Acceleration with parallel computation. 위의 분석은 graph 구축과 retrieval 모두에서 LinearRAG의 선형 확장성을 확인해 준다. 추가로 graph 구조의 벡터화된 정식화 덕분에 모든 데이터 조작을 병렬 계산을 통해 효율적으로 가속할 수 있어, 두 단계 모두에서 성능을 더욱 끌어올린다. 이는 4.3절과 Appendix E.4의 효율성 실험에서 실증적으로 검증된다.

E Additional Experiments

• E.1은 retrieval 품질 평가(Q4)를, E.2는 hyper-parameter 민감도(Q5)를 다룬다.
• E.3은 서로 다른 sentence embedding의 효과성(Q6)을, E.4는 대규모 효율성 분석(Q7)을 다룬다.
• E.5는 사례 연구(Q8)를 제시한다.

 

[Translated by Claude]

 

이 절은 retrieval 품질 평가(E.1), hyper-parameter 민감도(E.2), 서로 다른 sentence embedding의 효과성(E.3), 대규모 효율성 분석(E.4), 사례 연구(E.5)의 다섯 하위 절로 구성된다.

E.1 Retrieval Quality Evaluation (Q4)

• generation 성능을 넘어선 포괄적 평가를 위해 GraphRAG-Bench의 설정을 채택하고 난이도가 점증하는 네 태스크(Fact Retrieval, Complex Reasoning, Contextual Summarization, Creative Generation)를 활용한다. 비교는 GraphRAG-Bench와 동일하게 Medical 데이터셋에서 수행한다.
• Obs. 8. GraphRAG 모델은 RAG baseline 대비 recall 지표에서, 특히 creative generation 태스크에서 유의한 개선을 보이지만 relevance 지표에서는 뒤처진다. GFM-RAG는 creative generation에서 recall을 44.88%에서 83.51%로 높이지만 relevance는 58.73%에서 22.87%로 떨어진다.
• Obs. 9. LinearRAG는 relevance 지표에서 GraphRAG 모델 대비 막대한 성능 향상을 보이며 높은 recall과 강한 relevance의 이점을 동시에 갖는다.
• 구체적으로 complex reasoning 태스크에서 LinearRAG는 recall 87.03%, relevance 81.58%를 달성하여 recall 85.03%에 relevance는 33.06%에 그친 GFM-RAG를 크게 앞선다.

Table 4: Retrieval quality evaluation results (%) of different baselines across four different question categories. The table compares recall and relevance metrics for fact retrieval, complex reasoning, contextual understanding, and creative generation tasks. The best results are highlighted in bold, and second-best results are underlined.

 

 

[Translated by Claude]

 

generation 성능을 넘어선 더 포괄적인 평가를 제공하기 위해, 우리는 GraphRAG-Bench의 설정을 채택하고 난이도가 점증하는 네 개의 태스크, 즉 Fact Retrieval, Complex Reasoning, Contextual Summarization, Creative Generation을 활용한다. 비교는 GraphRAG-Bench와 동일하게 Medical 데이터셋에서 수행된다. LinearRAG를 대표적인 GraphRAG 방법들과 비교한 결과는 Table 4에 제시되어 있으며, 다음의 관찰을 얻는다.

Obs. 8. GraphRAG 모델은 RAG baseline에 비해, 특히 creative generation 태스크에서 recall 지표의 유의한 개선을 보이지만 relevance 지표에서는 뒤처진다. 우리는 그 이유가 두 가지라고 추론한다. 한편으로 fact retrieval 같은 더 단순한 태스크에서는 필요한 supporting fact를 모두 recall하기 위해 추론 사슬을 분석할 필요가 없다. 직접적인 semantic retrieval로 충분하며, 이는 graph traversal 동안 무관하거나 중복된 정보를 검색할 위험을 줄인다. 다른 한편으로 creative generation 같은 더 복잡한 태스크에서는 만족스러운 출력을 내기 위해 강한 논리적 의존성을 가진 연속적인 문서가 필요하다. RAG는 gold answer의 바탕에 깔린 graph 구조 때문에 그런 복잡한 관계를 포착하는 데 고전한다. 구체적으로 GFM-RAG는 creative generation에서 recall을 44.88%에서 83.51%로 개선하지만 relevance는 58.73%에서 22.87%로 하락한다.

Obs. 9. LinearRAG는 relevance 지표에서 GraphRAG 모델 대비 막대한 성능 개선을 보이며, 높은 recall과 강한 relevance라는 두 이점을 함께 갖는다. recall을 높이면 무관한 문서가 더 많이 유입되어 relevance가 낮아지고, relevance를 높이면 관련 결과를 놓쳐 recall이 낮아지기 때문에 두 지표를 동시에 개선하기는 어렵다. LinearRAG는 네 태스크 전반의 recall에서 가장 좋은 성능을 달성하면서 대부분의 경우 relevance 지표에서도 RAG보다 좋은 결과를 낸다. 우리는 그 이유가 중복 연결이 최소화된 고품질 graph를 구축하여 무관한 문서가 검색되지 않도록 보장한 데 있다고 추론한다. 구체적으로 complex reasoning 태스크에서 LinearRAG는 87.03%의 recall과 81.58%의 relevance를 달성하여, recall은 85.03%이지만 relevance는 33.06%에 불과한 GFM-RAG를 유의하게 능가하며, 포괄적인 정보 커버리지를 유지하면서도 높은 precision을 지킬 수 있는 LinearRAG의 능력을 입증한다.

E.2 Hyper-parameter Sensitivity (Q5)

• LinearRAG의 핵심 hyperparameter 영향을 조사하기 위한 ablation study를 수행하며, 모든 실험은 2WikiMultiHopQA에서 GPT-Acc.와 Contain-Acc.의 평균 점수로 평가한다.
• Obs. 10. 임계값 δ의 영향. δ는 dynamic pruning 동안 entity의 점수를 유지할지, 그리고 확장을 계속할지를 결정한다. δ가 너무 작으면 과도한 노이즈가 유입되고 retrieval 단계의 효율이 떨어진다. δ가 너무 크면 더 많은 관련 entity의 편입을 막아 포괄적인 맥락 정보를 포착하는 능력을 제한한다. 실험 설정에 기반해 δ = 4로 설정한다.
• Obs. 11. trade-off coefficient λ의 영향. λ는 passage 초기 점수 계산에서 DPR 기반 passage 유사도와 entity 수준 정보 사이의 균형을 제어한다.
• λ가 상대적으로 작은 값(예: 0.05)일 때 최적 성능이 달성되며, 이는 entity 정보가 주된 구성 요소이고 DPR 유사도 점수는 보조적 강화 역할을 함을 나타낸다.

Figure 5: Parameter analysis of LinearRAG performance in the 2WikiMultiHopQA dataset. (a) shows the dependency of LinearRAG performance on threshold δ in dynamic pruning. (b) examines the effect of trade-off coefficient λ.

 

 

[Translated by Claude]

 

우리는 LinearRAG의 핵심 hyperparameter가 미치는 영향을 조사하기 위해 ablation study를 수행한다. 모든 실험은 2WikiMultiHopQA에서 GPT-Acc.와 Contain-Acc.의 평균 점수를 사용해 평가된다.

Obs. 10. 임계값 δ의 영향. 임계값 δ는 dynamic pruning 동안 entity의 점수를 유지할지 여부와 확장을 계속할지 여부를 결정한다. Figure 5a에서 보듯 δ가 너무 작으면 과도한 노이즈를 유입시키고 retrieval 단계의 효율을 떨어뜨린다. 그러나 δ가 너무 크면 더 많은 관련 entity의 편입을 막아 포괄적인 맥락 정보를 포착하는 모델의 능력을 제한한다. 따라서 δ에 적절한 값을 선택하는 일이 retrieval 품질과 계산 효율의 균형에 결정적으로 중요하다. 그리고 우리는 실험 설정에 기반하여 δ = 4로 설정한다.

Obs. 11. trade-off coefficient λ의 영향. 파라미터 λ는 passage 초기 점수 계산 동안 DPR 기반 passage 유사도와 entity 수준 정보 사이의 균형을 제어한다. Figure 5b에서 관찰되듯 λ가 상대적으로 작은 값(예: 0.05)을 취할 때 최적 성능이 달성되며, 이는 entity 정보가 주된 구성 요소로 작용하고 DPR 유사도 점수는 보조적인 강화 역할을 함을 나타낸다.

E.3 Effectiveness of Different Sentence Embeddings (Q6)

• LinearRAG에서 서로 다른 sentence embedding의 효과성을 연구하며, all-mpnet-base-v2(Song et al., 2020), bge-large-en(Xiao et al., 2023), all-MiniLM-L6-v2(Wang et al., 2020), e5-large-v2(Wang et al., 2022)를 비교한다. 공식 사전학습 모델은 Huggingface에서 내려받았다.
• Obs. 12. 서로 다른 sentence embedding model 사이의 성능 변동은 상대적으로 크지 않으며, all-mpnet-base-v2가 대부분의 데이터셋에서 우수한 결과를 보인다.
• 이는 LinearRAG가 sentence embedding model 선택에 대해 robustness를 보인다는 것을 시사한다.
• 따라서 계산 효율성을 고려해 모든 실험에서 all-mpnet-v2를 기본 embedding model로 채택한다.

Table 5: Comparison of different sentence embedding models used in LinearRAG. The best results are highlighted in bold.

 

 

[Translated by Claude]

 

이 절에서 우리는 LinearRAG에서 서로 다른 sentence embedding의 효과성을 연구한다. 우리는 all-mpnet-base-v2(Song et al., 2020), bge-large-en(Xiao et al., 2023), all-MiniLM-L6-v2(Wang et al., 2020), e5-large-v2(Wang et al., 2022)를 비교한다. 공식 사전학습 모델은 Huggingface에서 내려받았다.

Obs. 12. Table 5에 제시된 결과에 기반하여, 우리는 서로 다른 sentence embedding model 사이의 성능 변동이 상대적으로 크지 않으며 all-mpnet-base-v2가 대부분의 데이터셋에서 우수한 결과를 보인다는 것을 관찰한다. 이는 LinearRAG가 sentence embedding model의 선택에 대해 robustness를 보인다는 것을 시사한다. 결과적으로 우리는 계산 효율성 때문에 모든 실험에서 all-mpnet-v2를 기본 embedding model로 채택한다.

E.4 Large-Scale Efficiency Analysis (Q7)

• 대규모 코퍼스에서 LinearRAG의 확장성과 효과성을 평가하기 위해 ATLAS-Wiki 데이터셋(Bai et al., 2025)을 사용해 포괄적인 효율성 분석을 수행한다.
• indexing 단계 평가를 위해 각각 5M과 10M token을 담은 두 개의 부분집합을 만든다.
• Obs. 13. LinearRAG는 전형적인 GraphRAG 방법 대비 유의한 효율성 이점을 달성한다. token 소비를 완전히 제거하면서(prompt와 completion 모두 0 token) 5M과 10M 데이터셋에서 RAPTOR 대비 각각 12.8배, 15.1배의 속도 향상을 달성한다.
• 이 무비용 indexing 접근은 API 의존 없이 대규모 엔터프라이즈 배포에 특히 적합하게 만든다.

Table 6: Indexing efficiency comparison of GraphRAG methods on large-scale ATLAS-Wiki corpus. Results are evaluated on ATLAS-Wiki subsets of 5M and 10M tokens. Notaly, prompt tokens represent input to LLM, and completion tokens represent LLM output.

 

 

[Translated by Claude]

 

대규모 코퍼스에서 LinearRAG의 확장성과 효과성을 평가하기 위해, 우리는 ATLAS-Wiki 데이터셋(Bai et al., 2025)을 사용해 포괄적인 효율성 분석을 수행한다. Table 6에서 보듯 indexing 단계 평가를 위해 각각 5M과 10M token을 담은 두 개의 부분집합을 만든다.

Obs. 13. 결과는 LinearRAG가 전형적인 GraphRAG 방법들에 비해 유의한 효율성 이점을 달성함을 보여준다. 구체적으로 LinearRAG는 token 소비를 완전히 제거하면서(prompt와 completion 모두 0 token) 5M과 10M 데이터셋에서 RAPTOR 대비 각각 12.8배와 15.1배의 속도 향상을 달성한다. 이 무비용 indexing 접근은 LinearRAG를 API 의존 없이 대규모 엔터프라이즈 배포에 특히 적합하게 만든다.

E.5 Case Study (Q8)

• 전형적인 GraphRAG baseline과 LinearRAG 프레임워크를 명확히 대비하기 위해 Table 7에 상세한 사례 분석을 포함하며, 2WikiMultihopQA 데이터셋의 multi-hop 질문에 대해 강력한 baseline인 HippoRAG2와 우리 모델의 결과를 비교한다.
• 질문은 "What nationality is Beatrice I, Countess Of Burgundy's husband?"이며 정답은 Germany다.
• Obs. 14. 이 사례는 HippoRAG2가 이 맥락에는 존재하지 않는, 명시적으로 사전 추출된 relation(예: husband)에 의존하기 때문에 관련 근거를 검색하는 데 실패함을 보여준다.
• 이에 비해 LinearRAG는 사전 추출된 relational tuple에 의존하지 않고 entity activation과 contextual chaining을 통해 암묵적 관계를 효과적으로 포착한다.

Table 7: Case study of LinearRAG. LinearRAG successfully captures implicit relationships without requiring explicit relation extraction, enabling correct multi-hop reasoning.

 

 

[Translated by Claude]

 

전형적인 GraphRAG baseline과 우리의 LinearRAG 프레임워크를 명확하게 대비하기 위해, 우리는 Table 7에 상세한 사례 분석을 포함하며 2WikiMultihopQA 데이터셋의 multi-hop 질문에 대해 강력한 baseline인 HippoRAG2와 우리 모델의 결과를 비교한다.

Obs. 14. 이 사례는 HippoRAG2가 이 맥락에서는 빠져 있는, 명시적으로 사전 추출된 relation(예: husband)에 의존하기 때문에 관련 근거를 검색하는 데 실패함을 보여준다. 이에 비해 우리의 LinearRAG 방법은 사전 추출된 relational tuple에 의존하지 않고 entity activation과 contextual chaining을 통해 암묵적 관계를 효과적으로 포착한다.

F Related Work

• large language model은 hallucination에 취약한 반면 RAG는 knowledge base의 맥락적 근거 위에 추론 과정을 접지시키는 유망한 해법이다. 그러나 실세계 지식은 여러 문서에 분산되어 있어, 복잡한 질문에 답하기 위해 이를 효과적으로 조직하는 일이 RAG의 도전적이면서 유망한 연구 주제였다.
• ❶ Clustering-based hierarchy construction: Louvain이나 Leiden 같은 알고리즘을 적용해 초기 graph 안의 조밀하게 연결된 entity cluster를 찾는 bottom-up 방식의 community detection을 사용한다. 다만 비지도 기법이라 error propagation에 취약하고, 대규모 graph에서는 확장성 문제가 크다.
• ❷ Relation-extraction-based knowledge graph construction: 각 텍스트 chunk에서 triple을 추출해 entity alignment로 연결하여 통합 knowledge graph를 만든다. context window 제한 때문에 각 passage의 OpenIE가 독립적으로 처리되어 생성된 triple이 비일관적일 수 있고, 전역 schema 기반의 top-down 구축은 전문가의 수작업 주석에 의존한다.
• ❸ Reasoning-enhanced RAG: 코퍼스를 명시적으로 구조화하는 대신 LLM 고유의 추론 능력을 활용해 복잡한 query를 dense retrieval로 다룰 수 있는 더 단순한 subquestion으로 분해한다. LogicRAG, LAG, Chain-of-Note(CoN), SelfRAG 등이 여기에 속한다.

 

[Translated by Claude]

 

large language model은 hallucination에 취약한 반면(Fang et al., 2024; Jiang et al., 2025; Fang et al., 2025; Zheng et al., 2025; Hong et al., 2024; Yuan et al., 2025; Zhong et al., 2024), RAG는 knowledge base로부터 얻은 맥락적 근거 위에 추론 과정을 접지시킴으로써 유망한 해법이 된다(Zhang et al., 2025a; Zhou et al., 2025b; Xiao et al., 2025a; Zhang et al., 2025b; Xiang et al., 2025). 그러나 실세계의 지식은 흔히 여러 문서에 걸쳐 분산되어 있어, 복잡한 질문에 답하기 위해 이를 효과적으로 조직하는 일은 늘 RAG에서 도전적이면서도 유망한 연구 주제였다. 아래에서 우리는 우리 연구와 밀접하게 관련된, 외부 지식 원천을 조직하기 위해 명시적 graph를 구축하는 graphRAG 연구의 두 주요 갈래(❶, ❷)를 논의한다. 그런 다음 코퍼스를 명시적으로 구조화하지 않고 복잡한 질문에 답하기 위해 LLM 고유의 추론 능력을 활용하는 reasoning-enhanced RAG(❸)를 논의한다.

❶ Clustering-based hierarchy construction. 한 갈래의 연구는 clustering 기반 community detection을 채택하는데, 이는 Louvain이나 Leiden 같은 알고리즘을 적용해 초기 graph 안에서 조밀하게 연결된 entity cluster를 식별하는 bottom-up 방법이다(Edge et al., 2024; Sarthi et al., 2024; Gutiérrez et al., 2024). 관련 entity를 묶음으로써 passage를 주제 기반 community로 추상화하는 계층 구조를 만들어 중복을 줄이고 데이터에 대한 더 넓은 거시적 관점을 제공한다. 그러나 비지도 기법이므로 error propagation에 취약하여 entity 관계의 부정확성이 더 높은 추상 수준에서 증폭된다. 나아가 이런 clustering 알고리즘을 대규모 graph에 적용하는 것은 유의한 확장성 문제를 낳아, 실무에서 실시간 응용을 불가능하게 만든다.

❷ Relation-extraction-based knowledge graph construction. 이 갈래의 연구(Gutiérrez et al., 2024; Guo et al., 2024; Xiao et al., 2025c)는 서로 다른 passage에 걸쳐 지식을 조직하기 위해 knowledge graph의 아이디어를 채택한다. 기본 발상은 각 텍스트 chunk(passage)에서 그 안의 지식에 대한 atomic 요약으로서 triple을 추출하는 것이다. 이 triple들은 entity alignment(Chen et al., 2025a; 2024)를 통해 연결되어 궁극적으로 통합된 knowledge graph를 형성하며, 이는 구조화된 지식을 직접 운반하고 passage의 index 역할을 하여 기성 graph 추론 알고리즘(Shengyuan et al., 2024; Qu & Tang, 2019; Liu et al., 2023)을 적용해 추론을 수행할 수 있게 한다(Sun et al., 2024; LUO et al., 2024). 그러나 context window 제한 때문에 각 passage에 대한 OpenIE가 독립적으로 처리되므로 생성된 triple이 비일관적일 수 있다. 최근 연구(Liang et al., 2024; Sharma et al., 2024)는 전역적으로 정의된 schema가 안내하는 top-down graph 구축을 통해 이를 완화하지만, 도메인별 schema를 만들고 유지하기 위해 전문가의 수작업 주석에 의존하므로 비용이 크고 시간이 많이 들며 도메인 전반에 잘 일반화되지 않는다.

❸ Reasoning-enhanced RAG. RAG에서 복잡한 질문에 답하는 핵심은 multihop 논리적 의존성을 뒷받침하는 여러 분산 문서를 효과적으로 식별하는 것이다. GraphRAG 방법이 효율적인 구조화 retrieval을 위해 인간의 사전 지식으로 코퍼스를 조직하는 graph를 명시적으로 구축하는 반면, reasoning-enhanced RAG는 LLM 고유의 추론 능력을 직접 활용하여 복잡한 query를 dense retrieval로 다룰 수 있는 더 단순한 subquestion으로 분해한다. LogicRAG(Chen et al., 2025b)와 LAG(Xiao et al., 2025b)는 이 아이디어를 정식화하여, 먼저 query를 subquery 집합으로 분해한 뒤 그들 사이의 논리적 의존성에 기반해 방향성 비순환 graph를 구성하고, 위상 순서를 따라 하위 문제를 하나씩 푼다. 유사하게 Chain-of-Note(CoN)(Yu et al., 2024)는 복잡한 query를 중간 추론 단계로 쪼개는 순차적 노트를 생성하고 각 단계마다 관련 문서를 검색해 일관된 답을 구성함으로써 RAG를 강화한다. 또 다른 접근인 SelfRAG(Asai et al., 2024)는 RAG 과정에 self-reflection을 통합하여, LLM이 subquery를 반복적으로 평가하고 정제하여 검색된 문서가 추론 과정의 논리 흐름과 정합하도록 보장한다. 이 방법들은 복잡한 multihop query에 대해 retrieval 효율성과 답변 품질을 개선하는 LLM 주도 추론의 잠재력을 종합적으로 부각한다.

G The Use of Large Language Models

• LLM은 주로 글다듬기 용도로 사용되었으며, 여기에는 철자 오류 교정, 문법 문제 수정, 비원어민적 표현의 재작성이 포함된다.
• LLM은 원고와 부록의 글다듬기에만 사용되었다.
• LLM은 연구 아이디어, 결과, 주장을 생성하지 않았다.
• 모든 과학적 기여와 구현이 독창적임을 보증한다.

 

[Translated by Claude]

 

우리는 LLM을 주로 글다듬기에 사용했으며, 여기에는 철자 오류 교정, 문법 문제 수정, 그리고 명료성과 유창성을 높이기 위한 비원어민적 표현의 재작성이 포함된다. 그리고 LLM은 우리 원고와 부록의 글다듬기에만 사용되었다. LLM은 연구 아이디어, 결과, 주장을 생성하지 않는다. 우리는 모든 과학적 기여와 구현이 독창적임을 보증한다.