관련 포스트근사 최근접 이웃 벡터 데이터베이스 양자화 임베딩

곱 양자화(Product Quantization)

•

2026년 11월 15일 발행•2026년 11월 15일 수정

요약

벡터를 부분 벡터로 나눠 부분공간별 코드북으로 압축하고 압축 상태에서 거리를 근사하는 벡터 양자화 기법

중급

k-평균 군집화와 벡터 거리 척도를 이해하고, 근사 최근접 이웃 색인의 재현율·메모리·지연 절충을 판단할 수 있어야 한다.

태그

근사 최근접 이웃 벡터 데이터베이스 양자화 임베딩

#개념

곱 양자화(Product Quantization, PQ)는 고차원 벡터를 여러 개의 저차원 부분 벡터로 나누고, 각 부분 벡터를 독립적으로 양자화해 짧은 코드로 압축하는 벡터 압축 기법이다. Jégou, Douze, Schmid(2011)가 근사 최근접 이웃 탐색을 위해 제안했으며, 압축된 코드 상태에서 거리를 빠르게 근사할 수 있어 대규모 벡터 검색의 기본 구성 요소가 되었다.

수억 개의 임베딩을 원본 그대로 메모리에 올리면 저장 비용이 매우 크다. 예를 들어 128차원 32비트 실수 벡터 하나는 512바이트를 차지하므로 10억 개면 약 512GB가 필요하다. 하나의 코드북으로 전체 공간을 양자화하는 벡터 양자화(Vector Quantization)로 64비트 코드를 만들려면 $2^{64}$개의 중심점이 필요해 학습도 저장도 불가능하다. 곱 양자화는 공간을 부분공간의 데카르트 곱으로 분해해 이 문제를 푼다.

$D$차원 벡터 $x$를 길이 $D^ = D/m$인 부분 벡터 $m$개로 나누고, 부분공간마다 k-평균 군집화(K-Means Clustering)로 $k^$개의 중심점을 가진 코드북을 따로 학습한다. 각 부분 벡터는 가장 가까운 중심점의 번호로 대체되므로, 벡터 하나는 $m$개의 정수 번호로 표현된다. 전체적으로는 $(k^)^m$개의 중심점을 표현할 수 있지만 실제로 저장하는 중심점은 $m \times k^$개뿐이다.

곱 양자화의 구성 요소와 설정값은 다음과 같다.

곱 양자화의 구성 요소

부분 양자화기 수($m$): 벡터를 몇 조각으로 나눌지 정하며, 차원 $D$는 $m$의 배수가 되도록 맞춘다.
*부분 코드북 크기($k^$): 부분공간별 중심점 수로, 1바이트로 표현되는 256이 가장 흔히 쓰인다.
코드 길이*: $m \log_2 k^$비트이며, $m=8$, $k^=256$이면 64비트(8바이트) 코드가 된다.
코드북 학습 데이터: 색인할 데이터와 분포가 비슷한 표본으로 부분공간별 k-평균을 학습한다.

압축률은 원본 크기를 코드 길이로 나누어 계산한다. 128차원 32비트 실수 벡터(512바이트)를 $m=8$, $k^=256$으로 압축하면 8바이트가 되어 64배 줄어든다. 같은 비트 예산이라면 부분 양자화기를 많이 쓰고 코드북을 작게 하기보다, 부분 양자화기 수를 줄이고 코드북을 크게 하는 편이 일반적으로 정확도가 높다고 원 논문은 보고했다.

곱 양자화의 핵심 장점은 벡터를 복원하지 않고도 거리를 근사할 수 있다는 점이다. 질의를 어떻게 다루는지에 따라 두 가지 거리 계산 방식이 있으며, 원 논문은 정확도가 더 높은 비대칭 방식을 권장한다.

거리 계산 방식

대칭 거리 계산(Symmetric Distance Computation, SDC): 질의도 양자화한 뒤, 미리 계산한 중심점 간 거리표로 거리를 구한다. 질의 쪽 양자화 오차까지 더해져 정확도가 낮다.
비대칭 거리 계산(Asymmetric Distance Computation, ADC): 질의는 원본 그대로 두고 데이터베이스 벡터만 코드로 표현한다. 오차가 데이터베이스 쪽 양자화에서만 생기므로 SDC보다 정확하다.

