hierarchy-metric-transition-theory

Teori Transisi Metrik: Bagaimana Kuantisasi Mengubah Geometri Similarity

Metrik similarity optimal untuk vector search BUKAN properti dari data — ia adalah properti dari representation precision. Vektor float32 pakai cosine (dot product). INT8 pakai cosine atau dot product dengan dequantization. Vektor biner pakai Hamming distance. Ini bukan pilihan — ini keharusan matematis yang didorong oleh information theory: begitu magnitude dihilangkan melalui sign quantization, continuous metric space collapse ke discrete space, dan cosine menjadi tidak bermakna. Catatan ini memformalkan Metric Transition Principle dan memetakan phase diagram dari {precision → optimal metric → compute instruction}.

---

1. Prinsip: Metric Mengikuti Precision

1.1 Inti Pemikiran

Diberikan representasi vektor pada precision $P$ (bit per dimensi), ada optimal similarity metric $M(P)$ yang memaksimalkan search quality di bawah compute constraints dari $P$.

$M(P)=\arg {\max }_{m\in \mathcal{M}}\mathbb{E}[{\text{Recall@k}}_m|\text{precision}=P]$

Dimana $\mathcal{M}$ adalah himpunan semua distance/similarity functions.

Pemetaan empiris:

$P$ (bits/dim)	Precision Level	Optimal $M$	Compute Primitive	Kenapa
32	float32	Cosine / dot product	FMA + reduction	Informasi geometrik penuh
16	float16	Cosine / dot product	FP16 FMA	Range berkurang, metric space sama
8	int8	Cosine (dequantized)	INT8 dot + dequant	Quantization noise tapi linear space terjaga
4	int4	Cosine / Manhattan	INT4 dot + lookup table	Noise ekstrem; koreksi nonlinear diperlukan
1	binary	Hamming distance	XOR + POPCNT	Metric space collapse: sign-only → angular sectors only

1.2 Kenapa Phase Transition? (Bukan Gradual)

Antara $P=8$ (INT8) dan $P=1$ (binary), ada lompatan diskontinu dalam optimal metric. Alasannya information-theoretic:

INT8 pada $P=8$: Setiap dimensi menyimpan 8 bit informasi. Nilai yang direpresentasikan membentuk skala linear (256 level). Dot product $D=\sum x_i{y}_i$ adalah aproksimasi valid dari float32 dot product asli. Cosine similarity valid karena:

$\cos (\mathbf{x},\mathbf{y})\approx \frac{\sum x_i^{(8)}{y}_i^{(8)}}{\sqrt{\sum (x_i^{(8)}{)}^2}\sqrt{\sum (y_i^{(8)}{)}^2}}$

Binary pada $P=1$: Setiap dimensi menyisakan 1 bit — hanya sign yang bertahan. Dot product dari vektor sign-encoded:

${\mathbf{b}}^{(x)}\cdot {\mathbf{b}}^{(y)}={\sum }_{i=1}^d{b}_i^{(x)}{b}_i^{(y)}=|\{i:x_i>0\wedge y_i>0\}|$

Ini BUKAN dot product dalam sense linear algebra — ini adalah count dari co-occurring signs. Dua vektor bisa punya $x_i=1000$ dan $y_i=0.001$ di dimensi yang sama, keduanya di-encode ke $b=1$, tapi magnitude float32 mereka berbeda 6 orde besaran. Cosine akan menangkap perbedaan ini; Hamming tidak.

Transisi dari $P=8$ ke $P=1$ adalah phase transition karena topologi metric space berubah:

Topological Property	Float32/INT8 Space	Binary (Hamming) Space
Linearity	✅ Linear	❌ Tidak linear (XOR space)
Continuity	✅ Continuous	❌ Discrete (hanya {0..d})
Magnitude encoding	✅ Full	❌ Nol (sign only)
Distance type	Metric (Euclidean)	Metric (Hamming)
Triangle inequality	✅	✅
Differentiability	✅	❌ (tidak untuk gradient)

---

2. Phase Diagram Metrik

2.1 Ruang Metrik

