곱 양자화Product Quantization
벡터를 부분 벡터 m개로 나누고 부분마다 따로 학습한 작은 코드북의 번호로 바꿔, 벡터 하나를 몇 바이트 코드로 압축하는 벡터 검색용 양자화다. 질의와 코드의 거리는 부분 거리표를 m번 찾아 더해 어림한다.
1요약
- 곱 양자화는 벡터 검색 안에서 저장 벡터를 몇 바이트 코드로 줄이는 압축 계층으로, 2011년 Jégou 등이 제안했고 IVF 색인의 목록 안 벡터 · 대규모 추천 · 이미지 검색이 이 코드 위에서 돈다 — 모델 가중치를 INT8 · INT4 로 줄이는 양자화와는 다른 개념이다.
- 64차원 float32 벡터 2만 개(5.12 MB)를 부분 8개 × 8비트 코드로 바꾸자 코드 160 KB + 코드북 65.5 KB 로 약 23분의 1이 됐고, 그 대신 참 최근접 이웃이 1위에 오는 비율은 0.19 로 내려갔다(본문 사례).
- 「압축 뒤 검색이 틀린다」는 상위 100개 안에 참 이웃이 남는가로 가른다 — 남으면 원 벡터 재순위로 고치는 정상 오차, 남지 않으면 코드북 학습 · 부분 분할 · 거리 계산 방식(SDC)을 의심한다.
2등장 배경
벡터 하나를 중심 하나의 번호로 바꾸는 벡터 양자화는 k-평균(Lloyd 1982)으로 코드북을 배운다. 그러나 64비트 코드를 쓰려면 중심이 2^64개 필요해 학습도 저장도 할 수 없다(André 2015 2절).
2011년 Jégou · Douze · Schmid 는 벡터를 m 조각으로 나눠 조각마다 중심 k* 개를 따로 배우는 곱 양자화를 내놓았다 — 8조각 × 256개면 저장은 중심 2,048개인데 표현은 256^8 = 2^64 조합이다(Jégou 2011). 2013년 Ge 등은 나누기 전에 회전을 학습하는 OPQ 를, 2015년 André 등은 4 ~ 6배 빠른 고속 스캔(PQ Fast Scan)을 더했다(Ge 2013 · André 2015 초록).
2020년 Guo 등은 내적 검색에서 오차 방향에 가중치를 두는 이방성 양자화로 손실 함수를 바꿨다(Guo 2020 초록). 오늘 Faiss 는 PQ 를 잔차 · 가산 양자화와 함께 다중 코드북 양자화의 한 종류로 묶어 구현한다(Douze 2024 4.1절).
3쉽게 이해하기 — 부위별 견본책으로 얼굴을 적는 몽타주 사무소
몽타주 사무소 직원 서윤은 등록된 얼굴 사진 2만 장을 모두 보관할 공간이 없다. 그래서 얼굴을 이마 · 눈 · 코 · 입처럼 8부위로 자르고, 부위마다 견본 256장이 든 견본책을 만들어 사진마다 「가장 닮은 견본 번호」 8개만 카드에 적는다. 새 손님이 오면 서윤은 손님의 진짜 얼굴을 부위마다 견본 256장과 견줘 닮음 점수표를 한 번 만들고, 카드 2만 장은 번호 8개로 점수를 찾아 더하기만 한다.
그림 1 · 사진 대신 번호 카드 8칸만 남기고, 새 손님은 진짜 얼굴로 점수표를 한 번 만든 뒤 카드마다 점수 8개를 더해 가장 닮은 얼굴을 고른다.
그림 2 · 손님 얼굴까지 몽타주로 바꾸면 오차가 두 번 쌓여 참 얼굴이 9위로 밀리고, 진짜 얼굴로 견주면 1위에 남는다.
| 비유 속 역할 | 실제 이름 | 실제로 하는 일 |
|---|---|---|
| 등록된 얼굴 사진 | 저장 벡터 | 64차원 float32 = 256바이트 |
| 8부위로 자르기 | 부분 벡터 m개 | 차원을 m 덩어리로 나눔(여기서 8 × 8차원) |
| 부위별 견본책 | 부분 코드북 | 부분마다 k-평균으로 중심 k* = 256개 학습 |
| 번호 카드 8칸 | PQ 코드 | 부분마다 가장 가까운 중심 번호 1바이트 |
| 닮음 점수표 | 거리표 m × k* | 질의마다 한 번 계산 · 셀 2,048개 |
| 카드 훑기 | ADC 스캔 | 코드 하나에 표 조회 · 덧셈 8번 |
| 원본 사진으로 다시 보기 | 재순위 | 앞쪽 후보만 원 벡터로 다시 잼 |
| 견본책 다시 만들기 | 코드북 재학습 | 데이터 분포가 바뀌면 모든 코드를 다시 부호화 |
⚠ 비유가 맞지 않는 곳: 실제 「부위」는 눈 · 코처럼 뜻이 있는 덩어리가 아니라 차원 번호를 잘라 묶은 것이라, 부위끼리 서로 얽혀 있으면(상관) 자르는 방법 자체가 오차를 키운다 — 그래서 자르기 전에 회전(OPQ)을 배운다(Douze 2024 4.2절).
4구조 — 부분 코드북과 코드
벡터 x 를 부분 u₁ … u_m 으로 나누면 코드는 부분마다 가장 가까운 중심 번호이고, 복원 벡터는 부분 중심을 이어 붙인 것이다. 코드 길이는 m × log₂k* 비트이고(Douze 2024 4.1절), 부분 코드북은 서로 독립이라 표현할 수 있는 중심 수는 k*^m 이다.
그림 3 · 부분 코드북 8개에 중심 2,048개만 저장해 256^8 조합을 표현하고, 벡터마다 남는 것은 번호 8바이트다.
| 요소 | 크기 · 단위 | 역할 | 값 · 근거 |
|---|---|---|---|
| 부분 벡터 | d ÷ m 차원 | 나눠 부호화할 단위 | d 가 m 으로 나눠떨어져야 함(Jégou 2011) |
| 부분 코드북 | k* × (d ÷ m) float | 부분별 중심 | 부분마다 k-평균 · 전체 k* × d 개 수 = 16,384개 |
| PQ 코드 | m × log₂k* 비트 | 저장 벡터를 대신함 | PQ 8×8 = 64비트가 가장 흔한 설정(André 2015 3.1절) |
| 거리표 | m × k* 셀 | 질의별 부분 거리 | 질의 하나에 한 번 · 여러 코드 비교로 비용이 나뉨(Douze 2024 4.3절) |
| ADC 거리 | 표 조회 m번 | 질의 ↔ 코드 거리 어림 | 질의 쪽 오차 없음 · Faiss 색인 대부분이 씀(Douze 2024 4절) |
| 회전 R | d × d 직교 행렬 | 부분 사이 상관 제거 | OPQ · 분산이 몇 성분에 몰릴 때 효과(Douze 2024 4.2절) |
| IVF 잔차 | 벡터 − 목록 중심 | 목록 안 부호화 대상 | 잔차를 압축하면 더 정확 · by_ |
🔑 곱 양자화가 줄이는 것은 «중심을 저장하는 비용»이지 «표현할 수 있는 중심 수»가 아니다 — 2,048개를 저장해 2^64개를 쓰는 대신, 부분 사이 상관은 버린다.
5동작 — 2만 개 부호화와 질의 #0 의 ADC 검색
사례 = 직접 실행(합성 데이터) — 64차원 가우스 분포(분산 exp(−i/12) 를 무작위 회전해 차원끼리 상관) 벡터 20,000개 · 질의 200개 · 시드 0 · 코드북 · ADC · SDC 를 numpy 로 구현했다.
- 정답 만들기 — 질의 200개를 2만 개와 모두 재어 참 최근접 이웃을 정한다. 질의 #0 의 1위는 #8224(거리 제곱 6.963)이고 2위 #5846 은 7.585 다.
- 코드북 학습 — 부분 8개마다 k-평균(중심 256 · 20회 반복)을 돌린다. 재구성 오차(MSE)는 3.363 으로 벡터 전체 분산 12.47 의 27% 다.
- 부호화 — 벡터마다 부분별 가장 가까운 중심 번호를 적는다. #8224 의 코드는 31 · 195 · 29 · 210 · 248 · 52 · 70 · 57 이다.
- 거리표 — 질의 #0 을 부분 8개로 나눠 중심 256개와 잰 셀 2,048개짜리 표를 만든다(곱셈 · 덧셈 16,384번 · 질의마다 한 번).
- ADC 스캔 — 코드 2만 개마다 표를 8번 찾아 더한다(조회 160,000번 · 원 벡터 전수는 곱셈 · 덧셈 1,280,000번). #8224 는 부분 거리 0.400 + 0.684 + … + 0.535 = 6.481 로 실제 6.963 보다 작게 어림되지만 1위에 남는다.
- SDC 와 비교 — 질의도 코드로 바꿔 코드끼리 재면 질의 #0 의 참 이웃은 9위로 밀린다. 질의 200개 평균 1-recall@1 은 ADC 0.19 · SDC 0.075 다.
- 재순위 — ADC 상위 100개를 원 벡터로 다시 재면 질의 200개 모두 참 이웃을 1위로 돌려받는다(1-recall@100 = 1.0).
그림 4 · 질의 #0 은 셀 2,048개짜리 거리표를 한 번 만든 뒤 코드마다 셀 8개를 더하고, #8224 는 6.481 로 어림돼 1위에 남는다.
그림 5 · 같은 8바이트라도 부분 수 · 비트 배분 · 회전에 따라 재구성 오차가 2배 넘게 갈리고, 회전(PCA 균형)이 바이트를 늘리지 않고 오차를 절반 아래로 줄인다.
🔑 같은 바이트에서는 «부분 하나에 비트를 더 주는 쪽»이 오차가 작고, 남은 오차의 큰 몫은 비트 부족이 아니라 부분 사이 상관이다 — 회전은 코드 길이를 그대로 두고 그 몫을 없앤다.
6비교 — 스칼라 · 곱 · 회전 · 잔차 양자화
같은 데이터에서 잰 값이다(부호화 방식만 바꾸고 전수 스캔).
| 기준 | SQ8(차원마다 8비트) | PQ 8×8 | OPQ(PCA 균형 회전 + PQ 8×8) | 잔차 양자화 8단 × 8비트 |
|---|---|---|---|---|
| 벡터당 바이트 | 64 | 8 | 8 | 8 |
| 재구성 오차(MSE) | 0.001 | 3.36 | 1.52 | 1.35 |
| 1-recall@1 · @10 | 0.96 · 1.0 | 0.19 · 0.665 | 0.375 · 0.875 | 0.48 · 0.89 |
| 코드북 크기(float 수) | 차원별 최소 · 최대 128 | 16,384 | 16,384 + 회전 4,096 | 131,072(단마다 64차원 중심 256) |
| 거리 계산 | 복원 뒤 곱셈 · 덧셈 64번 | 표 조회 8번 | 질의 회전 1번 + 표 조회 8번 | 단끼리 교차 항이 생겨 표 하나로 끝나지 않음(Douze 2024 4.3절) |
분석메모리가 넉넉하면 SQ8, 바이트를 8 ~ 16으로 묶어야 하면 회전을 붙인 PQ 가 기본이고, 잔차 양자화는 오차를 더 줄이지만 코드북이 8배이고 부호화 · 거리 계산이 무거워 정확도가 모자랄 때 고른다. 근거는 표의 바이트 · 오차 · 코드북 행과 Douze 2024 4.1 · 4.3절(가산 계열은 복원을 합으로 하므로 부분 거리표가 독립이 아님)이다.
7실무 진단 — 압축 뒤 검색 품질 원인 가르기
분석먼저 1-recall@100 을 본다. 100 안에 참 이웃이 남으면 PQ 의 정상 오차라 재순위로 끝나고, 100 밖으로 빠지면 코드북 · 분할 · 거리 계산 방식 쪽을 고쳐야 한다(사례 단계 7 · Jégou 2011).
| # | 증상 | 의심 원인 | 단계 | 확인 자료 | 판정 기준(근거) |
|---|---|---|---|---|---|
| 1 | @1 은 낮고 @100 은 높음 | 압축 오차(정상) | 거리 | ADC 상위 100 재순위 전후 recall | 재순위로 회복되면 코드 길이는 그대로 둠(Douze 2024 3.5절) |
| 2 | @100 도 낮음 | 질의까지 코드로 바꾼 SDC | 거리 | 거리 함수가 질의를 부호화하는가 | ADC 로 바꾸면 질의 쪽 오차가 사라짐(Douze 2024 4절) |
| 3 | MSE 가 분산의 큰 몫 | 부분 사이 상관 · 분산 쏠림 | 분할 | 부분별 분산 · 공분산 행렬 비대각 크기 | 회전(OPQ) 뒤 MSE 가 줄면 분할 탓(Douze 2024 4.2절) |
| 4 | 새 데이터에서만 recall 급락 | 코드북 학습 분포와 다름 | 학습 | 새 데이터 MSE ÷ 학습 데이터 MSE | 비율이 크게 오르면 코드북 재학습 · 전체 재부호화 |
| 5 | IVF-PQ 가 PQ 단독보다 나쁨 | 목록 중심 잔차를 쓰지 않음 | 색인 | IndexIVF.by_residual | 잔차 부호화가 더 정확 · 기본값 true(Douze 2024 5.1절) |
| 6 | 4비트 설정의 정확도 저하 | k* 16 이라 부분당 중심 부족 | 설정 | 같은 바이트의 m × 8비트와 MSE 비교 | 4비트는 거리표 셀 16개를 SIMD 레지스터에 넣는 속도용 설정(그림 5 · Douze 2024 부록 A.3절) |
회전 · 재학습은 코드를 모두 다시 만드는 작업이므로, 재순위로 해결되는지부터 보는 것이 비용이 가장 적은 순서다.
8시험 대비
시험에서는 곱 양자화의 원리 · 코드 길이 · 거리 계산을 묻는 정의 · 특징형, 스칼라 양자화 · OPQ · 잔차 양자화와 견주는 비교형이 나올 수 있다. 정의형은 「중심 2^64 개를 저장할 수 없다」에서 출발해 부분 코드북 그림과 ADC 거리표로 답하고, 비교형은 같은 바이트에서 오차가 어떻게 갈리는지를 표와 그래프로 보인다. 모델 양자화와 함께 물으면 「모델 양자화 = 가중치 수 격자 · 곱 양자화 = 벡터를 코드북 번호로」로 경계를 짓는다.
- 개요 — 정의 · 벡터 양자화의 한계(64비트 코드 = 중심 2^64개) · Jégou 2011 · 모델 양자화와의 차이
- 구조 — 그림 3 부분 분할 · 부분 코드북 · 코드(m × log₂k* 비트 · 2,048개로 2^64 조합)
- 검색 절차 — 그림 4 거리표 m × k* 한 번 → 코드마다 조회 m번 · ADC ↔ SDC 오차 차이
- 오차를 줄이는 법 — 그림 5 비트 배분 · 회전(OPQ) · IVF 잔차 부호화
- 비교 — SQ8 · PQ · OPQ · 잔차 양자화의 바이트 · 오차 · 거리 계산 표
- 발전 — 4비트 고속 스캔(SIMD 레지스터 거리표) · 이방성 양자화 · 재순위
꼭 쓸 키워드
부분 벡터부분 코드북k-평균코드 길이 m × log₂k*ADCSDC거리표OPQ잔차 부호화재순위
다른 답안과 차이를 내는 한 가지 — 같은 8바이트에서 분할 · 비트 배분 · 회전만 바꿔 오차가 5.61 ~ 1.52 로 갈리는 그래프를 그려 「곱 양자화의 오차는 바이트가 아니라 나누는 법이 정한다」를 숫자로 보인다.
9오해와 사실
- 오해곱 양자화는 모델 가중치를 줄이는 INT8 양자화와 같은 기법이다.사실INT8 양자화는 수 하나를 눈금 · 영점으로 좁은 격자에 옮기고, 곱 양자화는 8차원 부분 벡터를 k-평균 중심 번호로 바꿔 사례에서 256바이트를 8바이트로 줄였다(Douze 2024 4.1절).
- 오해질의도 같은 코드로 바꿔야 공정하게 비교된다.사실질의를 부호화하면 오차가 양쪽에 쌓여 사례 1-recall@10 이 0.665 에서 0.37 로 떨어졌고, Faiss 색인 대부분은 질의를 압축하지 않는 ADC 를 쓴다(Douze 2024 4절).
- 오해비트를 쪼개 부분 수를 늘리면 늘 더 정확하다.사실같은 8바이트에서 m16 × 4비트의 오차는 4.04 로 m8 × 8비트 3.36 보다 컸다 — 4비트 코드는 부분 거리표를 셀 16개로 줄여 SIMD 레지스터 안에서 찾게 하는 속도용 선택이다(Douze 2024 부록 A.3절 · 레지스터 거리표의 착상 = André 2015 4.1절).
10핵심 정리
| 요소 | 맡는 일 | 크기(사례) | 바꾸면 | 근거 |
|---|---|---|---|---|
| 부분 벡터 m | 벡터를 나눔 | 8 × 8차원 | 클수록 코드 길이 · 정확도 증가 | Jégou 2011 |
| 부분 코드북 k* | 부분별 중심 | 256개 · 16,384 float | 재학습 = 전체 재부호화 | Douze 2024 4.1절 |
| PQ 코드 | 저장 벡터 대신 | 8바이트 · 2만 개 160 KB | m × log₂k* 비트 | Douze 2024 4.1절 |
| 거리표 | 질의별 부분 거리 | 셀 2,048개 · 질의마다 한 번 | 비용이 코드 수로 나뉨 | Douze 2024 4.3절 |
| ADC | 질의 ↔ 코드 거리 | 1-recall@10 0.665 | SDC 0.37 | Douze 2024 4절 |
| 회전(OPQ) | 부분 사이 상관 제거 | MSE 3.36 → 1.52 | 코드 길이 그대로 | Douze 2024 4.2절 |
| IVF 잔차 | 목록 중심을 뺀 값 부호화 | — | by_ | Douze 2024 5.1절 |
| 재순위 | 압축 오차 회복 | 상위 100 → 1-recall@1 1.0 | 원 벡터 보관 필요 | Douze 2024 3.5절 |
11참고 문헌
- 먼저 볼 문헌
- ★ Product Quantization for Nearest Neighbor Search (Jégou · Douze · Schmid · IEEE TPAMI 33(1) 117-128) — 부분 벡터 분할 · 부분 코드북 · ADC 와 SDC 의 오차 차이를 원문으로 볼 때
- ★ Optimized Product Quantization for Approximate Nearest Neighbor Search (Ge · He · Ke · Sun · CVPR 2013 2946-2953) — 부분 벡터를 나누기 전에 회전을 학습해 왜곡을 줄이는 방법을 볼 때
- ★ Cache locality is not enough: High-Performance Nearest Neighbor Search with Product Quantization Fast Scan (André · Kermarrec · Le Scouarnec · PVLDB 9(4) 288-299) — PQ 8×8 이 널리 쓰이는 이유와 거리표를 SIMD 레지스터에 넣는 고속 스캔을 볼 때
- ★ The Faiss library (Douze et al. · arXiv 2401.08281v4 · HTML) — 다중 코드북 양자화 계열(PQ · 잔차 · 가산)과 IVF 잔차 부호화의 구현 선택을 볼 때
- 본문 근거
- Accelerating Large-Scale Inference with Anisotropic Vector Quantization (Guo et al. · ICML 2020 · arXiv 1908.10396v5) — arXiv · 2020-12 ·
arxiv.org/abs/1908.10396· 확인 2026-11-13 - Least Squares Quantization in PCM (IEEE Transactions on Information Theory 28(2) 129-137) — IEEE · 1982-03 ·
doi.org/10.1109/TIT.1982.1056489· 확인 2026-11-13 - NumPy 2.4 Reference numpy.linalg.svd — NumPy Developers · 2026-11 ·
numpy.org/doc/2.4/reference/generated/numpy.linalg.svd.html· 확인 2026-11-13