벡터 삽입 후 HNSW 검색 재현율은 어떻게 달라질까? (1만+1만)

후속 글 100만+100만 벡터 실험에서는 규모를 늘리고 세그먼트 기록과 코드로 삽입 후 거동을 살펴봤습니다.

벡터 검색 서비스를 운영하다 보면 기존 인덱스에 문서가 계속 추가됩니다. 새 문서가 검색된다는 사실은 확인하기 쉽습니다. 하지만 인덱스를 처음부터 다시 만들었을 때와 비교해 검색 품질이 달라졌는지는 알기 어렵습니다. 특히 같은 주제의 문서가 한꺼번에 들어오면 삽입 순서가 HNSW 그래프에 영향을 줄 수도 있습니다.

이를 확인하기 위해 pgvector와 Qdrant에서 작은 실험을 했습니다. 공개 임베딩 1만 개로 인덱스를 만든 뒤 신규 벡터 1만 개를 추가하고, 같은 최종 2만 개로 새로 구축한 인덱스와 비교했습니다. 신규 벡터는 전체를 섞거나 군집별로 묶었고, 각각 한 번 또는 다섯 번의 논리적 배치로 넣었습니다.

같은 200개 질의의 Recall@100은 삽입 전보다 삽입 후에 48개 이력 모두 낮았습니다. 다만 데이터가 늘면서 정답 이웃도 달라졌으므로, 하락분 전체를 인덱스 열화로 볼 수는 없습니다. 같은 최종 데이터로 별도 구축한 fresh 인덱스와 비교하면 증분 이력의 차이는 −0.0822~+0.1128%p 범위였습니다.

§1데이터가 늘어난 효과와 삽입 이력을 나누기

HNSW는 벡터 사이의 연결을 따라 후보를 찾는 근사 최근접 이웃 인덱스입니다. 정확 검색보다 빠르게 답할 수 있지만, 실제로 가장 가까운 이웃을 모두 찾는다는 보장은 없습니다. Recall@100은 정확 검색의 상위 100개 이웃 중 검색 결과에 포함된 비율입니다.

삽입 전후의 Recall만 비교하면 해석이 어렵습니다. 데이터가 1만 개에서 2만 개로 늘면 검색 대상과 정답 이웃도 달라지기 때문입니다. 인덱스가 바뀐 탓인지, 데이터 자체가 달라져 검색이 어려워진 탓인지 한 숫자로는 분리할 수 없습니다.

그래서 각 상태의 실제 벡터로 정확한 정답을 계산하고, 같은 최종 데이터로 별도 DB에서 새로 구축한 인덱스를 대조군으로 뒀습니다. 최종 상태의 fresh 구축은 세 번 수행해 질의별 재현율을 평균했습니다. 이것은 기존 DB에 삽입한 뒤 그 자리에서 재구축한 총비용을 측정한 것은 아닙니다. 증분 인덱스의 Recall에서 이 평균을 빼면, 같은 데이터와 질의에 대해 두 인덱스가 보인 차이를 볼 수 있습니다.

인덱스 이력에 따른 차이 = 증분 인덱스의 Recall − 재구축 인덱스의 평균 Recall

양수면 해당 증분 인덱스가 재구축 평균보다 높고, 음수면 낮습니다. 재구축할 때마다 결과도 달라질 수 있으므로, 이 차이만으로 그래프 구조가 왜 달라졌는지는 알 수 없습니다.

§2fresh 구축과 네 가지 삽입 경로

데이터는 MS MARCO Web Search의 SimANS 임베딩과 Wikipedia–Cohere의 공개 임베딩을 사용했습니다. 모두 768차원이며 검색은 원본 벡터의 내적을 기준으로 했습니다. 각 데이터셋에서 세 시드로 문서 2만 개를 뽑아 초기 1만 개와 신규 1만 개로 나눴습니다. 시드 간 문서 표본은 일부 겹치고 평가 질의도 공유합니다.

신규 벡터는 두 가지 순서를 만들었습니다. 하나는 전체를 무작위로 섞은 순서이고, 다른 하나는 신규 벡터를 다섯 군집으로 나눈 뒤 같은 군집을 연속으로 넣는 순서입니다. 군집화에는 벡터를 정규화한 복사본과 spherical k-means를 사용했으며, 검색에 들어가는 원본 벡터는 바꾸지 않았습니다. 따라서 군집은 벡터의 방향을 기준으로 만들어졌고, 검색 자체는 원본 내적을 사용합니다.

