[논문 리뷰] INFINI-GRAM MINI: Exact n-gram Search at the Internet Scale with FM-Index

INFINI-GRAM MINI

: Exact n-gram Search at the Internet Scale with FM-Index

* 투빅스 스터디에서 진행한 논문 리뷰를 요약한 글입니다.

 

 

요즘 흐름이 Modeling 으로는 성능을 올리는 데에 거의 한계에 도달했고, 데이터의 크기와 컴퓨팅자원이 성능을 결정하는 느낌이라

→ 요즘 NLP 트렌드는 Data-Centric AI + Retrieval + Efficient Indexing 인 것 같아요

1. 얼마나 잘 정제된 학습 데이터를 사용했는지,
2. Retrieval을 어떻게 잘 해서 어려운 task도 잘 해결하는지,
3. Retrieval 할 때 방대한 데이터를 얼마나 효율적으로 Indexing 해서 검색하는지

이 논문은 이 중에서 데이터 정제와 indexing과 관련이 있습니다.

 

Abstract 요약

“an efficient and scalable system that can make petabyte-level text corpora searchable”

페타바이트 규모의 텍스트 말뭉치를 검색 가능한, 효율적이고 확장 가능한 시스템

“based on the FMindex data structure”

FMindex 자료구조에 기반한

 

배경: 왜 초대형 n-gram 검색이 필요한가?

언어 모델의 학습 데이터 대형화

최근 LLM은 방대한 텍스트 코퍼스를 학습하며, Peta-Byte 단위 데이터를 다루어야 한다.

이때 필연적으로 제기되는 문제가 바로 Benchmark Contamination(벤치마크 오염)이다.

 

Benchmark Contamination 문제

• 정량적 평가지표만으로는 LLM의 추론 능력을 평가하기 어렵기 때문에, 다양한 분야의 수많은 평가 벤치마크들로 성능을 평가한다.
• 그런데 벤치마크의 질문과 정답이 인터넷에 떠돌다 학습 데이터에 포함될 수 있다.
• LLM 학습 데이터는 대부분 인터넷에서 크롤링되기 때문에, 벤치마크가 공개된 시점 이후에는 거의 필연적으로 학습 데이터에 섞일 수밖에 없다.
• 모델은 이를 암기하여 문제를 풀기 때문에 실제 추론 능력이 과대평가된다.
  • 예: 해커톤에서 테스트 데이터를 몰래 훈련에 넣는 상황과 동일한 문제.

따라서, 벤치마크 데이터가 학습 데이터 안에 포함되어 있었는지 정확하게 검색할 수 있어야 한다.

 

기존 방식의 한계

기존 검색 엔진(Elasticsearch 등)은 단어의 위치 정보(Offset)를 전부 저장해야 했다.

하지만 이는 원본 데이터보다 2배~29배 더 큰 인덱스 용량을 필요로 하여, 페타바이트급 데이터에 적용하는 것이 거의 불가능했다.

Exact-match를 하려면

1. 텍스트 원본을 그대로 유지해야 한다.
2. 텍스트의 모든 위치 정보를 추가로 저장해야 한다.
   • 간단한 예시로 The cat chased the dog / The dog chased the cat. 단어는 모두 같지만 순서에 따라 의미가 완전히 달라진다.
   • 이렇게 되면 원본 텍스트 + 위치 정보 + 기타 테이블 등으로 해서 용량이 최대 29배까지 늘어난다.
   • 1PB 텍스트를 검색하려면 29PB 인덱스가 필요한데, 이건 현실적으로 불가능하다.

 

이러한 문제를 해결하기 위해서,

⇒ Bioinformatics(생물정보학) 에서 주로 쓰이던 FM-index 기술을 대규모 자연어 데이터에 적용했다.

 

 

Background: FM-index

전체 텍스트를 고도로 압축하여 저장하면서도 패턴 매칭, 개수 세기(Counting), 텍스트 복원을 효율적으로 수행할 수 있는 자료구조

기존 Suffix Array(접미사 배열) 방식에 비해 저장 공간을 획기적으로 줄여준다.

구성 요소:

• Suffix Array (SA)
• Inverse SA (ISA)
• Burrows-Wheeler Transform (BWT)
• Huffman-shaped Wavelet Tree

 

Suffix Array (SA, 접미사 배열)

