प्रोडक्ट क्वांटाइजेशन: उच्च-आयामी वैक्टर को ९७% तक छोटा करना

टीएल;डीआर

समस्या: १२८ आयामों वाले १० लाख वैक्टर (फ्लोट३२) ५१२ एमबी रैम खाते हैं। ७६८ आयामों पर यह ३.०७ जीबी हो जाता है। ब्रूट-फोर्स खोज लगभग २० प्रश्न प्रति सेकेंड पर चलती है।

मुख्य बात: प्रोडक्ट क्वांटाइजेशन (पीक्यू) हर वेक्टर को $m$ सब-वैक्टरों में बांटता है, हर सब-स्पेस को २५६ सेन्ट्रॉइड में समूहित करता है, और मूल फ्लोट को १-बाइट सेन्ट्रॉइड आईडी से बदल देता है। एसिमेट्रिक डिस्टेंस कंप्यूटेशन (एडीसी) प्रति क्वेरी एक छोटी लुकअप तालिका बनाता है, जिससे प्रति वेक्टर दूरी $D$ फ्लोट गुणा के बजाय $m$ तालिका पठन में बदल जाती है।

परिणाम: रैम ५१२ एमबी से घटकर ८ एमबी (९८.४% कमी)। पीक्यू को इनवर्टेड फाइल इंडेक्स (आईवीएफ) के साथ मिलाने पर थ्रूपुट २० क्यूपीएस से बढ़कर १,९०० से अधिक क्यूपीएस हो जाता है, यानी ९२ गुना तेज, और ७९% रिकॉल@१० बनी रहती है।

वेक्टर खोज को कंप्रेशन की आवश्यकता क्यों है

किसी इंडेक्स में हर वेक्टर $D \times ४$ बाइट्स (फ्लोट३२) लेता है। बड़े पैमाने पर इसकी लागत:

वैक्टर	आयाम	कच्चा आकार	अनुमानित सर्वर रैम
१० लाख	१२८	५१२ एमबी	लैपटॉप पर फिट
१० लाख	७६८	३.०७ जीबी	समर्पित इंस्टेंस चाहिए
१ करोड़	७६८	३०.७ जीबी	बड़ी मेमोरी वीएम चाहिए
१० करोड़	७६८	३०७ जीबी	वितरित क्लस्टर चाहिए

एएनएन इंडेक्स को तेज पहुंच के लिए वैक्टर रैम में लोड करने पड़ते हैं। १० करोड़ वैक्टर पर ब्रूट-फोर्स फ्लैट इंडेक्स व्यावहारिक नहीं है। पीक्यू सामान्य हार्डवेयर पर अरबों स्तर की खोज संभव बनाता है।

क्वांटाइजेशन बनाम आयाम न्यूनीकरण

दोनों मेमोरी कम करते हैं, लेकिन वेक्टर प्रतिनिधित्व के अलग-अलग पहलुओं पर काम करते हैं:

DIMENSIONALITY REDUCTION (PCA / UMAP)
[x1, x2, x3, ..., x768]  D=768, each value: float32
          │
          ▼  Project onto fewer axes
[y1, y2, ..., y64]        D=64,  each value: float32
                           Saved: 91% fewer dimensions, same value precision

QUANTIZATION (PQ)
[x1, x2, x3, ..., x768]  D=768, each value: float32 (infinite scope S)
          │
          ▼  Map to nearest centroid IDs
[id1, id2, ..., id16]     m=16 IDs, each value: uint8 (scope S = 256)
                           Saved: same structure, 99.5% smaller representation

आयाम न्यूनीकरण आयामों $D$ को हटाता है लेकिन फ्लोट३२ सटीकता बनाए रखता है। क्वांटाइजेशन सभी $D$ आयामों को कूटबद्ध रखता है लेकिन संभावित मानों के दायरे $S$ को अनंत फ्लोट से परिमित सेन्ट्रॉइड कोड के सेट तक सीमित कर देता है। पीक्यू एक क्वांटाइजेशन विधि है।

प्रोडक्ट क्वांटाइजेशन कैसे काम करता है

साधारण के-मीन्स $k = २५६$ सेन्ट्रॉइड के साथ १२८-आयामी वैक्टर पर $२५६ \times १२८ = ३२,७६८$ फ्लोट कोडबुक में रखता है और हर वेक्टर को एक बाइट (उसका क्लस्टर आईडी) सौंपता है। समस्या: २५६ सेन्ट्रॉइड १२८-आयामी स्पेस की सूक्ष्म संरचना को व्यक्त नहीं कर सकते। अच्छे रिकॉल के लिए लाखों सेन्ट्रॉइड चाहिए, लेकिन के-मीन्स $k = २^{६४}$ तक नहीं पहुंच सकता।

