WARP - An Efficient Engine for Multi-Vector Retrieval

2501.17788

WARP: 멀티-벡터 검색을 위한 초고효율 엔진

이해를 돕기 위해, 먼저 정보 검색 기술의 흐름을 간단히 짚어보겠습니다.

• 1단계: 키워드 검색 (예: BM25)
  • 문서에 특정 단어가 몇 번 나오는지를 세어서 점수를 매기는 방식입니다. 단순하고 빠르지만, ‘자동차’와 ‘탈것’처럼 의미는 같지만 글자가 다른 단어는 잘 찾아내지 못합니다.
• 2단계: 싱글-벡터 검색 (Single-Vector Retrieval)
  • 문서 전체의 의미를 하나의 긴 숫자 배열(벡터)로 압축합니다. ‘자동차’와 ‘탈것’이 비슷한 의미라는 것을 벡터 공간에서 ‘가까운 거리’로 표현할 수 있어 의미 기반 검색이 가능해집니다. 하지만 문서의 풍부한 내용을 하나의 벡터로만 압축하다 보니, 세부적인 내용이나 뉘앙스를 놓치는 한계가 있었습니다.
• 3단계: 멀티-벡터 검색 (Multi-Vector Retrieval, 예: ColBERT, XTR)
  • 문서를 하나의 벡터가 아닌, 문서에 포함된 여러 개의 중요한 토큰(단어 혹은 단어의 일부) 각각을 벡터로 표현합니다. 예를 들어, “워프는 빠른 검색 엔진이다”라는 문장이 있다면 ‘워프’, ‘빠른’, ‘검색’, ‘엔진’ 각각을 벡터로 만들어 저장합니다. 이렇게 하면 훨씬 더 정밀하고 풍부한 의미를 표현할 수 있어 검색 정확도가 크게 향상됩니다.

WARP는 바로 이 3단계, 멀티-벡터 검색을 “어떻게 하면 비현실적으로 느린 속도를 현실적으로 빠르게 만들까?” 라는 문제를 해결하기 위해 탄생한 기술입니다.

---

B) 이 논문이 해결하려는 문제는 무엇인가요?

최신 멀티-벡터 검색 모델인 XTR 은 ColBERT의 아이디어를 한 단계 발전시켜, 검색 과정을 더 단순화하고 이론적으로 효율성을 높일 잠재력을 보여주었습니다. 하지만 논문 저자들이 직접 테스트해 보니, XTR의 공식 구현체는 아이디어는 좋았지만 최적화가 덜 되어 있어 실제 검색 속도가 매우 느렸습니다. 예를 들어, LoTTE라는 대규모 데이터셋에서 검색 한 번에 6초 이상이 걸렸습니다. 사용자가 검색 버튼을 누르고 6초를 기다려야 한다면 아무도 쓰지 않겠죠.

반면, ColBERT 모델을 빠르게 만든 PLAID 라는 엔진은 압축, 가지치기 등 다양한 최적화 기법으로 속도를 크게 향상시켰습니다.

여기서 저자들은 이런 질문을 던집니다.

“XTR의 똑똑한 검색 방식과 PLAID의 공격적인 속도 최적화 기술, 이 둘의 장점만 쏙쏙 뽑아 합치면 어떻게 될까?”

이 질문에 대한 답이 바로 WARP 입니다.

---

C) 그래서 WARP는 무엇을 제안했나요?

WARP는 XTR의 검색 품질은 그대로 유지하면서, 속도를 극적으로 끌어올리기 위해 세 가지 핵심 혁신을 제안합니다.

C.1) 혁신 1: WARPSELECT - 누락된 점수를 똑똑하게 예측하기

