Overview
TileMaxSim is a system of IO-aware Triton kernels designed to enhance the performance of MaxSim scoring on GPUs, particularly for multi-vector retrieval models such as ColBERT. The primary objective is to address inefficiencies in existing GPU implementations that result in underutilized hardware performance. This is achieved by mitigating a severe bandwidth gap identified in naive MaxSim implementations, which otherwise reach only 5-18% of peak HBM bandwidth.
Research Context
Multi-vector retrieval models, exemplified by ColBERT, utilize fine-grained, token-level MaxSim scoring to achieve high accuracy. Despite this, current GPU implementations are observed to leave a significant portion of hardware performance unused. A roofline analysis of MaxSim on modern GPUs revealed that naive implementations suffer from a substantial bandwidth gap. This gap arises because they materialize the $N_q \times N_d$ similarity matrix, leading to wasted memory traffic as data is consumed once and then discarded. Such an approach consumes memory traffic inefficiently, failing to fully leverage high-bandwidth memory (HBM) capabilities.
Approach
TileMaxSim integrates a family of IO-aware Triton kernels to overcome the identified bandwidth limitations. The approach is structured around three core mechanisms:
- Multi-query SRAM Tiling: This technique streams document embeddings through shared memory. It accumulates per-query-token maxima in registers, ensuring that each embedding is read from HBM exactly once.
- Dimension Tiling: This method partitions the embedding dimension into 128-wide chunks. This enables scoring for embeddings where $d > 128$, which would otherwise overflow shared memory.
- Fused Product-Quantization Scoring: This mechanism employs shared-memory lookup tables for scoring, which is reported to reduce HBM I/O by up to approximately 31x.
The design of TileMaxSim aims to improve HBM bandwidth utilization by minimizing redundant data movement and optimizing memory access patterns.
Findings
On NVIDIA H100 GPUs, TileMaxSim achieved 80.2% of peak HBM bandwidth. It demonstrated a scoring rate of 82 million documents per second (71.6 million documents per second on real MS MARCO passages). This represents a 220x speedup compared to loop-based scoring implementations. Specific comparisons include:
- 6.5x speedup over fused PyTorch implementations.
- 6.6x to 8.5x speedup over
torch.compileapproaches. - 469x the scoring throughput of WARP's CPU engine on the same node.
Regarding retrieval quality, TileMaxSim maintained exact retrieval quality across MS MARCO and three BEIR benchmarks, with rankings matching reference MaxSim implementations. When integrated as a drop-in replacement within ColBERTv2/PLAID, TileMaxSim reduced scoring latency for 100,000 candidates from 268 ms to 1.2 ms, resulting in a 98% reduction in end-to-end latency. Further observations include constant throughput for document counts ranging from 100,000 to 500,000, support for data-parallel multi-GPU sharding, robustness across embedding dimensions from 64 to 768, and compatibility with FP16, BF16, and FP32 numerical precisions.
Key Limitations Mentioned by Researchers
The abstract notes that concurrent work independently develops an IO-aware fused MaxSim kernel. The distinct aspects of TileMaxSim are its dimension tiling capability for $d > 128$ and its fused product-quantization scoring method. No other limitations were explicitly mentioned.