💬 NLP

Efficient Retrieval-Augmented Generation via Token Co-occurrence Graphs

본 논문은 토큰 공생 그래프와 반복적인 엔티티 기반 검색 전략을 활용하여 표준 RAG 시스템의 멀티홉 추론 한계를 극복하는 동시에 계산 비용을 크게 절감하고 QA 벤치마크 성능을 향상시키는 효율적인 검색 증강 생성 프레임워크인 TIGRAG를 제안한다.

원저자: Gianluca Bonifazi, Christopher Buratti, Michele Marchetti, Federica Parlapiano, Giulia Quaglieri, Davide Traini, Domenico Ursino, Luca Virgili

게시일 2026-06-30

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Gianluca Bonifazi, Christopher Buratti, Michele Marchetti, Federica Parlapiano, Giulia Quaglieri, Davide Traini, Domenico Ursino, Luca Virgili

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신에게 아주 똑똑한 비서(거대 언어 모델)가 있다고 상상해 보세요. 이 비서는 아는 것이 매우 많지만, 모든 사실을 직접 눈앞에서 확인하지 못하기 때문에 가끔 사실이 아닌 것을 지어내기도 합니다. 이를 해결하기 위해, 우리는 질문에 답하기 전 확인해 볼 수 있는 거대한 책 도서관을 제공합니다. 이것을 RAG(검색 증강 생성)라고 부릅니다.

하지만 문제가 하나 있습니다. 만약 당신이 세 권의 서로 다른 책에 있는 점들을 연결해야 하는 까다로운 질문(예: "The Last Horse에 출연했던 배우가 출연한 영화를 감독한 사람은 누구인가?")을 던진다면, 비서의 일반적인 검색 방식은 실패하게 됩니다. 보통의 방식은 질문과 가장 비슷해 보이는 책 한 권만을 찾아내기 때문에, 퍼즐을 푸는 데 꼭 필요한 나머지 두 권의 책을 놓치게 됩니다.

최근의 해결책들은 모든 사실이 어떻게 연결되는지 보여주는 거대한 복잡한 지도(지식 그래프)를 구축하려고 시도했습니다. 하지만 이 지도를 만드는 것은 마치 도시의 모든 거리 하나하나를 손으로 그리기 위해 값비싼 건축가 팀을 고용하는 것과 같습니다. 시간이 너무 오래 걸리고 때로는 실수도 생기기 때문입니다.

TIGRAG의 등장.

이 논문의 저자들은 그 지도를 훨씬 더 빠르게 구축하고 정답을 찾아내는 새로운 방법을 제안합니다. 그 작동 원리를 쉬운 비유를 통해 설명하겠습니다.

1. "단어 이웃" 지도 (도시 계획 대신)

전통적인 방식은 문장의 의미를 이해하여 지도를 만들려고 합니다. 하지만 TIGRAG는 지름길을 택합니다. 바로 **단어 공기(co-occurrence)**를 관찰하는 것입니다.

사람들이 대화를 나누고 있는 거대한 파티를 상상해 보세요. TIGRAG는 모든 사람을 인터뷰하여 그들의 깊은 관계를 이해하려 하는 대신, 그저 누가 누구 옆에 서 있는지를 지켜봅니다. 만약 "사과"와 "파이"라는 단어가 같은 문단(파티의 같은 '방')에서 자주 발견된다면, TIGR식은 두 단어 사이에 선을 긋습니다. TIGRAG는 도서관의 모든 단어에 대해 이 작업을 수행합니다.

결과: 값비싼 인간 수준의 분석 없이도, 누가 누구와 어울리는지를 바탕으로 자동으로 만들어진 거대하고 가벼운 연결망이 탄생합니다.

2. "파동 효과" 검색

질문을 던지면, TIGRAG는 단순히 정확한 단어를 찾는 것에 그치지 않습니다. 연못에 돌을 던져(질문) 그 파동이 퍼져나가는 것을 지켜봅니다.

먼저 질문에 포함된 단어들로부터 시작합니다.
그 후 "단어 이웃" 지도의 선을 따라가며, 당신이 언급하지 않았더라도 질문과 밀접하게 관련된 단어들을 찾아냅니다.
예시: 만약 당신이 "The Last Horse"에 대해 묻는다면, 지도는 "Edger Neville"(감독)이나 "스페인 코미디"(장르)와 같은 단어로 파동을 넓혀갈 수 있습니다. 이는 당신이 그 단어들을 직접 입력하지 않았더라도, 다단계 퍼즐을 푸는 데 필요한 다른 책들을 찾도록 도와줍니다.