graph LR
    subgraph Float32 Space
        A[Full Dot Product] --> B[Cosine Similarity]
        A --> C[Euclidean Distance]
        A --> D[Manhattan Distance]
    end

    subgraph INT8 Space
        E[Quantized Dot Product] --> F[Dequantized Cosine]
        E --> G[SQ8 Euclidean]
    end

    subgraph Binary Space
        H[Popcount] --> I[Hamming Distance]
        H --> J[Jaccard Index]
    end

    B -.->|Quantization| F
    F -.->|Sign Quantization| I
    C -.->|Quantization| G
    G -.->|Binary| I

2.2 Optimal Metric per Vector Database

Vector DB	Default Metric	Precision	Alternative Metrics	Metric Transition Point
FAISS	Inner Product / L2	float32	Cosine, L1, Hamming (IndexBinary* only)	Exact: binary = separate index type
pgvector	Cosine / L2 / IP	float32	Distances only	SQ8 quantization support via halfvec
sqlite-vec	Cosine	float32	L2	Tidak ada binary support
Milvus	Cosine / IP / L2	float32	Hamming, Jaccard, Tanimoto	Binary vectors via BINARY type
Qdrant	Dot / Cosine	float32	L2, Manhattan	Tidak ada binary support
eBVC	Hamming	binary	none	Mulai dari binary — tidak ada fallback

2.3 Biaya Komputasi Transisi

Perubahan optimal metric didorong oleh compute unit cost:

// float32 dot product (1 dim):
//   1 FLOP = 1 FMA = 5 cycles latency
//   1 float32 multiplication + 1 addition
//   Pipelined throughput: 0.5 cycles/dim (AVX-512)
 
// int8 dot product (1 dim):
//   1 VPMADDUBSW + VPMADDWD + VPADDD = ~3 cycles per 32 dims
//   Throughput: ~0.1 cycles/dim
 
// binary Hamming (1 dim = 1 bit = 1/64 u64 word per operation):
//   POPCNT pada 64-bit word: 3 cycles untuk 64 dims
//   Throughput: ~0.047 cycles/dim
 
//   Rasio: binary ~10× lebih cepat dari int8, ~50× lebih cepat dari float32

---

3. Information-Theoretic Bound

3.1 Shannon Rate-Distortion untuk Metric Transition

Untuk query $\mathbf{q}$ dan database vector $\mathbf{x}$ pada float32 precision, cosine similarity $\cos (\mathbf{q},\mathbf{x})$ mendefinisikan ranking “ground truth”.

Setelah kuantisasi ke $P=1$, Bayesian estimator optimal untuk cosine yang diberikan Hamming distance adalah:

$\hat{\cos }(\mathbf{q},\mathbf{x})\approx 1-\frac{2H({\mathbf{b}}_q,{\mathbf{b}}_x)}{d}$

Estimator ini memiliki variance bound:

$\text{Var}[\hat{\cos }]\ge \frac{1}{4d}\cdot \frac{1-\text{IoU}({\mathbf{b}}_q,{\mathbf{b}}_x)}{2}$

dimana IoU adalah Intersection over Union dari sign bits.

Dalam bahasa sederhana: Kualitas estimasi cosine dari Hamming distance membaik seiring $1/\sqrt{d}$ — artinya dimensionality yang lebih tinggi meningkatkan kualitas binary search. Inilah kenapa Jina v5 pada 1024-dim bekerja jauh lebih baik dengan binary quantization dibandingkan model 256-dim.

3.2 Validasi Praktis

Model	d	Cosine→Hamming Recall@10 (relatif terhadap float32)
text-embedding-3-small	1536	89-91%
text-embedding-3-large	3072	92-94%
Jina v5 text-small	1024	94-96%
Jina v5 text-large	2048	96-97%
Cohere Embed v3	1024	92-95%

Tren mengkonfirmasi teori: Dimensionality lebih tinggi → sign encoding lebih baik → informasi lebih sedikit hilang → recall lebih tinggi.

---

4. Implikasi untuk Production Systems

4.1 Multi-Tier Search dengan Metric Switching

Production vector search yang juga menggunakan binary quantization harus mengimplementasikan metric switching:

