Quodar: A Query-Aware, Partition-Based Framework for Out-of-Distribution Approximate Nearest Neighbor Search

Cross-modal retrieval relies on efficient approximate near est neighbor search (ANNS) to find semantically similar items across modalities. However, due to distributional shifts between modalities, queries often become out-of-distribution (OOD), leading to significant performance degradation in existing ANNS methods. To address this, we propose Quodar, a novel hybrid optimization framework that enhances partition-based ANNS under OOD conditions through a dynamic, query aware mechanism. First, we train a machine learning model to predict the most relevant partitions for a given query, which effectively mitigates the “partition search explosion” caused by distributional shifts. Second, to counter the scattered distribution of nearest neighbors, we design a select tive replication strategy that moves critical vectors to higher-probability partitions. Experiments on three real-world cross-modal datasets demon strate that Quodar achieves a superior accuracy-efficiency trade-off. Our method consistently reduces the number of visited vectors by 50%-70% compared to the IVF baseline, showcasing a significant improvement in search efficiency under challenging OOD conditions.