M5의 각 배치 크기는 C5와 맞췄습니다. 같은 시드와 DB의 네 경로는 동일한 초기 인덱스 스냅샷에서 출발해 동일한 최종 데이터에 도달합니다. 군집 내부는 거리순으로 정렬하지 않고 무작위로 섞었습니다.

여기서 배치는 API 요청 한 번을 뜻하지 않습니다. 실제 전송은 최대 1,000벡터씩 나눴습니다. 논리적 배치 수가 바뀌면 커밋과 인덱싱 대기, 중간 측정도 달라집니다. Qdrant는 요청 사이에도 백그라운드 최적화를 할 수 있습니다.

그림 1. 네 경로는 같은 초기 인덱스에서 시작하고 같은 최종 데이터에 도달합니다. 색은 예시 군집이며, 실제 군집 크기는 서로 다릅니다.

§3삽입 전후에는 얼마나 달라졌을까?

초기 1만 벡터와 최종 2만 벡터에서 같은 200개 질의를 사용해 Recall@100을 비교했습니다. 정답 이웃은 각 시점의 현재 데이터에서 따로 계산했습니다. 최종 값에서 초기 값을 빼면 48개 이력 모두 음수였고, 범위는 −0.8450~−0.0700%p였습니다.

그림 2. 각 점은 한 삽입 경로·시드에서 최종 Recall@100과 초기 Recall@100의 차이입니다. 파란색은 혼합 순서(M), 갈색은 군집 순서(C)입니다. 가로축의 −0.8은 −0.8%p, 즉 0.8%p 감소를 뜻합니다. 같은 200개 질의를 사용하지만, 정답 이웃은 각 시점의 데이터에서 계산했습니다. 신뢰구간은 표시하지 않았습니다.

데이터가 두 배로 늘면 더 가까운 이웃이 추가되고 검색 난도도 달라질 수 있습니다. 따라서 이 하락은 실제 전후 변화이지만, 전부가 HNSW 그래프의 열화라고 결론 내릴 수는 없습니다. 이를 살펴보기 위해 최종 데이터를 고정하고 비교했습니다.

§4같은 최종 데이터에서 fresh·1회·5회 비교

최종 2만 벡터에서 같은 600개 질의를 사용했습니다. F는 최종 데이터를 별도 DB에서 fresh 구축한 세 인덱스의 평균입니다. 표는 각 경로의 Recall@100에서 F를 뺀 값이며, 데이터·DB별 세 시드의 범위입니다. 음수는 증분 인덱스가 F보다 낮다는 뜻입니다. 단위는 %p입니다.

그림 3. 파란색은 혼합 순서(M), 갈색은 군집 순서(C)입니다. 점은 각 경로와 시드의 증분−F 차이이며, 가로선은 질의 쌍을 사용한 설명용 95% 부트스트랩 구간입니다. 구축 변동을 모두 포함하거나 다중 비교를 보정한 구간은 아닙니다.

전체 48개 증분 이력의 fresh 대비 점 추정치는 −0.0822~+0.1128%p였습니다. 이는 여러 조건의 범위이지 하나의 신뢰구간이 아닙니다. 설명용 95% 구간 48개 중 9개는 양수만 포함하고 39개는 0을 포함했습니다. 이 결과를 제품 전반의 우위로 일반화할 수는 없습니다.

같은 순서에서 5회−1회를 비교한 24개 설명용 95% 구간은 모두 0을 포함했습니다. 원래 사전 지정한 주 비교는 이와 별도로 C5−M5와 순서·분할의 상호작용 24개이며, 다중 비교 보정 구간이 모두 0을 포함했습니다. 이 구간들은 완성된 인덱스를 고정한 채 질의를 다시 뽑아 계산했습니다. 어느 쪽도 경로의 동등성이나 작은 배치의 우위를 입증하지는 않습니다.

삽입 전후 비교는 200개, 최종 fresh 비교는 600개 질의를 사용합니다. 두 수치는 서로 다른 질문에 답하므로 표의 차이를 직접 빼서 인덱스 열화량을 계산하지 않습니다.

§5최종 인덱스에서 ef별로 비교한 결과

본 실험 전에 별도의 보정용 문서와 질의로 HNSW 구축 설정과 검색 ef를 선택했습니다. 다섯 보정 상태에서 Recall@10과 Recall@100이 모두 99% 이상인 후보 중 지연시간·구축 및 쓰기 비용·메모리를 고려했습니다. 평가 결과를 보고 설정을 다시 고르지는 않았습니다.

