곱양자화

통계 수치해석 소프트웨어 마지막 수정: 2026-08-29 04:33:26

1. 개요[편집]

코드워드 $2^{64}$ 개짜리 양자기를 만들고 싶다. 다만 학습도 저장도 하고 싶지 않다.

곱양자화(Product Quantization, PQ)는 $D$ 차원 벡터를 $M$ 개의 부분벡터로 잘라 각 조각을 독립된 작은 코드북으로 따로 양자화하고, 그 인덱스들의 곱집합을 통째로 하나의 거대한 코드북으로 삼는 벡터 압축 기법이다. 조각마다 코드워드가 $K$ 개면 유효 코드워드는 $K^M$ 개인데, 학습하고 저장하는 것은 $MK$ 개뿐이다. 제구·두즈·슈미트가 2011년 TPAMI 논문에서 대규모 검색용으로 정리했고¹, 이후 십억 개 규모 벡터 검색이 노트북 램에서 돌아가게 만든 결정적 부품이 됐다.

스칼라 양자화와 벡터 양자화의 기초, 로이드 조건, 율-왜곡 관점의 이득 계산은 벡터 양자화 문서가 다룬다. 여기서는 하필 「곱」 구조를 쓰면 무엇이 공짜가 되고 무엇이 부러지는지, 그리고 메모리-정확도 손잡이를 어디에 다는지를 본다.

2. 지수 폭발을 우회하는 방식[편집]

전수 탐색 벡터 양자기는 비트율 $R$ , 차원 $D$ 일 때 코드워드가 $2^{RD}$ 개다. 128차원에 벡터당 8바이트(64비트)를 쓰겠다면 $2^{64}$ 개 — 학습 데이터도, 저장 공간도, 인코딩 시간도 전부 불가능하다. 곱양자화는 이 벽을 분해로 넘는다.

벡터 $\mathbf x \in \mathbb R^D$ 를 길이 $D^\ast = D/M$ 짜리 조각 $M$ 개로 자른다.

\mathbf x = (\underbrace{x_1,\dots,x_{D^\ast}}_{\mathbf u_1},\ \underbrace{x_{D^\ast+1},\dots}_{\mathbf u_2},\ \dots,\ \mathbf u_M)

조각별로 서브코드북 $\mathcal C_j = \{\mathbf c_{j,1},\dots,\mathbf c_{j,K}\}$ 를 k-평균 군집화로 따로 학습하고, 각 조각을 자기 코드북의 최근접 코드워드로 보낸다. 전체 양자기는 곱집합

q(\mathbf x) = \big(q_1(\mathbf u_1),\ \dots,\ q_M(\mathbf u_M)\big), \qquad \mathcal C = \mathcal C_1 \times \cdots \times \mathcal C_M

이고 $|\mathcal C| = K^M$ 이다. 이 구조가 성립하는 근거는 제곱 유클리드 거리가 좌표에 대해 분리 가능하다는 사실 하나다.

\lVert \mathbf x - q(\mathbf x) \rVert^2 = \sum_{j=1}^{M} \lVert \mathbf u_j - q_j(\mathbf u_j) \rVert^2

왜곡이 조각별 왜곡의 합으로 정확히 쪼개지므로, 전체 왜곡을 최소화하는 문제가 독립된 $M$ 개의 작은 k-평균 문제로 분해된다. 곱양자화가 「그냥 잘라서 따로 하기」 이상인 이유이자, 이 성질이 깨지는 거리(마할라노비스, 편집거리 등)에서는 이 기법이 통째로 성립하지 않는 이유다.

3. 산술 — 512바이트가 8바이트가 되는 계산[편집]

$K = 256$ 이 국룰이다. 인덱스 하나가 정확히 1바이트에 떨어지기 때문이고, 이 바닥 상수의 절반쯤은 이런 식으로 정해진다.² 그러면 코드 길이가 $M$ 바이트로 딱 떨어진다.

표현	128차원 벡터 1개	10억 개 총량
float32 원본	512 B	512 GB
PQ, M=16, K=256	16 B	16 GB
PQ, M=8, K=256	8 B	8 GB

코드북 자체의 저장량은 $M \cdot K \cdot D^\ast = K \cdot D$ 개의 실수, 즉 $256 \times 128 \times 4 \approx 128$ KB 다. 십억 개 데이터 옆에서는 반올림 오차다. 압축률이 아니라 「램에 들어가는가」가 이 표의 요점이다 — 512 GB는 클러스터를 사야 하고 8 GB는 노트북에 들어간다. 디스크를 건드리는 순간 질의 지연시간이 두 자릿수 나빠지므로, 이 한 줄이 시스템 설계 전체를 바꾼다.

