Each language version is independently generated for its own context, not a direct translation.

📚 SINDI: 거대한 도서관에서 '희박한' 단어를 찾아내는 초고속 비법

이 논문은 RAG(검색 증강 생성) 기술, 즉 AI 가 답변을 할 때 필요한 정보를 찾아내는 과정에서 쓰이는 '희박 벡터 (Sparse Vector)' 검색 속도를 획기적으로 높인 새로운 기술인 SINDI를 소개합니다.

이걸 이해하기 위해 거대한 도서관과 비밀 번호에 비유해 보겠습니다.

1. 문제 상황: 왜 기존 방식은 느릴까요?

상상해 보세요. 전 세계 모든 책이 있는 거대한 도서관이 있다고 합시다. 사용자가 "고양이를 좋아하세요?"라고 질문하면, 도서관 사서는 이 질문과 가장 관련 있는 책들을 찾아야 합니다.

기존 방식 (SEISMIC, PYANNS 등):
- 사서는 질문의 키워드 ("고양이", "좋아하다") 를 들고 각 책의 목차 (인덱스) 를 뒤적거립니다.
- 문제 1 (지루한 대조): "이 책에 '고양이'라는 단어가 있나? 있다면 점수는 얼마지?"라고 책 한 권 한 권을 직접 꺼내서 확인해야 합니다. 책을 꺼내는 과정이 너무 자주 일어나서 손이 아프고 (메모리 접근 지연), 같은 단어를 반복해서 확인하는 낭비가 생깁니다.
- 문제 2 (비효율적인 계산): 컴퓨터는 한 번에 여러 계산을 동시에 할 수 있는데 (SIMD), 기존 방식은 책들이 제각기 다른 형태로 저장되어 있어 동시 계산을 못 합니다. 마치 공장에서 조립 라인이 멈추고 수작업으로 하는 것과 비슷합니다.

2. SINDI 의 해결책: 세 가지 마법

SINDI 는 이 도서관을 완전히 재설계하여 3 가지 마법을 부릅니다.

🪄 마법 1: "인덱스 안에 점수까지 적어두기" (Value-Storing Inverted Index)

기존 방식은 인덱스에 "책 번호"만 적어두고, 점수를 계산하려면 다시 책을 꺼내야 했습니다.

SINDI 의 방식: 인덱스 카드에 "책 번호"와 함께 "점수"를 미리 적어둡니다.
비유: 도서관 사서가 책장 뒤에서 책을 꺼내지 않고, 인덱스 카드만 보고 "아, 이 책에 '고양이'가 0.8 점으로 적혀 있네!"라고 바로 계산할 수 있게 된 것입니다. 불필요한 책 꺼내기를 아예 없앴습니다.

🪄 마법 2: "줄 서서 계산하기" (Sequential Access & SIMD)

기존 방식은 책들이 흩어져 있어 사서가 여기저기 뛰어다니며 책을 찾아야 했습니다 (랜덤 메모리 접근).

SINDI 의 방식: 책들을 순서대로 줄을 서게 합니다.
비유: 사서가 한 줄로 서 있는 책들을 쭉 훑어가며, 컴퓨터가 한 번에 여러 개의 책을 동시에 처리할 수 있게 (SIMD 가속) 만들었습니다. 이제 사서는 뛰어다니지 않고, 책장 앞에서 줄을 따라가며 빠르게 점수를 합산합니다.

🪄 마법 3: "중요한 것만 남기기" (Vector Pruning)

모든 단어를 다 비교할 필요는 없습니다. "고양이"는 중요하지만, "그", "의" 같은 사소한 단어는 점수에 큰 영향을 주지 않습니다.

SINDI 의 방식: 점수가 아주 낮은 단어들은 아예 인덱스에서 잘라버립니다 (Mass Ratio Pruning).
비유: 도서관에서 "고양이"나 "사랑"처럼 중요한 단어만 적힌 책만 골라내서 검색 범위를 좁힙니다. 검색해야 할 책의 수가 반으로 줄어도, 정작 중요한 책들은 빠뜨리지 않고 찾아냅니다.

3. 실제 효과: 얼마나 빨라졌나요?

이 기술은 **Ant Group(안타그룹)**의 실제 시스템에 적용되었습니다.

속도: 기존 최고 성능 기술 (SEISMIC, PYANNS) 보다 4 배에서 26 배까지 더 빠릅니다.
- 예를 들어, 기존에 1 초에 100 개의 질문을 처리했다면, SINDI 는 1 초에 2,600 개까지 처리할 수 있습니다.
정확도: 속도가 빨라졌다고 해서 답을 틀리는 일은 없습니다. 오히려 99% 이상의 정확도를 유지하면서도 속도가 비약적으로 향상되었습니다.
적용: 이미 오픈소스 라이브러리인 VSAG에 통합되어 사용 중입니다.