• 문제점: XTR 방식은 검색어의 각 토큰(예: ‘빠른’)과 가장 관련 있는 문서 토큰 몇 개(예: ‘신속한’, ‘고속의’)만 비교하여 점수를 계산합니다. 그럼 나머지 수많은 문서 토큰들과의 점수는 어떻게 할까요? XTR은 이 ‘누락된 점수’를 그냥 이미 찾은 점수들 중 가장 낮은 값으로 대충 채워 넣었습니다. 이 방식은 부정확할 수 있고, 점수를 더 정확하게 예측하려면 더 많은 후보 토큰을 찾아봐야 하므로 속도가 느려지는 원인이 됩니다.
• WARP의 해결책: WARP는 문서 토큰들을 미리 여러 그룹(클러스터)으로 묶어 놓습니다. 그리고 검색어 토큰과 각 ‘그룹’의 대표 벡터와의 유사도를 미리 계산해 둡니다. WARPSELECT는 이 미리 계산된 그룹 유사도 정보를 활용하여, 굳이 모든 토큰을 비교하지 않고도 ‘누락된 점수’를 매우 빠르고 효율적으로 예측합니다. 이는 후보를 찾음과 동시에 누락된 점수까지 한 번에 계산하는 매우 영리한 방식입니다.

C.2) 혁신 2: 암시적 압축 해제 (Implicit Decompression) - 압축을 풀지 않고 바로 계산하기

• 문제점: 멀티-벡터 검색은 수많은 토큰 벡터들을 저장해야 해서 용량이 매우 큽니다. 그래서 PLAID 같은 엔진은 벡터를 압축해서 저장하고, 검색 시점에 이 압축을 푸는 과정(Decompression)을 거칩니다. 하지만 이 압축 해제 과정 자체가 상당한 시간을 소모하는 병목 구간이었습니다.
• WARP의 해결책: WARP는 “어차피 최종 유사도 점수만 알면 되는데, 굳이 압축된 벡터를 원래 벡터 형태로 완전히 복원할 필요가 있을까?”라고 생각했습니다. 그래서 압축된 벡터를 명시적으로 풀지 않고, 수학적 원리를 이용해 압축된 상태에서 바로 최종 점수를 계산해버립니다. 이는 마치 압축 파일의 내용물을 직접 보지 않고도, 그 안에 특정 단어가 몇 번 나오는지 계산하는 것과 같습니다. 이 ‘암시적 압축 해제’ 기법 덕분에 속도 저하의 주범이었던 압축 해제 단계를 사실상 건너뛸 수 있게 되어 엄청난 속도 향상을 이뤄냈습니다.

C.3) 혁신 3: 2단계 축소 (Two-Stage Reduction) - 효율적인 최종 점수 합산

• 문제점: 검색어의 모든 토큰과 후보 문서의 모든 토큰 간의 점수를 계산하면 거대한 점수표(Score Matrix)가 만들어집니다. 이 큰 표를 만들고, 행(문서)별로 점수를 합산하는 과정은 메모리를 많이 쓰고 계산도 비효율적입니다.
• WARP의 해결책: WARP는 이 과정을 두 단계로 나눕니다.
  1. 토큰 레벨 축소: 먼저 각 검색어 토큰에 대해, 어떤 문서에서 가장 높은 점수를 받았는지 ‘최댓값’만 남깁니다.
  2. 문서 레벨 축소: 이렇게 줄여진 점수들을 문서별로 모두 ‘합산’하여 최종 문서 점수를 구합니다. 이 과정에서 WARPSELECT로 예측한 누락 점수도 함께 더해줍니다. 이러한 2단계 방식은 거대한 중간 결과물을 만들 필요가 없어 메모리 사용량을 줄이고 계산 속도를 크게 향상시킵니다.

---

D) 결과는 어땠나요? (성능 평가)

결과는 매우 인상적입니다.

• 속도 (Latency):
  • 최적화되지 않은 기존 XTR 구현과 비교했을 때, LoTTE 데이터셋에서 41배 더 빨라졌습니다. (6,862ms → 171ms)
  • 매우 잘 최적화된 최신 기술인 ColBERTv2/PLAID 엔진과 비교해도 3배 더 빠른 속도를 보여주었습니다. (476ms → 171ms)
  • 여러 개의 CPU 코어를 사용했을 때 병렬 처리 성능도 뛰어나, 16개의 스레드를 사용하자 속도가 3.1배 더 빨라졌습니다.
