Formal Statement. Multivector retrieval models (e.g., ColBERT) represent documents as sets of token-level embeddings $\{x_{d,1}, \dots, x_{d,n_d}\} \subset \mathbb{R}^d$. Relevance is computed via late interaction (MaxSim):
- Core Problem Definition
- Method
- Token-Aware Clustering (Tac)
- Theoretical Speedup
- Residual Compression
- Tachiom Retrieval Architecture
- Training Configuration
- Experimental Results
Tachiom: Efficient Multivector Retrieval
Core Problem Definition
Formal Statement. Multivector retrieval models (e.g., ColBERT) represent documents as sets of token-level embeddings ${x_{d,1}, \dots, x_{d,n_d}} \subset \mathbb{R}^d$. Relevance is computed via late interaction (MaxSim):
$$S(q, d) = \sum_{i=1}^{n_q} \max_{j \in [n_d]} \text{sim}(q_i, d_j)$$
The storage and computation cost of these token vectors is prohibitive at scale. State-of-the-art solutions use $\kappa$-means clustering to compress token vectors into centroids + residuals, but $\kappa$-means has two critical flaws: 1. Scalability: $O(I \cdot N \cdot \kappa \cdot d)$ per iteration — becomes intractable for millions of centroids on billions of vectors 2. Token-blind: Treats all vectors equally, so frequent tokens (stopwords) dominate the WCSS loss, starving rare but discriminative tokens of centroid representation
Question: Can we design a clustering algorithm that (a) scales to millions of centroids and (b) allocates centroids based on token importance?
Method
Token-Aware Clustering (Tac)
Key observation. Multivector collections exhibit strong correlation between token type and embedding distribution. On Ms Marco-v1, the top 100 most frequent tokens account for 41% of all vectors. Standard $\kappa$-means allocates centroids proportional to frequency, so common tokens get most centroids while rare domain-specific tokens (most discriminative for retrieval) get minimal representation.
Tac's solution. Decompose the global clustering problem into independent per-token subproblems with non-uniform centroid allocation.
Four-stage pipeline:
Phase 1: Tail Handling. Isolate very rare tokens (frequency < threshold $\mu=128$) to prevent complete marginalization.
Phase 2: Damped Scoring. Compute allocation weight for each token $j$: $$w_j = f_j^{\alpha} \cdot v_j$$ where $f_j$ is the token frequency (with square-root damping, $\alpha=0.5$), and $v_j$ is the semantic variance. Damping suppresses the dominance of high-frequency tokens.
Phase 3: Bounding. Enforce: - Hard floor: $\kappa_j \geq \varepsilon=4$ (minimum representation for all active tokens) - Upper bound: $n_j / \kappa_j \geq \theta=39$ (at least $\theta$ vectors per centroid on average)
Phase 4: Budget Reconciliation. Redistribute surplus/deficit to exactly match global budget $\kappa$.
Final step: Perform independent $\kappa_j$-means clustering for each token $j$ with its assigned $\kappa_j$ centroids.
Theoretical Speedup
Standard $\kappa$-means: $O(I \cdot N \cdot \kappa \cdot d)$ for $I$ iterations over $N$ vectors.
Tac: $O(I \cdot \sum_{j=1}^{N_T} n_j \cdot \kappa_j \cdot d)$ where $N_T$ is the number of distinct tokens.
The speedup is lower-bounded by: $$\text{Speedup} \geq \frac{\sum_{j=1}^{N_T} w_j}{\max_{j=1}^{N_T} w_j}$$
This is the ratio of total weight to maximum single-token weight. With square-root damping, the maximum weight is strictly reduced, guaranteeing substantial speedup. Since cumulative vocabulary weight vastly exceeds any single token's weight, the speedup is significant.
Residual Compression
After clustering, residuals (difference between token vector and assigned centroid) are compressed using Product Quantization (PQ) with $M=32$ subspaces and 8-bit codes per subspace. Residuals are normalized before compression since Tac's non-uniform allocation produces heterogeneous residual magnitudes.
Tachiom Retrieval Architecture
Combines Tac clustering with a two-phase retrieval system:
Phase 1: HNSW Graph-Based Gathering. - Build an HNSW proximity graph over centroids ($M=32$ neighbors, $ef_c=1500$) - For query $q$ with tokens ${q_1, \ldots, q_{n_q}}$, find nearest centroids for each query token - Approximate MaxSim score using only centroid-level interactions: $$\tilde{S}(q, d) = \sum_{i=1}^{n_q} \tilde{s}_i(d)$$ - Truncate to top $\kappa_d$ documents using partial scores - Apply Candidates Pruning (CP) with parameter $\alpha$
Phase 2: PQ-Optimized Refine. - For pruned candidates, compute full MaxSim using centroids + PQ-compressed residuals - Cache-optimized document layout: all centroid IDs stored contiguously, followed by all PQ codes - SIMD-vectorized distance table computation
Training Configuration
| Parameter | Value |
|---|---|
| Implementation | Rust 1.92.0-nightly |
| Library | kANNolo |
| Hardware | Intel Xeon Silver 4314 @ 2.40GHz, 64 threads |
| Clustering iterations | 10 |
| Tail threshold $\mu$ | 128 |
| Tail cap $\tau$ | 256 |
| Min centroids $\varepsilon$ | 4 |
| Vectors/centroid $\theta$ | 39 |
| PQ subspaces | 32 |
| PQ bits per subspace | 8 |
| HNSW neighbors $M$ | 32 |
| HNSW $ef_c$ | 1500 |
Experimental Results
Datasets
- Ms Marco-v1: 2.4M passages, 266M token vectors, 2,931 queries
- LoTTE: Out-of-domain evaluation
Clustering Speed (Figure 2)
| Method | 262K centroids | 4M centroids |
|---|---|---|
| Faiss (MKL) | timeout (>24h for 131K) | — |
| Faiss (AVX2) | timeout (>24h for 131K) | — |
| FastKMeans-rs | timeout (>24h for 131K) | — |
| Tac | 8 minutes | 102 minutes |
Speedup over $\kappa$-means: - Up to 84x vs. Faiss with MKL - Up to 247x vs. Faiss (AVX2) - Up to 230x vs. FastKMeans-rs
Clustering Quality (MRR@10 on Ms Marco-v1, Figure 2 top)
At every centroid budget, Tac achieves equal or superior MRR@10 compared to $\kappa$-means, despite being dramatically faster. This validates that token-aware allocation improves centroid quality for retrieval.
End-to-End Retrieval (Table/Figure 3)
Centroid budgets: LoTTE: ~2M centroids ($2^{21}$); Ms Marco: ~4M centroids ($2^{22}$)
Search parameters: $\kappa_c \in {15,20,40,80,100,120}$, $\kappa_d \in {250,500,1000,2000,4000}$, $\alpha \in {0.35,0.40,0.45,0.50,0.55,0.60,0.65,0.70}$
Tachiom achieves up to 9.8x faster end-to-end retrieval compared to state-of-the-art systems (EMVB, Warp, IGP) while maintaining comparable or superior effectiveness (MRR@10 / Success@5).
Comparison with Existing Systems
| System | Clustering | Gathering | Refine | Speedup vs. ColBERTv2 |
|---|---|---|---|---|
| ColBERTv2 | $\kappa$-means | Inverted lists | Full residuals | 1x |
| Plaid | $\kappa$-means | Centroid interaction | PQ | ~3x |
| EMVB | $\kappa$-means | Bitvector prefilter | Optimized PQ | ~5x |
| Warp | $\kappa$-means | Centroid interaction + XTR | PQ | ~6x |
| IGP | $\kappa$-means | Graph over centroids | PQ | ~7x |
| Tachiom | Tac (token-aware) | HNSW over centroids | Cache-optimized PQ | up to 9.8x |
Critical Analysis
Strengths
- Massive speedup: 247x faster clustering is not incremental — it fundamentally changes what's possible (millions of centroids in minutes)
- Theoretical grounding: The speedup lower-bound proof is clean and insightful
- Token-aware design: The frequency-weighted allocation directly addresses a real problem in multivector retrieval
- Open source: Released on GitHub (https://github.com/TusKANNy/tachiom)
- End-to-end system: Not just clustering — the full Tachiom architecture with HNSW + optimized PQ is practical
Weaknesses and Open Questions
- Ms Marco-centric: Primary evaluation on Ms Marco-v1; LoTTE evaluation is more limited. Need more diverse domain evaluation
- Fixed vocabulary assumption: Tac relies on token identity, which assumes a fixed tokenizer. May not generalize to subword tokenizers with large vocabularies as well
- WCSS optimality gap: Independent per-token clustering cannot capture cross-token relationships. The paper shows this doesn't hurt retrieval quality, but theoretical analysis is limited
- Comparison fairness: Some competitors (EMVB, Warp) use different PQ variants; the speedup numbers may reflect implementation quality as much as algorithmic advantage
- Memory overhead of HNSW: The graph index adds memory overhead not fully accounted for in the efficiency analysis
- Scalability to billion-scale: Evaluated on 266M vectors; real-world systems may have billions
Implications for Our Work
- For retrieval systems: Tachiom's approach could dramatically reduce the cost of multivector retrieval in RAG pipelines
- For embedding research: Demonstrates that token-level structure can be exploited for efficiency gains
- For inference optimization: The centroid-only gathering phase idea is analogous to early-exit strategies — cheap approximation first, expensive computation only for promising candidates
- Practical consideration: The Rust implementation and open-source release make this immediately deployable
Related
- embedding — Text embedding methods and representations
- retrieval — Information retrieval paradigms
- inference — Inference optimization techniques
- qdrant-vector-search — Vector similarity search for RAG