The Centroid Bottleneck Is Real
If you have ever spent six hours watching a k-means job chew through 500 million token embeddings, you know the pain. The algorithm is blind to token identity. It lets high-frequency stopwords monopolize the centroid budget while rare, discriminative terms starve. A new paper from ISTI-CNR and the University of Pisa introduces Tachiom. This multivector retrieval system solves this by decomposing clustering into independent per-token subproblems. The authors report up to 247× faster clustering and 9.8× retrieval speedup over state-of-the-art systems. That sounds too good to be true. Let us see why it is not.
The Problem
Multivector models like ColBERT encode documents as sets of token-level vectors. To make them searchable, we must compress these vectors. The industry standard is a two-phase "gather-and-refine" strategy. First, use coarse centroids to find candidate documents. Second, compute full MaxSim scores on the residuals for those candidates.
The bottleneck is the centroid generation. Standard k-means treats all token embeddings as a uniform blob. In practice, common tokens appear millions of times. Domain-specific terms appear hundreds. Because k-means minimizes Within-Cluster Sum of Squares (WCSS), it allocates the vast majority of centroids to the frequent tokens. This minimizes overall error. This is inefficient. Frequent tokens are easy to approximate. Rare tokens carry the semantic signal needed for retrieval. By ignoring token frequency, standard clustering wastes capacity on noise. It leaves the critical signals under-resolved. Furthermore, k-means scales poorly with dataset size. It takes hours or days to converge on large corpora. This limits the granularity of the centroids we can afford to build.
How It Works
Tachiom replaces standard k-means with Token-Aware Clustering (Tac). It pairs this with a hierarchical graph index. The core insight is simple. We should not cluster all vectors together. We should cluster them by token type.
Tac executes in four distinct phases:
- Tail Handling: Extremely rare tokens (Micro tokens, occurring fewer than $\mu$ times) are guaranteed exactly one centroid. Small tokens ($\mu \le n < \tau$) get two. This prevents marginalization of low-frequency but high-value terms.
- Damped Scoring: For the remaining "Active" tokens, the system calculates a weight $w_j = \sqrt{n_j \cdot s_j}$. Here $n_j$ is frequency and $s_j$ is semantic variance. The square-root damping ensures that highly frequent tokens do not monopolize the budget. High variance pushes for more resolution.
- Bounding: The algorithm enforces a floor ($\epsilon$) and ceiling ($\theta$) on centroid allocation per token. This prevents over-clustering well-behaved tokens. It also prevents under-representing difficult ones.
- Budget Reconciliation: Surplus or deficit centroids are redistributed to hit the target budget exactly.
Once the weights are calculated, Tac runs independent k-means clusters for each token type. Because these subproblems are independent, they parallelize trivially across CPU cores. The theoretical speedup is bounded by the ratio of total weight to the maximum single-token weight. The authors show this yields massive gains.
With fine-grained centroids in place, Tachiom shifts the retrieval architecture. Instead of gathering via token-level interactions, it builds an HNSW graph over the centroids. Each centroid maintains an inverted list of document IDs. During the gather phase, the system traverses the HNSW graph to find nearest centroids. It accumulates partial scores based solely on centroid-document interactions. This bypasses expensive token-level math entirely.
For the refine phase, Tachiom uses a cache-optimized Product Quantization (PQ) layout. Standard PQ implementations suffer from scattered memory accesses. They compute distances for multiple query tokens against the same document token. Tachiom reorganizes distance tables into a three-level hierarchy. This includes Macro-blocks, Centroid blocks, and Query token micro-blocks. This ensures contiguous memory reads. It accelerates the final MaxSim computation by up to 3.8× compared to naive PQ.
[Figure 1] illustrates this distance table layout. It shows how query token distances are grouped into contiguous micro-blocks. This eliminates bandwidth bottlenecks.
Numbers
The authors evaluated Tachiom on Ms Marco-v1 (8.8M passages, 598M token vectors) and LoTTE-pooled (2.4M passages, 266M token vectors). All experiments ran on an Intel Xeon Silver 4314 CPU with 64 threads. This hardware is a mid-range server processor. It lacks the specialized acceleration of modern GPUs. Expect slower absolute latencies on consumer hardware.
Clustering Speed: Tac achieves up to 247× faster training than Faiss k-means. It is 230× faster than FastKMeans-rs. The paper reports clustering 262K centroids for Ms Marco-v1 in just 8 minutes. Crucially, Tac scales to 4M centroids in 102 minutes. Baselines timed out at 24 hours. They were unable to exceed 131K–524K centroids depending on optimization.
[Figure 2] plots these results. It shows that Tac reaches higher MRR@10 scores in a fraction of the time required by standard k-means.
Retrieval Latency: Tachiom delivers up to 9.8× faster end-to-end query processing. It beats state-of-the-art systems like Emvb, Warp, and Igp. On Ms Marco-v1, Tachiom achieves an average query time of 10–15 ms. Competitors take 55–98 ms. Tachiom matches or exceeds their MRR@10 effectiveness. The paper notes that Tachiom matches the peak effectiveness of Emvb. Emvb relies on computationally expensive joint optimization methods (JMPQ/OPQ). Tachiom uses standard PQ.
What's Missing
The paper is rigorous on the benchmarks it chooses. Several gaps remain for practitioners considering adoption.
First, generalizability beyond ColBERTv2 is untested. The entire architecture is tuned around the specific properties of ColBERTv2 embeddings. The authors acknowledge this limitation. They note future work will test Tac on other encoders. If your stack uses a different multivector model with different embedding distributions, the "tail handling" thresholds ($\mu$, $\tau$) may need significant re-tuning.
Second, the theoretical speedup bound assumes ideal conditions. The lower-bound derivation ignores the overhead of budget reconciliation and tail handling logic. In practice, if your vocabulary has extreme skew, the parallelization benefits might diminish. The paper does not report wall-clock timings for pathological vocabularies.
Third, memory footprint details are sparse. The paper discusses cache optimization. It does not provide a detailed breakdown of RAM requirements. We lack clarity on the HNSW graph versus PQ residuals. The HNSW graph stores graph edges and centroid pointers. PQ residuals store compressed vector differences. Knowing the exact memory ceiling for both components is critical. Engineers planning deployment on constrained hardware need to know if the HNSW graph fits in L3 cache. The paper focuses on CPU throughput. It does not analyze memory bandwidth constraints. This could become the new bottleneck.
Should You Prototype This
Yes.
The code is available at https://github.com/TusKANNy/tachiom. The implementation is in Rust. It leverages the kANNolo library. This dependency is a potential installation hurdle. Rust toolchains can be verbose to set up. However, it also promises raw performance and memory safety.
The clustering algorithm (Tac) is the highest-leverage component here. Even if you do not adopt the full Tachiom retrieval pipeline, replacing your k-means indexer with Tac’s token-aware decomposition is a low-risk change. It likely yields immediate speedups. It also improves centroid quality. The abstraction boundary is clear. You feed in token embeddings. You get back centroids. The rest is plumbing. Given the 247× speedup claim, a quick prototype to verify the clustering time on your own data is a ten-minute investment. It could save hours of infra time. If your current indexer is choking on scale, this is worth trying immediately.