ADC는 질의가 들어오면 먼저 룩업 테이블(Lookup Table)을 만든다. 각 부분공간에서 질의 부분 벡터와 $k^$개 중심점 사이의 거리를 미리 계산해 $m \times k^$ 크기의 표를 채운다. 이후 데이터베이스 벡터 하나와의 거리는 $\hat{d}(x, y)^2 = \sum_{j=1}^{m} d(u_j(x), c_j(q_j(y)))^2$로, 코드 번호로 표를 $m$번 조회해 더하기만 하면 된다. 벡터마다 $D$차원 연산 대신 $m$번의 덧셈으로 끝나므로 전수 탐색도 빠르다.

원 논문은 960차원 GIST 특징 약 100만 개에 64비트 코드를 적용해 상위 100개 안에 참 최근접 이웃이 포함되는 비율(recall@100)을 측정했다. SDC는 0.446, ADC는 0.652로 같은 코드 길이에서 ADC가 크게 앞섰다. 저장 공간은 원본 대비 수백 배 줄면서도 실용적인 재현율을 유지한다는 점이 확인되었다.

전수 탐색은 코드가 아무리 짧아도 데이터 수에 비례해 비용이 늘어난다. 이를 줄이기 위해 원 논문은 역파일 색인(Inverted File, IVF)과 곱 양자화를 결합한 IVFADC를 제안했다. 먼저 거친 k-평균 양자화기로 공간을 $k'$개 셀로 나누고, 각 벡터가 속한 셀 중심과의 차이인 잔차(Residual)를 곱 양자화로 부호화한다.

질의 시에는 가장 가까운 $w$개 셀만 골라 그 안의 코드만 ADC로 비교한다. 잔차를 양자화하면 벡터 자체보다 분산이 작아 같은 코드 길이로 더 정밀하게 표현된다. GIST 실험에서 $k'=1024$, $w=64$인 IVFADC는 recall@100 0.744를 기록했으며, 원 논문은 약 20억 개 SIFT 벡터 규모에서도 이 방식을 검증했다. 탐색할 셀 수를 늘리면 재현율은 오르지만 지연 시간도 함께 늘어난다.

기본 곱 양자화는 차원을 순서대로 잘라 나누므로, 상관된 차원이 한 부분공간에 몰리거나 분산이 부분공간마다 불균형하면 오차가 커진다. 이 한계를 보완하는 변형이 여러 제안되었으며, 대표적인 계열은 다음과 같다.

주요 변형 기법

최적화 곱 양자화(Optimized Product Quantization, OPQ): Ge 등(2013)이 제안했으며, 공간 분해 방식(회전)과 코드북을 함께 최적화해 양자화 왜곡을 줄인다.
가산 양자화(Additive Quantization, AQ): Babenko와 Lempitsky(2014)가 제안했으며, 부분공간으로 나누지 않고 전체 차원 코드북 벡터 여러 개의 합으로 원본을 근사한다.
잔차 양자화(Residual Quantization): 앞 단계의 양자화 오차를 다음 단계 코드북으로 반복해 부호화하는 방식이다.
비등방성 벡터 양자화(Anisotropic Vector Quantization): Guo 등(2020)이 ScaNN에 적용한 방식으로, 내적 탐색에 중요한 잔차의 평행 성분을 직교 성분보다 크게 벌점화한다.

OPQ는 입력 벡터에 직교 회전 행렬을 곱한 뒤 곱 양자화를 적용하는 구조라서 기존 PQ 색인에 전처리 단계로 쉽게 붙일 수 있다. 가산 양자화 계열은 같은 코드 길이에서 왜곡이 더 작지만 부호화가 조합 탐색 문제가 되어 색인 구축 비용이 크다. ScaNN의 비등방성 손실은 재구성 오차 자체보다 상위 결과의 내적 순위를 보존하는 데 초점을 맞춘다는 점에서 목적 함수를 바꾼 접근이다.

곱 양자화의 설계는 재현율, 메모리, 속도 사이의 절충이다. 실무에서 조정하는 주요 요소는 다음과 같다.

재현율-메모리 절충 요소

코드 길이: $m$을 늘리면 표현력이 커져 재현율이 오르지만 벡터당 메모리와 조회 횟수가 늘어난다.
탐색 셀 수: IVF 결합 시 탐색하는 셀 수를 늘리면 재현율이 오르고 지연 시간이 늘어난다.
재정렬(Re-ranking): PQ로 후보를 넉넉히 뽑은 뒤 원본 벡터나 더 긴 코드로 정확한 거리를 다시 계산해 순위를 보정한다.
코드북 재학습: 임베딩 모델이 바뀌거나 데이터 분포가 이동하면 코드북을 다시 학습해야 왜곡이 커지지 않는다.