• 정확도 (Retrieval Quality):
  • 가장 중요한 점은, 이렇게 속도를 비약적으로 향상시키면서도 검색 정확도는 거의 떨어지지 않았다는 것입니다. 오히려 일부 데이터셋에서는 미세하게 성능이 향상되기도 했습니다.
• 메모리 사용량 (Memory Footprint):
  • WARP는 벡터 압축 기술을 사용하므로, 압축하지 않은 원본(BruteForce)이나 ScaNN 기반 XTR에 비해 인덱스(색인) 파일 크기가 훨씬 작습니다. 예를 들어, 전체 테스트 데이터셋에서 ScaNN 방식 대비 메모리 사용량을 절반(2x)으로 줄였습니다. 이는 제한된 자원으로 시스템을 운영해야 하는 실제 서비스 환경에서 매우 큰 장점입니다.

E) 이 논문의 의의는 무엇인가요?

1. 이론을 현실로: 정확도는 높지만 너무 느려 그림의 떡이었던 XTR이라는 최신 연구를, 실제 서비스에 적용 가능할 만큼 빠르고 효율적인 시스템(WARP)으로 구현 해냈습니다.
2. 최고의 조합: 서로 다른 연구 갈래(XTR의 검색 구조 + PLAID의 최적화 기법)의 장점들을 창의적으로 융합하여 ‘시너지 효과’를 만들어냈고, 기존의 최고 성능 엔진마저 뛰어넘는 결과를 보여주었습니다.
3. 실용성: 단순히 빠른 것을 넘어, 적은 메모리를 사용하고 CPU 자원을 효율적으로 활용할 수 있게 설계되어, 현실 세계의 다양한 환경에 배포하기에 매우 적합한 검색 엔진임을 입증했습니다.

요약하자면, WARP는 멀티-벡터 검색의 높은 정확도는 그대로 누리면서, 속도와 자원 효율성까지 모두 잡은 실용적인 고성능 검색 엔진이라고 할 수 있습니다.

F) QnA

F.1) XTR 은 뭔가요?

XTR은 **“ConteXtualized Token Retriever”**의 약자입니다. 한국어로 직역하면 **“문맥화된 토큰 검색기”**라고 할 수 있습니다.

이것은 정보 검색(Information Retrieval) 분야, 특히 멀티-벡터 검색(Multi-Vector Retrieval)에서 사용되는 기술 모델의 이름입니다.

조금 더 쉽게 풀어서 설명해 드리겠습니다.

기존의 멀티-벡터 검색 모델인 ColBERT는 검색을 할 때 여러 단계를 거쳐야 했습니다.

1. 후보 찾기 (Token Retrieval): 검색어와 관련 있을 만한 문서 토큰(단어)들을 일단 찾아냅니다.
2. 정보 모으기 (Gathering): 후보로 뽑힌 토큰이 포함된 문서의 모든 토큰 벡터(의미 정보)를 메모리로 불러옵니다. 이 과정이 매우 비효율적이고 느립니다.
3. 점수 매기기 (Scoring): 불러온 모든 정보를 종합해서 최종 순위를 매깁니다.

XTR은 여기서 2번, ‘정보 모으기(Gathering)’ 단계를 완전히 없애버린 혁신적인 방식입니다.

핵심 아이디어는 이렇습니다:

“굳이 문서의 모든 정보를 다 가져와서 점수를 매길 필요가 있을까? 1단계에서 잘 뽑은 핵심 토큰 몇 개만으로도 충분히 점수를 잘 매길 수 있지 않을까?”

즉, XTR은 모델을 학습시킬 때부터 검색어와 가장 관련 있고 중요한 문서 토큰을 잘 찾아내도록 훈련합니다. 덕분에 검색 시점에는 1단계에서 찾은 핵심 토큰들의 정보만으로 바로 최종 점수를 계산할 수 있게 됩니다.