• 텍스트의 모든 접미사를 사전 순으로 정렬한 배열.정렬되어 있으므로 이진 탐색(Binary Search) 가능
• → 속도 O(m log n). n은 텍스트의 길이, m은 query의 길이
• 하지만 전체 SA 저장은 용량이 너무 크므로→ 일정 간격(a=32)로 샘플링하여 저장 → 나머지는 BWT 역추적으로 복원
• a 값이 커지면 메모리는 줄지만, 값을 복원할 때 연산량이 늘어난다.
  • 메모리 vs 검색 속도(CPU 연산량) 사이의 trade-off

 

BWT (Burrows-Wheeler Transform)

• 텍스트를 재배열하여 반복되는 문자를 뭉쳐놓은 문자열 → 압축 효율을 극대화
• LF Mapping: 변환된 문자열에서 역방향으로 원본을 추적

 

예시: banana_bandana_bundle… → bnndddddaaaaaaannn… → b2n5d7a3n..

 

Inverse SA (ISA)

SA[i] = j일 때 ISA[j] = i인 배열 검색된 패턴의 원본 문서 내 정확한 위치를 찾아낼 때 사용

 

INFINI-GRAM MINI의 특징

1) Raw Byte 기반 인덱싱

보통 LLM은 텍스트를 의미 단위인 토큰으로 쪼개서 처리한다. 하지만 이 모델은 토큰화를 버리고 컴퓨터가 보는 가장 기초 단위인 바이트(Byte)를 그대로 쓴다.

• 이유 1: FM-index 자체가 압축률이 좋아 굳이 토큰화로 데이터를 미리 줄일 필요가 없다.
• 이유 2: 언어에 상관없이 적용 가능(Language Agnostic)하다.
  • 한국어든 영어든 컴퓨터 입장에서는 다 똑같은 0~255 숫자
  • 만약 토큰화를 하면 각 언어별 tokenizer를 따로 만들어주어야 한다.
• 이유 3: 알파벳 크기를 256으로 고정하여 자료구조 성능 최적화
  • 다뤄야 할 문자 종류가 수만 개에서 256개로 줄어든다. → 훨씬 빠르다.

 

2) 기존 SDSL 대비 성능 향상

기존의 최적 라이브러리인 SDSL(Succinct Data Structure Library)과 비교했을 때 압도적인 성능 향상

• 속도: 18배 더 빠름
• 메모리(RAM): 3.2배 더 적게 사용
• Disk-based Query: 인덱스를 디스크에 저장해두고 쿼리할 수 있어, RAM이 적은 머신에서도 대용량 인덱스 검색이 가능

8.7GB 코퍼스 인덱싱 시, SDSL은 5,847초와 74,807MB RAM이 필요했으나, INFINI-GRAM MINI는 324초 (18배 속도 향상)와 23,742MB RAM (3.2배 감소)으로 완료했다.

 

 

INFINI-GRAM MINI의 인덱스 구축 방식 (Index Construction)

1) 완전 병렬화 (Full Parallelization)

기존 FM-index 구현(SDSL)은 단일 스레드 기반이라 대규모 코퍼스에 적용하기 어려웠다.

INFINI-GRAM MINI는 대규모 코퍼스를 구축하는 모든 단계를 병렬화했다.

 

병렬화된 주요 단계:

Suffix Array(SA) 생성

BWT(Burrows–Wheeler Transform) 생성

Wavelet Tree 생성

Sampling

 

기존 방식은 멀티코어를 활용하지 못했지만, INFINI-GRAM MINI는 인덱스 구축 전 단계를 병렬화하여 압도적인 속도 향상을 실현했다.

2) 전처리 (Preprocessing)

FM-index는 하나의 커다란 문자열을 대상으로 구축되므로, 코퍼스의 각 문서를 합치는 전처리 단계가 필요하다.

1. 모든 문서를 UTF-8 raw byte로 변환

→ “토큰화 없는 인덱싱”을 가능하게 하는 중요한 조치

 

2. 문서 경계에 0xFF 삽입

→ 원본 텍스트를 복원하거나 문서별 검색을 할 때

어디서 시작/끝인지 판단하기 위한 분리자(separator)

 

3. 문서 시작 위치를 offset 파일에 별도 저장

→ 나중에 특정 문자열이 발견되면, “이 문자열이 어느 문서에 있고, 문서 내 어느 위치인가?”를 빠르게 찾기 위해 필요

 

“문서를 하나의 거대한 문자열로 합치되, 나중에 원본 문서 단위 정보도 잃지 않도록” 하는 역할

3) 샤딩 (Sharding)