인코딩 비용도 싸다. 조각마다 $K$ 개 후보와 거리를 재면 되니 벡터당 $M \cdot K \cdot D^\ast = KD$ 번의 곱셈-덧셈이고, $M$ 과 무관하다. 학습은 $M$ 개의 독립된 k-평균이라 병렬화가 자명하다.

4. 비대칭 거리 계산(ADC)[편집]

압축했으면 푸는 게 순서일 것 같지만, 검색에서는 풀지 않는다. 질의 $\mathbf q$ 와 데이터베이스 벡터 $\mathbf y$ 의 거리를 재는 방식이 둘이다.

대칭(SDC). 질의도 양자화해서 $\lVert q(\mathbf q) - q(\mathbf y)\rVert$ 를 쓴다. 코드워드 쌍의 거리표를 미리 구워 두면 조회만 하면 되지만, 양쪽 모두에 양자화 오차가 얹힌다.
비대칭(ADC). 질의는 원본 그대로 두고 $\lVert \mathbf q - q(\mathbf y)\rVert$ 를 쓴다. 오차가 데이터베이스 쪽에만 생기므로 거의 항상 SDC보다 정확하다.

ADC가 빠른 이유는 분리성 덕분에 거리가 조각별 합으로 쪼개진다는 데 있다.

\lVert \mathbf q - q(\mathbf y) \rVert^2 = \sum_{j=1}^{M} \lVert \mathbf q_j - \mathbf c_{j,\,\mathrm{code}_j(\mathbf y)} \rVert^2

질의가 들어오면 먼저 $M \times K$ 짜리 룩업 테이블을 채운다. $j$ 번째 행에는 질의 조각 $\mathbf q_j$ 와 서브코드워드 $K$ 개 사이의 제곱거리를 넣는다. 이 준비 비용도 $KD$ 번의 연산이라 질의당 한 번이면 끝난다. 그다음 데이터베이스를 훑을 때 각 벡터의 거리는

“코드 $M$ 바이트를 읽어 테이블에서 $M$ 번 조회하고 더한다”

가 전부다. 곱셈이 없다. 부동소수점 거리 계산 $D$ 번이 정수 인덱싱 $M$ 번으로 바뀌었고, $D=128$ , $M=8$ 이면 산술량만 16배 줄어든 셈이다. 게다가 훑는 대상이 원본 512 B가 아니라 8 B라 메모리 대역폭이 64분의 1이 되는데, 현대 CPU에서 이 대규모 선형 스캔의 병목이 산술이 아니라 대역폭이라는 점을 생각하면 후자가 더 큰 이득이다.

한 가지 정직하게 짚을 것. ADC의 제곱거리 추정량은 편향돼 있다. 기댓값이 참값보다 대략 양자화 왜곡 $\mathbb E\lVert \mathbf y - q(\mathbf y)\rVert^2$ 만큼 크다. 다만 그 편향이 모든 데이터베이스 벡터에 거의 같은 양으로 얹히므로 순위는 크게 흔들리지 않고, 그래서 실무는 대개 보정 없이 쓴다. 최종 정확도가 아쉬우면 상위 후보 몇백 개만 원본 벡터로 다시 재는 재순위화(rerank)를 붙이는데, 이때 원본이 디스크에 있어도 후보가 적으니 감당이 된다.³

5. 부분공간 독립 가정이 깨질 때 — OPQ[편집]

곱 구조의 전제는 조각들이 서로 독립이고 정보가 조각마다 고르게 퍼져 있다는 것이다. 실제 데이터는 그렇지 않다.

SIFT 서술자처럼 좌표에 물리적 의미가 있으면 인접 좌표끼리 강하게 상관돼 있고, 상관된 성분을 같은 조각에 몰아넣으면 그 조각의 유효 자유도가 낮아 코드워드 256개가 낭비된다.
학습된 임베딩은 좌표축 자체가 임의적이라 조각 경계를 어디에 긋느냐가 순전히 운이다. 실제로 곱양자화 성능이 성분 순서에 의외로 민감하다.
주성분 분석으로 회전만 시켜 놓으면 오히려 나빠지기 쉽다. 분산이 앞쪽 성분에 몰려서 첫 조각이 왜곡을 독점하고 뒤쪽 조각들은 거의 0을 양자화하게 되기 때문이다.