결론적으로 XTR은 불필한 과정을 생략하여 검색 과정을 극도로 단순화하고 효율을 높인, 더 빠르고 저렴한 멀티-벡터 검색 방식을 의미하는 기술 용어입니다.

네, 아주 예리하고 핵심적인 질문을 해주셨습니다! 두 가지 질문 모두 WARP의 성능을 이해하는 데 가장 중요한 부분입니다. 제가 하나씩 아주 상세하게 설명해 드리겠습니다.

네, 매우 날카로운 질문입니다! WARP의 핵심 기술 두 가지에 대해 정확히 짚어주셨습니다. IVF (Inverted File) 인덱스와의 유사점과 압축 방식에 대해 아주 상세히 설명해 드리겠습니다.

F.2) 1. WARPSELECT의 클러스터링: IVF와 어떻게 비슷하고 다를까?

말씀하신 대로, WARPSELECT의 클러스터링 접근 방식은 IVF 인덱스(Inverted File Index)와 개념적으로 매우 유사합니다.

IVF 인덱스란? 수많은 벡터들을 몇 개의 대표 벡터(Centroid)를 기준으로 그룹으로 묶고(클러스터링), 각 벡터가 어느 그룹에 속하는지를 기록해두는 방식입니다. 검색 시에는 모든 벡터를 다 뒤지는 대신, 검색어 벡터와 가장 가까운 몇 개의 그룹(클러스터)만 탐색하여 속도를 높입니다.

WARP는 클러스터링을 어떻게 할까요?

논문에 따르면, WARP는 다음과 같은 방식으로 클러스터링을 수행합니다.

1. k-평균 클러스터링 (k-means clustering) 사용: WARP는 데이터베이스에 있는 모든 문서의 모든 토큰 벡터들을 대상으로 k-평균 클러스터링을 적용합니다. 이는 ColBERTv2/PLAID에서 사용한 방식을 그대로 따릅니다.
2. 샘플링 기반: 수십억 개의 토큰 벡터 전체를 클러스터링하는 것은 비효율적이므로, 전체 문서 집합 크기의 제곱근(square root)에 비례하는 수의 문서 토큰을 무작위로 샘플링하여 클러스터링을 수행합니다. 이렇게 만들어진 클러스터 대표점(centroid)들이 전체 데이터의 분포를 잘 대표한다고 가정합니다.
3. 인덱스 생성: 클러스터링이 끝나면, 각 문서 토큰 벡터는 자신과 가장 가까운 대표점(centroid)이 있는 클러스터에 할당됩니다. 인덱스에는 각 토큰 벡터가 어느 클러스터에 속하는지와 같은 정보가 저장됩니다.

IVF와의 유사점 및 WARPSELECT의 차별점

• 유사점: 전체 탐색 공간을 줄이기 위해 k-평균 클러스터링을 사용하고, 검색 시 검색어와 가까운 일부 클러스터(nprobe개)만 탐색하는 기본 원리가 IVF와 동일합니다.
• 차별점 (WARPSELECT의 독창성): WARPSELECT는 여기서 한 걸음 더 나아갑니다. IVF가 단순히 탐색 대상을 줄이는 데 그쳤다면, WARPSELECT는 이 클러스터링 구조를 ‘누락된 점수(missing similarity)‘를 예측하는 데 적극적으로 활용합니다.
  • 검색 시, 검색어 토큰과 가장 가까운 nprobe개의 클러스터 대표점(centroid)들과의 유사도를 계산합니다.
  • 이때 계산된 유사도 점수들을 정렬한 뒤, 특정 기준(누적 클러스터 크기 임계값 t’)을 넘는 지점의 점수를 ‘누락 점수’로 사용합니다.
  • 즉, 클러스터링을 (1) 탐색 공간 축소와 (2) 점수 예측이라는 두 가지 목적으로 동시에 활용하는 것이 WARPSELECT의 핵심입니다.