구현은 Meta의 Faiss가 사실상 표준이다. IndexPQ(d, M, nbits)는 전수 탐색형 PQ 색인으로 벡터당 $\lceil M \cdot nbits / 8 \rceil$바이트를 사용한다. IndexIVFPQ(quantizer, d, nlist, M, nbits)는 IVFADC 구조이며 벡터 ID 저장용 8바이트가 더해지고, 질의 시 nprobe로 탐색 셀 수를 정한다. index_factory 문자열로는 IVF1024,PQ8처럼 간단히 구성할 수 있다.

곱 양자화는 HNSW 같은 그래프 색인과도 결합된다. 그래프로 후보를 찾고 PQ 코드로 거리를 근사하거나, 디스크 기반 색인에서 메모리에는 PQ 코드만 두고 원본은 디스크에 두어 재정렬에 쓰는 방식이 널리 쓰인다. 이처럼 곱 양자화는 단독 색인보다 다른 색인 구조의 거리 계산과 저장을 담당하는 압축 계층으로 쓰이는 경우가 많다.

곱 양자화는 신경망 가중치나 활성값의 비트 수를 줄이는 모델 양자화(Model Quantization)와 이름이 비슷하지만 목적과 대상이 다르다. 모델 양자화는 32비트 실수를 8비트나 4비트 정수로 바꿔 추론 연산과 모델 크기를 줄이는 기법이고, 곱 양자화는 검색 대상 벡터를 코드북 번호로 바꿔 저장과 거리 계산을 줄이는 기법이다. 두 기법 모두 정밀도를 일부 양보해 비용을 줄인다는 공통점이 있지만, 곱 양자화의 오차는 모델 출력이 아니라 검색 재현율로 나타난다.

곱 양자화는 단순한 k-평균 조합만으로 수십 배 이상의 압축과 빠른 근사 거리 계산을 동시에 달성해, 10억 규모 벡터 검색을 단일 서버 메모리에서 가능하게 만든 기법이다. 추천 후보 생성, 유사 이미지 검색, 검색 증강 생성의 문서 검색처럼 대규모 임베딩을 다루는 시스템에서는 코드 길이와 탐색 범위를 서비스의 재현율·지연 목표에 맞춰 조정하는 것이 핵심이다.

#관련 용어

벡터 양자화

연속적인 벡터를 유한한 코드북의 대표 벡터 번호로 대체해 표현하는 압축 방법

코드북

양자화에 쓰이는 대표 벡터(중심점)의 집합

비대칭 거리 계산(ADC)

질의는 원본으로 두고 데이터베이스 벡터만 코드로 표현해 룩업 테이블로 거리를 근사하는 방식

역파일 색인(IVF)

거친 양자화기로 공간을 셀로 나누고 질의와 가까운 셀만 탐색하는 색인 구조

근사 최근접 이웃 탐색

정확도를 일부 양보하고 고차원 벡터의 최근접 이웃을 빠르게 찾는 탐색 기법

k-평균 군집화

데이터를 k개 군집으로 나누고 각 군집의 중심점을 반복적으로 갱신하는 군집화 알고리즘

#직무 연관도

Data Analyst낮음

검색·추천 품질 지표 변화를 해석할 때 색인 압축으로 인한 재현율 손실 가능성을 고려

Data Scientist보통

임베딩 압축이 검색 재현율에 미치는 영향을 분석하고 양자화 방식을 비교·개선

Data Engineer밀접

벡터 검색 색인을 설계·구축하고 코드 길이와 탐색 파라미터를 서비스 지연·메모리 목표에 맞춰 튜닝

#사용 사례

전자상거래인터넷 서비스미디어금융통신

개요

곱 양자화는 대규모 임베딩을 제한된 메모리에서 빠르게 검색해야 하는 서비스에 쓰인다. 전자상거래와 미디어 분야에서는 추천 후보 생성과 유사 이미지·콘텐츠 검색에, 인터넷 서비스에서는 의미 기반 검색과 검색 증강 생성의 문서 검색에, 금융과 통신 분야에서는 유사 거래·패턴 조회에 활용된다.

사례

전자상거래 서비스에서 수억 개 상품 이미지 임베딩을 IVF-PQ 색인으로 압축해 단일 서버 메모리에 올리고, 유사 상품 검색 시 PQ로 후보를 뽑은 뒤 원본 벡터로 재정렬해 재현율을 보정