처방은 회전을 학습하는 것이다. 직교행렬 $R$ 을 앞에 붙여 $q(R\mathbf x)$ 를 쓰되, $R$ 을 총 왜곡이 최소가 되도록 고른다. 이것이 OPQ(Optimized Product Quantization, 2013)이고, 거의 같은 시기에 「Cartesian k-means」라는 이름으로 독립 제안됐다. 두 갈래가 있다.

모수적 해법. 데이터가 가우시안이라 가정하면 최적 조건이 닫힌 형태로 나온다 — PCA로 축을 정렬한 뒤 고윳값의 곱이 조각마다 같아지도록 성분을 조각에 배분한다(“고윳값 배분”). 정렬된 고윳값을 조각들에 탐욕적으로 나눠 담는 몇 줄짜리 코드다.
비모수적 해법. 회전과 코드북을 번갈아 최적화한다. 코드북을 고정하면 $R$ 은 직교 프로크루스테스 문제라 SVD 한 번으로 풀리고, $R$ 을 고정하면 조각별 k-평균이다. 로이드 반복에 회전 갱신 한 단계를 더 얹은 구조.

효과는 데이터에 따라 다르지만, 좌표축이 데이터와 어긋난 경우 재현율이 눈에 띄게 오른다. 회전은 무작위 사영처럼 그냥 아무 직교행렬을 써도 무회전보다는 낫고(상관을 흩뜨리니까), 학습된 회전은 그보다 낫다.

곱 구조를 아예 버리는 방향도 있다. 잔차 양자화는 조각으로 쪼개는 대신 단을 쌓아 오차를 갚아 나가고, 가법 양자화·합성 양자화는 부분공간 분해 제약 자체를 풀어 코드워드들의 합으로 벡터를 표현한다. 정확도는 더 좋지만 인코딩이 조합 최적화가 되어 비싸진다. 곱양자화가 살아남은 이유는 정확도 1등이라서가 아니라 인코딩과 스캔이 둘 다 자명하게 싸기 때문이다.

6. IVF-PQ — 압축과 비전수 탐색의 결합[편집]

ADC는 여전히 전수 스캔이다. 십억 개면 아무리 바이트 단위여도 질의당 8 GB를 훑어야 한다. 그래서 실전 인덱스는 앞단에 조대 양자기를 세운다.

조대 양자화. 전체 데이터를 k-평균으로 클러스터 $K'$ 개(보통 $\sqrt n$ 규모, 수천~수십만)로 나눠 역파일(inverted file, IVF) 인덱스를 만든다.
잔차 인코딩. 각 벡터를 자기 중심으로부터의 잔차 $\mathbf r = \mathbf y - \mathbf c_{\text{coarse}}$ 로 바꾼 뒤 그것을 PQ로 압축한다. 잔차는 원본보다 분산이 작고 분포가 등방적이라 같은 바이트로 훨씬 정확해진다. 이 한 줄이 IVF-PQ의 핵심 트릭이다.
질의. 질의와 가까운 클러스터 $w$ 개(nprobe)만 열어, 그 안의 코드들만 ADC로 훑는다.

이제 손잡이가 둘이다 — $M$ (바이트 수)이 메모리와 정밀도를, $w$ (nprobe)가 속도와 재현율을 조절한다. 곡선을 그려 파레토 최적점을 고르는 방식은 최근접 이웃 탐색 문서의 평가 절과 같다.

주의할 것은 잔차 ADC의 룩업 테이블이 클러스터마다 달라진다는 점이다. 질의-중심 거리 항이 클러스터별로 다르므로, 엄밀히 하려면 $w$ 개 클러스터 각각에 대해 테이블을 다시 굽거나 항을 분해해 재사용해야 한다. $w$ 가 크면 이 준비 비용이 무시할 수 없어서, 구현들은 테이블 계산을 $\lVert \mathbf q - \mathbf c\rVert^2$ 항과 잔차 항으로 쪼개 캐시한다.

