SIGIR25' - IGP, Efficient Multi-Vector Retrieval via Proximity Graph Index
IGP: Efficient Multi-Vector Retrieval via Proximity Graph Index
1. 문제 정의
기존의 PLAID나 DESSERT 논문에서 제시한 방법들은 다수의 1차 후보군을 얻은 다음에 이를 가지고 Rerank를 해서 정확도를 높이는 방법을 채택한다. 이 과정에서 1차 후보군을 다수 얻는게 성능상 가장 큰 병목이라고 지적한다.
2. IGP 디자인
해당 논문에서는 ColBERTv2 방식의 IVF에서 Centroid들을 가지고 그래프를 만들어서 점진적 탐욕법(Incremental Greedy Probe, IGP)을 사용한 방식을 제시한다. 세부적인 방식은 아래와 같다.
2.1. Index build
기본적인 Indexing 방식은 ColBERTv2에서 크게 달라지지 않았다고 생각하면 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
[1] 문서 encoding
ColBERTv2 encoder로 token-level embeddings 생성
[2] Centroid selection
sample token embeddings에 대해 k-means 수행
centroid set C 생성
[3] Vector quantization
각 token embedding v를 nearest centroid C_t에 할당
centroid ID 저장
[4] Residual compression
residual r = v - C_t 계산
residual을 1-bit 또는 2-bit로 scalar quantization
centroid ID + quantized residual 저장
[5] Inverted list 생성
centroid → Document vector IDs
[6] Inverted list의 Centroid들로 ip-NSW 그래프 구성
4번까지는 동일하나 5번부터는 약간 다르다. PLAID의 경우 Centroid에 Document ID를 저장했으나 IGP의 경우 Document Vector ID가 달려있다.
Centroid들을 가지고 ip-NSW 그래프를 구성한다고 되어있는데, 이는 HNSW의 가장 아래층에 있는 그래프라고 생각하면 된다.
모든 점이 있으며 서로 거리가 가까운 점에 대해서 Edge로 연결되어 이동가능한 그래프이다.
2.2. Search
IGP 논문에서 말하는 검색의 전체적인 구조를 크게 나누자면 아래와 같다.
1
2
3
4
5
6
7
[1] 후보군 생성
graph + IVF + next-similar fetch로 후보 문서 생성
[2] 후보군 정제
후보 문서의 전체 vector를 SQ로 복원
full MaxSim 계산
top-k 반환
2.2.1. 후보군 생성
먼저 검색 Query가 들어오면 Multi-vector로 만든다.
각 쿼리를 이루는 다수의 벡터가 있고 각 벡터를 q라고 할 때 q에 대해서 그래프 탐색을 하며 후보군을 선정한다.
입력값과 변수는 아래와 같다.
1
2
3
4
5
6
7
Input:
Query Q = {q1, q2, ..., qn} // 쿼리 Vector 집합
result size k // 상위 몇 개의 문서를 반환할 것인지
Parameters:
φcand = query vector당 GetNext 호출 횟수
φref = refinement할 candidate document 수
절차는 아래와 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
1. 각 query vector q에 대해 NFq.Init() 수행
2. hash table Ψ 생성
key = document ID
value = score, isSeen[q]
3. rank = 1 ... φcand 반복:
for each q ∈ Q:
v = NFq.GetNext()
id = document ID containing v
if id가 Ψ에 없으면:
Ψ[id].score = 0
Ψ[id].isSeen[q] = false for all q
if Ψ[id].isSeen[q] == false:
Ψ[id].isSeen[q] = true
Ψ[id].score += <q, v>
4. Ψ에서 score가 높은 top-φref document ID 선택
5. 각 candidate document ID를 반환
NFq.Init()는 각 q가 사용해야하는 변수에 대한 초기화 이다.
아래와 같은 변수를 사용한다.
1
2
3
4
Svis = visited centroid set
Sout = out-neighbor를 이미 확장한 centroid set
Srtn = 이미 반환한 centroid set
Leval = 반환 대기 중인 document vector queue
위 변수들을 아래와 같이 초기화한다.
1
2
3
4
Svis = {(G.vent, <G.vent, q>)}
Sout = ∅
Srtn = ∅
Leval = ∅
NFq.GetNext()이 함수는 간단히 말해서 q에 대해 반환하지 않은 document vector중에 <q,v>에 대해서 내적이 가장 큰 다음 vector를 반환하는 함수라고 생각하면 되며, 이러한 GetNext 함수는 아래와 같은 알고리즘으로 구동된다.
1
2
3
4
5
6
7
8
9
function GetNext():
if Leval is empty:
CR = GetNextCentroid(nb)
for c in CR sorted by <q, c> descending:
for v in IVF(c):
Leval.enqueue(v)
return Leval.dequeue()
Leval에 반환할 vector가 있으면 하나 꺼내고, 비어 있으면 graph에서 새로운 centroid들을 가져온 뒤 그 centroid들의 IVF list를 queue에 넣는다. Algorithm 2에서도 Leval이 비어 있을 때 GetNextCentroid(nb)를 호출하고, 반환된 centroid c에 대해 IVF(c)의 vector들을 Leval에 enqueue한 뒤 하나를 dequeue한다.
여기서 GetNextCentroid는 query vector q에 대해 아직 반환하지 않은 centroid 중 inner product가 큰 centroid를 graph traversal로 찾는 함수이다. GetNextCentroid 함수는 아래와 같은 알고리즘으로 구동된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
while A is not empty:
vbest = A에서 score가 가장 높은 centroid
vfnd = Sfnd에서 score가 가장 낮은 centroid
if <vbest, q> < <vfnd, q>:
break
vbest의 neighbor들을 graph에서 확인
아직 방문하지 않은 neighbor vadj에 대해:
score = <vadj, q>
Svis에 추가
score가 충분히 좋으면 A와 Sfnd에 추가
Sfnd는 항상 top(nb + bs)만 유지
R = Sfnd.Top(nb)
Srtn = Srtn ∪ R
return R
여기서 각 변수에 대한 설명은 아래와 같다.
1
2
3
4
nb // 한번에 반환할 cetorid 수 (시스템 변수)
bs // graph search buffer size (시스템 변수)
A = Svis - Sout // 방문은 했지만 아직 neighbor 확장을 하지 않은 후보 centroid
Sfnd = (Svis - Srtn).Top(nb + bs) // 방문은 했지만 아직 반환하지 않은 centroid 중, 현재까지 좋은 nb + bs개 후보
2.2.2. 후보군 정제
2.2.1에서 얻은 후보 문서들의 Vector를 모두 잔차 복구하고 Query에 대해서 Maxsim Score를 구하여 ReranK 한 뒤에 Top-k 만큼 반환한다.
3. 제한
해당 논문은 CPU를 대상으로 구현된 것이다. 때문에 비교대상도 PLAID-CPU 버전이다.
때문에 이러한 한계를 지적하여 해당 논문의 GPU 확장형인 GIGP+ 논문이 등장했다.
※ 추가 업데이트 예정이다.
참고문헌
- Bian, Zheng, Man Lung, Yiu, and Bo, Tang. “IGP: Efficient Multi-Vector Retrieval via Proximity Graph Index.” . In Proceedings of the 48th International ACM SIGIR Conference on Research and Development in Information Retrieval (pp. 2524–2533). Association for Computing Machinery, 2025.