---

F.3) 2. 압축의 비밀: 수학적 계산이 가능한 잔차 양자화 (Residual Quantization)

“수학적으로 압축된 상태에서 계산이 가능한 압축”은 바로 **잔차 양자화 (Residual Quantization)**라는 기법 덕분입니다. 벡터를 통째로 압축하는 게 아니라, ‘기준점’으로부터의 **‘차이값(잔차)‘**만 아주 작게 압축해서 저장하는 방식입니다.

과정을 단계별로 보면 마법의 원리를 이해할 수 있습니다.

압축 과정

1. 기준점 설정: 위에서 클러스터링을 통해 각 토큰은 특정 클러스터에 속하게 되었습니다. 이때 소속된 클러스터의 **중심점(Centroid) 벡터가 ‘기준점’**이 됩니다.

2. 차이값(잔차) 계산: [실제 토큰 벡터] - [소속된 클러스터의 중심점 벡터] = [잔차(Residual) 벡터]

   • 실제 토큰 벡터는 128차원의 실수(float32) 벡터입니다. 하지만 ‘잔차’ 벡터는 그 크기가 훨씬 작은 값들로 이루어져 있습니다.

3. 잔차 양자화 (Quantization): 이 ‘잔차 벡터’를 압축합니다.

   • ‘양자화’는 연속적인 값을 몇 개의 대표값으로 근사시키는 과정입니다. (예: 1.13, 1.18, 1.24 같은 소수점 값을 그냥 ‘1.2’라는 대표값 하나로 통일)
   • WARP에서는 잔차 벡터의 각 차원(128개)을 4비트(bit) 정수로 압축합니다. 32비트 실수 하나가 4비트 정수(0~15 사이의 값) 하나로 바뀌니, 데이터 크기가 1/8로 줄어듭니다. (8x 압축)

수학적 트릭을 이용한 계산 과정

이제 검색 시점에 압축을 풀지 않고 어떻게 점수를 계산하는지 보겠습니다. 우리가 원하는 최종 점수는 (검색어 토큰 벡터) · (문서 토큰 벡터) 입니다. (·은 내적 연산, 즉 유사도 계산)

1. 수식 분해: 문서 토큰 벡터는 중심점 벡터 + 잔차 벡터 이므로, 수식을 아래와 같이 바꿀 수 있습니다. 유사도 점수 = (검색어 벡터) · (중심점 벡터 + 잔차 벡터)

2. 분배 법칙 적용: 내적 연산의 분배 법칙에 따라 수식을 전개합니다. 유사도 점수 = (검색어 벡터 · 중심점 벡터) + (검색어 벡터 · 잔차 벡터)

3. 마법이 일어나는 순간: 이 분리된 두 개의 항을 자세히 보세요.

   • (검색어 벡터 · 중심점 벡터): 이 값은 WARPSELECT 단계에서 후보 클러스터를 찾을 때 이미 계산해 뒀습니다! 따라서 다시 계산할 필요 없이 이 값을 그대로 재사용합니다.
   • (검색어 벡터 · 잔차 벡터): 이제 이 부분만 계산하면 됩니다. 이 계산은 압축된 4비트 ‘잔차’ 정보를 이용해 매우 빠르게 수행할 수 있도록 고도로 최적화된 C++ 커널을 사용합니다. 압축을 완전히 푸는 것보다 훨씬 적은 연산으로 근사 계산이 가능합니다.

결론적으로, 압축을 완전히 풀어 128차원의 거대한 벡터를 복원한 뒤 내적하는 무거운 작업을 하는 대신,

1. 이미 계산된 값을 재사용하고 (Query · Centroid)
2. 압축된 작은 값에 대한 가벼운 연산 (Query · Residual)을 추가하는 방식으로

