LinearRAG: Linear Graph Retrieval Augmented Generation on Large-scale Corpora

Paper: Luyao Zhuang; Shengyuan Chen; Yilin Xiao; Huachi Zhou; Yujing Zhang; Hao Chen; Qinggang Zhang; Xiao Huang (2025). "LinearRAG: Linear Graph Retrieval Augmented Generation on Large-scale Corpora." arXiv:2510.10114v4. PDF

1. 문제: 그래프가 원문보다 먼저 틀릴 수 있다

GraphRAG는 문서에서 (주체, 관계, 객체) 삼중항을 뽑고 그래프로 연결해 다중 홉 검색을 돕는다. LinearRAG의 출발점은 이 관계 추출이 국소적으로 틀리거나 여러 문단에서 모순되는 관계를 만들면 검색이 흔들린다는 진단이다(§2.2). 예컨대 부정문 속 관계를 양의 사실로 바꾸면, 이후 그래프 탐색은 그 잘못된 연결을 더 자신 있게 따른다.

저자들은 관계를 추출하지 않는다. Tri-Graph는 엔티티·문장·문단 세 종류의 node와 엔티티–문장, 엔티티–문단 연결만 둔다. 엔티티는 멀리 떨어진 문단을 잇는 닻이고, 구체적 관계와 문맥은 원문 문단 안에 남긴다. 관계를 생략해도 의미까지 버리지는 않는다. 의미 판단은 질의 시 문장 임베딩과 원문 문단이 맡는다. graph edge에 문장형 라벨을 붙이지 않는 선택이다.

그림 1. Zhuang et al., Figure 1, arXiv:2510.10114v4 PDF p. 2의 원도판이다. vanilla RAG, 관계 추출 GraphRAG, 관계 없는 Tri-Graph의 차이를 비교한다. 이 진단 그림은 특정 corpus에서 모든 관계 추출이 해롭다는 정량적 증명은 아니다.

2. 검색: 가까운 엔티티를 찾고, 문단 중요도를 전역으로 모은다

온라인 검색은 두 단계다(Fig. 3). 첫째 semantic bridging은 질문과 문장의 유사도를 이용해 질문에 직접 나오지 않은 관련 엔티티까지 활성화한다. 둘째는 활성화된 엔티티를 시작점으로 엔티티–문단 graph에서 personalized PageRank를 실행해 여러 활성 엔티티와 연결된 문단의 전역 중요도를 모은다.

“linear”는 추론 단계가 한 홉이라는 뜻이 아니라, 논문이 주장하는 색인 규모의 성질이다. spaCy NER와 임베딩으로 문단을 처리하고 두 인접 구조를 만들기 때문에 corpus 크기에 따라 선형으로 구축되며, 색인 중 LLM 호출 토큰은 0이라고 보고한다(§3, §4.3). 토큰 0은 downstream answer generator까지 포함한 전체 운영비 0이라는 뜻은 아니다.

그림 2. Zhuang et al., Figure 3, arXiv:2510.10114v4 PDF p. 4의 원도판이다. 오프라인에 entity–sentence·entity–passage 연결을 만들고, 질의 시 activation 뒤 global importance aggregation을 수행하는 경로를 보라. 인접성만으로 논리 관계를 보장하지 않는다는 한계는 그림에 해결돼 있지 않다.

3. 공정한 비교의 단위: 세 다중홉 벤치마크와 별도 Medical 열

주 실험은 HotpotQA, 2WikiMultiHopQA, MuSiQue에서 HippoRAG와 같은 retrieval corpus 및 각각 1,000개 validation question을 사용한다(§4.1). Medical은 GraphRAG-Bench의 별도 domain-specific dataset으로 도입되며, 확인한 본문에는 그 질문 수가 명시돼 있지 않다. 정확도는 답에 gold answer가 포함됐는지 보는 Contain-Acc.와 GPT가 정답 일치를 판정하는 GPT-Acc.를 함께 쓴다. 단 Medical 열은 서술형 gold answer 때문에 GPT-Acc.만 쓴다.