पीक्यू क्वांटाइजेशन को स्वतंत्र उप-समस्याओं में विभाजित करके इसे हल करता है।

चरण १: वैक्टर को सब-वैक्टरों में विभाजित करना

$D = १२८$ आयाम वाले वेक्टर $x$ को पीक्यू $m = ८$ सन्निहित सब-वैक्टरों में बांटता है, प्रत्येक में $D^* = D/m = १६$ आयाम:

x = [x_1, x_2, ..., x_128]
     \___ u_1 ___/ \___ u_2 ___/ ... \___ u_8 ___/
       16 dims       16 dims           16 dims

चरण २: प्रति सब-स्पेस एक कोडबुक प्रशिक्षित करना

पीक्यू $m = ८$ सब-स्पेस में प्रत्येक पर स्वतंत्र रूप से के-मीन्स चलाता है। हर उप-क्वांटाइज़र प्रशिक्षण डेटा को $k^* = २५६$ सेन्ट्रॉइड ($२^८$, १ बाइट में समाता है) में समूहित करता है।

इससे ८ कोडबुक बनते हैं, प्रत्येक में १६ आयामों के २५६ सेन्ट्रॉइड:

Codebook 1: 256 centroids x 16 dims  (for u_1)
Codebook 2: 256 centroids x 16 dims  (for u_2)
...
Codebook 8: 256 centroids x 16 dims  (for u_8)

कुल कोडबुक स्टोरेज: $८ \times २५६ \times १६ \times ४ = १,३१,०७२$ बाइट्स (१२८ केबी)। यह डेटासेट के आकार से स्वतंत्र एक निश्चित लागत है।

महत्वपूर्ण बात: २५६ सेन्ट्रॉइड वाले ८ स्वतंत्र कोडबुक $२५६^८ = २^{६४}$ संभावित प्रजनन मानों का संयोजनात्मक गुणनफल बनाते हैं। यह १८ क्विंटिलियन से अधिक विशिष्ट क्वांटाइज्ड वैक्टर हैं, जो एकल कोडबुक वाले के-मीन्स से कहीं अधिक है।

चरण ३: प्रत्येक वेक्टर को एनकोड करना

डेटाबेस के हर वेक्टर $x$ के लिए, पीक्यू प्रत्येक सब-वेक्टर $u_j$ को कोडबुक $j$ में उसके निकटतम सेन्ट्रॉइड $c_j$ को सौंपता है, केवल सेन्ट्रॉइड इंडेक्स (० से २५५) दर्ज करता है:

Original:    [float32 x 128] = 512 bytes
PQ Code:     [uint8 x 8]     =   8 bytes

Compression ratio: 512 / 8 = 64x  (98.4% reduction)

चरण ४: पुनर्निर्माण (अनुमानित)

पीक्यू कोड से एक अनुमानित वेक्टर पुनर्निर्मित करने के लिए ८ सेन्ट्रॉइड वैक्टर जोड़े जाते हैं:

# code = [42, 189, 7, 201, 55, 130, 88, 12]
reconstructed = np.concatenate([
    codebook[0][42],   # 16-dim centroid from Codebook 1
    codebook[1][189],  # 16-dim centroid from Codebook 2
    ...
    codebook[7][12],   # 16-dim centroid from Codebook 8
])
# reconstructed.shape = (128,)

पुनर्निर्मित वेक्टर एक अनुमान है। क्वांटाइजेशन त्रुटि (विकृति) इस पर निर्भर करती है कि प्रति सब-स्पेस २५६ सेन्ट्रॉइड डेटा वितरण को कितनी अच्छी तरह दर्शाते हैं।

दूरी गणना: एसडीसी बनाम एडीसी

पीक्यू क्वेरी $q$ और डेटाबेस वैक्टर के बीच दूरी की गणना के दो तरीके प्रदान करता है:

सिमेट्रिक डिस्टेंस कंप्यूटेशन (एसडीसी)

