TL;DR
Multi-vector retrieval models typically assign a fixed number of embeddings to every sample, wasting computation on simple queries while bottlenecking complex ones. This paper introduces Sample-Adaptive Multi-Vector Representation (SAMVR) and the AdaptiveEmbed framework, which dynamically allocates the number of vectors per sample based on its actual retrieval utility. Across image, video, and audio benchmarks, it outperforms fixed-capacity baselines while using an average of just ~2 vectors per sample compared to fixed budgets of up to 40.
What Problem Does This Paper Address?
Multimodal retrieval is rapidly moving away from compact single-vector embeddings (like standard CLIP) toward more expressive multi-vector representations (like ColBERT or ColPali) to capture fine-grained, cross-modal details. However, existing multi-vector methods suffer from a "one-size-fits-all" limitation: they assign the exact same number of vectors to every single sample regardless of its actual complexity or retrieval difficulty.
This uniform allocation ignores the inherent heterogeneity of data. A simple image of a clear blue sky requires far less representation capacity to be successfully retrieved than a complex, cluttered scene containing dozens of interacting objects. Treating capacity as a fixed global constant leads to severe computational inefficiencies at scale. The authors formalize this challenge as a new problem setting: Sample-Adaptive Multi-Vector Representation (SAMVR), where representation capacity is treated as a sample-dependent decision variable driven by retrieval utility.
Methods
To realize the SAMVR setting, the authors propose AdaptiveEmbed, a unified two-stage framework:
- Embedding Set Learning (Stage I): The model learns a structured pool of candidate embeddings using Multi-Group Contrastive Learning (MGCL). Instead of using the standard asymmetric MaxSim operator common in late-interaction models, the authors introduce Set-to-Set Similarity (SetSim). SetSim computes an exact, bijective one-to-one matching between embedding sets. Because it is symmetric, a single embedding set can serve both retrieval directions (e.g., text-to-image and image-to-text) seamlessly.
- CAES Construction (Stage II): To build the final Content-Adaptive Embedding Set (CAES), a lightweight Token Selection Transformer (TST) determines the optimal capacity for each sample. It uses Utility Policy Optimization (UPO) and Marginal Utility Allocation (MUA) to iteratively decide whether to activate additional vectors or stop, guided dynamically by feedback matrix signals from a small retrieval bank.
Datasets
The framework was evaluated across eight distinct benchmarks spanning three multimodal domains:
- Image–Text: COCO (used as the primary training source), Flickr30K, ADE20K, and OpenImages (evaluated strictly zero-shot to test generalization).
- Video–Text: ActivityNet and DiDeMo.
- Audio–Text: MACS and Clotho.
Key Insights and Ideas
- Retrieval Utility $\neq$ Surface Complexity: A highly detailed text narrative might only need a single coarse vector to be uniquely identified in a gallery, whereas a short caption for a visually ambiguous scene might require maximum vector capacity to avoid false positives. Capacity should be dictated by how hard a sample is to distinguish within a gallery, not just how much content it contains.
- The Danger of Token Collapse: Standard late-interaction mechanisms (like MaxSim) allow multiple query tokens to match onto the same database token. As capacity scales up, tokens tend to collapse onto identical targets. By enforcing a strict one-to-one assignment, SetSim ensures that expanding capacity actually introduces novel, complementary information.
- The Power of Early Stopping: The majority of retrieval queries are "easy" cases. By allowing the model to terminate token generation early when marginal utility drops, the system drastically cuts down on average token counts without sacrificing retrieval accuracy.
Key Results
- Superior Efficiency and Accuracy: On the COCO image-text benchmark, AdaptiveEmbed achieved a higher mean Average Precision (63.45% T2I / 61.14% I2T) than fixed-capacity MetaEmbed baselines, while activating an average of only 2.1 tokens per query (compared to fixed baselines using 3 to 40 tokens).
- Robust Zero-Shot Generalization: When tested zero-shot on the massive OpenImages gallery (over 546,000 items), AdaptiveEmbed outperformed all fixed-capacity configurations in both retrieval directions, proving that the learned allocation policy generalizes well across domains.
- Cross-Modal Versatility: The benefits consistently extended to video and audio. On ActivityNet, AdaptiveEmbed achieved top-tier multi-vector performance utilizing an average of just 1.9 tokens.
Limitations and Future Work
- The Oracle Gap: A significant performance gap still remains between the learned policy and the theoretical "Oracle" upper bound (which exhaustively scores all token combinations). Closing this gap will require finer decision granularities and richer utility signals.
- Gallery-Side Storage Bottleneck: While AdaptiveEmbed optimizes matching time by reducing query tokens, the active token positions are query-dependent. This means gallery items must still store their full candidate embedding sets in memory so the correct positions can be read off at runtime. Reducing gallery-side storage remains an open challenge.
Summary updated