PaperlayerView exact revision on arXiv

Source-linked AI summary

CORAL: Cross-modal Vector Retrieval via Incremental Graph Construction at Scale

Shixin Wan, Guoyu Hu, Yifan Wu, Ke Chen, Lidan Shou

arXiv:2610.11230v1cs.DB

TL;DR

Cross-modal retrieval is an OOD search problem, and existing indexes are limited in their use of query information, GPU parallelism, and dynamic updates. CORAL combines incremental graph construction, coverage-aware pruning, GPU-oriented projection, and topology-aware updates. It reports up to 1.6 times the throughput at matched recall, reduces construction time by up to 56%, and remains robust under updates at billion scale.

  • Problem

    Cross-modal retrieval uses query and indexed vectors from different modalities, while existing OOD indexes have limitations in query coverage, GPU parallelism, and dynamic-update support.

    Source: §1 · p. 2

  • Method

    CORAL incrementally builds a graph index using coverage-aware pruning and GPU-oriented neighborhood projection, with topology-aware insertion and deletion.

    Source: §1 · p. 2

  • Results

    CORAL achieves up to 1.6 times the throughput at matched recall and reduces construction time by up to 56% compared with existing methods.

    Source: §1 · p. 2

  • Takeaways & Limitations

    CORAL remains robust under dynamic updates and scales to billions of vectors.

    Source: §6 · p. 12

    The theoretical routing analysis depends on three modeling assumptions about beam search, including entry-cost monotonicity, entry proximity, and no local-cost penalty.

    Source: §3.5 · p. 8

Abstract

from arXiv · show

Cross-modal vector retrieval is widely used in multimodal systems, such as search engines and vector databases. It typically operates in out-of-distribution (OOD) settings, where query vectors follow a distribution that differs from that of the vectors stored in the database. In such cases, conventional indexes suffer significant performance degradation, and even methods specially designed for OOD remain limited by inefficient use of query modal characteristics, restricted GPU parallelism, and inadequate support for dynamic updates. We present CORAL, a novel GPU-accelerated graph-based vector index for scalable cross-modal retrieval, featuring hierarchical memory management that spans GPU, CPU, and disk. Specifically, CORAL incrementally incorporates the characteristics of query modality and terminates index construction timely. Crucially, it introduces coverage-aware adaptive pruning to address the imbalanced coverage of the query vector's neighbors. Moreover, CORAL presents a fully neighborhood-aware projection approach to efficiently utilize GPUs for highly parallel index construction, and a targeted connectivity enhancement method to refine the index structure. Besides, CORAL also supports modal-semantics-based vector insertion and topology-repairing deletion that restore node connectivity. Experimental results demonstrate that CORAL outperforms existing methods with up to 1.6 times the throughput at matched recall while reducing construction time by up to 56%. Furthermore, it exhibits remarkable resilience under dynamic updates and remains effective at the billion scale.

1 INTRODUCTION

Cross-modal retrieval uses query and base vectors from different modalities, creating an OOD setting in which existing indexes face coverage, GPU-parallelism, and update-maintenance challenges. CORAL addresses these challenges with incremental graph construction and topology-aware updates, and reports higher throughput at matched recall with lower construction time.