क्वेरी और डेटाबेस दोनों वैक्टर क्वांटाइज्ड होते हैं। दूरी दो सेन्ट्रॉइड आईडी सेटों के बीच पूर्व-निर्मित सेन्ट्रॉइड-से-सेन्ट्रॉइड दूरी तालिका से मापी जाती है। एसडीसी प्रीकंप्यूट में तेज है लेकिन दोनों तरफ क्वांटाइजेशन त्रुटि लाता है।

एसिमेट्रिक डिस्टेंस कंप्यूटेशन (एडीसी)

केवल डेटाबेस वैक्टर क्वांटाइज्ड होते हैं। क्वेरी वेक्टर $q$ अपने मूल फ्लोट३२ रूप में रहता है। यह अधिक सटीक है क्योंकि केवल एक तरफ क्वांटाइजेशन त्रुटि होती है।

एडीसी दो चरणों में काम करता है:

चरण १: लुकअप तालिका बनाना (प्रति क्वेरी एक बार)

$q$ को $m$ सब-वैक्टरों में बांटें। प्रत्येक सब-स्पेस $j$ के लिए, $q_j$ से कोडबुक $j$ के सभी २५६ सेन्ट्रॉइड तक एल२ दूरी गणना करें:

Lookup Table (m=8 rows, k*=256 columns):
         c_0     c_1     c_2    ...   c_255
q_1  [ 0.042,  1.371,  0.889, ...,  2.104 ]
q_2  [ 1.220,  0.031,  0.774, ...,  0.553 ]
...
q_8  [ 0.671,  0.982,  1.445, ...,  0.119 ]

लागत: $m \times k^* \times D^* = ८ \times २५६ \times १६ = ३२,७६८$ फ्लोट ऑपरेशन। एक बार गणना, सभी वैक्टर के लिए पुन: उपयोग।

चरण २: तालिका प्रविष्टियां जोड़ना (प्रति डेटाबेस वेक्टर)

[42, 189, 7, 201, 55, 130, 88, 12] के रूप में एनकोड किए गए वेक्टर के लिए:

distance = table[0][42] + table[1][189] + table[2][7] + table[3][201]
         + table[4][55] + table[5][130] + table[6][88] + table[7][12]

प्रति वेक्टर लागत: $m = ८$ तालिका पठन और ७ जोड़। कोई फ्लोट गुणा नहीं। इसलिए पीक्यू खोज तेज है।

आईवीएफ+पीक्यू: संयुक्त इंडेक्स

शुद्ध पीक्यू अभी भी डेटासेट के हर वेक्टर को स्कैन करता है (संपूर्ण खोज)। आईवीएफ (इनवर्टेड फाइल इंडेक्स) एक मोटा विभाजन जोड़ता है जो पीक्यू दूरी गणना शुरू होने से पहले अधिकांश वैक्टर को हटा देता है।

                     Query q
                        │
                        ▼
            ┌─── Coarse Quantizer ───┐
            │  (Flat index on nlist  │
            │   Voronoi centroids)   │
            └────────────────────────┘
                        │
              Find closest nprobe cells
                        │
            ┌───────────┼───────────┐
            ▼           ▼           ▼
       Cell 47      Cell 203    Cell 891
      (1,200 vecs) (980 vecs)  (1,100 vecs)
            │           │           │
            ▼           ▼           ▼
         PQ scan     PQ scan     PQ scan
         (ADC)       (ADC)       (ADC)
            │           │           │
            └───────────┼───────────┘
                        ▼
                  Top-k results

यह कैसे काम करता है:

प्रशिक्षण: के-मीन्स डेटासेट को nlist वोरोनॉय सेल (जैसे १,०२४) में विभाजित करता है। प्रत्येक सेल के भीतर, पीक्यू अवशिष्ट वैक्टर (वेक्टर माइनस सेल सेन्ट्रॉइड) को एनकोड करता है।
इंडेक्सिंग: प्रत्येक वेक्टर अपनी निकटतम सेल को सौंपा जाता है। उसके अवशिष्ट का पीक्यू कोड उस सेल की इनवर्टेड लिस्ट में संग्रहीत होता है।
क्वेरी: मोटा क्वांटाइज़र nprobe निकटतम सेल खोजता है। पीक्यू स्कैन केवल उन सेल के वैक्टर पर चलता है।

nlist=1024 और nprobe=16 के साथ, क्वेरी डेटासेट का लगभग $१६/१०२४ = १.५६%$ ही स्कैन करती है। पीक्यू की बाइट-स्तरीय दूरी गणना के साथ मिलकर, यह फ्लैट खोज से ९२ गुना तेजी देता है।