3. "스마트 필터" (입구의 보안 요원)

TIGRAG가 잠재적인 책의 장(텍스트 덩어리)들을 찾아냈다고 해서, 이를 비서 앞에 그대로 쏟아붓지는 않습니다. 그것은 마치 방 안에 도서관 전체를 통째로 던져 넣는 것과 같습니다.

1단계: T-G-R-A-G는 가장 관련성이 높은 장들만 남기기 위해 빠른 수학적 검사(명단을 확인하는 보안 요원처럼)를 수행합니다.
2단계: 그 후 "뉴럴 리랭커(neural reranker)"(매우 똑똑한 필터)를 사용하여, 이 장들이 단순히 관련 주제를 다루는 것이 아니라 실제로 특정 질문에 답을 하는지 다시 한번 확인합니다로.
결과: 비서는 더 많은 정보 없이, 딱 필요한 내용만을 담은 완벽하고 작은 페이지 뭉치를 전달받게 됩니다.

4. "탐정의 수첩" (다단계 추론)

정말 어려운 질문의 경우, TIGRAG는 단계별로 미스터리를 해결하는 탐정처럼 행동합니다.

첫 번째 단서: 첫 번째 관련 장을 찾습니다.
새로운 단서: 그 장을 읽고, 핵심적인 이름(사람이나 장소 등)을 찾아내어 검색어에 추가합니다.
두 번째 단서: 그 새로운 이름을 사용하여 다음 장을 찾기 위해 다시 검색합니다.
해결: 두 장에서 얻은 단서들을 결합하여 전체 질문에 대한 답을 냅니다.

왜 이것이 중요한가요?

이 논문은 TIGRAG가 다음 세 가지 이유로 게임 체인저라고 주장합니다.

속도: 지도를 만드는 데 값비싼 AI를 사용하여 선을 그릴 필요 없이, 단어가 얼마나 자주 함께 나타나는지만 세면 되기 때문에 구축 속도가 믿을 수 없을 정도로 빠릅니다. 이는 땅을 측량하는 대신 발자국 수를 세어 지도를 만드는 것과 같습니다.
정확도: 단순히 정확한 단어 일치를 찾는 대신 관련 단어의 "파동"을 따라가기 때문에, 복잡한 다단계 퍼즐을 기존 방식보다 더 잘 해결합니다.
효율성: 비서에게 훨씬 더 작고 깨끗한 정보만을 제공합니다. 이는 시간을 절약하고 계산 능력을 아껴주며, 비서가 너무 많은 텍스트 때문에 혼란에 빠지는 것을 방지합니다.

요약하자면, TIGRAG는 도서관의 모든 페이지를 먼저 다 읽지 않고도 서로 다른 책들 사이의 점들을 연결할 줄 아는 빠르고, 효율적이며, 똑똑한 사서입니다. 복잡한 질문에 대해 필요한 증거를 빠르고 정확하게 찾아냅니다.

기술 요약: TIGRAG (Token-Induced GraphRAG)

1. 문제 정의

검색 증강 생성(Retrieval-Augmented Generation, RAG)은 외부 지식에 기반하여 생성을 수행함으로써 대규모 언어 모델(LLM)의 환각 현상을 완화하는 표준적인 접근 방식이다. 그러나 일반적인 벡터 기반 RAG 시스템은 문서를 독립된 단위로 취급하기 때문에, 독립적인 텍스트 청크 전반에 흩어진 증거를 합성해야 하는 다중 홉 추론(multi-hop reasoning) 작업에는 효과적이지 못하다.

그래프 증강 RAG(Graph-augmented RAG, GraphRAG) 방식은 지식 그래프(Knowledge Graphs, KGs)를 통해 관계를 모델링함으로써 이 문제를 해결하려고 시도하지만, 두 가지 결정적인 도입 장벽에 직면해 있다:

계산 오버헤드: 오프라인 KG 구축은 종종 계산 비용이 많이 들고 지연 시간을 유발하는 LLM 기반 추출 파이프라인에 의존한다.
추출 취약성: LLM 기반의 엔티티 및 관계 추출은 환각, 노이즈, 누락된 연결에 취약하다. 이러한 오류는 검색 파이프라인을 통해 전파되어 다운스트림 추론 과정에서 연쇄적인 실패를 일으킨다.

2. 방법론: TIGRAG 아키텍처

저자들은 LLM 기반 추출 대신 토큰 공생(token co-occurrences)으로부터 직접 위상적 지식 그래프를 구축하는 프레임워크인 **TIGRAG (Token-Induced GraphRAG)**를 제안한다. 이 아키텍처는 오프라인 그래프 구축과 온라인 추론의 두 단계로 작동한다.

2.1. 오프라인 그래프 구축

TIGRAG는 엔티티와 관계를 추출하기 위해 LLM을 사용하는 대신 통계적 접근 방식을 사용한다:

전처리: 코퍼스를 문장 단위의 슬라이딩 윈도우 전략을 사용하여 중첩되는 텍스트 청크로 분할한다.
토큰화: 청크를 토큰화하고 불용어(stopwords)를 제거한다. 유효한 토큰은 길이 및 숫자 제약 조건을 기준으로 필터링된다.
그래프 구축: 다음과 같은 속성을 가진 가중치 부여된 무방향 KG를 구축한다:
- 노드는 유효한 토큰을 나타낸다.
- 엣지는 크기 $w$ 인 슬라이딩 윈도우 내에서의 토큰 간 공생을 나타낸다.
- 가중치는 코퍼스 전반에 걸친 공생 빈도의 누적치를 나타낸다.
임베딩: 각 청크에 대한 밀집 벡터 표현(dense vector representations)을 사전 계산하고 유사도 검색을 위해 인덱싱한다.

2.2. 온라인 추론

검색 프로세스는 반복적이고 다중 홉 방식으로 진행되며, 네 가지 핵심 구성 요소로 이루어진다:

의미론적 확장 (PPR):
- 사용자 질의를 토큰화하여 KG의 시드 노드(seed nodes)를 식별한다.
- 시드 노드로부터 **개인화 페이지랭크(Personalized PageRank, PPR)**를 실행하여 위상적 이웃을 탐색하고 의미론적으로 관련된 개념을 식별한다.
- 상위- $\gamma$ 노드를 선택하여 확장된 토큰 집합 $\Phi_\mu$ 를 형성한다.
후보 검색 및 그래프 가중치 점수 산정:
- 원래의 질의 또는 확장된 집합에 포함된 토큰을 포함하는 경우 후보 청크를 검색한다.
- 단순한 어휘적 중복보다 구조적으로 관련 있는 개념을 우선시하도록, BM25 점수와 PPR 유래 토큰 확률 가중치를 결합하여 하이브리드 점수 $\rho(c, \mu)$ 를 계산한다.
동적 후보 풀링:
- 누적 점수 임계값 메커니즘을 통해 후보 목록을 필터링한다. 전체 점수 질량의 사전 정의된 비율( $th_\rho$ )에 도달하는 청크만 유지하며, 신뢰도에 따라 풀 크기를 동적으로 조정한다.
신경망 재순위화 (Neural Reranking):
- 질의 임베딩과 청크 임베딩 간의 코사인 유사도를 사용하여 동적 풀을 재순위화함으로써 최대의 의미론적 충실도를 보장한다.

2.3. 다중 홉 추론 전략

여러 추론 단계가 필요한 복잡한 질의를 처리하기 위해 다음을 수행한다:

반복적 엔티티 기반 확장: 첫 번째 검색 홉 이후, 상위 검색된 청크들은 개체명 인식(NER) 파이프라인을 거친다.
질의 증강: 이 청크들에서 추출된 새로운 미인지 엔티티들을 원래의 질의에 결합하여 확장된 질의( $\mu_{exp}$ )를 형성한다.
재검색: 확장된 질의를 사용하여 그래프 기반 검색 및 재순위화 과정을 반복한다.
종료: 더 이상 새로운 엔티티가 발견되지 않거나 최대 홉 제한에 도달할 때까지 프로세스가 지속된다.
최종 집계: 모든 홉에서 검색된 청크들을 병합하며, 각 청크에 대해 최대 관련도 점수를 유지하고, 상위- $\beta$ 청크를 LLM 프롬프트에 주입한다.