Table 1에서 LinearRAG의 GPT-Acc.는 HotpotQA 66.50, 2Wiki 63.70, MuSiQue 37.00, Medical 63.72다. 2Wiki의 63.70은 표의 다음 값 HippoRAG 59.90보다 3.80 percentage points 높고, HotpotQA는 GFM-RAG 65.60보다 0.90 points 높다. 이는 저자 설정의 end-to-end answer 지표이며, 사람 평가나 새 corpus에 같은 개선이 난다는 보장은 아니다.

4. 비용 결과: 정확도와 별개의 유용성

2Wiki 색인 비교(Table 2)에서 LinearRAG는 249.78초, LLM prompt/completion token 0을 보고했다. 표의 66.95 accuracy는 네 데이터셋 평균이 아니라 2Wiki Contain-Acc. 70.20과 GPT-Acc. 63.70의 평균이다. 같은 표의 HippoRAG는 936.00초, GFM-RAG는 1,202.77초다. 이 수치는 이 구현·하드웨어·2Wiki corpus에서 색인 시간을 줄였다는 근거다.

그림 3. Zhuang et al., Figure 4, arXiv:2510.10114v4 PDF p. 9의 원도판이다. entity activation과 global importance aggregation을 각각 뺀 네 데이터셋의 비교다. Fig. 4의 일반 설명은 Contain-Acc.와 GPT-Acc. 평균을 말하지만, Medical의 full-method 63.72는 Table 1과 같이 GPT-Acc.만의 값이다.

Appendix Table 6의 ATLAS-Wiki 10M은 1천만 tokens 규모 색인 실험이며, RAPTOR 대비 15.1배는 색인 속도 결과다. 추가 QA 성능 근거나 answer-generation 비용 결과로 읽어서는 안 된다. 두 모듈 절제는 semantic bridging과 PageRank를 모두 유지할 때 가장 좋다는 저자 주장에 근거를 보탠다(§4.4). 다만 관련 엔티티 인식과 embedding 품질이 함께 바뀌면 모듈별 기여를 완전히 분리하기 어렵다.

5. 어디에 맞는가

관계 추출 LLM의 비용과 오류가 부담스럽고, 동일 엔티티가 여러 문단을 연결하는 긴 지식 corpus라면 LinearRAG는 실용적 후보가 된다. 적용 전에는 NER이 도메인 용어를 얼마나 놓치는지, 문단 분할이 의미를 얼마나 보존하는지, top-k 문단과 PageRank iteration이 지연 예산 안에 드는지를 측정해야 한다. 질문이 엔티티를 거의 공유하지 않는 추상 추론이거나 관계의 방향·부정·시간성이 답의 핵심이면 원문 안에 관계를 남긴다는 선택만으로 충분하지 않을 수 있다.

6. 정리

LinearRAG는 “더 정교한 관계 graph” 대신 “덜 주장하는 graph”로 검색 후보를 조직하자고 제안한다. Tri-Graph는 엔티티와 원문 문단의 연결을 보존하고 질의 시 의미 브리징과 전역 집계로 다중 홉 후보를 만든다. 저자 보고 성능과 2Wiki 색인 효율은 유망한 근거다. 그러나 이는 정해진 세 다중홉 QA 표본과 별도 Medical 열, 특정 NER·임베딩·LLM 평가 설정의 결과이므로, 도입 판단은 자신의 corpus에서 relation extraction 오류율과 entity coverage를 먼저 비교하는 데서 시작해야 한다.

상세 읽기

References

Zhuang, L., Chen, S., Xiao, Y., Zhou, H., Zhang, Y., Chen, H., Zhang, Q., & Huang, X. (2025). LinearRAG: Linear graph retrieval augmented generation on large-scale corpora (arXiv:2510.10114v4). https://arxiv.org/abs/2510.10114