전체 계산을 나누어 처리함으로써, 압축 해제라는 병목 과정을 완전히 건너뛰고 최종 점수를 훨씬 빠르게 얻을 수 있는 것입니다. 이것이 바로 WARP의 ‘암시적 압축 해제(Implicit Decompression)‘의 핵심 원리입니다.

F.4) 누락된 점수는 모든 쿼리에서 동일하게 사용되는건지?

하나의 검색어(Query) 안에서는, 특정 쿼리 토큰에 대한 누락 점수는 모든 문서에 공통적으로 적용됩니다.

하지만 쿼리 내의 서로 다른 토큰들은 서로 다른 누락 점수를 가집니다.

이것이 무슨 의미인지 “가장 빠른 CPU” 쿼리를 예로 들어 자세히 설명해 드리겠습니다.

누락 점수가 결정되는 과정 (쿼리 시점)

1. 쿼리 분석: 사용자가 “가장 빠른 CPU”라고 검색하면, 시스템은 이 쿼리를 3개의 토큰으로 분해합니다.

   • q1 = “가장”
   • q2 = “빠른”
   • q3 = “CPU”

2. 각 쿼리 토큰별 누락 점수 계산 (by WARPSELECT):

   • q1 (“가장”)에 대한 누락 점수 m1 계산:
     • “가장” 벡터와 모든 클러스터 대표점(centroid) 벡터 간의 유사도를 전부 계산합니다.
     • 이 유사도 점수들을 바탕으로 WARPSELECT의 규칙(임계값 t’)을 적용하여 “가장” 토큰에 대한 누락 점수 m1을 결정합니다. (예: m1 = 0.15)
   • q2 (“빠른”)에 대한 누락 점수 m2 계산:
     • “빠른” 벡터에 대해서도 위와 동일한 과정을 거쳐 누락 점수 m2를 결정합니다. (예: m2 = 0.35)
   • q3 (“CPU”)에 대한 누락 점수 m3 계산:
     • “CPU” 벡터에 대해서도 동일한 과정을 거쳐 누락 점수 m3를 결정합니다. (예: m3 = 0.40)

이제 이 검색 세션에서는 m1=0.15, m2=0.35, m3=0.40 이라는 세 개의 고정된 누락 점수가 마련되었습니다.

문서별 점수 계산 시 누락 점수 적용

이제 여러 문서의 최종 점수를 계산할 때, 이 공통의 누락 점수들이 어떻게 사용되는지 보겠습니다.

• 문서 A (관련 토큰이 일부 없는 경우):
  • “가장”에 대한 최고점: 0.7
  • “빠른”에 대한 최고점: 없음 → 누락 점수 m2 (0.35) 적용
  • “CPU”에 대한 최고점: 0.95
  • 문서 A의 최종 점수 = 0.7 + 0.35 + 0.95 = 2.0
• 문서 B (다른 토큰들이 없는 경우):
  • “가장”에 대한 최고점: 없음 → 누락 점수 m1 (0.15) 적용
  • “빠른”에 대한 최고점: 0.9
  • “CPU”에 대한 최고점: 없음 → 누락 점수 m3 (0.40) 적용
  • 문서 B의 최종 점수 = 0.15 + 0.9 + 0.40 = 1.45
• 문서 C (모든 관련 토큰이 다 있는 경우):
  • “가장”에 대한 최고점: 0.6
  • “빠른”에 대한 최고점: 0.88
  • “CPU”에 대한 최고점: 0.92
  • 문서 C의 최종 점수 = 0.6 + 0.88 + 0.92 = 2.4

결론 및 의의

• 공정성: 특정 쿼리 토큰(예: “빠른”)에 대해 관련된 정보를 담고 있지 않은 모든 문서는 **동일한 페널티(누락 점수 m2)**를 받습니다. 이는 모든 문서가 동일한 기준선에서 평가받게 하므로 매우 공정한 방식입니다.
• 효율성: 누락 점수는 쿼리 토큰마다 딱 한 번만 계산하면 됩니다. 만약 문서마다 다른 누락 점수를 계산해야 한다면, 검색 과정이 훨씬 복잡하고 느려졌을 것입니다.