4. 결론: 왜 이것이 중요한가요?

우리가 AI 에게 질문을 할 때, AI 가 더 빠르고 정확하게 답변을 하려면 방대한 데이터에서 필요한 정보를 순간에 찾아야 합니다.

SINDI 는 "불필요한 작업을 줄이고, 중요한 정보만 빠르게 계산하며, 컴퓨터의 힘을 최대한 활용하는" 지능적인 검색 시스템입니다. 마치 도서관 사서가 더 이상 책을 일일이 꺼내지 않고, 스마트한 인덱스 카드와 줄서기 시스템을 통해 사용자의 질문에 순간에 최고의 책을 찾아주는 것과 같습니다.

이 기술은 앞으로 우리가 사용하는 AI 챗봇, 검색 엔진, 추천 시스템이 훨씬 더 빠르고 똑똑해지도록 돕는 핵심 열쇠가 될 것입니다.

Each language version is independently generated for its own context, not a direct translation.

1. 문제 정의 (Problem)

최근 검색 증강 생성 (RAG, Retrieval-Augmented Generation) 시스템의 성능을 높이기 위해, 밀집 벡터 (Dense Vector) 기반 검색에 희소 벡터 (Sparse Vector) 기반 검색을 결합하는 하이브리드 방식이 주목받고 있습니다. 희소 벡터 (예: SPLADE 모델) 는 정확한 어휘 매칭 (Lexical Matching) 을 제공하여 밀집 벡터가 놓칠 수 있는 세부 정보를 보완합니다.

하지만 희소 벡터에 대한 **최대 내적 검색 (MIPS, Maximum Inner Product Search)**을 수행할 때 기존 알고리즘 (SEISMIC, PYANNS 등) 은 다음과 같은 심각한 병목 현상을 겪습니다:

중복된 거리 계산 비용: 쿼리와 문서 벡터 간의 공통 비영 (Non-zero) 차원을 찾기 위해 모든 엔트리를 스캔해야 하며, 이는 $O(\|q\| + \|x\|)$ 의 복잡도를 가집니다.
SIMD 가속 불가: 희소 벡터의 불규칙한 저장 구조로 인해 병렬 처리가 가능한 SIMD (Single Instruction, Multiple Data) 명령어를 효과적으로 활용할 수 없습니다.
랜덤 메모리 접근 (Random Memory Access): 기존 인덱스는 원본 벡터 데이터를 무작위로 접근해야 하므로 캐시 미스 (Cache Miss) 가 빈번하게 발생하여 메모리 바운드 (Memory-bound) 지연을 유발합니다.

2. 제안 방법론: SINDI (Methodology)

저자들은 위 문제들을 해결하기 위해 **SINDI (Sparse Inverted Non-redundant Distance Index)**를 제안합니다. 이는 희소 벡터 검색을 위한 새로운 역색인 (Inverted Index) 구조로, 세 가지 핵심 최적화를 적용합니다.

가. 값 저장형 역색인 (Value-Storing Inverted Index)

기존 방식: 역색인에는 문서 ID 만 저장하고, 실제 값은 원본 벡터에서 별도로 조회해야 함.
SINDI 방식: 역색인 리스트 (Posting List) 에 **문서 ID 와 함께 해당 차원의 값 (Value)**을 직접 저장합니다.
효과: 공통 차원을 찾기 위한 별도의 조회 (Lookup) 오버헤드를 제거하고, 검색 과정에서 내적 계산을 즉시 수행할 수 있게 합니다.

나. 효율적인 내적 계산 및 SIMD 활용 (Efficient Inner Product Computation)

두 단계 검색 프로세스:
1. 곱셈 단계: 쿼리 값과 역색인 리스트에 저장된 값들을 SIMD 명령어를 사용하여 배치 (Batch) 로 곱셈합니다.
2. 누적 단계: 계산된 곱셈 결과를 미리 할당된 거리 배열 (Distance Array) 에 순차적으로 누적합니다.
복잡도 개선: 기존 $O(\|q\| + \|x\|)$ 에서 $O(\|q\|/s)$ (여기서 $s$ 는 SIMD 폭) 로 복잡도를 낮추어 CPU 활용도를 극대화합니다.

다. 메모리 친화적 설계 (Memory-Friendly Design & Window Switch)