def search_threshold_hierarchy(query: np.ndarray, top_k: int = 10):
    """
    3-tier search: setiap tier menggunakan metric berbeda
 
    Tier 1: Binary + Hamming (tercepat, 100K+ QPS)
    Tier 2: SQ8 + Cosine (medium, 10K QPS)
    Tier 3: Float32 + Cosine (paling lambat, 1K QPS)
    """
    # Tier 1: Binary cache
    q_bin = binary_quantize(query)
    candidates = hamming_search(q_bin, db_binary, top_k=top_k * 5)
 
    # Cek confidence: jika min Hamming distance << mean_dist, return early
    if candidates[0].distance < 0.1 * d:
        return candidates[:top_k]
 
    # Tier 2: INT8 re-score
    q_int8 = quantize_to_int8(query)
    rescored = cosine_search(q_int8, db_int8[candidates.ids], top_k=top_k)
 
    # Tier 3: Jika masih tidak yakin, full float32 re-rank
    if rescored[-1].score < 0.7:
        final = cosine_search(query, db_float32[rescored.ids], top_k=top_k)
    else:
        final = rescored
 
    return final

Ini mengeksploitasi Metric Transition Principle: setiap tier menggunakan metric optimal untuk precision level-nya, dan kombinasinya mencapai recall mendekati float32 dengan throughput mendekati binary.

4.2 Kapan TIDAK Pakai Binary (dan Tetap dengan Cosine)

Kondisi	Stay with Cosine	Alasan
d < 256	✅	Information loss terlalu tinggi; bound $\sqrt{d}$ terlalu lemah
Embedding isotropy < 0.3	✅	Distribusi sudut tidak uniform → binary collapse
Magnitude membawa makna	✅ contoh: document importance, confidence scores	Sign quantization membuang magnitude
RE-RANKING dilakukan downstream	✅	Reranker mengharapkan continuous scores, bukan Hamming distances
Multi-vector / weighted queries	✅	Query weighting membutuhkan continuous dot product

---

5. Ringkasan Formal

Metric Transition Principle (MTP): Untuk setiap vector similarity search system, ada precision threshold kritis $P^{\ast }$ sehingga untuk semua $P<P^{\ast }$, optimal metric bergeser secara diskontinu dari metric berbasis inner-product kontinu ke metric kombinatorial diskrit (Hamming, Jaccard, atau Tanimoto).

Untuk $P^{\ast }=4$ bit per dimensi (INT4), metric tetap aproksimasi linear. Untuk $P^{\ast }=1$ bit per dimensi (binary), metric HARUS Hamming (atau derived binary metric) — segala upaya menggunakan cosine pada sign-encoded vectors secara matematis ekuivalen dengan Hamming hingga monotonic transform.

Verifikasi: $\cos (\text{sgn}(\mathbf{x}),\text{sgn}(\mathbf{y}))=1-\frac{2H({\mathbf{b}}_x,{\mathbf{b}}_y)}{d}$ untuk balanced encodings, membuktikan metric tersebut terkait secara deterministik.

---

References

1. hierarchy-binary-quantization-hamming-popcount — §3: The Metric Transition, §5: Why Binary Works
2. cosine-similarity-deepdive — §2: Formula & Geometry, §7: Cosine vs Other Metrics
3. cosine-vs-euclidean-vs-dot — Tabel per metrik
4. vector-database-internals-optimization — §4: Quantization comparison
5. hierarchy-recursive-ring-deepdive — Phase transition conceptual framework
6. C. Shannon. “A Mathematical Theory of Communication.” Bell System Technical Journal, 1948.
7. T. Dao et al. “FlashAttention.” 2022.

Koneksi ke Vault

Catatan	Koneksi
hierarchy-binary-quantization-hamming-popcount	§3 Metric Transition — expanded version of this concept
cosine-similarity-deepdive	Cosine formula & geometry — sebagai continuous baseline
vector-database-internals-optimization	§4 Quantization — precision trade-offs
hierarchy-kernel-bypass-networking	eBPF compute constraints → kenapa Hamming adalah satu-satunya opsi