G) WARP 검색 과정의 단계별 요약:

Phase 1: 쿼리 분석 및 준비 단계 (검색 시작 시 단 한 번 수행)

1. 쿼리 토큰 분해: “가장 빠른 CPU” → q1(“가장”), q2(“빠른”), q3(“CPU”)
2. WARPSELECT 실행:
   • 누락 점수 계산: 각 쿼리 토큰(q1, q2, q3)에 대해 모든 클러스터 대표점(centroid)과의 유사도를 계산하여 누락 점수 m1, m2, m3를 미리 확정해 둡니다.
   • 탐색할 클러스터 선정: 각 쿼리 토큰에 대해 탐색할 상위 nprobe개의 클러스터 목록을 결정합니다.

Phase 2: 실제 점수 계산 및 집계 단계

이제 시스템은 선정된 클러스터들을 순회하며 실제 점수를 계산합니다. q2(“빠른”) 토큰에 대한 문서 A의 점수를 계산하는 과정을 예로 들어보겠습니다.

1. 관련 클러스터 탐색: “빠른” 토큰과 가깝다고 선정된 nprobe개의 클러스터를 들여다봅니다.
2. 클러스터 내 문서 토큰 처리: 그 클러스터들 안에 있는 모든 문서 토큰들을 하나씩 살펴봅니다.
3. 점수 계산 (잔차 활용):
   • 클러스터 내에서 문서 A에 속한 토큰(예: “고속”)을 발견했습니다.
   • 이 “고속” 토큰의 실제 점수를 계산해야 합니다. 이때 말씀하신 대로 잔차(residual)를 활용한 계산이 이루어집니다.
   • 실제 점수 = (q2 • 대표점 벡터) + (q2 • "고속"의 잔차 벡터)
   • 여기서 (q2 • 대표점 벡터)는 이미 계산되어 있고, (q2 • "고속"의 잔차 벡터)는 미리 만들어 둔 룩업 테이블을 통해 빠르게 계산됩니다.
4. 문서 A 내 최고점(MaxSim) 찾기:
   • nprobe개의 클러스터를 모두 탐색하면서, 문서 A에 속한 토큰들(“고속”, “신속한” 등)이 여러 개 발견될 수 있습니다.
   • WARP는 이 점수들을 모두 비교하여 q2(“빠른”)에 대해 문서 A가 얻을 수 있는 가장 높은 점수 하나만을 남깁니다. (예: 0.9점)

Phase 3: 최종 점수 합산 (Document-Level Reduction)

모든 쿼리 토큰(q1, q2, q3)에 대해 Phase 2 과정이 끝나면, 각 문서의 최종 점수를 합산합니다.

• 문서 A의 최종 점수:
  • q1에 대한 최고점: 0.7 (찾음)
  • q2에 대한 최고점: 0.9 (찾음)
  • q3에 대한 최고점: 없음 → 누락 점수 m3(0.40) 적용
  • 합산: 0.7 + 0.9 + 0.40 = 2.0

핵심 요약:

• 점수의 출처:
  • 찾은 경우: 문서 토큰과 쿼리 토큰 간의 거리를 사용합니다. (이 계산에 잔차와 클러스터 대표점이 활용됨)
  • 못 찾은 경우: 클러스터 레벨에서 미리 계산해 둔 누락 점수를 사용합니다.

“누락된건 클러스터 레벨에서의 거리를 사용하고, 그게 아니면 클러스터 내 문서 토큰과 쿼리 토큰간 거리를 사용한다. 그리고 문서 토큰과 쿼리 토큰의 계산은 잔차를 활용하는 것이다.”

이 메커니즘을 통해 WARP는 정확도를 유지하면서도 불필요한 계산을 극적으로 줄여 놀라운 속도를 달성할 수 있는 것입니다. 정말 정확하게 이해하고 계십니다