1 INTRODUCTION

  • Skewed query coverage leaves some base nodes weakly connected while repeatedly retrieved regions receive excessive updates.Adding more auxiliary queries incurs substantial construction overhead but yields limited structural improvement when updates remain concentrated on well-connected nodes.Source: §1 · p. 2
  • Existing graph updates offer limited parallelism for GPUs, while sequential node expansion restricts GPU acceleration during search.Fine-grained updates affect few nodes per query, hindering batching; graph search also sequentially expands nodes.Source: §1 · p. 2
  • Localized insertions and lazy-tombstone deletions can leave inserted vectors disconnected from the global graph and impede effective rewiring.Stale deleted nodes occupy limited out-degree slots, allowing graph structure to drift from the updated data distribution.Source: §1 · p. 2
  • CORAL incrementally processes batched query workloads and uses a convergence test for early termination, alongside coverage-aware adaptive pruning.Its pruning promotes coverage in underexplored regions while pruning redundant updates on frequently visited nodes.Source: §1 · p. 2
  • Fully Neighborhood-Aware Projection enables bulk-synchronous GPU construction; CPU–GPU co-processing, hierarchical GPU-to-disk storage, and Targeted Connectivity Enhancement address scale and residual connectivity gaps.CORAL also inserts vectors using auxiliary queries and repairs local topology after deletions rather than relying on lazy tombstones.Source: §1 · p. 2
  • Up to 1.6× throughput at matched recall and up to 56% lower construction time distinguish CORAL from existing methods.After replacing 50% of the original dataset, CORAL sustains Recall@100 around 98%, while the best competitor falls below 90% after only 10% replacement.Source: §1 · p. 2

2 BACKGROUND

The background defines OOD nearest-neighbor search, formalizes cross-modal retrieval, and motivates CORAL through construction inefficiency, skewed coverage, and connectivity challenges during updates. It then describes CORAL's early termination, adaptive pruning, and topology-aware update mechanisms.

2.1 Out-of-Distribution ANNS

  • OOD ANNS arises when query and base vectors follow different distributions; auxiliary query vectors guide graph construction by connecting their nearest base vectors.Graph search uses query-aware edges as shortcuts, while weak connectivity or isolated nodes can trap traversal and reduce recall.Source: §2.1 · p. 3
  • The OOD ANNS construction workflow computes query neighborhoods, projects them into a bounded-degree graph, and enhances connectivity afterward.Traditional connectivity enhancement typically involves all nodes; after construction, search proceeds by greedy graph traversal with a bounded beam budget.Source: §2.1 · p. 3

2.2 Problem Statement

  • Cross-modal retrieval seeks the top-k nearest base vectors for a query embedded from a different modality, with approximate quality measured by Recall@k.Exhaustive computation is prohibitive at scale, motivating an approximate result set.Source: §2.2 · p. 3

2.3 Motivation

  • Existing OOD methods' construction cost depends on auxiliary-query volume, but reducing that volume by 50% can retain comparable index performance.On T2I-10M, recall converges at 85.25% after about 4.6M queries while construction cost continues to grow.Source: §2.3 · pp. 3–4
  • CORAL batches auxiliary queries and stops construction when evaluation metrics converge, avoiding unnecessary neighborhood computations and graph updates while preserving retrieval performance.This targets diminishing benefit from ingesting additional queries after the graph structure has gradually converged.Source: §2.3 · p. 4
  • In RoarGraph on T2I-10M, over 30% of nodes remain isolated after 1M queries, and the top 1% of base nodes account for 15.04% of access.CORAL's Coverage-Aware Adaptive Pruning monitors newly covered isolated nodes and removes high-frequency nodes from subsequent neighborhood acquisition when that fraction falls below 10%.Source: §2.3 · p. 4
  • Accumulated updates can degrade retrieval when localized insertions fail to maintain global connectivity and deletion strategies stagnate or destroy local links.CORAL strengthens inserted-node global connectivity through graph search, physically removes deleted nodes, and reconnects affected neighbors.Source: §2.3 · p. 4

3 CORAL

This section presents CORAL’s cross-modal graph index, covering query-guided incremental construction, topology-aware updates, and its shared FNAP primitive, alongside coverage-aware pruning, connectivity refinement, GPU parallelism, and hierarchical storage. It also analyzes how CAAP, FNAP, and TCE relate to query coverage, structural gain, and navigability, with construction results supporting improved connectivity and query-aligned navigability.

3.1 Overview

  • CORAL’s two phases are incremental index construction and topology-aware updates, sharing FNAP; its hierarchical index spans GPU, main memory, and disk.The construction phase ingests auxiliary queries in batches; the update phase supports insertion and deletion alongside ongoing searches.Source: §3.1 · pp. 4–5