문제: 대규모 데이터셋에서 전체 거리 배열을 무작위로 접근하면 캐시 미스가 발생합니다.
해결책 (Window Switch): 문서 ID 공간을 고정된 크기 ( $\lambda$ ) 의 '윈도우'로 나눕니다. 각 윈도우 내에서만 거리 배열을 순차적으로 접근하도록 제한합니다.
효과: 메모리 접근 패턴을 순차 스캔에 가깝게 만들어 캐시 효율성을 높이고, 랜덤 접근으로 인한 지연을 최소화합니다.

라. 벡터 대량 가지치기 (Vector Mass Pruning)

전략: 희소 벡터의 대부분 정보는 소수의 고가 (High-value) 비영 엔트리에 집중되어 있다는 점을 활용합니다.
Mass Ratio Pruning (MRP): 벡터의 전체 '질량 (Mass, 절대값의 합)' 중 상위 $\alpha$ 비율을 차지하는 엔트리를만 남기고 나머지를 제거합니다.
효과: 검색 공간을 획기적으로 줄이면서도 내적 오차를 최소화하여 정확도를 유지합니다.

마. 재순위화 (Reordering)

가지치기를 통해 얻은 후보 집합 (Coarse Candidates) 에 대해 정확한 내적 계산을 수행하여 최종 Top-k 결과를 도출하는 2 단계 전략을 사용합니다. 이를 통해 가지치기로 인한 정확도 손실을 보정합니다.

3. 주요 기여 (Key Contributions)

새로운 인덱스 구조 (SINDI): 역색인에 값을 직접 저장하여 ID 조회 오버헤드를 제거하고, SIMD 를 활용한 배치 내적 계산을 가능하게 함.
Window Switch 전략: 대규모 데이터셋에서도 캐시 효율성을 극대화하기 위한 메모리 접근 최적화 기법 제안.
Mass Ratio Pruning (MRP): 기존 List Pruning 이나 Vector Number Pruning 보다 내적 오차를 최소화하면서 검색 공간을 줄이는 새로운 가지치기 알고리즘 제안.
실제 환경 통합: Ant Group 의 오픈소스 벡터 검색 라이브러리인 VSAG에 통합되어 실제 프로덕션 환경에서 검증됨.

4. 실험 결과 (Results)

저자들은 MSMARCO, NQ, AntSparse(중국어) 등 다양한 규모와 언어의 실세계 데이터셋에서 SINDI 를 평가했습니다.

성능 (QPS vs Recall):
- Recall@50 > 99% 조건에서 SINDI 는 기존 SOTA 알고리즘 대비 압도적인 성능을 보였습니다.
- MSMARCO (SPLADE-1M): SEISMIC 대비 2.0 배, PYANNS 대비 26.4 배 높은 단일 스레드 QPS 를 달성.
- AntSparse-10M (중국어): SEISMIC 대비 2.5 배 높은 QPS 달성.
- Random Dataset: 데이터 분포에 민감한 그래프 기반 (HNSW 등) 방법론이 성능이 저하되는 반면, SINDI 는 데이터 분포에 구애받지 않고 일관된 고성능을 유지.
인덱스 구축 시간:
- PYANNS(그래프 기반) 는 이웃 탐색을 위해 수천 초가 소요되는 반면, SINDI 는 약 60 초 내에 880 만 건 (SPLADE-FULL) 의 인덱스를 구축하여 71.5 배 빠른 구축 속도를 보임.
확장성:
- 멀티스레드 환경 (2~10 코어) 에서도 높은 병렬 효율성을 유지하며, 코어 수 증가에 따른 QPS 증가율이 선형에 가까움.

5. 의의 및 결론 (Significance)

SINDI 는 희소 벡터 검색 분야에서 정확도 (Recall) 와 처리량 (Throughput) 의 트레이드오프를 획기적으로 개선한 솔루션입니다.

기술적 의의: 희소 벡터의 불규칙한 구조를 역이용하여 SIMD 가속과 순차 메모리 접근을 가능하게 함으로써, 기존에 희소 벡터 검색의 병목으로 여겨지던 메모리 및 계산 오버헤드를 해결했습니다.
실용적 의의: RAG 시스템의 핵심 구성 요소로서, 더 빠르고 정확한 문서 검색을 가능하게 하여 생성형 AI 의 응답 품질을 높이는 데 기여합니다. 특히 Ant Group 의 실제 비즈니스 환경 (VSAG) 에 통합되어 그 실용성을 입증했습니다.

결론적으로, SINDI 는 대규모 희소 벡터 데이터셋에 대한 Approximate MIPS 문제를 해결하는 **새로운 표준 (State-of-the-Art)**으로 자리 잡을 것으로 기대됩니다.

SINDI: an Efficient Index for Approximate Maximum Inner Product Search on Sparse Vectors