PB 규모 데이터를 한 번에 인덱싱하는 것은 메모리/CPU 모두에 무리이다.

그래서 코퍼스를 여러 shard로 나누어 독립적으로 FM-index를 구축한다.

장점:

• 각 shard는 별도 노드에서 병렬 구축 가능 → 빠름
• 샤드 단위로 메모리 사용량 관리 가능
• 후처리나 재구축도 shard 단위로 유연하게 진행

이 방식 덕분에 PB 스케일 데이터에서도 시스템이 무너질 일 없이 인덱싱이 가능해진다.

 

128vCPUs와 2TiB RAM을 가진 CPU 노드를 사용했을 때 전체 83TB 인덱싱에 총 98.8 노드-일이 소요됨

하지만,  137개의 노드에 병렬로 나누어 수행했을 경우 19시간 만에 완료 가능

 

 

결과적으로 인덱스 크기: 원본 크기의 44% 수준

병렬화 + raw byte 처리 + 샤딩 덕분에

페타바이트급 대형 코퍼스도 실제로 구축 가능한 FM-index 인덱서를 만들었다.

 

INFINI-GRAM MINI를 활용한 벤치마크 오염 분석

INFINI-GRAM MINI의 대규모 검색 기능을 사용해 24개의 주요 벤치마크가 The Pile / DCLM-baseline / Common Crawl 등 LLM을 학습시킬 때 사용하는 거대 코퍼스에 어느 정도 포함되어 있는지(오염되었는지) 분석

오염도 측정 방법: Lexical Overlap(어휘적 중복)

• 50자 길이의 substring을 벤치마크 질문/지문에서 1단어 간격으로 전부 추출한다.
• 각 substring이 코퍼스에서 한 번이라도 등장하면 오염으로 기록한다.
• 등장한 substring의 비율 η(0~100%)을 계산한다.

 

최신 벤치마크도 실제로 상당히 오염됨

• MMLU: 27.7%
• ARC-Challenge: 32.6%→ 최근 LLM 성능이 실제보다 높게 평가되었을 가능성이 큼
  • → 두 벤치마크 모두 DCLM-baseline에서 Dirty 수준에 가깝다

코퍼스 크기·신선도(?)에 따라 오염도 급상승

• 더 큰 데이터(DCLM)가 Pile보다 오염도가 훨씬 높음
  • ARC-Challenge 오염도는 Pile → DCLM에서 17배 증가
• 시간이 지날수록 새 데이터에 벤치마크가 더 많이 등장
  • AIME-2024: 처음엔 깨끗했으나 CC-2025-21에서 40% 오염
  • GSM8K: 최신 CC-2025-21에서 74.2% 오염

도메인별 차이

• 오염 심함:
  • Commonsense
  • Reading Comprehension
  • 온라인 글/블로그에서 쉽게 인용되는 도메인
• 상대적으로 깨끗함:
  • Math
  • Code
  • 전문성·작성 난이도 때문에 인터넷에 누출되는 양이 적은 편

 

오염의 종류

 

오염의 원인

벤치마크가 인터넷에 자연스럽게 퍼지면서 오염이 발생한다.

• 벤치마크 자체가 인터넷에서 수집된 경우
  • (예: AIME-2024, SWE-bench)
• 다른 온라인 문제집/퀴즈 사이트가 해당 문제를 인용하는 경우
  • (예: GSM8K)
• 연구 논문이나 블로그 글에서 예제 문제로 인용
  • (예: GPQA, MMLU 등)

즉, 벤치마크는 시간이 지날수록 인터넷에 더 많이 퍼지고, 학습 데이터에 더 쉽게 포함될 수밖에 없다.

그래서? 실시간으로 지속적인 모니터링이 필요하다.

 

벤치마크 오염 게시판 (Benchmark Contamination Bulletin)

INFINI-GRAM MINI는 단순 분석을 넘어서 지속 서비스 형태로 운영될 수 있다.

 

목적

새로 크롤링된 데이터를 계속 인덱싱하고, 벤치마크 오염도를 주기적으로 갱신하기 위함

기능

• Common Crawl 최신 버전 자동 인덱싱
• 벤치마크별 오염 분석 결과 지속 업데이트
• 사용자가 자신의 벤치마크를 업로드해 오염 여부를 직접 확인 가능

 

 

Demo & Code

https://github.com/xuhaoxh/infini-gram-mini

GitHub - xuhaoxh/infini-gram-mini