3.2 Incremental Index Construction

  • Hierarchical storage keeps the complete graph on disk and caches active nodes in main memory, loading necessary metadata for batched updates to reduce data movement and support million- to billion-scale datasets.Neighbor metadata is read-only and shareable, while adjacency-list updates use exclusive access.Source: §3.2 · p. 5
  • CAAP redirects kNV acquisition away from frequently retrieved hot nodes, while convergence monitoring stops query-guided updates when they are no longer useful and TCE repairs isolated nodes and refines hot-node neighborhoods.CORAL uses hot nodes as search entry points; its default TCE selection ratio ρ_CE is 0.5.Source: §3.2 · pp. 5–6
  • FNAP makes every node in a query’s kNV an adjacency-update pivot, using neighborhood information more fully while exposing parallelism and preserving degree constraints and graph stability.For isolated pivots it considers all other kNV nodes; for non-isolated pivots it considers existing neighbors plus isolated kNV nodes, then applies NAP pruning.Source: §3.2 · p. 6

3.3 Topology-Aware Index Update

  • Insertions use accompanying or surrogate query vectors to find neighbors, then FNAP and graph search establish and strengthen connections; deletions reconnect a removed node’s in- and out-neighbors with FNAP.This guides insertion by query-modal semantics and repairs topology after physical node removal.Source: §3.3 · pp. 6–7

3.4 GPU Primitives

  • GPU primitives parallelize FNAP’s pairwise distance and pivot updates, and full-expansion beam search expands all unvisited beam nodes concurrently using GPU blocks and warps.CORAL combines hot-node entry points with farthest-point-sampled entries to cover graph regions beyond the query-aligned hot nodes.Source: §3.4 · p. 7

3.5 Theoretical Analysis

  • CORAL’s theoretical analysis establishes increased query-coverage entropy under CAAP, no worse isolated-node coverage under FNAP, and lower expected routing cost for TCE with hot-node entries under stated routing conditions.The routing-cost result assumes entry-cost monotonicity, closer hot-node entries, and no local-cost penalty.Source: §3.5 · p. 8
  • On T2I-10M, the top 1% most-accessed nodes receive about 15× the uniform access share, supporting the hot-node basis for the r=0 condition.The analysis uses hot-node statistics to support the strict inequality at r=0.Source: §3.5 · p. 8
  • Raising ρ_CE from 0.5 to 1 lowers throughput by 10%, indicating that exhaustive refinement does not reduce local traversal cost.The passage cites this as empirical corroboration of condition (R3).Source: §3.5 · p. 8
  • With equal auxiliary-query budgets, CAAP balances query coverage, FNAP extracts more structural gain per query’s kNV, and TCE refines nodes that dominate search efficiency.Together, these designs improve graph connectivity and query-aligned navigability in the OOD scenario.Source: §3.5 · pp. 8–9
  • After 1M queries, CORAL lowers T2I-10M’s isolated-node ratio below 10%, while RoarGraph remains above 30% (Figure 2(c)).The passage connects this result to improved coverage balance and connectivity.Source: §3.5 · p. 9

4 EVALUATION

The evaluation compares CORAL with OOD and ID ANNS baselines across retrieval effectiveness, update robustness, construction cost, parameter sensitivity, and component contributions.

4.1 Experimental Setup

  • Experiments span five datasets and scales from 1M to 1B vectors, with GPU, main-memory, and disk configurations selected to fit dataset scale.The evaluation uses Recall@10 and Recall@100, throughput in QPS, and average hops; throughput is generally reported at Recall@100 = 95%.Source: §4.1 · p. 9, §4 · p. 9

