Background
소속: Microsoft Research
게재:
Abstract & 1 Introduction
기존의 연관 문서를 검색하고 쿼리와 함께 입력해서 질문에 대한 답변을 생성하는 vector RAG 방식은 query-focused summarization(QFS)이기 때문에, “지난 10년간 과학적 발견이 학제 간 연구의 영향을 받은 주요 트렌드는 무엇인가?”와 같이 전체 데이터 세트에 대한 전반적인 이해가 필요한 sensemaking query들을 지원하지 못한다.
본 논문에서는 large text corpus에 대한 sensemaking을 가능하게 하는 graph-based RAG 접근 방식 GraphRAG를 제안한다.
- LLM을 사용하여 knowledge graph를 구성하는데, 노드는 corpus에서 주요 entities에 해당하고 엣지는 이 entities의 관계를 표현한다.
- graph를 밀접하게 관련된 entities의 community 계층 구조로 분할한 후 LLM을 사용해 community 수준의 요약을 생성한다. 요약은 계층 구조에 따라 상향식 방식으로 생성되며, 상위 수준 요약은 하위 수준 요약을 재귀적으로 통합한다.
- 마지막으로 GraphRAG는 community 요약의 map-reduce 처리를 통해 쿼리에 대한 답변을 생성한다. 즉, 질문이 주어지면 각 community summarization은 부분 응답을 생성하는데 사용되며, 모든 부분 응답은 다시 사용자에게 최종 응답으로 요약된다.
GraphRAG는 private text corpora 대상으로하는 다양한 질문을 소화하면서도, 수많은 문서를 효율적으로 다룰 수 있는 그래프 기반의 QA 방법이다.
3 Methods
3.1 GraphRAG Workflow
Figure 1 illustrates the high-level data flow of the GraphRAG approach and pipeline. In this section, we describe the key design parameters, techniques, and implementation details for each step.
3.1.1 Source Documents → Text Chunks
To start, the documents in the corpus are split into text chunks. The LLM extracts information from each chunk for downstream processing.
3.1.2 Text Chunks → Entities & Relationships
In this step, the LLM is prompted to extract instances of important entities and the relationships between the entities from a given chunk. LLM은 entities와 relationships를 위한 짧은 설명을 생성한다.
| a chunk contained the following text: NeoChip’s (NC) shares surged in their first week of trading on the NewTech Exchange. However, market analysts caution that the chipmaker’s public debut may not reflect trends for other technology IPOs. NeoChip, previously a private entity, was acquired by Quantum Systems in 2016. The innovative semiconductor firm specializes in low-power processors for wearables and IoT devices. The LLM is prompted such that it extracts the following: - The entity NeoChip, with description “NeoChip is a publicly traded company specializing in low-power processors for wearables and IoT devices.” => node - The entity Quantum Systems, with description “Quantum Systems is a firm that previously owned NeoChip.” => node - A relationship between NeoChip and Quantum Systems, with description “Quantum Systems owned NeoChip from 2016 until NeoChip became publicly traded.” => edge |
3.1.3 Entities & Relationships → Knowledge Graph
앞서 추출된 entity들과 relationship은 그래프의 노드와 엣지로 변환된다. 그리고 노드와 엣지에 대한 entity 설명이 수집되고 요약된다. relationship들은 엣지로 통합되며, 동일한 관계가 여러 번 등장할 경우 그 수가 엣지 가중치가 된다.
3.1.4 Knowledge Graph → Graph Communities
이전 단계에서 생된 그래프 인덱스가 주어지면, Leiden 알고리즘을 사용해서 그래프를 더 이상 쪼갤 수 없는 최종 community에 도달할 때까지 반복 수행하여 community를 분할
3.1.5 Graph Communities → Community Summaries
각 커뮤니티에 대한 요약을 생성한다. GraphRAG에서는 대규모 그래프 데이터를 LLM에 효과적으로 넣기 위해, 커뮤니티(노드 집합)를 요약하고 우선순위에 따라 선택합니다. 이 과정은 커뮤니티의 계층 수준(leaf-level / higher-level)에 따라 달라집니다.
* Leaf-level 커뮤니티 (더 이상 쪼갤 수 없는 최종 커뮤니티)
- 노드 연결 정도가 높은 엣지부터 순서대로 요약 추가
- 각 엣지에 대해 노드들의 설명, 엣지 설명, 관련 주장을 차례로 LLM에 입력
- 토큰 한도에 도달할 때까지 반복 추가
* Higher-level 커뮤니티
- 만약 요약 전체가 토큰 한도 안에 들어간다면, 그냥 전부 넣음
- 초과될 경우 하위 커뮤니티들을 토큰 양 기준으로 정렬하고 토큰이 많은 요약 순으로 더 짧은 하위 커뮤니티 요약을 생성하고 대체해서 전체 입력이 토큰 한도 내로 들어가도록 조정
3.1.6 Community Summaries → Community Answers → Global Answer
사용자 쿼리가 주어지면 이전 단계에서 생성된 커뮤니티 요약을 사용하여 다단계 프로세스를 통해 최종 답변을 생성할 수 있습니다. 주어진 커뮤니티 수준에 대해 모든 사용자 쿼리에 대한 글로벌 답변은 다음과 같이 생성됩니다:
- 모든 커뮤니티 요약을 랜덤하게 섞은 뒤 일정한 토큰 크기의 청크로 나눈다. 특정 커뮤니티의 정보가 한 덩어리에만 몰리지 않고, 그 정보가 여러 청크에 분산될 수 있도록 한다.
- 각 청크에 대한 LLM의 중간 답변을 만들고, LLM은 생성된 답변이 목표 질문에 대한 답변에 얼마나 도움이 되는지를 나타내는 0~100점 사이의 점수를 생성하도록 요청받습니다. 점수가 0점인 답변은 필터링됩니다.
- 전체 답변으로 축소합니다. 중간 커뮤니티 답변은 도움 점수 내림차순으로 정렬되고 토큰 한도에 도달할 때까지 반복적으로 새 컨텍스트 창에 추가됩니다. 이 최종 컨텍스트는 사용자에게 반환되는 글로벌 답변을 생성하는 데 사용됩니다.
4 Analysis
4.1 Experiment 1
아래 6가지 방식을 비교함
- CO. Uses root-level community summaries (fewest in number) to answer user queries.
- C1. Uses high-level community summaries to answer queries. These are sub-communities of C0, if present, otherwise C0 communities projected downwards.
- C2. Uses intermediate-level community summaries to answer queries. These are subcommunities of C1, if present, otherwise C1 communities projected downwards.
- C3. Uses low-level community summaries (greatest in number) to answer queries. These are sub-communities of C2, if present, otherwise C2 communities projected downwards.
- TS. The same method as in Section 3.1.6, except source texts (rather than community summaries) are shuffled and chunked for the map-reduce summarization stages.
- SS. An implementation of vector RAG in which text chunks are retrieved and added to the available context window until the specified token limit is reached.
4.2 Experiment 2
factual claims을 추출하기 위해 답변에서 적어도 하나의 사실적 주장을 포함하는 문장을 식별한 다음 이러한 문장을 단순하고 독립적인 사실적 주장으로 분해하는 LLM 기반 방법인 Claimify를 사용.
두 가지 지표를 정의했으며, 값이 높을수록 더 나은 성능을 나타남:
- Comprehensiveness: 각 조건에서 생성된 답변에서 추출된 claims 의 평균 수로 측정
- Diversity: 각 답변의 claims을 클러스터링하고 평균 클러스터 수를 계산하여 측정
5 Results
5.1 Experiment 1
Global approaches vs. vector RAG
- Global approaches이 데이터 세트 전반에서 Comprehensiveness 및 Diversity 기준 모두에서 기존의 vector RAG(SS)를 크게 앞질렀다.
- 각 조건 쌍에 대해 질문 125개로 비교하고, 이를 5번 반복해서 결과를 평균 낸 뒤, 어떤 조건이 다른 조건보다 더 잘 작동했는지를 "승률(%)"로 나타냈을 때, TS 83%, C0 72% ... 로 우수함
Empowerment
- How well does the answer help the reader understand and make informed judgments about the topic?
- Global approaches과 vectorRAG(SS) 접근 방식, Global approaches과 소스 텍스트 요약(TS) 접근 방식 모두에서 혼합된 결과가 나타났다.
- 사용자들이 이해도 높은 답변을 얻기 위해 중요한 요소로 구체적인 예시, 직접적인 인용, 출처의 명시가 꼽혔다. 이런 정보를 더 잘 보존해 답변을 생성하면 답변의 품질을 높이는데 도움이 될 수 있다.
Community summaries vs. source texts
- GraphRAG를 사용하여 커뮤니티 요약과 소스 텍스트(TS)를 비교했을 때, 커뮤니티 요약은 일반적으로 루트 수준의 요약을 제외하고는 답의 Comprehensiveness과 Diversity에서 작지만 일관되게 개선된 결과를 제공
- 표 2는 소스 텍스트 요약에 비해 GraphRAG의 확장성 이점을 보여줍니다. 낮은 수준의 커뮤니티 요약(C3)의 경우 GraphRAG는 26~33% 더 적은 컨텍스트 토큰이 필요했고, 루트 수준의 커뮤니티 요약(C0)의 경우 97% 이상 더 적은 토큰이 필요(TS는 source text에서 청크를 그대로 나누니깐 더 많은 토큰으로 나뉘고, graphRAG는 요약을 청크로 나누니깐 상대적으로 적은 토큰이 필요함)
5.2 Experiment 2
- 표 3은 조건별 추출된 평균 claims 수(즉, claim-based measure of comprehensiveness)에 대한 결과를 보여줍니다. 뉴스와 팟캐스트 데이터 세트 모두에서, 모든 글로벌 검색 조건(C0-C3)과 소스 텍스트 요약(TS)이 벡터 RAG(SS)보다 comprehensiveness이 더 높았습니다.
- for the podcast dataset, 모든 global approches가 SS보다 더 큰 diversity를 달성했다. C0가 가장 우수하고 통계적으로 유의미한 결과다.
- for the news dataset, global approches가 우수하기는 한데, 통계적으로 유의미하지는 않음.. C1과 C2 보다 C3가 더 다양함.
- 포괄성과 다양성 모두에서 두 데이터 세트 모두에서 글로벌 검색 조건 간 또는 글로벌 검색과 TS 간에는 통계적으로 유의미한 차이가 관찰되지 않았습니다.
7 Conclusion
We have presented GraphRAG, a RAG approach that combines knowledge graph generation and query-focused summarization (QFS) to support human sensemaking over entire text corpora.
QFS에서 sensemaking을 지원하기 위해 GraphRAG를 제안함
Initial evaluations show substantial improvements over a vector RAG baseline for both the comprehensiveness and diversity of answers, as well as favorable comparisons to a global but graph-free approach using map-reduce source text summarization.
comprehensiveness와 diversity 평가에서 Graph RAG가 vector RAG 보다 성능이 향상된 것을 파악함. TS와 비교했을 때도 유리한 결과를 보임
For situations requiring many global queries over the same dataset, summaries of root-level communities in the entity-based graph index provide a data index that is both superior to vector RAG and achieves competitive performance to other global methods at a fraction of the token cost.
동일한 데이터 세트에 대해 많은 글로벌 쿼리가 필요한 상황의 경우, summaries of root-level communities이 vectorRAG보다 우수하고 토큰 비용의 일부로 다른 global approches보다 경쟁력 있는 성능을 달성할 수 있는 데이터 인덱스를 제공합니다.