선택된 검색 ef는 MS MARCO/pgvector 1000, Wikipedia–Cohere/pgvector 512, Qdrant는 두 데이터셋 모두 256이었습니다. 보정 조건을 통과해도 다른 평가 질의에서 같은 재현율이 보장되지는 않습니다. 실제로 MS MARCO/Qdrant의 C5 결과 두 시드는 99% 미만이었습니다.

최종 C5 인덱스를 그대로 두고 ef=100과 128에서도 검색했습니다. MS MARCO의 결과는 다음과 같습니다. 각 값은 세 시드의 최종 600개 평가 질의에서 측정한 범위입니다.

그림 4. 각 점은 ef=100, 128과 해당 조합의 운영 ef에서 측정한 결과입니다. 선은 점을 연결한 것으로 중간 ef를 측정했다는 뜻은 아닙니다.

측정한 같은 숫자의 ef=100·128에서는 Qdrant의 Recall이 더 높았습니다. 다만 pgvector는 M=16, ef_construction=100, Qdrant는 M=48, ef_construction=300을 사용했고, 같은 ef 값이 두 구현의 동일한 탐색 비용을 뜻하지도 않습니다. 따라서 이 표로 제품의 속도나 효율을 비교할 수는 없습니다.

추가 ef 측정은 최종 상태에서만 수행했습니다. 초기 상태의 같은 ef 결과가 없으므로, 이 표만으로 Qdrant의 삽입 전후 하락폭이 pgvector보다 컸던 원인을 설명할 수 없습니다.

§6실제로 HNSW를 검색했는가

높은 Recall이 순차 검색이나 정확 검색에서 나왔다면 인덱스 이력 비교가 성립하지 않습니다. PostgreSQL에서는 초기 대량 적재에 COPY를 사용하고 인덱스를 만든 뒤 신규 행을 추가했습니다. 검색 세션에서 enable_seqscan=off를 설정했으며, 각 질의의 실행 계획에서 지정한 HNSW 인덱스를 확인했습니다. 대표 질의는 EXPLAIN ANALYZE로 실제 실행도 확인했습니다.

Qdrant에서는 신규 ID를 최대 1,000개씩 전송했습니다. 쓰기 요청의 성공과 인덱싱 완료를 구분해, 각 측정 전에 데이터와 인덱싱 상태를 확인했습니다. 시간 측정 구간의 검색 전후 telemetry에서는 HNSW 검색 수가 증가하고 plain·exact 검색 수는 증가하지 않았는지 확인했습니다.

이 검증은 이번 평가 검색에 대한 것입니다. Qdrant의 백그라운드 최적화나 각 제품의 모든 운영 조건을 통제했다는 뜻은 아닙니다. 측정은 공유 로컬 호스트에서 DB별 CPU 2개와 메모리 4GiB 한도로 순차 실행했습니다.

§7더 큰 인덱스에서는?

대규모 갱신을 다룬 연구에서는 다른 결과도 나옵니다. Azure Cosmos DB의 DiskANN 논문^[1]은 1,000만 벡터 데이터에서 군집별 삽입과 삭제를 반복했습니다. 삭제 주변의 연결을 복구하는 방식은 단순 삭제보다 해당 군집 워크로드에서 Recall이 최대 20%p 높았습니다. 이는 두 삭제 정책의 차이이며 삽입만의 전후 감소폭은 아닙니다.

IP-DiskANN 연구^[2]는 3,000만 벡터 군집 워크로드에서 HNSW와 DiskANN 계열 알고리즘을 비교하고, 일부 시점에는 같은 활성 데이터로 재구축한 인덱스도 측정했습니다. 이 연구의 알고리즘 결과를 pgvector나 Qdrant의 제품 결과로 옮길 수는 없지만, 규모와 갱신 유형을 확장해 볼 이유는 충분합니다.

fresh는 최종 데이터를 별도 DB에 넣어 새로 구축한 대조군입니다. 기존 DB에서 삽입 후 재구축하는 총 시간과 비용은 측정하지 않았습니다.

이번 실험이 다룬 것은 신규 ID 삽입입니다. 삭제, 삭제와 삽입의 반복, 기존 ID의 벡터 교체는 측정하지 않았습니다. 필터 선택도와 카디널리티, 더 큰 데이터 및 장기간 갱신도 후속 과제로 남았습니다. 리소스가 확보되면 같은 최종 데이터의 재구축 대조를 유지한 채 이 조건들을 시험할 계획입니다.

전체 기술보고서와 실험 결과^[3]에는 설정, 전체 표, 통계 구간과 원시 집계 링크를 정리했습니다.