4.2 Effectiveness of Vector Retrieval (EQ1)

  • CORAL reaches 1.4× the best-baseline throughput on T2I-10M and 1.6× at Recall@100 = 98% on WebVid-2.5M, while sustaining strong performance across 50 update steps.On T2I-10M it maintains Recall@100 around 98%; on LAION-10M it maintains approximately 95% recall and the highest throughput throughout the updates.Source: Figure 7 · p. 10, §4.2 · p. 11, Figure 10 · p. 11
  • At matched recall, CORAL improves average throughput by 3.03× over FAISS-IVF, 1.74× over CAGRA, 1.70× over RoarGraph, 2.27× over ParaGraph, and 1.39× over CDMG+.It also achieves the lowest average hops in most cases, requiring approximately 25%–36% fewer hops than RoarGraph and ParaGraph and approximately 20% fewer than CDMG+.Source: §4.2 · p. 10, Figure 8 · p. 10

4.3 Cost Analysis (EQ2)

  • CORAL takes 635 s on T2I-10M and 1341 s on LAION-10M, reducing construction time by up to 56% relative to the fastest OOD ANNS baselines.On T2I-10M, it takes 635 s versus ParaGraph’s 3583 s, a 5.6× speedup; bounded-degree graph baselines have comparable storage costs.Source: §4.3 · p. 11, Figure 11 · p. 11

4.4 Parameter Sensitivity Analysis (EQ3)

  • Increasing k_b from 10 to 100 improves throughput by 92%, while increasing ρ_CE from 50% to 100% reduces throughput by 10%.The reported analysis finds diminishing returns as |Q_b| and k_b increase and supports k_b = 100 and ρ_CE = 50% as defaults.Source: Figure 12 · p. 11, §4.4 · p. 12

4.5 Ablation Study (EQ4)

  • Removing FNAP reduces QPS from 10647.30 to 3397.55 on T2I-10M and from 3099.81 to 1703.87 on LAION-10M, the largest ablation drop.CAAP alone yields 1.46× and 1.16× speedups, TCE alone yields 2.63× and 1.69×, and full CORAL yields 3.28× and 1.82× over the variant without CAAP and TCE.Source: §4.5 · p. 12, Table 1 · p. 12

5 RELATED WORK

Prior work addresses cross-modal OOD search, dynamic updates, and GPU acceleration through distinct approaches; CORAL combines incremental coverage-aware graph construction with targeted refinement and hierarchical storage.

OOD ANNS in Cross-Modal Scenarios

  • RoarGraph, ParaGraph, and CDMG address cross-modal OOD search, while CORAL targets their costly kNV computation and redundant connectivity enhancement with incremental coverage-aware construction.LeanVec addresses OOD search at the representation layer through query-aware projection with quantization.Source: §5 · p. 12

Dynamic and Streaming OOD ANNS

  • FreshDiskANN and SPFresh support incremental insertions but target ID settings; CORAL instead combines local insertion with global refinement and physically removes deleted nodes through topological repair.RoarGraph's localized insertion limits global integration, while tombstone deletion accumulates redundancy and degrades search efficiency.Source: §5 · p. 12

GPU-Accelerated OOD ANNS

  • ParaGraph adapts RoarGraph to GPUs, but its pivot-centric construction limits parallelism and caps scalability at 10M vectors; CORAL combines full-neighborhood projection, targeted refinement, and hierarchical storage.Source: §5 · p. 12

6 CONCLUSION

CORAL improves retrieval effectiveness, reduces construction time, remains robust under updates, and scales to billions of vectors. The authors identify evolving data distributions and heterogeneous CPU–GPU–disk execution as future work.

6 CONCLUSION

  • CORAL reduces construction time by up to 56% over existing baselines, remains robust under updates, and scales to billions of vectors.Experiments also showed improved retrieval effectiveness.Source: §6 · p. 12
  • CORAL combines incremental query-guided construction, CAAP, FNAP, TCE, and topology-aware dynamic updates in a GPU-accelerated graph index for cross-modal retrieval.Source: §6 · p. 12
  • Future work will address evolving data distributions and optimize heterogeneous CPU–GPU–disk execution.Source: §6 · p. 12

Related papers

Loading 2610.11230v1…