Beyond Overlap: Hierarchical Graph Abstraction for Out-of-Core Vector Search
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "Beyond Overlap: Hierarchical Graph Abstraction for Out-of-Core Vector Search".
Jane: Here's the gist of the paper. OrchANN presents an out-of-core Approximate Nearest Neighbor Search engine that orchestrates query routing, partition access, and query execution under tight memory constraints to improve performance on billion-scale vector collections The single most informative sentence about the paper's subject and finding is OrchANN delivers up to 17.2× higher QPS and 25.0× lower latency than state-of-the-art baselines, while preserving accuracy Decoupling Locality from Connectivity The architectural insight behind the design is to decouple physical locality from logical connectivity The system stores vectors in disjoint SSD partitions and maintains a graph abstraction composed of centroid anchors and representative vectors This allows the memory-resident layer to provide logical connectivity by routing queries to relevant partitions before SSD access, while the SSD layer preserves physical locality by searching only selected non-replicated partitions Shape-aware Partition Search The memory-resident routing layer combines centroid anchors with representative vectors to capture partition shape The SSD layer then searches selected partitions using local indexes adapted to partition scale and memory pressure This addresses the challenge of skewed cluster sizes by designing a hierarchical search structure where the compact graph abstraction exposes partition-level evidence before SSD access Access-hotness-aware Execution OrchANN uses per-query partition signals to refresh the graph abstraction, prioritize useful partitions, and prune low-value accesses This is achieved by incrementally adapting the graph abstraction with representative vectors from frequently useful clusters based on cluster hotness Furthermore, it schedules queries with similar cluster visits close together to improve temporal locality in the page cache Performance Gains and I/O Analysis Across five datasets under strict memory constraints, OrchANN achieves up to 17.2× higher QPS and 25.0× lower latency than state-of-the-art out-of-core baselines The I/O analysis shows that OrchANN reduces unnecessary SSD work by guiding queries to relevant partitions and skipping low-utility candidates before issuing local searches This stability indicates that higher recall does not require blindly probing many more disk-resident regions, as its I/O grows by less than 10% from Recall@10 = 90% to 98% The disjoint SSD partitions with local indexes provide a suitable substrate for OrchANN because they reduce unnecessary out-of-core accesses The hybrid indexing strategy, using Flat for tiny clusters, Graph as the primary high-accuracy path, and auxiliary IVF views only for large clusters, avoids extremes in local search structures Query-locality scheduling complements cluster pruning by improving locality among the clusters that are still searched This combination of mechanisms reduces redundant SSD accesses and improves locality without changing the partition layout The final results demonstrate that OrchANN remains effective at a billion scale and under tight DRAM limits, allowing it to maintain high efficiency where existing systems degrade sharply Evaluation Against Baselines OrchANN consistently achieves higher QPS and lower latency across recall targets when compared against state-of-the-art out-of-core baselines such as Starling
48: , DiskANN
20: , and SPANN
4: On semantic workloads like TriviaQA and HotpotQA, OrchANN achieves up to 17.2× higher QPS and 25.0× lower latency than SPANN at Recall@100 = 0.85 The gains are attributed to reducing unnecessary SSD work at multiple levels, including avoiding replicated posting-list accesses and using representative-vector graph abstraction for stronger partition evidence The smallest footprint of OrchANN at 44.9 GB on DEEP compared to SPANN's 230.3 GB storage overhead confirms its efficiency in resource-constrained environments Index Construction and Cost Efficiency OrchANN's build pipeline consists of partition construction, graph-abstraction generation, and per-cluster local index construction The memory-resident graph abstraction is lightweight to build while local indices are constructed independently for each partition, enabling scalable parallelism across clusters The additional cost of hybrid local access paths is small, adding only about 272 s to the total construction pipeline compared to DiskANN
20: By keeping partitions physically independent while avoiding vector replication, OrchANN achieves a 1.78× faster build than SPANN The duplication-free design keeps storage overhead low while preserving accuracy and out-of-core efficiency, as the graph abstraction occupies only about 100 MB Parameter Sensitivity and Scalability When moving from Recall@1 to Recall@10, all systems experience a QPS drop of roughly 20%, yet OrchANN consistently achieves the highest QPS and the lowest latency across the entire recall range from 80% to 98% At Recall@10 = 90%, OrchANN delivers 3.5× higher QPS than Starling
48: and at Recall@1 = 90%, it achieves 3.2× higher QPS than Starling In multi-threaded settings, OrchANN also scales effectively, with 64 threads outperforming Starling by 2.2× and SPANN
4: by 5.4× in QPS at Recall@10 OrchANN exhibits strong robustness to parameter changes, maintaining low latency and high throughput under varying recall targets and concurrency levels The architecture is designed for resource-constrained environments and operates under a strict 10 GB memory cap Related Work Context Prior work in out-of-core ANNS systems mainly includes algorithmic indexing optimized for low-latency search when the index fits in RAM, and accelerator-based systems that leverage specialized hardware such as GPUs and PIM to improve throughput Existing designs typically rely on IVF-based indices
4, 7, 53, 61: , disk-resident graph indices
12, 32: , or hierarchical structures with a small in-memory navigator over SSD-resident data These methods are effective with sufficient DRAM and GPU HBM but do not directly address CPU–SSD search under tight memory budgets The paper addresses the limitation where most vectors and index structures remain SSD-resident The work builds upon foundational systems like DiskANN
20: and SPANN
4: , focusing on improving I/O efficiency through hierarchical orchestration Dataset Characteristics The evaluation is conducted on five public datasets ranging from millions to billions of vectors, including HotpotQA
54: , SIFT
21: , TriviaQA
26: , DEEP
9: , and SpaceV1B (SPACEV)
3: Across all datasets, IVF partitioning exhibits clear cluster-size skewness, while QA corpora such as HotpotQA and TriviaQA show particularly strong semantic skewness in addition to a pronounced long-tail distribution The dataset characteristics are summarized in Table 1 The evaluation uses a tighter 1 GB memory limit for the experiments Implementation Details OrchANN is implemented as a C++17 CPU–SSD out-of-core search engine built with CMake The codebase contains roughly 12K lines of project code, excluding third-party and generated code OrchANN uses FAISS
25: for k-means clustering and auxiliary IVF-view indexes, HNSWLib
31: for the graph abstraction, and NSG
12: for local graph indexes inside clusters Cluster vectors, id mappings, and local index artifacts are stored as disk files and accessed through memory mapping at query time The experiments were conducted on a server with two 64-core Intel Xeon Gold CPUs (2.5 GHz), 512 GB of DRAM, and a 1.92 TB SATA SSD Following the cgroup-based memory-constrained methodology used in Starling
48: , each method is run inside a Linux cgroup v2 memory controller with memory.high=4 GB and memory.max=10 GB by default The evaluation includes comparisons against PipeANN
17: on SIFT and HotpotQA Table 3 compares index construction time and disk storage overhead on DEEP
9: The results show that OrchANN completes indexing in 6,793 s, only slightly slower than DiskANN
20: , while providing substantially higher query throughput and lower latency during serving The system is designed to operate under a strict 10 GB memory cap Ablation Study Summary The ablation study isolates the I/O behavior of the architectural substrate, the graph abstraction and its cluster-level pruning support, and query-locality scheduling in the execution layer The partition-local graph substrate consistently reduces unnecessary out-of-core accesses across SIFT and TriviaQA datasets The representative-vector graph abstraction provides stronger cluster evidence by capturing off-center cluster shape, with pruning being nearly lossless at a 0.90 recall target Query access skewness is exploited by dynamically updating the graph abstraction with representative vectors from frequently useful clusters, which improves the ranking of candidate clusters before SSD access Query-locality scheduling improves temporal locality among cluster accesses by reordering nearby queries, which is complementary to cluster pruning The hybrid indexing approach consistently achieves the highest QPS across recall targets and provides a more compact access pattern under tighter memory budgets The results show that better cluster evidence improves QPS and latency, and also makes pruning more effective by ranking useful clusters earlier before SSD access Final Conclusion on Architecture OrchANN preserves physical locality by keeping vectors in non-replicated SSD partitions, providing logical connectivity through a compact memory-resident graph abstraction, and combining scale-aware local indexes with utility-aware execution This hierarchical design reduces redundant SSD work without sacrificing recall The final results demonstrate that OrchANN remains effective at a billion scale and under tight DRAM limits, allowing it to maintain high efficiency where existing systems degrade sharply The architecture is designed to preserve locality while maintaining reachability through memory-resident logical overlap over non-replicated partitions This separation of roles between the memory-resident layer and the SSD-resident layer is key to its success References
1: Adebowale Jeremy Adetayo, Mariam Oyinda Aborisade, and Basheer Abiodun Sanni.
Jane: Microsoft Copilot and Anthropic Claude AI in education and library service.
Tom: Library Hi Tech News (2024).
Paper summary: Tom: We've talked about how this paper, "Beyond Overlap: Hierarchical Graph Abstraction for Out-of-Core Vector Search," uses a graph abstraction to manage query routing across disjoint partitions to improve performance. The authors essentially show that you can keep vectors on separate SSD partitions without having to duplicate them or replicate the whole index structure across all of them <ref:2512.22838#pg1>.
Jane: It sounds like the title itself is telling us a lot about the solution they found, moving "Beyond Overlap" to a more sophisticated hierarchical approach for out-of-core search. This isn't just a tweak to an old system; it’s a fundamental way of organizing how we connect data stored on disks <ref:2512.22838#pg1>.
Lu: What this means practically is that if you have massive vector datasets that won't fit in memory, this architecture allows the memory layer to provide logical connectivity through that compact graph abstraction while the SSD layer handles physical access in a locality-preserving way <ref:2512.22838#pg1>.
Meng: For me, what I see is that it’s about reducing redundant SSD work without sacrificing recall, which is exactly what we need when we're dealing with real traffic where every millisecond counts <ref:2512.22838#pg1>.
Tom: Exactly. The authors show that this separation of roles between the memory-resident layer and the SSD-resident layer is key to its success, allowing it to remain effective at a billion scale even under strict DRAM limits <ref:2512.22838#pg1>.
Conclusion: Tom: So, we’ve looked at how they built this whole system, and now we get to the end of "Beyond Overlap: Hierarchical Graph Abstraction for Out-of-Core Vector Search."
Jane: Yeah, it’s really about taking a big problem—searching billion-scale vectors when your computer has very little memory—and solving it by splitting the work between what lives in fast memory and what lives on slower storage.
Lu: The core idea is this decoupling of physical locality from logical connectivity. They store the actual vector data across separate storage partitions, but they use a graph abstraction in memory to figure out which partitions are actually relevant for any given query.
Meng: So, the naive question is, how does that graph abstraction actually keep up with all those billion vectors? It sounds like a lot of bookkeeping just to map things out.
Tom: It’s not just bookkeeping; they use this shape-aware partition search where the memory layer combines anchors and representative vectors to get a preview of which partitions look promising before it ever touches the slow storage.
Jane: That makes sense for someone who doesn't read math; it’s like having a really smart map in your head that tells you which neighborhood to go into first before you drive out to the actual city.
Lu: Exactly. And they add this access-hotness-aware execution, where the system learns which partitions are useful and updates its memory map based on what queries it’s actually getting asked about, cutting down on wasted disk reads.
Meng: From a deployment standpoint, that sounds like something that might actually work under real traffic at scale instead of just being a neat research paper idea.
Tom: It does show up in the numbers too; they got higher query per second and lower latency than the old baselines, even when memory is extremely tight.
Jane: That’s the big part—that even with all that complexity, it stays efficient enough to handle those massive datasets without crashing your system.
Lu: It proves that for out-of-core search, you don't need one single perfect index; a layered approach where memory handles the high-level logic and storage handles the physical data is what really matters.
Nanjing University 2 · AISoft (QiyuanLab) 3 · Peking University 4 · University of New South Wales5 · Institute of Software, Chinese Academy of Sciences6 · Tsinghua University7 · Huawei5
cs.DB, cs.IR
Submitted: 2025-12-28
Updated: 2026-11-06
Comments: Accepted to EuroSys 2027
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 99/100
The gist: OrchANN presents an out-of-core Approximate Nearest Neighbor Search engine that orchestrates query routing, partition access…
Key concepts
- Decoupling Locality from Connectivity
- The system separates where the data physically resides (SSD partitions) from how the system logically connects different parts of the data. This allows the memory layer to manage logical connections by routing queries efficiently before hitting slow disk storage, improving overall search speed.
- Shape-aware Partition Search
- The memory layer uses a combination of centroid anchors and representative vectors to understand the shape and structure of the SSD partitions. This information guides the search process, allowing the system to intelligently select which partitions are most relevant before performing expensive disk lookups.
- Access-hotness-aware Execution
- OrchANN dynamically manages performance by prioritizing frequently used data clusters. It updates its internal graph abstraction based on cluster 'hotness' and schedules similar queries close together. This ensures that the system focuses its limited resources on the most valuable parts of the dataset.
- Hybrid Indexing Strategy
- The indexing uses a mix of structures: Flat for small clusters, Graph as the main path for high accuracy, and auxiliary IVF views for large clusters. This tailored approach avoids using one single search method everywhere, optimizing both speed and precision under memory limits.
Terminology
Summary
OrchANN presents an out-of-core Approximate Nearest Neighbor Search engine that orchestrates query routing, partition access, and query execution under tight memory constraints to improve performance on billion-scale vector collections
The single most informative sentence about the paper's subject and finding is OrchANN delivers up to 17.2× higher QPS and 25. p. 0 p. 0 p. 00× lower latency than state-of-the-art baselines, while preserving accuracy
Decoupling Locality from Connectivity
The architectural insight behind the design is to decouple physical locality from logical connectivity The system stores vectors in disjoint SSD partitions and maintains a graph abstraction composed of centroid anchors and representative vectors This allows the memory-resident layer to provide logical connectivity by routing queries to relevant partitions before SSD access, while the SSD layer preserves physical locality by searching only selected non-replicated partitions
Shape-aware Partition Search
The memory-resident routing layer combines centroid anchors with representative vectors to capture partition shape The SSD layer then searches selected partitions using local indexes adapted to partition scale and memory pressure This addresses the challenge of skewed cluster sizes by designing a hierarchical search structure where the compact graph abstraction exposes partition-level evidence before SSD access
Access-hotness-aware Execution
OrchANN uses per-query partition signals to refresh the graph abstraction, prioritize useful partitions, and prune low-value accesses This is achieved by incrementally adapting the graph abstraction with representative vectors from frequently useful clusters based on cluster hotness Furthermore, it schedules queries with similar cluster visits close together to improve temporal locality in the page cache
Performance Gains and I/O Analysis
Across five datasets under strict memory constraints, OrchANN achieves up to 17.2× higher QPS and 25.0× lower latency than state-of-the-art out-of-core baselines The I/O analysis shows that OrchANN reduces unnecessary SSD work by guiding queries to relevant partitions and skipping low-utility candidates before issuing local searches This stability indicates that higher recall does not require blindly probing many more disk-resident regions, as its I/O grows by less than 10% from Recall@10 = 90% to 98%
Conclusion on Substrate and Optimization
The disjoint SSD partitions with local indexes provide a suitable substrate for OrchANN because they reduce unnecessary out-of-core accesses The hybrid indexing strategy, using Flat for tiny clusters, Graph as the primary high-accuracy path, and auxiliary IVF views only for large clusters, avoids extremes in local search structures Query-locality scheduling complements cluster pruning by improving locality among the clusters that are still searched This combination of mechanisms reduces redundant SSD accesses and improves locality without changing the partition layout The final results demonstrate that OrchANN remains effective at a billion scale and under tight DRAM limits, allowing it to maintain high efficiency where existing systems degrade sharply
Evaluation Against Baselines
OrchANN consistently achieves higher QPS and lower latency across recall targets when compared against state-of-the-art out-of-core baselines such as Starling [48], DiskANN [20], and SPANN [4] On semantic workloads like TriviaQA and HotpotQA, OrchANN achieves up to 17.2× higher QPS and 25.0× lower latency than SPANN at Recall@100 = 0. p. 885 The gains are attributed to reducing unnecessary SSD work at multiple levels, including avoiding replicated posting-list accesses and using representative-vector graph abstraction for stronger partition evidence The smallest footprint of OrchANN at 44. p. 89 GB on DEEP compared to SPANN's 230.3 GB storage overhead confirms its efficiency in resource-constrained environments
Index Construction and Cost Efficiency
OrchANN's build pipeline consists of partition construction, graph-abstraction generation, and per-cluster local index construction The memory-resident graph abstraction is lightweight to build while local indices are constructed independently for each partition, enabling scalable parallelism across clusters The additional cost of hybrid local access paths is small, adding only about 272 s to the total construction pipeline compared to DiskANN [20] By keeping partitions physically independent while avoiding vector replication, OrchANN achieves a 1.78× faster build than SPANN The duplication-free design keeps storage overhead low while preserving accuracy and out-of-core efficiency, as the graph abstraction occupies only about 100 MB
Parameter Sensitivity and Scalability
When moving from Recall@1 to Recall@10, all systems experience a QPS drop of roughly 20%, yet OrchANN consistently achieves the highest QPS and the lowest latency across the entire recall range from 80% to 98% At Recall@10 = 90%, OrchANN delivers 3.5× higher QPS than Starling [48] and at Recall@1 = 90%, it achieves 3. p. 82× higher QPS than Starling In multi-threaded settings, OrchANN also scales effectively, with 64 threads outperforming Starling by 2. p. 82× and SPANN [4] by 5. p. 04× in QPS at Recall@10 OrchANN exhibits strong robustness to parameter changes, maintaining low latency and high throughput under varying recall targets and concurrency levels The architecture is designed for resource-constrained environments and operates under a strict 10 GB memory cap
Related Work Context
Prior work in out-of-core ANNS systems mainly includes algorithmic indexing optimized for low-latency search when the index fits in RAM, and accelerator-based systems that leverage specialized hardware such as GPUs and PIM to improve throughput Existing designs typically rely on IVF-based indices [4, 7, 53, 61], disk-resident graph indices [12, 32], or hierarchical structures with a small in-memory navigator over SSD-resident data These methods are effective with sufficient DRAM and GPU HBM but do not directly address CPU–SSD search under tight memory budgets The paper addresses the limitation where most vectors and index structures remain SSD-resident The work builds upon foundational systems like DiskANN [20] and SPANN [4], focusing on improving I/O efficiency through hierarchical orchestration
Dataset Characteristics
The evaluation is conducted on five public datasets ranging from millions to billions of vectors, including HotpotQA [54], SIFT [21], TriviaQA [26], DEEP [9], and SpaceV1B (SPACEV) [3] Across all datasets, IVF partitioning exhibits clear cluster-size skewness, while QA corpora such as HotpotQA and TriviaQA show particularly strong semantic skewness in addition to a pronounced long-tail distribution The dataset characteristics are summarized in Table 1 The evaluation uses a tighter 1 GB memory limit for the experiments
Implementation Details
OrchANN is implemented as a C++17 CPU–SSD out-of-core search engine built with CMake The codebase contains roughly 12K lines of project code, excluding third-party and generated code OrchANN uses FAISS [25] for k-means clustering and auxiliary IVF-view indexes, HNSWLib [31] for the graph abstraction, and NSG [12] for local graph indexes inside clusters Cluster vectors, id mappings, and local index artifacts are stored as disk files and accessed through memory mapping at query time The experiments were conducted on a server with two 64-core Intel Xeon Gold CPUs (2.5 GHz), 512 GB of DRAM, and a 1. p. 792 TB SATA SSD Following the cgroup-based memory-constrained methodology used in Starling [48], each method is run inside a Linux cgroup v2 memory controller with memory. p. 7high=4 GB and memory. p. 0max=10 GB by default The evaluation includes comparisons against PipeANN [17] on SIFT and HotpotQA Table 3 compares index construction time and disk storage overhead on DEEP [9] The results show that OrchANN completes indexing in 6,793 s, only slightly slower than DiskANN [20], while providing substantially higher query throughput and lower latency during serving The system is designed to operate under a strict 10 GB memory cap
Ablation Study Summary
The ablation study isolates the I/O behavior of the architectural substrate, the graph abstraction and its cluster-level pruning support, and query-locality scheduling in the execution layer The partition-local graph substrate consistently reduces unnecessary out-of-core accesses across SIFT and TriviaQA datasets The representative-vector graph abstraction provides stronger cluster evidence by capturing off-center cluster shape, with pruning being nearly lossless at a 0.90 recall target Query access skewness is exploited by dynamically updating the graph abstraction with representative vectors from frequently useful clusters, which improves the ranking of candidate clusters before SSD access Query-locality scheduling improves temporal locality among cluster accesses by reordering nearby queries, which is complementary to cluster pruning The hybrid indexing approach consistently achieves the highest QPS across recall targets and provides a more compact access pattern under tighter memory budgets The results show that better cluster evidence improves QPS and latency, and also makes pruning more effective by ranking useful clusters earlier before SSD access
Final Conclusion on Architecture
OrchANN preserves physical locality by keeping vectors in non-replicated SSD partitions, providing logical connectivity through a compact memory-resident graph abstraction, and combining scale-aware local indexes with utility-aware execution This hierarchical design reduces redundant SSD work without sacrificing recall The final results demonstrate that OrchANN remains effective at a billion scale and under tight DRAM limits, allowing it to maintain high efficiency where existing systems degrade sharply The architecture is designed to preserve locality while maintaining reachability through memory-resident logical overlap over non-replicated partitions This separation of roles between the memory-resident layer and the SSD-resident layer is key to its success
References
[1] Adebowale Jeremy Adetayo, Mariam Oyinda Aborisade, and Basheer Abiodun Sanni. 2024. Microsoft Copilot and Anthropic Claude AI in education and library service. p. 0 p. 0 Library Hi Tech News (2024).
[2] Shubham Agarwal, Sai Sundaresan, Subrata Mitra, Debabrata Mahapatra, Archit Gupta, Rounak Sharma, Nirmal Joshua Kapu, Tong Yu, and Shiv Saini. 2025. Cache-Craft: Managing Chunk-Caches for Efficient Retrieval-Augmented Generation. p. 0 p. 0 Proc. ACM Manag. Data 3, 3 (Article 136)
[3] Qi Chen, Haidong Wang, Mingqin Li, Gang Ren, Scarlett Li, Jeffery Zhu, Jason Li, Chuanjie Liu, Lintao Zhang, and Jingdong Wang. 2018. SPTAG: A library for fast approximate nearest neighbor search
[4] Qi Chen, Bing Zhao, Haidong Wang, Mingqin Li, Chuanjie Liu, Zengzhong Li, Mao Yang, and Jingdong Wang. 2021. Spann: Highly efficient billion-scale approximate nearest neighborhood search
[5] Sitian Chen, Amelie Chi Zhou, Yucheng Shi, Yusen Li, and Xin Yao. 2024. MemANNS: Enhancing Billion-Scale ANNS Efficiency with Practical PIM Hardware
[6] Weijian Chen, Haotian Liu, Yangshen Deng, Long Xiang, Liang Huang, Gezi Li, and Bo Tang. 2026. AlayaLaser: Efficient Index Layout and Search Strategy for Large-scale High-dimensional Vector Similarity Search
[7] Yaoqi Chen, Ruicheng Zheng, Qi Chen, Shuotao Xu, Qianxi Zhang, Xue Wu, Weihao Han, Hua Yuan, Mingqin Li, Yujing Wang et al. 2024. Onesparse: A unified system for multi-index vector search
[8] Zhuoming Chen, Ranajoy Sadhukhan, Zihao Ye, Yang Zhou et al. 2024. Magicpig: Lsh sampling for efficient llm generation
[9] Paul Covington, Jay Adams, and Emre Sargin. 2016. Deep neural networks for youtube recommendations
[10] Florin Cuconasu et al. 2024. The power of noise: Redefining retrieval for rag systems
[11] Yangshen Deng et al. 2025. AlayaDB: The Data Foundation for Efficient and Effective Long-context LLM Inference
[12] Cong Fu et al. 2019. Fast Approximate Nearest Neighbor Search With The Navigating Spreadingout Graph
[13] Jianyang Gao et al. 2025. Practical and asymptotically optimal quantization of high-dimensional vectors in euclidean space for approximate nearest neighbor search
[14] Jianyang Gao and Cheng Long. 2024. RaBitQ: quantizing high-dimensional vectors with a theoretical error bound for approximate nearest neighbor search
[15] Yutong Gou et al. 2025. SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor Search
Conclusion
OrchANN presents a hierarchical out-of-core ANNS engine that decouples physical locality from logical connectivity By keeping vectors in non-replicated SSD partitions, providing boundary reachability through a compact memoryresident graph abstraction, and combining scale-aware local indexes with utility-aware execution, OrchANN reduces redundant SSD work without sacrificing recall The final results demonstrate that OrchANN remains effective at a billion scale and under tight DRAM limits, allowing it to maintain high efficiency where existing systems degrade sharply This separation of roles between the memory-resident layer and the SSD-resident layer is key to its success
[1] Adebowale Jeremy Adetayo, Mariam Oyinda Aborisade, and Basheer Abiodun Sanni. 2024. Microsoft Copilot and Anthropic Claude AI in education and library service. Library Hi Tech News (2024).
[2] Shubham Agarwal, Sai Sundaresan, Subrata Mitra, Debabrata Mahapatra, Archit Gupta, Rounak Sharma, Nirmal Joshua Kapu, Tong Yu, and Shiv Saini. 2025. Cache-Craft: Managing Chunk-Caches for Efficient Retrieval-Augmented Generation. Proc. ACM Manag. Data 3, 3 (Article 136)
[3] Qi Chen, Haidong Wang, Mingqin Li, Gang Ren, Scarlett Li, Jeffery Zhu, Jason Li, Chuanjie Liu, Lintao Zhang, and Jingdong Wang. 2018. SPTAG: A library for fast approximate nearest neighbor search
[4] Qi Chen, Bing Zhao, Haidong Wang, Mingqin Li, Chuanjie Liu, Zengzhong Li, Mao Yang, and Jingdong Wang. 2021. Spann: Highly efficient billion-scale approximate nearest neighborhood search
[5] Sitian Chen, Amelie Chi Zhou, Yucheng Shi, Yusen Li, and Xin Yao. 2024. MemANNS: Enhancing Billion-Scale ANNS Efficiency with Practical PIM Hardware
[6] Weijian Chen, Haotian Liu, Yangshen Deng, Long Xiang, Liang Huang, Gezi Li, and Bo Tang. 2026. AlayaLaser: Efficient Index Layout and Search Strategy for Large-scale High-dimensional Vector Similarity Search
[7] Yaoqi Chen, Ruicheng Zheng, Qi Chen, Shuotao Xu, Qianxi Zhang, Xue Wu, Weihao Han, Hua Yuan, Mingqin Li et al. 2024. Onesparse: A unified system for multi-index vector search
[8] Zhuoming Chen et al. 2024. Magicpig: Lsh sampling for efficient llm generation
[9] Paul Covington, Jay Adams, and Emre Sargin. 2016. Deep neural networks for youtube recommendations
[10] Florin Cuconasu et al. 2024. The power of noise: Redefining retrieval for rag systems
[11] Yangshen Deng et al. 2025. AlayaDB: The Data Foundation for Efficient and Effective Long-context LLM Inference
[12] Cong Fu et al. 2019. Fast Approximate Nearest Neighbor Search With The Navigating Spreadingout Graph
[13] Jianyang Gao et al. 2025. Practical and asymptotically optimal quantization of high-dimensional vectors in euclidean space for approximate nearest neighbor search
[14] Jianyang Gao and Cheng Long. 2024. RaBitQ: quantizing high-dimensional vectors with a theoretical error bound for approximate nearest neighbor search
[15] Yutong Gou et al. 2025.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Decouple physical locality from logical connectivity by keeping
raw vectors in non-replicated SSD partitions
while providingboundary reachability through memory-resident logical overlap.
This allows high recall without incurring the overhead ofphysical overlap in the SSD index or quantized search with raw-vector reranking.
-
Implement shape aware partition guidance by using a memory resident routing layer that combines
centroid anchors with representative vectors to capture partition shape
instead of relying solely on centroids, ensuring thatdense semantic partitions can have large regions far from the centroid
are adequately covered before SSD access. -
Employ utility aware execution by using
per-query graph evidence to prioritize and prune candidate partitions,
and schedule queries with similar cluster visits close together toimprove temporal locality in the page cache.
This reduces redundant SSD accesses by avoidingblindly searching them
and improving reuse among remaining SSD accesses. -
Implement a hybrid local access path where the system uses
Flat for tiny clusters, Graph as the primary high-accuracy path, and memory-efficient auxiliary IVF views only for large clusters whose graph working set is likely to cause page-cache pressure.
This avoids using one fixed structure and ensures thatthe best structure changes with cluster scale under the same accuracy target.
Sources
- UpANNS: Enhancing Billion-Scale ANNS Efficiency with Real-World PIM Architecture
- AlayaLaser: Efficient Index Layout and Search Strategy for Large-scale High-dimensional Vector Similarity Search
- MagicPIG: LSH Sampling for Efficient LLM Generation
- AlayaDB: The Data Foundation for Efficient and Effective Long-context LLM Inference
- RAGCache: Efficient Knowledge Caching for Retrieval-Augmented Generation
- TriviaQA: A Large Scale Distantly Supervised Challenge Dataset for Reading Comprehension
- Scalable Disk-Based Approximate Nearest Neighbor Search with Page-Aligned Graph
- RetrievalAttention: Accelerating Long-Context LLM Inference via Vector Retrieval
- PiPNN: Ultra-Scalable Graph-Based Nearest Neighbor Indexing
- EdgeRAG: Online-Indexed RAG for Edge Devices
- DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search
- AutoGen: Enabling Next-Gen LLM Applications via Multi-Agent Conversation
- ReAct: Synergizing Reasoning and Acting in Language Models
Related papers
- EMA: Approximate Nearest Neighbor Search with General Attribute Filtering and Dynamic Updates
- Open Biomedical Knowledge Graphs at Scale: Construction, Federation, and AI Agent Access with Samyama Graph Database
- Samyama: A Unified Graph-Vector Database with In-Database Optimization, Agentic Enrichment, and Hardware Acceleration
- GenTUS: Table Union Search via Constrained Generation of Semantic Table Identifiers
- Common-Neighbor-Count-Based Representative Possible World Finding on Uncertain Graphs
- SAGA: Synthetic Agentic Graph Architecture for Temporal Benchmark Generation