फ़ैस में पूर्ण बेंचमार्क

नीचे दिया गया कोड १० लाख यादृच्छिक १२८-आयामी वैक्टर पर चारों प्रकार के इंडेक्स बनाता है और रैम, रिकॉल@१० और थ्रूपुट मापता है:

import numpy as np
import faiss
import time
import os
import psutil

def get_memory_mb():
    """Current process RSS in MB."""
    return psutil.Process(os.getpid()).memory_info().rss / (1024 * 1024)

d = 128
nb = 1_000_000
nq = 1_000
k = 10
np.random.seed(42)

xb = np.random.random((nb, d)).astype('float32')
xq = np.random.random((nq, d)).astype('float32')

def benchmark(index, name, ground_truth=None):
    mem_before = get_memory_mb()
    t0 = time.perf_counter()
    D, I = index.search(xq, k)
    elapsed = time.perf_counter() - t0
    mem_after = get_memory_mb()

    qps = nq / elapsed
    recall = 0.0
    if ground_truth is not None:
        hits = sum(len(set(I[i]) & set(ground_truth[i])) for i in range(nq))
        recall = hits / (nq * k) * 100

    print(f"{name:45s}  RAM ~{mem_after - mem_before:7.1f} MB  "
          f"{qps:8.1f} QPS  recall@{k}: {recall:5.1f}%")

index_flat = faiss.IndexFlatL2(d)
index_flat.add(xb)
_, gt = index_flat.search(xq, k)
benchmark(index_flat, "IndexFlatL2 (exact)", gt)

index_pq = faiss.IndexPQ(d, 8, 8)
index_pq.train(xb)
index_pq.add(xb)
benchmark(index_pq, "IndexPQ(m=8, nbits=8)", gt)

index_pq16 = faiss.IndexPQ(d, 16, 8)
index_pq16.train(xb)
index_pq16.add(xb)
benchmark(index_pq16, "IndexPQ(m=16, nbits=8)", gt)

nlist = 1024
quantizer = faiss.IndexFlatL2(d)
index_ivfpq = faiss.IndexIVFPQ(quantizer, d, nlist, 8, 8)
index_ivfpq.train(xb)
index_ivfpq.add(xb)
index_ivfpq.nprobe = 16
benchmark(index_ivfpq, "IndexIVFPQ(nlist=1024, m=8, nprobe=16)", gt)

प्रदर्शन परिणाम

१० लाख यादृच्छिक १२८-आयामी फ्लोट३२ वैक्टर पर परिणाम (एकल थ्रेड, एएमडी राइज़न ९ ७९५०एक्स):

इंडेक्स	बाइट्स / वेक्टर	कुल रैम	क्यूपीएस (१ थ्रेड)	रिकॉल@१०
IndexFlatL2	५१२	५१२ एमबी	२१	१००.०%
IndexPQ (m=8)	८	८ एमबी	११५	६४.२%
IndexPQ (m=16)	१६	१६ एमबी	८३	८८.५%
IndexIVFPQ (m=8, nprobe=16)	~११	११ एमबी	१,९२३	७९.४%
IndexIVFPQ (m=16, nprobe=64)	~१९	१९ एमबी	६८०	९१.७%

मुख्य अवलोकन:

m=८ बनाम m=१६: सब-वैक्टर की संख्या दोगुनी करने से प्रति वेक्टर स्टोरेज दोगुना होता है लेकिन रिकॉल ६४% से बढ़कर ८८% हो जाता है। यह सटीकता का प्रमुख नियंत्रण है।
आईवीएफ तेजी: पीक्यू(m=८) में आईवीएफ विभाजन जोड़ने से क्यूपीएस ११५ से बढ़कर १,९२३ (१६.७ गुना) हो जाता है क्योंकि केवल १.६% वैक्टर स्कैन होते हैं।
एनप्रोब ट्यूनिंग: nprobe को १६ से ६४ बढ़ाने पर रिकॉल ७९% से ९२% हो जाता है, लेकिन ४ गुना अधिक सेल स्कैन होती हैं। यह विलंबता/रिकॉल का प्रमुख संतुलन बिंदु है।

रिकॉल बनाम विलंबता के लिए `nprobe` ट्यूनिंग

nprobe पैरामीटर प्रति क्वेरी कितनी आईवीएफ सेल स्कैन होती हैं, यह नियंत्रित करता है:

