SIGIR25' - IGP, Efficient Multi-Vector Retrieval via Proximity Graph Index
IGP: Efficient Multi-Vector Retrieval via Proximity Graph Index
※ 본 논문을 읽기 전에 PLAID 논문을 읽고 오는게 좋다.
1. 문제 정의
기존의 PLAID나 DESSERT 논문에서 제시한 방법들은 다수의 1차 후보군을 얻은 다음에 이를 가지고 Rerank를 해서 정확도를 높이는 방법을 채택한다. 이 과정에서 1차 후보군을 다수 얻는데 이렇게 많은 1차 후보군을 뽑아내는 것 자체가 시간이 많이 걸리며 그렇다고 1차 후보군을 적게 뽑으면 Recall이 떨어지기 때문에 정확도를 위해 많은 후보군을 뽑을 수 밖에 없는 구조가 성능상 가장 큰 병목이라고 지적한다.
때문에 IGP에서는 기존의 방식보다 정답에 가까운 후보군을 좀 더 적게 뽑는 방식을 제시하였다.
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로 연결되어 이동가능한 그래프이다. 모든 점을 가지고 ip-NSW를 만든게 아니기 때문에 그래프 구축시간이 매우 짧으며 구축 파라미터로는 탐색 빔 너비(efConstruction=200)와 이웃 노드 수(M=64)를 사용한다고 되어있다.
※ ip-NSW 구축법
IVF를 구성하는 Centroid 들을 대상으로 ip-NSW를 구성하는데 절차는 아래와 같다.
1. entry vertex 선택
그래프 생성시 가장 먼저 사용되는 Centroid를 선택한다. 이 Centroid는 그래프 탐색시 가장 먼저 시작하는 Centroid가 될 수 있다(혹은 Random 선택해서 시작 Cetroid로 고정하거나)
2. centroid를 하나씩 삽입
Entry vertex가 Graph에 들어간 뒤 Centroid를 그래프에 하나씩 넣는다.
이미 graph에 들어간 centroid들을 대상으로, 새 centroid x와 inner product가 높은 후보 neighbor를 찾는다.
3. build-time graph search로 neighbor 후보 탐색
새 centroid x를 삽입할 때, 기존 graph에서 x와 가까운 centroid 후보를 찾아야 하는데 이를 위해서 entry vertex부터 BFS로 탐색한다.
탐색간 아래의 알고리즘대로 행동한다.
1
2
3
4
5
6
7
8
1. entry vertex에서 시작
2. entry와 x의 inner product 계산
3. 현재까지 발견한 후보 중 score가 가장 높은 vertex를 확장
4. 그 vertex의 neighbor들을 방문
5. x와 neighbor들의 inner product 계산
6. 좋은 후보를 priority queue에 유지
7. efConstruction개 정도의 후보를 유지하면서 탐색
8. 최종적으로 x와 가까운 후보 centroid set 반환
여기서 efConstruction 값은 IGP의 경우 200을 사용한 것이다.
4. top-M neighbor 선택
SearchGraph로 얻은 후보들 중에서 x와 inner product가 가장 높은 M개를 선택한다.
IGP에서 사용하는 방식은 이 M값이 64개인것이다.
5. edge 연결
선택된 M개의 노드와 edge를 연결한다. 구현체에 따라서는 양방향으로 이동가능하게 연결 할 수 있다.
6. 기존 vertex의 neighbor list pruning
만약 반대 통로도 추가하는 양방향 구현이라면, 기존 vertex n의 neighbor 수가 M을 초과할 수 있는데, 이 경우 n의 neighbor list에서 n과 inner product가 높은 상위 M개만 남긴다.
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개 후보
알고리즘을 읽어보면 알겠지만 GetNextCentroid() 함수를 호출시 그래프 진입점부터 체크하는게 아니라, A라는 이전에 방문을 했던 지점부터 다시 탐색을 한다. 이러한 방식은 중복된 거리 계산과 노드 방문을 획기적으로 줄인다고 논문에서 말하고 있다.
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.