# ann

Approximate Nearest Neighbor (ANN) search quickly locates data points closest to a query vector.

This is one page of public article previews, not the complete archive. Follow Next page to continue. Summaries are not the original full articles.

## Variants of Beam Search for DiskANN

DevFeed: [Variants of Beam Search for DiskANN](<https://devfeed.tech/articles/variants-of-beam-search-for-diskann-145739.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.26609>)

Author: Viraj Agrawal, Kirankumar Shiragur

Published: 2026-11-20T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Databases](<https://devfeed.tech/sources/arxiv-databases.md>)

Topics: [ann](<https://devfeed.tech/topics/ann.md>)

Tags: [ann](<https://devfeed.tech/tags/ann.md>), [approximate-nearest-neighbor](<https://devfeed.tech/tags/approximate-nearest-neighbor.md>), [beam-search](<https://devfeed.tech/tags/beam-search.md>), [cs-db](<https://devfeed.tech/tags/cs-db.md>), [cs-ds](<https://devfeed.tech/tags/cs-ds.md>), [cs-ir](<https://devfeed.tech/tags/cs-ir.md>), [diskann](<https://devfeed.tech/tags/diskann.md>), [graph](<https://devfeed.tech/tags/graph.md>), [search](<https://devfeed.tech/tags/search.md>)

### AI overview

The paper generalizes guarantees for adaptive beam search (ABS): on α-reachable graphs it proves approximation factor (α+1)/(α(γ+1)−1) for any metric, with a tighter bound for sorted α-reachable graphs under ℓ2. It also introduces a beam predictor trained to minimize mean distance computations while meeting a target recall. Across three 100-million-point benchmarks, on SSD indices at matched recall, it reduces mean query latency by up to 29.6% versus classical beam search (CBS). Against ABS it is faster in 11 of 15 settings, by up to 6.5%, and no more than 1.4% slower in the other four; at 95% recall its advantage over ABS is larger for 500 neighbors than 100. In memory, it uses 1.3-23.7% fewer distance computations than CBS and 0.0-3.9% fewer than ABS.

### Source excerpt

arXiv:2611.26609v1 Announce Type: cross Abstract: Graph-based data structures such as DiskANN, HNSW, and NSG constitute the state of the art for large-scale approximate nearest-neighbor (ANN) search. Indyk and Xu introduced the notion of $\alpha$-reachable graphs, which include graphs built by DiskANN's slow-preprocessing construction, and proved that greedy search achieves an approximation factor of $\tfrac{\alpha+1}{\alpha-1}$. Independently, Al-Jazzazi et al. proposed adaptive beam search (ABS) with a relaxation parameter $\gamma > 0$, showing a $\tfrac{2}{\gamma}$ approximation on navigable graphs ($\alpha \approx 1$), where greedy search admits no guarantees. In this work, we unify and generalize these results by proving that ABS with parameter $\gamma$ on $\alpha$-reachable graphs achieves an approximation of $\tfrac{\alpha+1}{\alpha(\gamma+1)-1}$ for any metric. Moreover, on sorted $\alpha$-reachable graphs (introduced by Gollapudi et al.) under the $\ell_2$ metric, we obtain the tighter bound $\max\bigl(\tfrac{\alpha}{\alpha(\gamma+1)-1}, \tfrac{\alpha^{2}+1}{\alpha^{2}(\gamma+1)-1}\bigr)$. Beyond these theoretical results, we design a beam predictor using features inspired by fine-grained analysis of ABS, trained via a constrained objective that minimizes mean distance computations subject to a target recall. On three 100-million-point benchmarks, using graphs built by DiskANN's practical construction, beam predictor lowers mean query latency on SSD-resident indices at matched recall by up to $29.6\%$ relative to classical beam search (CBS). Relative to ABS, it is faster in $11$ of $15$ settings, by up to $6.5\%$, and at most $1.4\%$ slower in the other $4$; at $95\%$ recall, its advantage over ABS grows from $0.8$--$4.2\%$ for $100$ neighbors to $4.6$--$5.6\%$ for $500$ neighbors. In memory, it needs $1.3$--$23.7\%$ fewer distance computations than CBS and $0.0$--$3.9\%$ fewer than ABS.

## What Is a Vector Database? How It Works and Why AI Needs One

DevFeed: [What Is a Vector Database? How It Works and Why AI Needs One](<https://devfeed.tech/articles/what-is-a-vector-database-how-it-works-and-why-ai-needs-one-145883.md>)

Original publisher: [Read original article](<https://montecarlo.ai/blog-what-is-a-vector-database>)

Author: Virna Sekuj

Published: 2026-11-19T17:18:16Z

Content type: article

Language: en

Sources: [Monte Carlo](<https://devfeed.tech/sources/monte-carlo.md>)

Topics: [Vectors & LLMs](<https://devfeed.tech/topics/vectors-llms.md>), [Embeddings](<https://devfeed.tech/topics/embeddings.md>), [vector embeddings in AI](<https://devfeed.tech/topics/vector-embeddings-in-ai.md>), [Retrieval Augmented Generation (RAG)](<https://devfeed.tech/topics/retrieval-augmented-generation-rag.md>), [ann](<https://devfeed.tech/topics/ann.md>), [Database](<https://devfeed.tech/topics/database.md>), [information retrieval](<https://devfeed.tech/topics/information-retrieval.md>), [hybrid-search](<https://devfeed.tech/topics/hybrid-search.md>)

Tags: [agent-trust](<https://devfeed.tech/tags/agent-trust.md>), [agent-trust-glossary](<https://devfeed.tech/tags/agent-trust-glossary.md>), [agents](<https://devfeed.tech/tags/agents.md>), [ai](<https://devfeed.tech/tags/ai.md>), [ai-agents](<https://devfeed.tech/tags/ai-agents.md>), [data](<https://devfeed.tech/tags/data.md>), [database](<https://devfeed.tech/tags/database.md>), [embeddings](<https://devfeed.tech/tags/embeddings.md>), [glossary](<https://devfeed.tech/tags/glossary.md>), [rag](<https://devfeed.tech/tags/rag.md>), [rag-systems](<https://devfeed.tech/tags/rag-systems.md>), [retrieval](<https://devfeed.tech/tags/retrieval.md>), [retrieval-augmented-generation](<https://devfeed.tech/tags/retrieval-augmented-generation.md>), [retrieval-augmented-generation-rag](<https://devfeed.tech/tags/retrieval-augmented-generation-rag.md>), [vector](<https://devfeed.tech/tags/vector.md>), [vector-database](<https://devfeed.tech/tags/vector-database.md>), [vector-database-examples](<https://devfeed.tech/tags/vector-database-examples.md>), [vector-database-for-rag](<https://devfeed.tech/tags/vector-database-for-rag.md>), [vector-database-vs-relational-database](<https://devfeed.tech/tags/vector-database-vs-relational-database.md>), [vector-search](<https://devfeed.tech/tags/vector-search.md>), [vector-store](<https://devfeed.tech/tags/vector-store.md>)

### AI overview

Vector databases store content embeddings and use similarity search to retrieve relevant passages even when query wording differs. In a typical RAG flow, source content is chunked and embedded, stored with metadata, and indexed for approximate nearest-neighbor search; the user query is embedded and matching chunks are passed to the LLM as context. ANN indexing trades a small amount of precision for speed, and metadata filters can narrow results. Options include dedicated databases, database extensions, and vector search built into data platforms; choice depends on scale, latency, data location, and operational overhead. Retrieval can silently degrade when source syncs become stale, ingestion or chunking breaks, embedding models change without re-embedding, duplicate versions compete, or permission filters are missing. The text recommends monitoring freshness and ingestion volume, checking chunk quality, tracking embedding versions, measuring relevance and grounding, and tracing which chunks each agent request retrieves.

### Source excerpt

A vector database is a database built to store embeddings, which are numeric representations of the meaning of text, images, or other data, and to quickly find the embeddings most similar to a query. It's the retrieval layer behind most retrieval-augmented generation (RAG) systems and many AI agents, letting them find relevant information by meaning instead of exact keywords.

## SIMQ: A Single Graph-based Index for Multi-Vector Query

DevFeed: [SIMQ: A Single Graph-based Index for Multi-Vector Query](<https://devfeed.tech/articles/simq-a-single-graph-based-index-for-multi-vector-query-140627.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.22079>)

Author: Yifan Lu, Jiabao Jin, Xiaoyao Zhong, Peng Cheng, Xiangyu Wang, Haotian Li, Hua Chen, Junqing Chen, Wei Xi, Heng Tao Shen

Published: 2026-11-18T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Databases](<https://devfeed.tech/sources/arxiv-databases.md>)

Topics: [ann](<https://devfeed.tech/topics/ann.md>), [clustering](<https://devfeed.tech/topics/clustering.md>), [Vectors & LLMs](<https://devfeed.tech/topics/vectors-llms.md>)

Tags: [abstract](<https://devfeed.tech/tags/abstract.md>), [accelerated](<https://devfeed.tech/tags/accelerated.md>), [analysis](<https://devfeed.tech/tags/analysis.md>), [approximation](<https://devfeed.tech/tags/approximation.md>), [arxiv](<https://devfeed.tech/tags/arxiv.md>), [benchmarks](<https://devfeed.tech/tags/benchmarks.md>), [bottlenecks](<https://devfeed.tech/tags/bottlenecks.md>), [candidate](<https://devfeed.tech/tags/candidate.md>), [cluster](<https://devfeed.tech/tags/cluster.md>), [clustering](<https://devfeed.tech/tags/clustering.md>), [clusters](<https://devfeed.tech/tags/clusters.md>), [compression](<https://devfeed.tech/tags/compression.md>), [construction](<https://devfeed.tech/tags/construction.md>), [cost](<https://devfeed.tech/tags/cost.md>), [cpu](<https://devfeed.tech/tags/cpu.md>), [cs-db](<https://devfeed.tech/tags/cs-db.md>), [cs-ir](<https://devfeed.tech/tags/cs-ir.md>), [data](<https://devfeed.tech/tags/data.md>), [graph](<https://devfeed.tech/tags/graph.md>), [index](<https://devfeed.tech/tags/index.md>), [query](<https://devfeed.tech/tags/query.md>), [vector](<https://devfeed.tech/tags/vector.md>)

### AI overview

SIMQ approximates ColBERT-style MaxSim retrieval by grouping token vectors into fine-grained, data-aware clusters, indexing their centroids in one graph, and navigating that graph per query token. The approach avoids building a full centroid interaction matrix and does not require GPU acceleration for this search process; the index is independent of PLAID's residual representation. The paper's theoretical result is conditional on a manifold assumption and successful cell retrieval, under which data-aware partitioning has lower expected approximation error than data-oblivious partitioning. SIMQ+ adds count-based scoring and a dynamic candidate set to improve robustness across query conditions. Evaluation on five benchmarks compares recall, throughput, and construction time against several baselines, primarily on CPU; large-scale PLAID k-means centroids were built on a separate GPU machine. SIMQ is integrated into VSAG.

### Source excerpt

arXiv:2611.22079v1 Announce Type: cross Abstract: Multi-vector retrieval models such as ColBERT achieve state-of-the-art effectiveness by representing documents as sets of token-level vectors and scoring via MaxSim, but their high computational cost limits scalability to large corpora. Existing approximate methods face fundamental bottlenecks: centroid interaction matrix approaches require computing a full matrix at every query and rely on GPU-accelerated clustering, while data-oblivious compression methods yield unstable recall that requires repeated compensation. We propose SIMQ (Single graph Index for Multi-vector Query), a framework that bridges single-vector graph indices and multi-vector retrieval through data-aware sampling-based clustering and per-token graph navigation, simultaneously bypassing all aforementioned bottlenecks. SIMQ organizes all token vectors into fine-grained clusters via data-aware sampling, builds a single graph index over cluster centroids independently of PLAID's residual representation, and approximates the MaxSim score through per-token graph search without materializing any interaction matrix or relying on GPU acceleration. We provide theoretical analysis showing that, under a manifold assumption and successful cell retrieval, data-aware partitioning has a smaller expected approximation error than a data-oblivious partition. Building on this foundation, SIMQ+ further introduces count-based scoring and a dynamic candidate set to improve robustness across varying query conditions. Experiments on five benchmarks compare recall, throughput, and construction time against several baselines, primarily on CPU; large-scale PLAID k-means centroids are built on a separate GPU machine. SIMQ has been integrated into VSAG, an Ant Group's open-source vector search library.

## Pelorus: Warped-Product Graph Indexing for Hyperbolic Vector Search

DevFeed: [Pelorus: Warped-Product Graph Indexing for Hyperbolic Vector Search](<https://devfeed.tech/articles/pelorus-warped-product-graph-indexing-for-hyperbolic-vector-search-140628.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.22159>)

Author: Wenxuan Xiao, Xu Cao

Published: 2026-11-18T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Databases](<https://devfeed.tech/sources/arxiv-databases.md>)

Topics: [ann](<https://devfeed.tech/topics/ann.md>), [Embeddings](<https://devfeed.tech/topics/embeddings.md>), [Graphs](<https://devfeed.tech/topics/graphs.md>), [quantization](<https://devfeed.tech/topics/quantization.md>)

Tags: [amd-epyc](<https://devfeed.tech/tags/amd-epyc.md>), [approximate-nearest-neighbor-search](<https://devfeed.tech/tags/approximate-nearest-neighbor-search.md>), [avx2](<https://devfeed.tech/tags/avx2.md>), [benchmarks](<https://devfeed.tech/tags/benchmarks.md>), [cs-db](<https://devfeed.tech/tags/cs-db.md>), [efficiency](<https://devfeed.tech/tags/efficiency.md>), [embeddings](<https://devfeed.tech/tags/embeddings.md>), [graph](<https://devfeed.tech/tags/graph.md>), [indexing](<https://devfeed.tech/tags/indexing.md>), [memory](<https://devfeed.tech/tags/memory.md>), [recall](<https://devfeed.tech/tags/recall.md>), [reranking](<https://devfeed.tech/tags/reranking.md>), [search](<https://devfeed.tech/tags/search.md>), [throughput](<https://devfeed.tech/tags/throughput.md>), [traversal](<https://devfeed.tech/tags/traversal.md>), [vector](<https://devfeed.tech/tags/vector.md>), [vector-search](<https://devfeed.tech/tags/vector-search.md>)

### AI overview

Pelorus is a hyperbolic vector search graph index designed to reduce navigation memory and traversal cost while retaining geodesic ordering. It stores FP32 radial and conformal scalars separately from 2-bit spherical direction codes, then uses FP64 full-vector evaluation only in a compact reranking tail. Its distortion corrections include orthogonal-projection debiasing, purity-gated tangent-cone residuals, and Conformal Jacobian gating; QuadriPrune distributes edges across geodesic fibers, same-shell rings, and radial elevators. Across eight benchmarks on AMD EPYC 9654, it builds Cohere-1M indices 5.44x faster than full-precision polar graphs using 32 threads, with 517 MB of hot navigation memory. At 99% Recall@10, Cohere-1M throughput is reported as 4.30x higher on one thread and 6.31x higher on 24 threads; MERU-1M reaches 53,483 QPS. Tangent-cone residuals lift recall from 34.22% to 99.385% on clustered narrow shells, but isotropic narrow-shell tests still reveal recall limits.

### Source excerpt

arXiv:2611.22159v1 Announce Type: new Abstract: Hyperbolic embeddings capture hierarchical relations, but million-scale approximate nearest neighbor search must reconcile geodesic fidelity with memory efficiency. Flat inner-product indices distort order across radial shells, while native hyperbolic graphs repeatedly access full-precision vectors or quantize coordinates with singular conformal scales. We present Pelorus, a warped-product proximity-graph index for hyperbolic vector search. Pelorus separates unquantized FP32 radial and conformal scalars from scale-invariant 2-bit spherical directional codes and defers full-vector FP64 evaluation to a compact reranking tail. A conformal distortion analysis motivates orthogonal-projection debiasing, purity-gated tangent-cone residuals, and Conformal Jacobian gating. QuadriPrune allocates edges across geodesic fibers, same-shell rings, and radial elevators, with spanning-tree chord swaps restoring entry reachability. A single-page record layout and carry-save AVX2 kernel accelerate traversal. Across eight real and synthetic benchmarks on AMD EPYC 9654, Pelorus builds Cohere-1M indices 5.44x faster than full-precision polar graphs on 32 threads, reducing hot navigation memory to 517.0 MB. At 99% Recall@10, it improves Cohere-1M throughput by 4.30x on one thread and 6.31x on 24 threads, and delivers 53,483 QPS on MERU-1M. On clustered narrow shells, tangent-cone residuals raise recall from 34.22% to 99.385%, while isotropic narrow-shell stress tests expose remaining recall limits.

## HorizANN: Elastically Scaling Vector Search with Ghost Edges

DevFeed: [HorizANN: Elastically Scaling Vector Search with Ghost Edges](<https://devfeed.tech/articles/horizann-elastically-scaling-vector-search-with-ghost-edges-138291.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.19077>)

Author: Talika Gupta, Yunqi Li, Aditya Kunte, Claire Lin, Supawit Chockchowwat, Daniel Waddington, Hubertus Franke, Yongjoo Park

Published: 2026-11-17T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Databases](<https://devfeed.tech/sources/arxiv-databases.md>)

Topics: [ann](<https://devfeed.tech/topics/ann.md>), [Deployment & Scaling](<https://devfeed.tech/topics/deployment-scaling.md>), [Graphs](<https://devfeed.tech/topics/graphs.md>)

Tags: [ai](<https://devfeed.tech/tags/ai.md>), [ai-applications](<https://devfeed.tech/tags/ai-applications.md>), [approximate-nearest-neighbor](<https://devfeed.tech/tags/approximate-nearest-neighbor.md>), [approximate-nearest-neighbor-search](<https://devfeed.tech/tags/approximate-nearest-neighbor-search.md>), [connectivity](<https://devfeed.tech/tags/connectivity.md>), [cs-db](<https://devfeed.tech/tags/cs-db.md>), [distributed](<https://devfeed.tech/tags/distributed.md>), [graph](<https://devfeed.tech/tags/graph.md>), [index](<https://devfeed.tech/tags/index.md>), [indexes](<https://devfeed.tech/tags/indexes.md>), [indexing](<https://devfeed.tech/tags/indexing.md>), [nearest-neighbor](<https://devfeed.tech/tags/nearest-neighbor.md>), [partition](<https://devfeed.tech/tags/partition.md>), [partitioning](<https://devfeed.tech/tags/partitioning.md>), [queries](<https://devfeed.tech/tags/queries.md>), [recall](<https://devfeed.tech/tags/recall.md>), [scaling](<https://devfeed.tech/tags/scaling.md>), [search](<https://devfeed.tech/tags/search.md>), [throughput](<https://devfeed.tech/tags/throughput.md>), [vector](<https://devfeed.tech/tags/vector.md>), [vector-search](<https://devfeed.tech/tags/vector-search.md>)

### AI overview

HorizANN scales distributed graph-based approximate nearest neighbor search without rebuilding the full index when machines are added or removed. Its "ghost edges" preserve cross-partition connectivity during repartitioning by reusing structural information that would otherwise be discarded. The abstract reports growth from 100 million vectors on one worker to 1 billion on ten workers, inserting each additional 100 million within 2.5 hours while sustaining 3.4-3.5K queries per second at 0.998 Recall@10.

### Source excerpt

arXiv:2611.19077v1 Announce Type: new Abstract: Approximate nearest neighbor search (ANNS) is fundamental to modern data-intensive AI applications such as retrieval-augmented generation, recommendation systems, and semantic search. Among existing indexing methods, graph-based indexes emerge as the state of the art due to their superior recall-throughput tradeoffs. Scaling these indexes to multiple machines requires partitioning the data and building indexes on each. However, when new machines are added or removed, the data must be repartitioned and the indexes reconstructed from scratch, making horizontal scaling costly at billion scale. In this work, we present HorizANN, a distributed graph-based ANNS system that scales horizontally without requiring full index reconstruction. To achieve this, we introduce ghost edges, a mechanism for preserving cross-partition connectivity as partition boundaries change during repartitioning. By reusing the structural information that would otherwise be discarded during repartitioning, HorizANN avoids costly full index reconstruction. As the index grows from 100M vectors on one worker to 1B vectors on ten workers, HorizANN inserts each 100M vectors within 2.5 hours and sustains 3.4--3.5K queries per second at 0.998 Recall@10.

## NemoANN: I/O-Efficient Filtered Vector Search on SSDs with Graph Tunneling

DevFeed: [NemoANN: I/O-Efficient Filtered Vector Search on SSDs with Graph Tunneling](<https://devfeed.tech/articles/nemoann-i-o-efficient-filtered-vector-search-on-ssds-with-graph-tunneling-138282.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2603.21466>)

Author: Nakyung Lee, Soobin Cho, Jiwoong Park, Gyuyeong Kim

Published: 2026-11-17T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Databases](<https://devfeed.tech/sources/arxiv-databases.md>)

Topics: [ann](<https://devfeed.tech/topics/ann.md>)

Tags: [approximate-nearest-neighbor-search](<https://devfeed.tech/tags/approximate-nearest-neighbor-search.md>), [benchmark](<https://devfeed.tech/tags/benchmark.md>), [connectivity](<https://devfeed.tech/tags/connectivity.md>), [cs-db](<https://devfeed.tech/tags/cs-db.md>), [cs-os](<https://devfeed.tech/tags/cs-os.md>), [filter](<https://devfeed.tech/tags/filter.md>), [graph](<https://devfeed.tech/tags/graph.md>), [i-o](<https://devfeed.tech/tags/i-o.md>), [index](<https://devfeed.tech/tags/index.md>), [memory](<https://devfeed.tech/tags/memory.md>), [metadata](<https://devfeed.tech/tags/metadata.md>), [predicate](<https://devfeed.tech/tags/predicate.md>), [recall](<https://devfeed.tech/tags/recall.md>), [routing](<https://devfeed.tech/tags/routing.md>), [search](<https://devfeed.tech/tags/search.md>), [ssd](<https://devfeed.tech/tags/ssd.md>), [ssds](<https://devfeed.tech/tags/ssds.md>), [system](<https://devfeed.tech/tags/system.md>), [systems](<https://devfeed.tech/tags/systems.md>), [throughput](<https://devfeed.tech/tags/throughput.md>), [vector](<https://devfeed.tech/tags/vector.md>), [vector-search](<https://devfeed.tech/tags/vector-search.md>)

### AI overview

NemoANN reduces SSD work in filtered approximate nearest-neighbor search by checking a node's predicate before reading its full-precision vector. For nonmatching nodes, it uses the small neighbor list and in-memory routing metadata to tunnel through the graph, preserving connectivity without modifying or rebuilding the index. On a 100-million-vector benchmark at 10% selectivity and 90% recall, it reports about 10x fewer SSD reads and 8.0x higher throughput than post-filtering, and 5.0x higher throughput than PipeANN-Filter. Against post-filtering, the throughput gain reaches 13.1x at 5% selectivity.

### Source excerpt

arXiv:2603.21466v3 Announce Type: replace-cross Abstract: We introduce NemoANN, an I/O-efficient SSD-based Approximate Nearest Neighbor Search (ANNS) system for filtered search. Existing SSD-based systems either waste I/O on post-filtering or require expensive filter-aware index rebuilds. Our key insight is that a nonmatching node can never be a result, so the search needs only its small neighbor list, not the full-precision vector on SSD. NemoANN therefore checks each predicate before the SSD read and tunnels through non-matching nodes using in-memory routing metadata, preserving graph connectivity without modifying the index. On a 100M-vector benchmark, NemoANN reduces SSD reads by about 10x and improves throughput by 8.0x over post-filtering and by 5.0x over PipeANN-Filter, a state-of-the-art filtered SSD system, at 10% selectivity and 90% recall. The gains over post-filtering grow at lower selectivity, reaching 13.1x at 5% selectivity.

## CapCover Filter: Semantic Approximate Membership Queries over Embeddings

DevFeed: [CapCover Filter: Semantic Approximate Membership Queries over Embeddings](<https://devfeed.tech/articles/capcover-filter-semantic-approximate-membership-queries-over-embeddings-137541.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.20132>)

Author: Dvir David Biton, Shay Hahiashvili, Nadav Keren, Gil Einziger, Roy Friedman

Published: 2026-11-17T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Artificial Intelligence](<https://devfeed.tech/sources/arxiv-artificial-intelligence.md>), [arXiv: Databases](<https://devfeed.tech/sources/arxiv-databases.md>)

Topics: [Embeddings](<https://devfeed.tech/topics/embeddings.md>), [cosine similarity search](<https://devfeed.tech/topics/cosine-similarity-search.md>), [quantization](<https://devfeed.tech/topics/quantization.md>), [ann](<https://devfeed.tech/topics/ann.md>), [clustering](<https://devfeed.tech/topics/clustering.md>)

Tags: [2](<https://devfeed.tech/tags/2.md>), [abstract](<https://devfeed.tech/tags/abstract.md>), [also](<https://devfeed.tech/tags/also.md>), [arxiv](<https://devfeed.tech/tags/arxiv.md>), [can](<https://devfeed.tech/tags/can.md>), [compare](<https://devfeed.tech/tags/compare.md>), [construction](<https://devfeed.tech/tags/construction.md>), [cosine](<https://devfeed.tech/tags/cosine.md>), [cosine-similarity](<https://devfeed.tech/tags/cosine-similarity.md>), [cs-ai](<https://devfeed.tech/tags/cs-ai.md>), [cs-db](<https://devfeed.tech/tags/cs-db.md>), [data](<https://devfeed.tech/tags/data.md>), [data-structure](<https://devfeed.tech/tags/data-structure.md>), [datasets](<https://devfeed.tech/tags/datasets.md>), [embedding](<https://devfeed.tech/tags/embedding.md>), [embeddings](<https://devfeed.tech/tags/embeddings.md>), [evaluation](<https://devfeed.tech/tags/evaluation.md>), [faiss](<https://devfeed.tech/tags/faiss.md>), [filter](<https://devfeed.tech/tags/filter.md>), [over](<https://devfeed.tech/tags/over.md>), [queries](<https://devfeed.tech/tags/queries.md>), [semantic](<https://devfeed.tech/tags/semantic.md>)

### AI overview

CapCover Filter uses spherical caps to summarize embeddings and reject queries when no indexed vector meets a requested similarity threshold, while guaranteeing no false negatives. Its threshold-independent representation supports arbitrary thresholds without reconstruction. Across five datasets at cosine similarity 0.95, it eliminated about 20-100% of index accesses using 2% of raw FP32 embedding memory. Ahead of a FAISS flat index, it increased throughput by up to 382% and about 116% on average while returning the same range-search result. The reported gains are strongest when thresholds are tight, retrieval is expensive, and embeddings are highly clustered; the abstract also says lower thresholds were evaluated but gives no results for them.

### Source excerpt

arXiv:2611.20132v1 Announce Type: cross Abstract: Determining whether an embedding is sufficiently similar to any vector in a vector store without performing a nearest-neighbor search can substantially improve query throughput in vector-store systems. We study Semantic Approximate Membership Queries (SAMQs), which allow queries to be rejected when no indexed vector meets the requested similarity threshold, while guaranteeing no false negatives. We introduce CapCover Filter, a geometric data structure that summarizes a set of embeddings using spherical caps. Its representation is independent of the query threshold, allowing a single filter to support arbitrary thresholds without reconstruction. We evaluate alternative construction and quantization methods, compare CapCover Filter with competing filters, and measure its impact on query throughput. Across five real-world datasets, at a cosine similarity threshold of 0.95, CapCover Filter eliminates approximately 20--100\% of index accesses while using only 2\% of the raw (FP32) embedding memory. When placed before a FAISS flat index, it improves query throughput by up to 382\% and by approximately 116\% on average across the five datasets, while returning the same range-search result. We also evaluate lower similarity thresholds. Our results show that CapCover Filter can substantially improve vector-store throughput when similarity thresholds are tight, retrieval is expensive, and indexed embeddings are highly clustered. We release an optimized implementation of CapCover Filter and its evaluation framework.

## ResGraph: Cross-Model Graph-based Index Migration via Residual Reachability in ANN Search

DevFeed: [ResGraph: Cross-Model Graph-based Index Migration via Residual Reachability in ANN Search](<https://devfeed.tech/articles/resgraph-cross-model-graph-based-index-migration-via-residual-reachability-in-ann-search-135438.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2609.23036>)

Author: Baoyuan Gu, Xiaoyao Zhong, Jiabao Jin, Peng Cheng, Wangze Ni, Haoyang Li, Haotian Li, Jingkuan Song, Heng Tao Shen

Published: 2026-11-16T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Databases](<https://devfeed.tech/sources/arxiv-databases.md>)

Topics: [ann](<https://devfeed.tech/topics/ann.md>), [Graphs](<https://devfeed.tech/topics/graphs.md>), [Embeddings](<https://devfeed.tech/topics/embeddings.md>)

Tags: [ann](<https://devfeed.tech/tags/ann.md>), [approximate-nearest-neighbor](<https://devfeed.tech/tags/approximate-nearest-neighbor.md>), [approximate-nearest-neighbor-search](<https://devfeed.tech/tags/approximate-nearest-neighbor-search.md>), [beam](<https://devfeed.tech/tags/beam.md>), [bounded](<https://devfeed.tech/tags/bounded.md>), [construction](<https://devfeed.tech/tags/construction.md>), [cost](<https://devfeed.tech/tags/cost.md>), [cs-db](<https://devfeed.tech/tags/cs-db.md>), [deployment](<https://devfeed.tech/tags/deployment.md>), [embedding](<https://devfeed.tech/tags/embedding.md>), [embedding-model](<https://devfeed.tech/tags/embedding-model.md>), [encoding](<https://devfeed.tech/tags/encoding.md>), [exploits](<https://devfeed.tech/tags/exploits.md>), [explore](<https://devfeed.tech/tags/explore.md>), [faster](<https://devfeed.tech/tags/faster.md>), [framework](<https://devfeed.tech/tags/framework.md>), [graph](<https://devfeed.tech/tags/graph.md>), [index](<https://devfeed.tech/tags/index.md>), [migration](<https://devfeed.tech/tags/migration.md>), [model](<https://devfeed.tech/tags/model.md>), [search](<https://devfeed.tech/tags/search.md>)

### AI overview

ResGraph speeds up graph-index migration when a corpus is re-encoded with a new embedding model by reusing connectivity in the old index: many exact neighbors under the new model remain reachable within a few hops. Res-Local expands shallowly in parallel and screens second-hop candidates with packed position sign codes before exact evaluation; Res-Search uses hop-bounded beam traversal to explore farther. Across eight text and image migrations, the abstract reports up to 17.43x faster construction than the fastest degree-matched reconstruction method, with competitive recall.

### Source excerpt

arXiv:2609.23036v2 Announce Type: replace Abstract: Approximate nearest neighbor search (ANNS) underpins large-scale vector retrieval in search, recommendation, and retrieval-augmented generation. Graph-based indexes have demonstrated state-of-the-art search performance for ANNS: they connect each corpus vector to a small set of nearby or navigationally useful vertices and answer queries by traversing the resulting graph. Because these edges are selected using construction-time distances, the graph index is tied to the embedding model; re-encoding a corpus with a new model may change distances and neighborhoods of the vectors, and reconstructing the graph for the new embedding vectors incurs substantial construction cost and delays deployment. When the embedding model changes, we observe a phenomenon in the old graph index that we call residual reachability: although derived from different models, the vectors describe the same underlying objects and often retain part of their similarity structure, which the old graph reflects as connectivity, leaving many exact new-model neighbors reachable within a few hops. Motivated by this observation, we develop ResGraph, an index-migration framework that exploits the residual reachability of the old graph index to construct the new graph index faster. ResGraph provides two migration paths. Res-Local performs parallel shallow expansion over the inherited graph index and screens second-hop candidates with packed position sign codes before exact evaluation. Res-Search uses hop-bounded beam traversal to explore beyond shallow expansion. Across eight text and image migrations, ResGraph attains up to 17.43 times speedup on constructing the new graph index than the fastest degree-matched reconstruction method while keeping competitive recalls.

## WETW: Learning Pair-Specific Weighted Euclidean Distances for Efficient DTW Search

DevFeed: [WETW: Learning Pair-Specific Weighted Euclidean Distances for Efficient DTW Search](<https://devfeed.tech/articles/wetw-learning-pair-specific-weighted-euclidean-distances-for-efficient-dtw-search-135064.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.17412>)

Author: Christos Panourgias, Qitong Wang, George Tzagkarakis, Themis Palpanas

Published: 2026-11-16T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Artificial Intelligence](<https://devfeed.tech/sources/arxiv-artificial-intelligence.md>), [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [Embeddings](<https://devfeed.tech/topics/embeddings.md>), [ann](<https://devfeed.tech/topics/ann.md>), [metric learning](<https://devfeed.tech/topics/metric-learning.md>)

Tags: [abstract](<https://devfeed.tech/tags/abstract.md>), [alignment](<https://devfeed.tech/tags/alignment.md>), [also](<https://devfeed.tech/tags/also.md>), [arxiv](<https://devfeed.tech/tags/arxiv.md>), [best](<https://devfeed.tech/tags/best.md>), [build](<https://devfeed.tech/tags/build.md>), [building](<https://devfeed.tech/tags/building.md>), [but](<https://devfeed.tech/tags/but.md>), [collections](<https://devfeed.tech/tags/collections.md>), [compare](<https://devfeed.tech/tags/compare.md>), [comparison](<https://devfeed.tech/tags/comparison.md>), [comparisons](<https://devfeed.tech/tags/comparisons.md>), [computing](<https://devfeed.tech/tags/computing.md>), [cost](<https://devfeed.tech/tags/cost.md>), [cs-ai](<https://devfeed.tech/tags/cs-ai.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [datasets](<https://devfeed.tech/tags/datasets.md>), [embedding](<https://devfeed.tech/tags/embedding.md>), [embeddings](<https://devfeed.tech/tags/embeddings.md>), [learning](<https://devfeed.tech/tags/learning.md>), [pair](<https://devfeed.tech/tags/pair.md>), [search](<https://devfeed.tech/tags/search.md>)

### AI overview

WETW speeds up DTW time-series search by predicting pair-specific weights for fixed-length embeddings, without first computing an alignment. In a filter-and-verify pipeline, it uses those estimates to shortlist candidates and exact DTW to verify them, so returned distances are exact even though search may miss neighbors. Across eight datasets, WETW-FV was 11.4x faster than the fastest tested exact method at mean recall@10 of 0.93; the best learned baseline reached 0.59 recall at the same speed. For 48K-point series, it was 40x faster than the UCR Suite at recall@10 of 0.91. The proposed WESEE encoder's multi-scale features retain timing information and raised recall@1 from 0.90 to 0.95. The abstract also reports that ranking regularization raised recall@1 from 0.79 to 0.95, as fitting distances by regression alone misordered nearest neighbors.

### Source excerpt

arXiv:2611.17412v1 Announce Type: cross Abstract: Dynamic Time Warping (DTW) is the standard distance for similarity search over time series that are misaligned in time, but its cost is quadratic in the series length and lower bounds often prune few candidates, so search over large collections of long series is slow. Learned approximations embed the series to make comparisons cheap, yet compare every pair with the same fixed rule, usually the Euclidean distance, although DTW aligns each pair differently. We observe that, once a pair is aligned, DTW is a Euclidean distance over coordinates selected for that pair. Building on this view, we propose Weighted Euclidean Time Warping (WETW), a learned distance that adapts the comparison of fixed-length embeddings to each pair. A small symmetric network predicts one weight per embedding di- mension and pair without computing an alignment, which halves the error of the best static distance on the same embeddings. The embeddings come from the Weighted Euclidean SEries Encoder (WESEE), whose multi-scale Temporal Feature Extractor keeps the timing information that global pooling removes and raises recall@1 from 0.90 to 0.95, although WETW works with any encoder. We also show that fitting DTW distances is not enough for search, as regression alone misorders the closest neighbours, and that ranking regularization raises recall@1 from 0.79 to 0.95. Our filter-and-verify pipeline, WETW-FV, uses WETW to build a shortlist and exact DTW to check it, so the search is approximate but every returned distance is exact. Over eight datasets, WETW-FV is 11.4x faster than the fastest exact method among the UCR Suite, lower bounds and MESSI-DTW, at a mean recall@10 of 0.93, while the best learned baseline reaches 0.59 at the same speed. On 48K-point series, WETW- FV remains 40x faster than the UCR Suite at a recall@10 of 0.91.

## Authenticated Approximate Nearest Neighbor Search in Outsourced Vector Databases

DevFeed: [Authenticated Approximate Nearest Neighbor Search in Outsourced Vector Databases](<https://devfeed.tech/articles/authenticated-approximate-nearest-neighbor-search-in-outsourced-vector-databases-132702.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.16516>)

Author: Yuanhang Zhou, Xinyi Zhang, Cheng Xu, Jianliang Xu

Published: 2026-11-13T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Cryptography and Security](<https://devfeed.tech/sources/arxiv-cryptography-and-security.md>), [arXiv: Databases](<https://devfeed.tech/sources/arxiv-databases.md>)

Topics: [ann](<https://devfeed.tech/topics/ann.md>), [Embeddings](<https://devfeed.tech/topics/embeddings.md>), [Database](<https://devfeed.tech/topics/database.md>), [Distributed Systems & Parallel Computing](<https://devfeed.tech/topics/distributed-systems-parallel-computing.md>), [Data transmission](<https://devfeed.tech/topics/data-transmission.md>)

Tags: [ann](<https://devfeed.tech/tags/ann.md>), [approximate-nearest-neighbor](<https://devfeed.tech/tags/approximate-nearest-neighbor.md>), [approximate-nearest-neighbor-search](<https://devfeed.tech/tags/approximate-nearest-neighbor-search.md>), [authenticated-data-structure](<https://devfeed.tech/tags/authenticated-data-structure.md>), [authentication](<https://devfeed.tech/tags/authentication.md>), [cs-cr](<https://devfeed.tech/tags/cs-cr.md>), [cs-db](<https://devfeed.tech/tags/cs-db.md>), [database-management](<https://devfeed.tech/tags/database-management.md>), [databases](<https://devfeed.tech/tags/databases.md>), [efficiency](<https://devfeed.tech/tags/efficiency.md>), [embedding](<https://devfeed.tech/tags/embedding.md>), [experiments](<https://devfeed.tech/tags/experiments.md>), [exploits](<https://devfeed.tech/tags/exploits.md>), [graph](<https://devfeed.tech/tags/graph.md>), [inner-product](<https://devfeed.tech/tags/inner-product.md>), [integrity](<https://devfeed.tech/tags/integrity.md>), [latency](<https://devfeed.tech/tags/latency.md>), [nearest-neighbor](<https://devfeed.tech/tags/nearest-neighbor.md>), [overhead](<https://devfeed.tech/tags/overhead.md>), [search](<https://devfeed.tech/tags/search.md>), [vector](<https://devfeed.tech/tags/vector.md>), [vector-databases](<https://devfeed.tech/tags/vector-databases.md>)

### AI overview

VIDA aims to make outsourced graph-based approximate nearest neighbor search verifiable with less communication and proof overhead. It replaces transmission of raw vectors with compact vector commitments, uses an aggregated Inner Product Argument to verify multiple distance computations, and introduces MeST, whose authentication paths follow graph traversal. A quantization-aware strategy uses distance bounds to prune candidates and reduce exact distances needing cryptographic authentication. The abstract reports up to 6.6x faster end-to-end latency and up to 99.2% less data transfer than state-of-the-art methods; it provides no experimental details in this excerpt.

### Source excerpt

arXiv:2611.16516v1 Announce Type: new Abstract: Approximate Nearest Neighbor (ANN) search has become a fundamental query primitive in modern vector databases for managing large-scale embedding data. To support growing vector collections, organizations increasingly outsource database management and query processing to third-party clouds. However, untrusted service providers may return suboptimal or fabricated results, posing a serious threat to ANN search integrity. Existing authenticated ANN approaches face substantial scalability challenges. They typically require transmitting high-dimensional vectors for distance verification and rely on topology-agnostic authentication structures, resulting in excessive communication and verification overhead. In this paper, we propose VIDA, a novel and efficient scheme for authenticated graph-based ANN search. VIDA replaces raw vector transmission with compact vector commitments and employs an aggregated Inner Product Argument to efficiently verify multiple distance computations. Furthermore, we introduce MeST, a topology-aware authenticated data structure that aligns authentication paths with graph traversal, significantly reducing structural proof overhead. Additionally, we design a quantization-aware authentication strategy that exploits distance bounds for pruning, reducing the number of exact distances requiring cryptographic authentication. Extensive experiments demonstrate that the proposed schemes substantially improve the efficiency of authenticated ANN search, achieving up to a $6.6\times$ speedup in end-to-end latency and reducing data transfer time by up to 99.2% compared with state-of-the-art methods.

## When Does Low-Bit Quantization Preserve the Decisions of Vector Search?

DevFeed: [When Does Low-Bit Quantization Preserve the Decisions of Vector Search?](<https://devfeed.tech/articles/when-does-low-bit-quantization-preserve-the-decisions-of-vector-search-132678.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2609.09854>)

Author: Wenxuan Xiao, Xu Cao

Published: 2026-11-13T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Databases](<https://devfeed.tech/sources/arxiv-databases.md>)

Topics: [quantization](<https://devfeed.tech/topics/quantization.md>), [ann](<https://devfeed.tech/topics/ann.md>)

Tags: [cs-db](<https://devfeed.tech/tags/cs-db.md>), [cs-ir](<https://devfeed.tech/tags/cs-ir.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [error](<https://devfeed.tech/tags/error.md>), [graph](<https://devfeed.tech/tags/graph.md>), [margin](<https://devfeed.tech/tags/margin.md>), [pruning](<https://devfeed.tech/tags/pruning.md>), [quantization](<https://devfeed.tech/tags/quantization.md>), [query](<https://devfeed.tech/tags/query.md>), [rank](<https://devfeed.tech/tags/rank.md>), [ranking](<https://devfeed.tech/tags/ranking.md>), [recall](<https://devfeed.tech/tags/recall.md>), [rotation](<https://devfeed.tech/tags/rotation.md>), [search](<https://devfeed.tech/tags/search.md>), [topology](<https://devfeed.tech/tags/topology.md>), [vector](<https://devfeed.tech/tags/vector.md>), [vector-search](<https://devfeed.tech/tags/vector-search.md>)

### AI overview

Low-bit quantization can preserve vector-search decisions only when its errors are judged against the exact margins of the comparisons graph search makes. The excerpt reports that shared endpoints make distance errors partly cancel, and an exact replay identity links candidate actions to neighbour selection. In 24 dataset-code configurations, calibration-estimated risk correlated with held-out ranking and pruning flips at 0.97 and 0.99; distance-rank correlation was a weaker predictor (0.74 and 0.05). For two-bit Cohere codes, rotation raised distance-rank correlation from 0.75 to 0.91 but also increased nearest-neighbour comparison flips by 51%. The authors also report margin-based certificates, a Gaussian error model, a heavy-tail construction, and paired 200,000-vector graph builds connecting rotation, query scoring and topology with recall and search work.

### Source excerpt

arXiv:2609.09854v2 Announce Type: replace Abstract: An orthogonal rotation improves the distance rank correlation of two-bit Cohere codes from 0.75 to 0.91, yet increases nearest-neighbour comparison flips by 51%. We analyse quantization through the comparisons made by graph search. A comparison changes only when its quantization error exceeds its exact margin, giving a flip bound that separates close calls from large errors. Shared endpoints induce correlated distance errors that partly cancel within a comparison. An exact replay identity connects candidate-level actions to the output of neighbour selection. A Gaussian model gives coordinate-code errors in closed form, and a rare-spike construction exposes heavy tails in the population-radius error. Held-out blocks give model-free certificates for acceptance rules based on exact or quantized margins. Across 24 dataset-code configurations, calibration-estimated risk correlates with held-out ranking and pruning flips at 0.97 and 0.99, compared with 0.91 and 0.99 for a margin-to-noise summary and 0.74 and 0.05 for distance rank correlation. Paired builds of 200,000-vector graphs connect rotation, query scoring, and topology to end-to-end recall and search work.

## CRINN: Contrastive Reinforcement Learning for Approximate Nearest Neighbor Search

DevFeed: [CRINN: Contrastive Reinforcement Learning for Approximate Nearest Neighbor Search](<https://devfeed.tech/articles/crinn-contrastive-reinforcement-learning-for-approximate-nearest-neighbor-search-131847.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2508.02091>)

Author: Xiaoya Li, Albert Wang, Guoyin Wang, Chris Shum, Jiwei Li

Published: 2026-11-13T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Artificial Intelligence](<https://devfeed.tech/sources/arxiv-artificial-intelligence.md>), [arXiv: Databases](<https://devfeed.tech/sources/arxiv-databases.md>), [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [ann](<https://devfeed.tech/topics/ann.md>), [Reinforcement learning](<https://devfeed.tech/topics/reinforcement-learning.md>), [Machine learning](<https://devfeed.tech/topics/machine-learning.md>), [Large Language Model](<https://devfeed.tech/topics/llm.md>)

Tags: [ai](<https://devfeed.tech/tags/ai.md>), [algorithms](<https://devfeed.tech/tags/algorithms.md>), [approximate-nearest-neighbor-search](<https://devfeed.tech/tags/approximate-nearest-neighbor-search.md>), [benchmark](<https://devfeed.tech/tags/benchmark.md>), [cs-ai](<https://devfeed.tech/tags/cs-ai.md>), [cs-cl](<https://devfeed.tech/tags/cs-cl.md>), [cs-db](<https://devfeed.tech/tags/cs-db.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [datasets](<https://devfeed.tech/tags/datasets.md>), [llms](<https://devfeed.tech/tags/llms.md>), [optimization](<https://devfeed.tech/tags/optimization.md>), [reinforcement-learning](<https://devfeed.tech/tags/reinforcement-learning.md>), [retrieval-augmented-generation-rag](<https://devfeed.tech/tags/retrieval-augmented-generation-rag.md>), [search](<https://devfeed.tech/tags/search.md>), [speed](<https://devfeed.tech/tags/speed.md>)

### AI overview

CRINN treats approximate nearest-neighbor search optimization as reinforcement learning, using execution speed as the reward while maintaining accuracy constraints. Across six widely used NNS benchmark datasets, it reportedly achieves the best performance on GIST-960-Euclidean and MNIST-784-Euclidean, and ties for first on SIFT-128-Euclidean and GloVe-25-angular. The abstract presents this as evidence that reinforcement-learning-augmented LLMs can automate specialized algorithm optimization that otherwise requires labor-intensive manual refinement. These are abstract-level claims; the supplied text does not describe the implementation or evaluation details.

### Source excerpt

arXiv:2508.02091v5 Announce Type: replace-cross Abstract: Approximate nearest-neighbor search (ANNS) algorithms have become increasingly critical for recent AI applications, particularly in retrieval-augmented generation (RAG) and agent-based LLM applications. In this paper, we present CRINN, a new paradigm for ANNS algorithms. CRINN treats ANNS optimization as a reinforcement learning problem where execution speed serves as the reward signal. This approach enables the automatic generation of progressively faster ANNS implementations while maintaining accuracy constraints. Our experimental evaluation demonstrates CRINN's effectiveness across six widely-used NNS benchmark datasets. When compared against state-of-the-art open-source ANNS algorithms, CRINN achieves best performance on three of them (GIST-960-Euclidean, MNIST-784-Euclidean, and GloVe-25-angular), and tied for first place on two of them (SIFT-128-Euclidean and GloVe-25-angular). The implications of CRINN's success reach well beyond ANNS optimization: It validates that LLMs augmented with reinforcement learning can function as an effective tool for automating sophisticated algorithmic optimizations that demand specialized knowledge and labor-intensive manual refinement. Code can be found at https://github.com/ornith-ai/CRINN

## Graph-Based Nearest-Neighbor Search with Recall Guarantees Using Graph Spanners

DevFeed: [Graph-Based Nearest-Neighbor Search with Recall Guarantees Using Graph Spanners](<https://devfeed.tech/articles/graph-based-nearest-neighbor-search-with-recall-guarantees-using-graph-spanners-132673.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2607.02338>)

Author: Minghao Li, Raghav Mittal, Sanjivni Rana, Suraj Shetiya, Gautam Das, Nick Koudas

Published: 2026-11-13T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Databases](<https://devfeed.tech/sources/arxiv-databases.md>)

Topics: [ann](<https://devfeed.tech/topics/ann.md>), [information retrieval](<https://devfeed.tech/topics/information-retrieval.md>)

Tags: [cs-cl](<https://devfeed.tech/tags/cs-cl.md>), [cs-db](<https://devfeed.tech/tags/cs-db.md>), [cs-ir](<https://devfeed.tech/tags/cs-ir.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [databases](<https://devfeed.tech/tags/databases.md>), [experiments](<https://devfeed.tech/tags/experiments.md>), [graph](<https://devfeed.tech/tags/graph.md>), [guarantees](<https://devfeed.tech/tags/guarantees.md>), [hnsw](<https://devfeed.tech/tags/hnsw.md>), [nearest-neighbor](<https://devfeed.tech/tags/nearest-neighbor.md>), [recall](<https://devfeed.tech/tags/recall.md>), [recovery](<https://devfeed.tech/tags/recovery.md>), [search](<https://devfeed.tech/tags/search.md>), [throughput](<https://devfeed.tech/tags/throughput.md>)

### AI overview

Certify-then-Rectify (CTR) aims to guarantee population recall for graph-based nearest-neighbor search: it accepts an initial result when a calibrated test certifies it, otherwise searches for missing neighbors using the existing graph and previously computed distances. Stretch-Bounded Expansion from Query (SBE-Q) sets the recovery search budget using graph stretch and the fraction of true neighbors needed for the requested recall; Metric Bound Verification prunes work. Finite-sample tolerance bounds support the budget estimate, while recorded recovery paths provide a conservative alternative to separate shortest-path calculations. Independent tests certify acceptance and recovery; queries that cannot be certified fall back to exact scan. The abstract reports experiments comparing five stretch estimators and assessing recovery, compliance, and throughput on HNSW databases up to 100 million vectors, plus evaluation on another graph index. It does not identify that index or give comparative results.

### Source excerpt

arXiv:2607.02338v3 Announce Type: replace Abstract: Graph-based indexes such as Hierarchical Navigable Small World (HNSW) graphs make nearest-neighbor retrieval efficient, but a high average recall can hide queries whose results fall below an application's quality requirement. We introduce Certify-then-Rectify (CTR), which returns an initial graph-search result when a calibrated rule accepts it and searches for missing neighbors otherwise. The recovery search reuses the existing graph and the distances already evaluated by the initial search. To determine how far this search should proceed, we relate metric distances to graph-path lengths through graph stretch. We develop Stretch-Bounded Expansion from Query (SBE-Q), together with Metric Bound Verification (MBV) to prune unnecessary work, and estimate its budget from paths to the fraction of true neighbors needed for the requested recall. Finite-sample tolerance bounds support this recall-aligned estimate; paths recorded during proposal recovery offer a conservative alternative to separate shortest-path computations. Independent tests certify initial acceptance and recovery outcomes, giving an end-to-end population recall guarantee even when the estimated stretch does not cover every relevant path. If recovery cannot be certified, rejected queries use exact scan. Experiments on HNSW compare five stretch estimators, assess recovery efficiency, and evaluate compliance and throughput on databases of up to 100 million vectors. CTR is not specific to HNSW, and we also evaluate it on another graph index.

## REWEAVE: Online Learning for Workload-Adaptive HNSW Indexes

DevFeed: [REWEAVE: Online Learning for Workload-Adaptive HNSW Indexes](<https://devfeed.tech/articles/reweave-online-learning-for-workload-adaptive-hnsw-indexes-132697.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.16060>)

Author: Minghao Li, Nick Koudas, Raghav Mittal

Published: 2026-11-13T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Databases](<https://devfeed.tech/sources/arxiv-databases.md>), [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [Machine learning](<https://devfeed.tech/topics/machine-learning.md>), [ann](<https://devfeed.tech/topics/ann.md>), [Embeddings](<https://devfeed.tech/topics/embeddings.md>), [AI-driven information retrieval](<https://devfeed.tech/topics/ai-driven-information-retrieval.md>)

Tags: [adaptive](<https://devfeed.tech/tags/adaptive.md>), [cs-db](<https://devfeed.tech/tags/cs-db.md>), [cs-ir](<https://devfeed.tech/tags/cs-ir.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [databases](<https://devfeed.tech/tags/databases.md>), [edge](<https://devfeed.tech/tags/edge.md>), [feedback](<https://devfeed.tech/tags/feedback.md>), [graph](<https://devfeed.tech/tags/graph.md>), [graphs](<https://devfeed.tech/tags/graphs.md>), [hnsw](<https://devfeed.tech/tags/hnsw.md>), [index](<https://devfeed.tech/tags/index.md>), [indexes](<https://devfeed.tech/tags/indexes.md>), [learning](<https://devfeed.tech/tags/learning.md>), [maintenance](<https://devfeed.tech/tags/maintenance.md>), [online](<https://devfeed.tech/tags/online.md>), [online-learning](<https://devfeed.tech/tags/online-learning.md>), [query](<https://devfeed.tech/tags/query.md>), [search](<https://devfeed.tech/tags/search.md>), [similarity](<https://devfeed.tech/tags/similarity.md>), [similarity-search](<https://devfeed.tech/tags/similarity-search.md>), [utility](<https://devfeed.tech/tags/utility.md>), [vector](<https://devfeed.tech/tags/vector.md>), [vector-databases](<https://devfeed.tech/tags/vector-databases.md>)

### AI overview

REWEAVE adapts HNSW indexes to skewed or changing query workloads by learning edge utility from query feedback and periodically rewiring the bottom layer while respecting the original per-node degree cap. It combines sparse exact-neighbor feedback with self-labels; standard HNSW serving has no learning overhead once adaptation is disabled, though adaptation itself adds work. The authors report formal value-estimation and graph-stabilization guarantees under explicit assumptions. In reported evaluations, it improves held-out recall by up to 23.3 percentage points over HNSW under stationary skew, reaches up to 3.3x NGFix's query throughput at recall@100 of 0.80, and on Amazon-ESCI with query drift raises stream recall@100 from 0.745 to 0.979 while using 34% fewer search distance computations than frozen HNSW.

### Source excerpt

arXiv:2611.16060v1 Announce Type: new Abstract: Vector databases rely on Hierarchical Navigable Small World (HNSW) indexes for similarity search, but a graph built from data alone can be poorly matched to a skewed or changing query workload. We present REWEAVE (Reward-Guided Rewiring of Vector Graphs), an online index-maintenance method that learns edge utility from query feedback and periodically rewires the bottom layer within the original per-node degree cap. The method supports sparse exact-neighbor feedback combined with self-labels, and standard HNSW serving without learning overhead once adaptation is disabled. Under explicit assumptions we prove value-estimation and graph-stabilization guarantees. Under stationary skew, REWEAVE improves held-out recall by up to 23.3 percentage points over HNSW. In comparisons with query-aware baselines on up to 100M vectors, it achieves up to 3.3x NGFix's query throughput at recall@100 of 0.80. On Amazon-ESCI with query drift, it increases stream recall@100 from 0.745 to 0.979 with 34% fewer search distance computations than frozen HNSW. These results illustrate the potential to improve retrieval quality and reduce search effort within an existing graph-degree budget, while incurring additional work during adaptation.

## Calibrated Early Termination with Bounded Optimality Gaps for Constrained Vector Search

DevFeed: [Calibrated Early Termination with Bounded Optimality Gaps for Constrained Vector Search](<https://devfeed.tech/articles/calibrated-early-termination-with-bounded-optimality-gaps-for-constrained-vector-search-132699.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.16148>)

Author: Xinyu Zhang, Jingze Li, Baihua Zheng, Weiwei Sun

Published: 2026-11-13T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Databases](<https://devfeed.tech/sources/arxiv-databases.md>), [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [ann](<https://devfeed.tech/topics/ann.md>), [Embeddings](<https://devfeed.tech/topics/embeddings.md>), [Vectors & LLMs](<https://devfeed.tech/topics/vectors-llms.md>)

Tags: [cost](<https://devfeed.tech/tags/cost.md>), [cs-db](<https://devfeed.tech/tags/cs-db.md>), [cs-ir](<https://devfeed.tech/tags/cs-ir.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [datasets](<https://devfeed.tech/tags/datasets.md>), [duality](<https://devfeed.tech/tags/duality.md>), [dynamic-programming](<https://devfeed.tech/tags/dynamic-programming.md>), [embeddings](<https://devfeed.tech/tags/embeddings.md>), [failure](<https://devfeed.tech/tags/failure.md>), [faster](<https://devfeed.tech/tags/faster.md>), [graph](<https://devfeed.tech/tags/graph.md>), [indexes](<https://devfeed.tech/tags/indexes.md>), [linear](<https://devfeed.tech/tags/linear.md>), [lower-bound](<https://devfeed.tech/tags/lower-bound.md>), [multiple-testing](<https://devfeed.tech/tags/multiple-testing.md>), [nearest-neighbor](<https://devfeed.tech/tags/nearest-neighbor.md>), [queries](<https://devfeed.tech/tags/queries.md>), [query](<https://devfeed.tech/tags/query.md>), [recall](<https://devfeed.tech/tags/recall.md>), [recommendation](<https://devfeed.tech/tags/recommendation.md>), [search](<https://devfeed.tech/tags/search.md>), [vector](<https://devfeed.tech/tags/vector.md>), [vector-search](<https://devfeed.tech/tags/vector-search.md>)

### AI overview

CaST calibrates early stopping for constrained vector search to bound the probability of returning an inexact answer by ε, with confidence 1−δ. It restricts stopping rules to those monotone in declared observations, computes a nested chain of staircase rules by dynamic programming, and uses fixed-sequence binomial tests to calibrate them. Lagrangian weak duality supplies a lower bound on the best cost within that class across risk levels without a union bound over rules. In replay on two million-item datasets, CaST cost at most 1.132 times the class optimum for risk levels 0.03-0.10, with 95% joint confidence per setting; on held-out queries at a common risk target, other calibrated rules tested took 4.8%-45.5% more mean time. The guarantee and optimality comparison are limited to the declared rule class and reported experiments.

### Source excerpt

arXiv:2611.16148v1 Announce Type: new Abstract: Vector search over learned embeddings is the retrieval layer of recommendation and retrieval-augmented generation, and many applications cap how many answer items one category may contribute. Graph indexes answer a query by best-first traversal, and where it stops determines its cost and whether its answer is exact. We study early termination for such constrained $k$-nearest-neighbor ($k$-NN) queries, with plain $k$-NN as a special case, and seek the cheapest stopping rule whose answer is exact with probability at least $1-\varepsilon$. Learned early-termination methods instead target average recall, which does not guarantee exact answers. Multiple testing can calibrate any parameterized stopping rule to our target, but it cannot tell how much a better rule with the same risk and observations would save. Answering this needs a lower bound on the optimum of a rule family too large to enumerate, valid for the query population. Our key idea is to declare the observations a rule may use and to consider every rule monotone in them. Risk-constrained stopping then becomes a linear program over an order polytope, whose Lagrangian minimizers form a nested chain of staircase rules computed exactly by dynamic programming. Fixed-sequence binomial tests along this chain calibrate our rule, CaST, whose failure probability is at most $\varepsilon$ with confidence $1-\delta$. Lagrangian weak duality bounds the optimum of the declared class from below at all risk levels at once, without a union bound over the rules. On two datasets of one million items each, CaST replayed on logged searches costs at most 1.132 times the class optimum for risk levels from 0.03 to 0.10, at 95% joint confidence per setting. Larger savings thus need a rule outside the class. At a common risk target on held-out queries, CaST is faster than every other calibrated rule we time, which take 4.8% to 45.5% more mean time.

## How Vector Search Works Inside TiDB for AI Applications

DevFeed: [How Vector Search Works Inside TiDB for AI Applications](<https://devfeed.tech/articles/how-vector-search-works-inside-tidb-for-ai-applications-128968.md>)

Original publisher: [Read original article](<https://www.pingcap.com/blog/integrating-vector-search-into-tidb-for-ai-applications/>)

Author: Xin Shi

Published: 2026-11-10T18:43:16Z

Content type: article

Language: en

Sources: [TiDB](<https://devfeed.tech/sources/tidb.md>)

Topics: [Retrieval Augmented Generation (RAG)](<https://devfeed.tech/topics/retrieval-augmented-generation-rag.md>), [Embeddings](<https://devfeed.tech/topics/embeddings.md>), [ann](<https://devfeed.tech/topics/ann.md>), [cosine similarity search](<https://devfeed.tech/topics/cosine-similarity-search.md>)

Tags: [ai](<https://devfeed.tech/tags/ai.md>), [ai-applications](<https://devfeed.tech/tags/ai-applications.md>), [application](<https://devfeed.tech/tags/application.md>), [applications](<https://devfeed.tech/tags/applications.md>), [article](<https://devfeed.tech/tags/article.md>), [can](<https://devfeed.tech/tags/can.md>), [context](<https://devfeed.tech/tags/context.md>), [customer](<https://devfeed.tech/tags/customer.md>), [database](<https://devfeed.tech/tags/database.md>), [embeddings](<https://devfeed.tech/tags/embeddings.md>), [first](<https://devfeed.tech/tags/first.md>), [form](<https://devfeed.tech/tags/form.md>), [inside](<https://devfeed.tech/tags/inside.md>), [job](<https://devfeed.tech/tags/job.md>), [keep](<https://devfeed.tech/tags/keep.md>), [mysql](<https://devfeed.tech/tags/mysql.md>), [product](<https://devfeed.tech/tags/product.md>), [search](<https://devfeed.tech/tags/search.md>), [tidb](<https://devfeed.tech/tags/tidb.md>), [tidb-serverless](<https://devfeed.tech/tags/tidb-serverless.md>), [vector](<https://devfeed.tech/tags/vector.md>), [vector-search](<https://devfeed.tech/tags/vector-search.md>), [works](<https://devfeed.tech/tags/works.md>)

### AI overview

TiDB stores embeddings with transactional data: TiKV commits writes, then TiFlash replicates them and serves HNSW vector search. This lets RAG retrieval join vectors with permissions, tenants, and document versions in one SQL query, and makes committed rows searchable without a separate sync pipeline. New or updated rows in TiFlash's Delta layer remain searchable but run more slowly until compaction moves them into the indexed Stable layer. The article reports HNSW recall generally above 90% and notes that a 500 MiB dataset of 768-dimensional vectors may take up to 20 minutes to index. Vector search requires TiFlash; pre-KNN WHERE filters bypass the index, so the suggested subquery pattern can return fewer than K rows. Availability varies by deployment: TiDB Cloud documentation labels the feature beta, while Self-Managed documentation calls it experimental and not recommended for production.

### Source excerpt

Key Takeaways When a RAG application keeps embeddings in a separate vector store, an edited support article can keep surfacing in its old form until the next sync job runs. The model then answers from stale context, and nobody notices until a customer does. Knowing how vector search works inside your database tells you how [...] The post How Vector Search Works Inside TiDB for AI Applications appeared first on TiDB.

## NAVIS: Concurrent Search and Update with Low Position-Seeking Overhead in On-SSD Graph-Based Vector Search

DevFeed: [NAVIS: Concurrent Search and Update with Low Position-Seeking Overhead in On-SSD Graph-Based Vector Search](<https://devfeed.tech/articles/navis-concurrent-search-and-update-with-low-position-seeking-overhead-in-on-ssd-graph-based-vector-search-126686.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2605.11523>)

Author: Jaeyong Song, Hongsun Jang, Changmin Shin, Seongyeon Park, Yong Jae Ryoo, Seo Jin Park, Jinho Lee

Published: 2026-11-10T05:00:00Z

Content type: news

Language: en

Sources: [arXiv: Distributed Computing](<https://devfeed.tech/sources/arxiv-distributed-computing.md>)

Topics: [ann](<https://devfeed.tech/topics/ann.md>)

Tags: [benchmarks](<https://devfeed.tech/tags/benchmarks.md>), [cache](<https://devfeed.tech/tags/cache.md>), [concurrent](<https://devfeed.tech/tags/concurrent.md>), [convergence](<https://devfeed.tech/tags/convergence.md>), [cs-dc](<https://devfeed.tech/tags/cs-dc.md>), [decoupling](<https://devfeed.tech/tags/decoupling.md>), [graph](<https://devfeed.tech/tags/graph.md>), [latency](<https://devfeed.tech/tags/latency.md>), [lightweight](<https://devfeed.tech/tags/lightweight.md>), [overhead](<https://devfeed.tech/tags/overhead.md>), [reranking](<https://devfeed.tech/tags/reranking.md>), [reuse](<https://devfeed.tech/tags/reuse.md>), [search](<https://devfeed.tech/tags/search.md>), [serving](<https://devfeed.tech/tags/serving.md>), [shortcuts](<https://devfeed.tech/tags/shortcuts.md>), [ssd](<https://devfeed.tech/tags/ssd.md>), [stable](<https://devfeed.tech/tags/stable.md>), [system](<https://devfeed.tech/tags/system.md>), [update](<https://devfeed.tech/tags/update.md>), [vector](<https://devfeed.tech/tags/vector.md>), [vector-search](<https://devfeed.tech/tags/vector-search.md>)

### AI overview

NAVIS targets position seeking--the broad neighbor-finding traversal performed during updates--as a bottleneck in concurrent on-SSD graph-based vector search. It separates vectors from edge lists and packs graph-local edge lists together, allowing cache capacity to focus on edge lists. Convergence-aware speculative reranking loads full vectors selectively to resolve close neighbors, while choosing remaining long-range shortcuts with approximate distances. Lightweight updates reuse traversal information to keep the entrance graph fresh and maintain a hot set of nearby edge lists. Across multiple large-scale benchmarks, NAVIS reports up to 3.97x higher insertion throughput, up to 4.00x higher concurrent search throughput, and up to 75.69% lower search latency. The abstract does not specify benchmark details.

### Source excerpt

arXiv:2605.11523v2 Announce Type: replace Abstract: On-disk graph-based vector search (GVS) has become the dominant approach for serving large-scale vector databases at high recall. Yet prior systems struggle to sustain concurrent search and update throughput on high-dimensional workloads. We identify the main bottleneck as position seeking, the graph traversal that finds neighbors during each update. Unlike search, which returns only the top-K closest vectors, it explores a much larger set to build an R-neighbor list of close neighbors and long-range shortcuts. These neighbors have different distance-accuracy requirements, yet search-oriented packed layouts fetch full vectors with every edge-list access, consuming cache capacity regardless of their role. We present NAVIS, an on-SSD GVS system that redesigns position seeking around this mismatch. At its core, locality-driven decoupling separates vectors from edgelists and packs graph-local edgelists together. This decoupling enables convergence-aware speculative reranking to selectively load full vectors until a sufficient set of close neighbors is resolved, while selecting the remaining shortcuts using approximate distances. It also allows NAVIS to devote cache capacity entirely to edgelists. To make this cache effective, NAVIS keeps the entrance graph fresh via lightweight updates that reuse traversal information already produced during position seeking, thereby maintaining a stable hot set of edgelists near its entry points. Across multiple large-scale benchmarks, NAVIS improves insertion throughput by up to 3.97x and concurrent search throughput by up to 4.00x while reducing search latency by up to 75.69%.

## Query- and Candidate-Aware Long User Sequence Modeling for Sponsored Product Ranking in Search

DevFeed: [Query- and Candidate-Aware Long User Sequence Modeling for Sponsored Product Ranking in Search](<https://devfeed.tech/articles/query-and-candidate-aware-long-user-sequence-modeling-for-sponsored-product-ranking-in-search-125427.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.11675>)

Author: Dongyue Xie, Sergey Kolbin, Manavender Malgireddy, Iurii Shcherbak, Weixing Tang, Arushi Jain, Wanchen Shao, Kurt Zimmer, Raja Hafiz Affandi, Matt Lindsay

Published: 2026-11-10T05:00:00Z

Content type: news

Language: en

Sources: [arXiv: Machine Learning](<https://devfeed.tech/sources/arxiv-machine-learning.md>)

Topics: [information retrieval](<https://devfeed.tech/topics/information-retrieval.md>), [personalization](<https://devfeed.tech/topics/personalization.md>), [ann](<https://devfeed.tech/topics/ann.md>), [product-experimentation](<https://devfeed.tech/topics/product-experimentation.md>)

Tags: [actions](<https://devfeed.tech/tags/actions.md>), [advertising](<https://devfeed.tech/tags/advertising.md>), [behavior](<https://devfeed.tech/tags/behavior.md>), [candidate](<https://devfeed.tech/tags/candidate.md>), [context](<https://devfeed.tech/tags/context.md>), [conversion](<https://devfeed.tech/tags/conversion.md>), [cs-lg](<https://devfeed.tech/tags/cs-lg.md>), [framework](<https://devfeed.tech/tags/framework.md>), [fusion](<https://devfeed.tech/tags/fusion.md>), [history](<https://devfeed.tech/tags/history.md>), [metrics](<https://devfeed.tech/tags/metrics.md>), [model](<https://devfeed.tech/tags/model.md>), [modeling](<https://devfeed.tech/tags/modeling.md>), [nearest-neighbor](<https://devfeed.tech/tags/nearest-neighbor.md>), [product](<https://devfeed.tech/tags/product.md>), [query](<https://devfeed.tech/tags/query.md>), [ranking](<https://devfeed.tech/tags/ranking.md>), [search](<https://devfeed.tech/tags/search.md>), [sequence](<https://devfeed.tech/tags/sequence.md>), [sponsored](<https://devfeed.tech/tags/sponsored.md>), [stat-ml](<https://devfeed.tech/tags/stat-ml.md>), [user](<https://devfeed.tech/tags/user.md>)

### AI overview

The framework ranks sponsored products by combining recent behavior with two long-term history retrieval channels: actions similar to the current candidate and actions similar to the current query. It encodes retrieved actions with query and candidate context tokens, and injects candidate context into each history token through early fusion. Offline ablations report improved major ranking metrics over the production baseline. An online A/B test on sponsored-product search traffic reports increases in CTR, attributed conversion rate, and orders per impression; the excerpt gives no effect sizes or implementation details.

### Source excerpt

arXiv:2611.11675v1 Announce Type: cross Abstract: User sequence modeling is widely used in recommendation and advertising. Search ranking presents an additional challenge: the current query expresses immediate intent, while a candidate product determines which parts of a user's long-term history are relevant. We present a production sequence framework for sponsored-product ranking that augments recent behavior with two retrieval channels over long-term history: candidate-nearest-neighbor retrieval and query-nearest-neighbor retrieval. The selected actions are encoded together with dedicated query and candidate context tokens, while candidate-aware early fusion injects the candidate into every history token. Offline ablations show that dual retrieval improves major ranking metrics relative to the production baseline. In an online A/B test on sponsored-product search traffic, the model increased CTR, attributed conversion rate, and orders per impression.

## Dynamic Graph Indexing for Label-Filtered Approximate Nearest Neighbor Search

DevFeed: [Dynamic Graph Indexing for Label-Filtered Approximate Nearest Neighbor Search](<https://devfeed.tech/articles/dynamic-graph-indexing-for-label-filtered-approximate-nearest-neighbor-search-125676.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.12539>)

Author: Mengxu Jiang, Zhi Yang, Fangyuan Zhang, Yin Yang, Sibo Wang

Published: 2026-11-10T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Databases](<https://devfeed.tech/sources/arxiv-databases.md>)

Topics: [ann](<https://devfeed.tech/topics/ann.md>), [LanceDB vector database](<https://devfeed.tech/topics/lancedb-vector-database.md>), [search-engines](<https://devfeed.tech/topics/search-engines.md>)

Tags: [approximate-nearest-neighbor-search](<https://devfeed.tech/tags/approximate-nearest-neighbor-search.md>), [composite-index](<https://devfeed.tech/tags/composite-index.md>), [cs-db](<https://devfeed.tech/tags/cs-db.md>), [exploits](<https://devfeed.tech/tags/exploits.md>), [fragmentation](<https://devfeed.tech/tags/fragmentation.md>), [graph](<https://devfeed.tech/tags/graph.md>), [hnsw](<https://devfeed.tech/tags/hnsw.md>), [indexing](<https://devfeed.tech/tags/indexing.md>), [maintenance](<https://devfeed.tech/tags/maintenance.md>), [memory](<https://devfeed.tech/tags/memory.md>), [query](<https://devfeed.tech/tags/query.md>), [trie](<https://devfeed.tech/tags/trie.md>), [update](<https://devfeed.tech/tags/update.md>), [vector](<https://devfeed.tech/tags/vector.md>), [vector-similarity](<https://devfeed.tech/tags/vector-similarity.md>)

### AI overview

DYLAN combines a frequency-ordered trie over label sets with selectively shared HNSW-style graph indices for label-filtered approximate nearest-neighbor search. It supports containment, overlap, and combinations of those filters. Cross-region search uses ancestor-level indices as bridges between fragmented regions; a threshold-based policy rebuilds shared indices when needed to support insertions at low amortized update cost. The abstract reports higher query throughput at comparable recall, reaching up to two orders of magnitude improvement on challenging label-rich datasets, with competitive memory, construction, and update costs. These are abstract-level claims; no experiment details are provided in the supplied text.

### Source excerpt

arXiv:2611.12539v1 Announce Type: new Abstract: Approximate nearest neighbor search (ANNS) over high-dimensional vectors is a core primitive in modern retrieval systems. In practice, objects are often also associated with labels (e.g., attributes or keywords), and retrieval must combine vector similarity with explicit label-based filtering, giving rise to label-filtered ANNS. This task is challenging because label filtering and ANNS favor very different index structures, selective filters fragment the admissible search space, and updates complicate index maintenance. To address these challenges, we propose DYLAN, a dynamic composite index for label-filtered ANNS supporting containment, overlap, and their conjunctions and disjunctions. DYLAN organizes label sets by shared prefixes in a frequency-ordered trie and selectively shares HNSW-style graph indices across trie-induced subsets, so that each trie region has a constant-factor covering index while each object participates in only logarithmically many indices. To mitigate fragmentation, DYLAN performs a cross-region multi-graph search that exploits ancestor-level indices as bridges between otherwise isolated trie regions. To support insertions, it adopts a threshold-based maintenance scheme that rebuilds shared indices only when necessary, yielding low amortized update cost. Extensive experiments with real data show that DYLAN consistently improves query throughput at comparable recall, by up to two orders of magnitude on challenging label-rich datasets, while retaining competitive memory, construction, and update costs.

## RACORN: Robust Predicate-Agnostic Filtered Vector Search under Extreme Selectivity

DevFeed: [RACORN: Robust Predicate-Agnostic Filtered Vector Search under Extreme Selectivity](<https://devfeed.tech/articles/racorn-robust-predicate-agnostic-filtered-vector-search-under-extreme-selectivity-124224.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2607.00768>)

Author: Yoonseok Kim, Gyusik Choe

Published: 2026-11-09T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Databases](<https://devfeed.tech/sources/arxiv-databases.md>)

Topics: [ann](<https://devfeed.tech/topics/ann.md>)

Tags: [cs-db](<https://devfeed.tech/tags/cs-db.md>), [cs-ir](<https://devfeed.tech/tags/cs-ir.md>), [predicate](<https://devfeed.tech/tags/predicate.md>), [robust](<https://devfeed.tech/tags/robust.md>), [search](<https://devfeed.tech/tags/search.md>), [vector](<https://devfeed.tech/tags/vector.md>), [vector-search](<https://devfeed.tech/tags/vector-search.md>)

### AI overview

RACORN-1 extends ACORN-1's filter-first traversal with Adaptive Search Fallback for highly selective predicates. When a node's two-hop expansion yields too few candidates, it adds failing nodes as budget-limited bridges to the candidate queue, never to the results. The abstract reports that RACORN-1 reaches 0.95 recall at selectivities from 3% down across the swept datasets, while ACORN-1 cannot reach 0.9 below 1%; it also reaches 0.9 on the tested natural, conjunction, and caption predicates where ACORN-1 misses more than half. At 1% selectivity and 0.9 recall, RACORN-1 is reported 1.3-8.4x faster than HNSW across eight indexes, and 2.2-10.5x faster under adverse correlation. These findings are limited to the reported benchmarks.

### Source excerpt

arXiv:2607.00768v2 Announce Type: replace Abstract: Filtered vector search returns the nearest neighbors among the vectors that pass a predicate. The predicate is often selective: most tag queries of the Big ANN filtered track select less than 1% of YFCC 10M. Predicate-agnostic methods search one HNSW graph built without metadata and so take any predicate, but below a few percent selectivity they break down. ACORN-1 draws candidates only from passing neighbors and its recall collapses below 1%. HNSW keeps searching but spends about ef/s expansion cycles at selectivity s. We present RACORN-1, an extension of ACORN-1 that keeps its graph and filter-first traversal and adds Adaptive Search Fallback. When the two-hop expansion of a node falls short of a target, failing nodes enter the candidate queue as bridges, under a per-expansion budget, but never enter the result queue. RACORN-1 serves the selectivities ACORN-1 cannot: from 1% down ACORN-1 no longer reaches recall 0.9 at any ef, while RACORN-1 reaches 0.95 from 3% down on every dataset we sweep. It also reaches 0.9 on every natural filter that YFCC and LAION ship and on every conjunction and caption predicate we run, where ACORN-1 misses more than half. With a deadline equal to the time HNSW needs to fill its result queue, RACORN-1 returns the higher recall on all eight datasets at four selectivities. On eight indexes of 1M to 100M vectors, at 1% selectivity and recall 0.9 it is 1.3-8.4x faster than HNSW, and it is 2.2-10.5x faster under adverse correlation.

## Beyond Overlap: Hierarchical Graph Abstraction for Out-of-Core Vector Search

DevFeed: [Beyond Overlap: Hierarchical Graph Abstraction for Out-of-Core Vector Search](<https://devfeed.tech/articles/beyond-overlap-hierarchical-graph-abstraction-for-out-of-core-vector-search-124223.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2512.22838>)

Author: Lizheng Chen, Pinhuan Wang, Shaonan Ma, Jie Zhang, Qing Wang, Zhengyi Yang, Heng Zhang, Mingxing Zhang, Fan Yang, Guihai Chen, Chen Tian, Chengying Huan

Published: 2026-11-09T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Databases](<https://devfeed.tech/sources/arxiv-databases.md>)

Topics: [ann](<https://devfeed.tech/topics/ann.md>), [clustering](<https://devfeed.tech/topics/clustering.md>), [Memory Heirarchy](<https://devfeed.tech/topics/memory-heirarchy.md>), [quantization](<https://devfeed.tech/topics/quantization.md>), [abstraction](<https://devfeed.tech/topics/abstraction.md>)

Tags: [abstraction](<https://devfeed.tech/tags/abstraction.md>), [approximate-nearest-neighbor](<https://devfeed.tech/tags/approximate-nearest-neighbor.md>), [approximate-nearest-neighbor-search](<https://devfeed.tech/tags/approximate-nearest-neighbor-search.md>), [cluster](<https://devfeed.tech/tags/cluster.md>), [clusters](<https://devfeed.tech/tags/clusters.md>), [cs-db](<https://devfeed.tech/tags/cs-db.md>), [cs-ir](<https://devfeed.tech/tags/cs-ir.md>), [efficiency](<https://devfeed.tech/tags/efficiency.md>), [graph](<https://devfeed.tech/tags/graph.md>), [i-o](<https://devfeed.tech/tags/i-o.md>), [locality](<https://devfeed.tech/tags/locality.md>), [memory](<https://devfeed.tech/tags/memory.md>), [nearest-neighbor](<https://devfeed.tech/tags/nearest-neighbor.md>), [partition](<https://devfeed.tech/tags/partition.md>), [partitions](<https://devfeed.tech/tags/partitions.md>), [query](<https://devfeed.tech/tags/query.md>), [search](<https://devfeed.tech/tags/search.md>), [vector](<https://devfeed.tech/tags/vector.md>), [vector-search](<https://devfeed.tech/tags/vector-search.md>)

### AI overview

GANNS targets billion-scale approximate nearest neighbor search when the vector collection and index exceed memory and SSD traffic dominates. It keeps clusters in disjoint SSD partitions with scale-aware indexes, while a memory-resident graph abstraction supplies logical overlap before SSD access. Query hotness and cluster priorities guide pruning of low-value clusters and improve access locality. This design avoids the index replication and extra I/O associated with physical overlap; the abstract contrasts it with quantization, which can require costly raw-vector reranking to preserve recall. Across five datasets under strict memory constraints, GANNS reports representative QPS gains of 2.0-4.7x over state-of-the-art baselines while preserving accuracy.

### Source excerpt

arXiv:2512.22838v3 Announce Type: replace Abstract: At billion scale, approximate nearest neighbor search (ANNS) often becomes an out-of-core problem: the full vector collection and index structures exceed memory capacity, making query performance dominated by SSD accesses and DRAM-SSD data movement. Existing systems struggle to strike a balance between accuracy and efficiency: physical-overlap methods replicate vectors or index entries across partitions, enlarging the SSD-resident index and incurring extra I/O; quantization-based methods reduce memory usage, but their approximate distances are less reliable and often require costly raw-vector reranking from SSD to preserve recall. We present GANNS (Graph-Abstraction ANNS), a hierarchical out-of-core ANNS engine that improves accuracy and I/O efficiency simultaneously. GANNS stores each cluster as a disjoint SSD partition with scale-aware indexes, while a memory-resident graph abstraction provides logical overlap before SSD access. During serving, GANNS uses query hotness and cluster priorities from the graph abstraction to prune low-value clusters and improve access locality. Across five datasets under strict memory constraints, GANNS delivers representative QPS improvements of 2.0--4.7x over state-of-the-art baselines, while preserving accuracy.

## MV-IVF: Multi-Vector Retrieval via Multi-Vector Clustering

DevFeed: [MV-IVF: Multi-Vector Retrieval via Multi-Vector Clustering](<https://devfeed.tech/articles/mv-ivf-multi-vector-retrieval-via-multi-vector-clustering-124227.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2611.09040>)

Author: Kishen N Gowda, Laxman Dhulipala, Lars Gottesb\\"uren, Rajesh Jayaram

Published: 2026-11-09T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Databases](<https://devfeed.tech/sources/arxiv-databases.md>)

Topics: [search-engines](<https://devfeed.tech/topics/search-engines.md>), [Embeddings](<https://devfeed.tech/topics/embeddings.md>), [clustering](<https://devfeed.tech/topics/clustering.md>), [ann](<https://devfeed.tech/topics/ann.md>), [quantization](<https://devfeed.tech/topics/quantization.md>), [Compression](<https://devfeed.tech/topics/compression.md>)

Tags: [accelerate](<https://devfeed.tech/tags/accelerate.md>), [algorithm](<https://devfeed.tech/tags/algorithm.md>), [arxiv](<https://devfeed.tech/tags/arxiv.md>), [beam](<https://devfeed.tech/tags/beam.md>), [benchmarks](<https://devfeed.tech/tags/benchmarks.md>), [build](<https://devfeed.tech/tags/build.md>), [c-plus-plus](<https://devfeed.tech/tags/c-plus-plus.md>), [cache](<https://devfeed.tech/tags/cache.md>), [candidate](<https://devfeed.tech/tags/candidate.md>), [cluster](<https://devfeed.tech/tags/cluster.md>), [clustering](<https://devfeed.tech/tags/clustering.md>), [clusters](<https://devfeed.tech/tags/clusters.md>), [compression](<https://devfeed.tech/tags/compression.md>), [construction](<https://devfeed.tech/tags/construction.md>), [cs-db](<https://devfeed.tech/tags/cs-db.md>), [cs-ir](<https://devfeed.tech/tags/cs-ir.md>), [data](<https://devfeed.tech/tags/data.md>), [embeddings](<https://devfeed.tech/tags/embeddings.md>), [evaluation](<https://devfeed.tech/tags/evaluation.md>), [ivf](<https://devfeed.tech/tags/ivf.md>), [retrieval](<https://devfeed.tech/tags/retrieval.md>), [vector](<https://devfeed.tech/tags/vector.md>)

### AI overview

MV-IVF indexes multi-vector data directly with a hierarchical inverted-file tree. Its MV-Lloyd algorithm clusters point clouds using a Chamfer objective; after assignment, center updates reduce to standard clustering over flattened embeddings. At query time, best-first beam search selects promising leaf clusters, whose documents are then scored. Low-bit quantization, query compression, and cache-efficient batched search further accelerate retrieval. On BEIR and LoTTE text retrieval benchmarks, the authors report strong latency-recall tradeoffs, the best batched throughput frontiers, and favorable build-time and index-size profiles. At 90% Recall-10@10, they report up to 8.03x lower single-query latency and 173.5x higher QPS than the evaluated baselines.

### Source excerpt

arXiv:2611.09040v1 Announce Type: cross Abstract: Multi-vector retrieval represents each query and document as a set of embeddings and scores relevance via fine-grained set-to-set interactions such as MaxSim (Chamfer similarity). This expressiveness improves retrieval quality over single-vector representations, but makes search substantially more expensive. Existing systems address this challenge primarily through proxy representations or filter-and-rerank pipelines that reduce candidate generation to single-vector search. We study the complementary direction of building a native IVF-style index directly over multi-vector data. We introduce MV-IVF, an inverted-file index for multi-vector retrieval built on MV-Lloyd, a new Lloyd-style algorithm for clustering point clouds under a Chamfer objective. Our key observation is that once point clouds are assigned to clusters, the center-update step reduces to standard single-vector clustering over the flattened embeddings in each cluster. This enables efficient construction of a hierarchical IVF tree with center point clouds at internal nodes. At query time, MV-IVF performs best-first beam search over the tree to identify promising leaf clusters, then scores the documents in those leaves. We further accelerate search using low-bit quantization, query compression, and cache-efficient batched search. We implement MV-IVF in MVSIC, an optimized C++ library and unified evaluation framework for multi-vector retrieval that includes several major approaches. Across BEIR and LoTTE text retrieval benchmarks, MV-IVF achieves strong latency--recall tradeoffs, the best batched throughput frontiers, and favorable build-time and index-size profiles. At $90\%$ Recall-$10$@$10$, MV-IVF achieves up to $8.03\times$ lower single-query latency and up to $173.5\times$ higher QPS than the baselines, demonstrating that native IVF-style indexing is practical and effective for scalable multi-vector retrieval.

## MCGI: Manifold-Consistent Graph Indexing for Billion-Scale Disk-Resident Vector Search

DevFeed: [MCGI: Manifold-Consistent Graph Indexing for Billion-Scale Disk-Resident Vector Search](<https://devfeed.tech/articles/mcgi-manifold-consistent-graph-indexing-for-billion-scale-disk-resident-vector-search-124366.md>)

Original publisher: [Read original article](<https://arxiv.org/abs/2601.01930>)

Author: Dongfang Zhao

Published: 2026-11-09T05:00:00Z

Content type: article

Language: en

Sources: [arXiv: Artificial Intelligence](<https://devfeed.tech/sources/arxiv-artificial-intelligence.md>)

Topics: [ann](<https://devfeed.tech/topics/ann.md>), [Graphs](<https://devfeed.tech/topics/graphs.md>)

Tags: [abstract](<https://devfeed.tech/tags/abstract.md>), [analysis](<https://devfeed.tech/tags/analysis.md>), [ann](<https://devfeed.tech/tags/ann.md>), [approximate-nearest-neighbor](<https://devfeed.tech/tags/approximate-nearest-neighbor.md>), [benchmarks](<https://devfeed.tech/tags/benchmarks.md>), [candidate](<https://devfeed.tech/tags/candidate.md>), [cs-ai](<https://devfeed.tech/tags/cs-ai.md>), [cs-ir](<https://devfeed.tech/tags/cs-ir.md>), [diskann](<https://devfeed.tech/tags/diskann.md>), [graph](<https://devfeed.tech/tags/graph.md>), [indexing](<https://devfeed.tech/tags/indexing.md>), [intrinsic](<https://devfeed.tech/tags/intrinsic.md>), [intrinsic-dimensionality](<https://devfeed.tech/tags/intrinsic-dimensionality.md>), [list](<https://devfeed.tech/tags/list.md>), [local](<https://devfeed.tech/tags/local.md>), [nearest-neighbor](<https://devfeed.tech/tags/nearest-neighbor.md>), [performance](<https://devfeed.tech/tags/performance.md>), [probability](<https://devfeed.tech/tags/probability.md>), [scale](<https://devfeed.tech/tags/scale.md>), [search](<https://devfeed.tech/tags/search.md>), [vector](<https://devfeed.tech/tags/vector.md>), [vector-search](<https://devfeed.tech/tags/vector-search.md>)

### AI overview

MCGI adapts disk-resident graph search effort to each query's local intrinsic dimensionality (LID), addressing cases where greedy routing diverges from the data manifold. It estimates LID using distances already computed during search, without extra disk reads, then resizes the candidate list once: longer for high-LID regions and shorter for low-LID regions. Theoretical analysis says the success probability of a fixed-size search list falls exponentially with query LID. At matched high recall, MCGI reportedly improves DiskANN throughput on the same standard Vamana index by up to 1.43x on three million-scale benchmarks and 1.24x on the billion-scale SIFT1B and Deep1B datasets.

### Source excerpt

arXiv:2601.01930v4 Announce Type: replace-cross Abstract: Graph-based Approximate Nearest Neighbor (ANN) search often suffers from performance degradation in high-dimensional spaces due to the Euclidean-Geodesic mismatch, where greedy routing diverges from the underlying data manifold. To address this challenge, this paper presents Manifold-Consistent Graph Indexing (MCGI), a geometry-aware and disk-resident indexing method that leverages Local Intrinsic Dimensionality (LID) to allocate the search effort of a graph index according to the intrinsic geometry of data. Specifically, MCGI estimates the LID around each query from the distances that its own search has already computed and resizes the candidate list of the query once, so that queries in high-LID regions receive longer lists while queries in low-LID regions terminate earlier; the estimate itself costs no additional disk reads. Theoretical analysis shows that the success probability of any fixed search list decays exponentially with the LID of the query. At matched high recall, MCGI raises the query throughput of DiskANN on the same standard Vamana index by up to $1.43\times$ on three million-scale benchmarks and by up to $1.24\times$ on the billion-scale SIFT1B and Deep1B.

## Open Source pg\_vectorsearch Brings More Scalable Vector Search to PostgreSQL

DevFeed: [Open Source pg\_vectorsearch Brings More Scalable Vector Search to PostgreSQL](<https://devfeed.tech/articles/open-source-pg-vectorsearch-brings-more-scalable-vector-search-to-postgresql-122002.md>)

Original publisher: [Read original article](<https://www.infoq.com/news/2026/11/postgresql-vector-search/>)

Author: Renato Losio

Published: 2026-11-07T09:49:00Z

Content type: news

Language: en

Sources: [InfoQ](<https://devfeed.tech/sources/infoq.md>)

Topics: [PostgreSQL](<https://devfeed.tech/topics/postgresql.md>), [Embeddings](<https://devfeed.tech/topics/embeddings.md>), [ann](<https://devfeed.tech/topics/ann.md>), [Open Source](<https://devfeed.tech/topics/open-source.md>)

Tags: [ai](<https://devfeed.tech/tags/ai.md>), [ai-ml-data-engineering](<https://devfeed.tech/tags/ai-ml-data-engineering.md>), [algorithm](<https://devfeed.tech/tags/algorithm.md>), [alpha](<https://devfeed.tech/tags/alpha.md>), [approximate-nearest-neighbor](<https://devfeed.tech/tags/approximate-nearest-neighbor.md>), [architecture](<https://devfeed.tech/tags/architecture.md>), [compression](<https://devfeed.tech/tags/compression.md>), [data-partitioning](<https://devfeed.tech/tags/data-partitioning.md>), [database](<https://devfeed.tech/tags/database.md>), [development](<https://devfeed.tech/tags/development.md>), [extension](<https://devfeed.tech/tags/extension.md>), [hnsw](<https://devfeed.tech/tags/hnsw.md>), [index](<https://devfeed.tech/tags/index.md>), [memory](<https://devfeed.tech/tags/memory.md>), [ml-data-engineering](<https://devfeed.tech/tags/ml-data-engineering.md>), [news](<https://devfeed.tech/tags/news.md>), [open-source](<https://devfeed.tech/tags/open-source.md>), [pg-vectorsearch](<https://devfeed.tech/tags/pg-vectorsearch.md>), [pgvector](<https://devfeed.tech/tags/pgvector.md>), [postgres](<https://devfeed.tech/tags/postgres.md>), [postgresql](<https://devfeed.tech/tags/postgresql.md>), [postgresql-vector-search](<https://devfeed.tech/tags/postgresql-vector-search.md>), [relational-databases](<https://devfeed.tech/tags/relational-databases.md>), [search](<https://devfeed.tech/tags/search.md>), [similarity](<https://devfeed.tech/tags/similarity.md>), [similarity-search](<https://devfeed.tech/tags/similarity-search.md>), [tiger-data](<https://devfeed.tech/tags/tiger-data.md>), [vector](<https://devfeed.tech/tags/vector.md>), [vector-databases](<https://devfeed.tech/tags/vector-databases.md>), [vectorsearch](<https://devfeed.tech/tags/vectorsearch.md>)

### AI overview

Tiger Data's alpha pg_vectorsearch adds PRISM vector indexing to PostgreSQL, using hierarchical clustering, compressed partitions, and RaBitQ quantization to narrow searches and scan vectors sequentially. It supports existing pgvector columns and uses PostgreSQL's storage and concurrency mechanisms. In Tiger Data's benchmark on 100 million vectors, PRISM built an index in 1 hour 40 minutes on a 128 GB machine; HNSW took 42 hours on a 512 GB machine. The results have not been independently validated. The extension requires PostgreSQL 18 or later, supports up to 1,968 dimensions, and does not yet support filtered searches combining WHERE and ORDER BY. It is in alpha, and incomplete incremental rebalancing means frequent data changes may require rebuilding the index to maintain search efficiency.

### Source excerpt

Tiger Data has released pg_vectorsearch, an open source PostgreSQL extension for vector similarity search, currently in alpha. Its PRISM index uses data partitioning and compression instead of the graph-based approach used by pgvector's HNSW index, reducing memory requirements and index build times. By Renato Losio

[Next page](<https://devfeed.tech/topics/ann.md?cursor=WyIyMDI2LTExLTA3VDA5OjQ5OjAwKzAwOjAwIiwgImYyYjFkNGYyLThlZmQtNDhmMC1hOTMwLTY2NzgyMTVmOTViOCJd>)