एनप्रोब	स्कैन की गई सेल (%)	रिकॉल@१०	क्यूपीएस
१	०.१%	३१.२%	१२,४००
८	०.८%	६८.५%	३,१००
१६	१.६%	७९.४%	१,९२३
६४	६.३%	९१.७%	६८०
१२८	१२.५%	९५.१%	३५०
१,०२४	१००%	९७.८%	४२

अधिकांश उत्पादन कार्यभार के लिए nprobe १६ से ६४ के बीच सबसे अच्छा संतुलन देता है। nprobe=32 से शुरू करें और अपने रिकॉल लक्ष्य के अनुसार समायोजित करें।

उत्पादन संबंधी विचार

पीक्यू बनाम स्केलर क्वांटाइजेशन (एसक्यू) कब चुनें

स्केलर क्वांटाइजेशन (एसक्यू८) हर फ्लोट३२ आयाम को यूइंट८ में बदलता है, स्टोरेज ४ गुना कम करता है। $m=८$ वाला पीक्यू स्टोरेज ६४ गुना कम करता है। पीक्यू तब चुनें जब रैम मुख्य बाधा हो और ५-१५% रिकॉल हानि स्वीकार्य हो। एसक्यू८ तब चुनें जब लगभग बिना हानि के रिकॉल चाहिए और ४ गुना कंप्रेशन पर्याप्त है।

अधिक रिकॉल के लिए री-रैंकिंग

आईवीएफपीक्यू इंडेक्स से एक विस्तारित उम्मीदवार सेट ($k = १००$) प्राप्त करें, फिर उन १०० उम्मीदवारों को एसएसडी पर संग्रहीत मूल फ्लोट३२ वैक्टर के विरुद्ध सटीक एल२ दूरी से पुनः क्रमबद्ध करें। यह दो-चरणीय प्रक्रिया आमतौर पर ९५% से अधिक रिकॉल पुनः प्राप्त करती है।

D_approx, I_approx = index_ivfpq.search(xq, 100)
candidates = xb[I_approx[0]]
D_exact = np.linalg.norm(candidates - xq[0], axis=1)
top10 = I_approx[0][np.argsort(D_exact)[:10]]

ऑप्टिमाइज्ड प्रोडक्ट क्वांटाइजेशन (ओपीक्यू)

मानक पीक्यू मानता है कि सब-वेक्टर सीमाएं स्वतंत्र हैं, जो वास्तविक एम्बेडिंग के लिए शायद ही कभी सच होता है। ओपीक्यू क्वांटाइजेशन से पहले एक सीखी हुई रोटेशन मैट्रिक्स लागू करता है, जो डेटा को सब-वेक्टर सीमाओं के साथ संरेखित करता है और क्वांटाइजेशन त्रुटि को कम करता है। फ़ैस में:

opq = faiss.OPQMatrix(d, 16)
index_opq = faiss.IndexPQ(d, 16, 8)
index = faiss.IndexPreTransform(opq, index_opq)
index.train(xb)
index.add(xb)

ओपीक्यू आमतौर पर बिना किसी अतिरिक्त क्वेरी-समय लागत के मानक पीक्यू की तुलना में रिकॉल में ५ से १० प्रतिशत अंकों का सुधार करता है।

सब-वेक्टर संख्या ($m$) का चयन

$D$ को $m$ से पूर्ण विभाजित होना चाहिए। $D = ७६८$ के लिए: मान्य मान $m = ८, १२, १६, २४, ३२, ४८, ६४, ९६$ हैं।

अंगूठे का नियम: $m = D / ४$ (यानी ४-आयामी सब-स्पेस) से शुरू करें, जो सबसे अधिक रिकॉल देता है। यदि रैम सीमित है, तो $D^*$ को २ या १ आयाम प्रति सब-वेक्टर तक कम करें, कम रिकॉल स्वीकार करते हुए।

प्रशिक्षण डेटा आवश्यकताएं

प्रत्येक उप-क्वांटाइज़र $k^* = २५६$ सेन्ट्रॉइड के साथ के-मीन्स प्रशिक्षित करता है। के-मीन्स को अभिसरण के लिए कम से कम $३० \times k^*$ प्रशिक्षण बिंदु चाहिए, यानी न्यूनतम लगभग ८,००० वैक्टर। सर्वोत्तम परिणामों के लिए, इसका १० से १०० गुना (६५ हजार से ६.५ लाख प्रशिक्षण वैक्टर) उपयोग करें।