3. 주요 기여

효율적인 그래프 구축: TIGRAG는 LLM 기반 엔티티 추출 없이 토큰 공생 통계를 통해 KG를 구축함으로써 인덱싱 시간과 계산 비용을 크게 줄인다.
위상적 의미론적 확장: PPR을 활용하여 검색 신호를 의미론적 노드 전반으로 자연스럽게 전파함으로써, 명시적인 질의 분해 없이도 서로 연결된 증거를 발견할 수 있게 한다.
반복적 엔티티 기반 검색: 검색된 문맥으로부터 브릿징 엔티티(bridging entities)를 사용하여 질의를 점진적으로 확장하는 메커니즘을 도입하여, 특히 다중 홉 추론의 간극을 타겟팅한다.
하이브리드 점수 산정 및 재순위화: 그래프 가중치가 적용된 구조적 관련성과 신경망 기반의 의미론적 정렬을 결합하여 노이즈를 필터링하고 고품질의 문맥 선택을 보장한다.

4. 실험 결과

본 프레임워크는 세 가지 다중 홉 QA 벤치마크인 HotpotQA, 2WikiMultiHopQA, MuSiQue를 통해 평가되었다.

검색 성능: TIGRAG는 밀집 검색(NaiveRAG) 및 최신 그래프 기반 방식(HippoRAG2, LightRAG, GraphRAG 포함)을 일관되게 능가했다.
- HotpotQA에서 NaiveRAG 대비 Recall@2를 9.70% 향상시켰다.
- MuSiQue에서 HippoRAG2 대비 Recall@2를 19.92% 개선했다.
다운스트림 QA 성능: TIGRAG는 모든 데이터셋에서 Exact Match (EM) 및 토큰 수준 F1 점수에서 새로운 SOTA(State-of-the-art) 결과를 달성했다. 예를 들어, HotpotQA에서 NaiveRAG 대비 EM을 13.67% 향상시켰다.
효율성:
- 인덱싱 시간: TIGRAG의 오프라인 그래프 구축은 다른 그래프 기반 방식(예: HotpotQA에서 HippoRAG2의 ~308,000초 대비 ~191초)보다 현저히 빨랐으며, 밀집 검색과 유사한 수준이었다.
- 추론 지연 시간: 복잡한 데이터셋(2WikiMultiHopQA, MuSiQue)에서 TIGRAG는 줄어든 프롬프트 풋프린트 덕분에 엔드투엔드(end-to-end) 측면에서 NaiveRAG보다 빨랐다.
- 프롬프트 풋프린트: 압축적이고 높은 관련성을 가진 청크를 동적으로 선택함으로써, TGRAC는 광범적인 KG 요약이나 트리플렛을 주입하는 방식에 비해 LLM에 전달되는 토큰 수를 크게 줄였다.

5. 의의 및 주장

본 논문은 TIGRAG가 계산 효율성을 희생하지 않으면서도 복잡한 다중 홉 추론 작업을 해결할 수 있는 그래프 증강 RAG 시스템을 보여준다고 주장한다.

확장성: LLM 기반의 비용이 많이 드는 그래프 구축을 우회함으로써, TGRAC는 실제 배포에 적합한 매우 확장 가능한 솔루션을 제공한다.
견고성: 통계적 방식의 그래프 구축은 LLM 기반 추출 파이프라인에서 발생하는 환각 및 노이즈 문제를 방지한다.
성능: 이 프레임워크는 검색 정확도와 생성 품질 모두에서 새로운 벤치마크를 설정하며, 토큰 공생을 통한 위상적 확장이 전통적인 밀집 검색 및 복잡한 GraphRAG 아키텍처에 대한 유효하고 우수한 대안임을 입증한다.

저자들은 한계점을 인정하며, 프레임워크가 NER 파이프라인의 품질에 의존한다는 점(엔티티가 부정확할 경우 의미론적 표류 위험)과 주로 토큰 근접성에 기반하여 관계를 포착한다는 점을 언급했다. 향후 연구로는 의미론적 엣지를 통합하고, 토큰의 다의성(polysemy) 문제를 해결하며, 멀티모달 환경으로 확장하는 것이 제안되었다.