구현 지형도 짧게 정리하면 이렇다. FAISS(2017)가 사실상 표준 라이브러리로 IVF-PQ·OPQ·GPU 커널을 다 들고 있고, 조대 양자기 자체에 곱 구조를 다시 적용한 역다중인덱스(2012)는 같은 메모리로 훨씬 촘촘한 셀 분할을 얻는다. 스캔 쪽에서는 $K$ 를 256에서 16으로 낮춰 룩업 테이블을 SIMD 레지스터 안에 통째로 넣고 셔플 명령으로 조회하는 4비트 PQ 기법(2015)이 큰 폭의 가속을 냈고, 지금은 FAISS의 fast-scan 계열과 구글 ScaNN(2020)이 이 방식을 쓴다. ScaNN은 여기에 더해 내적 검색에서 잔차 오차의 방향에 따라 중요도가 다르다는 관찰로 양자화 손실을 이방적으로 가중한다 — 질의 방향과 나란한 성분의 오차가 내적을 직접 망치므로 그쪽을 더 무겁게 벌한다는 것. 요즘 벡터 데이터베이스 제품들은 대개 그래프 기반 인덱스 아니면 IVF-PQ, 혹은 둘의 조합을 엔진으로 쓴다.

7. 트레이드오프를 읽는 법[편집]

곱양자화를 도입할 때 실제로 마주하는 선택은 다음 네 가지다.

$M$ 을 늘릴 것인가, $K$ 를 늘릴 것인가. 코드 길이는 $M \log_2 K$ 비트로 둘 다 늘리면 정확해진다. 하지만 $K$ 를 512로 올리면 인덱스가 1바이트를 넘어 정렬이 깨지고 테이블이 캐시에서 밀린다. 거의 항상 $K=256$ 고정, $M$ 으로 조절이 답이다.
재현율의 천장. PQ 코드만으로는 정확한 순위를 절대 복원하지 못한다. recall@1을 0.99 위로 올리고 싶으면 재순위화가 필수이며, 그러려면 원본 벡터에 접근할 경로가 있어야 한다. “메모리를 64배 줄였다”는 원본을 완전히 버렸을 때만 참이다.
거리 함수. 유도가 전부 제곱 $\ell_2$ 에 걸려 있다. 코사인은 정규화해서 $\ell_2$ 로 바꾸면 되지만, 정규화되지 않은 최대 내적 탐색은 다른 문제다 — 노름이 큰 벡터가 유리해지므로 양자화 오차의 영향이 비대칭이고, ScaNN류의 이방적 손실이 필요해지는 지점이 여기다.
데이터 이동. 학습된 코드북은 학습 분포에 매여 있다. 임베딩 모델을 갈아 끼우면 코드북도 다시 학습해야 하고, 그것은 십억 개 재인코딩을 뜻한다. 인덱스 재구축 비용을 운영 계획에 넣지 않으면 나중에 곤란해진다.

여담으로, 곱양자화는 검색만의 물건이 아니다. 신경망 가중치 행렬을 부분벡터로 잘라 코드북으로 대체하는 모델 압축 계열이 정확히 같은 기법이며, 다만 신경망 양자화의 주류인 균일 정수 양자화와 목적이 다르다 — 저쪽은 하드웨어가 그 격자를 직접 계산할 줄 알아서 이기는 것이고, 이쪽은 순수하게 메모리를 이기는 것이다. 압축률로는 곱양자화가 앞서지만 룩업이 정수 커널의 이득을 못 받으므로, “메모리가 병목이냐 연산이 병목이냐”가 선택을 가른다.

8. 관련 문서[편집]

Jégou, Douze, Schmid (2011), IEEE TPAMI 33(1). 이 논문의 진짜 기여는 곱 구조 자체가 아니라 — 곱 코드북은 1980년대 음성 코덱에서 이미 쓰였다 — ADC와 IVF를 붙여 「압축된 채로 비전수 탐색」이라는 완성된 파이프라인을 제시한 것이다. 부품이 전부 고전인데 조립도가 새로웠던 사례. ↩
$K=256$ 의 근거가 율-왜곡 이론이 아니라 «1바이트에 딱 들어가서»라는 점은 처음 들으면 허탈하다. 그런데 이 선택이 SIMD 셔플로 16개를 한 번에 조회하려고 $K=16$ 까지 내려가는 후속 연구를 낳았으니, 하드웨어가 하이퍼파라미터를 정하는 흐름은 오히려 강화된 셈이다. ↩
재순위화를 붙이는 순간 “메모리를 64배 줄였다”는 마케팅 문구는 조용히 취소된다. 원본을 어딘가에는 들고 있어야 하니까. 그래서 이 바닥의 정직한 보고 형식은 압축률이 아니라 재현율-지연시간 곡선 + 실제 상주 메모리이고, 둘 중 하나만 적힌 벤치마크는 나머지 하나가 나쁘다는 뜻으로 읽으면 대체로 맞는다. ↩