Scaling Retrieval and Search to External Memory

This direction is split into other directions: delayed duplicate detection, disk I/O bottleneck. Its last version stays readable and citable here.

Version 1 of 177 papers87 conceptsfrozen 2026-10-04

As datasets for Large Language Models, vector databases, and scientific simulations reach the billion- and trillion-scale, they inevitably hit the memory wall. While modern CPUs and GPUs can process data at incredible speeds, the cost and physical capacity of RAM cannot keep pace with the explosion of data. This forces a shift from "in-memory" algorithms to out-of-core or external-memory computations, where the primary dataset resides on secondary storage like SSDs or hard disks.

The challenge is not just capacity, but a fundamental change in the physics of data access. In RAM, the cost of accessing any byte is roughly equal. On disk, the cost of a "random seek" (jumping to a new location) is orders of magnitude higher than a "sequential read" (streaming contiguous data). Research in this area focuses on redesigning search and retrieval to minimize these expensive random I/Os.

The I/O Bottleneck and the Sequentiality Principle

The core intuition behind external-memory research is that computation is cheap, but movement is expensive. In Optimization of Out-of-Core Computations Using Chain Vectors, Mahmut T. Kandemir and Alok N. Choudhary argue that when data lives on disk, the primary execution bottleneck is the movement of data between disk and RAM.

To solve this, researchers prioritize sequential access patterns. If an algorithm needs to check a million data points, it is much faster to sort them first and read them in one continuous stream than to jump around the disk a million times. This is the logic behind Delayed Duplicate Detection (DDD), introduced by Richard E. Korf in Delayed Duplicate Detection: Extended Abstract. Instead of using a hash table in RAM to check if a state has been visited (which requires random lookups), DDD offloads states to disk and uses efficient sequential sorting to identify duplicates in bulk.

Localizing Search via State-Space Abstraction

When searching massive graphs or solving planning problems that exceed RAM, you cannot afford to keep the entire "visited" list in memory. Rong Zhou and Eric A. Hansen pioneered Structured Duplicate Detection (SDD) in Structured Duplicate Detection in External-Memory Graph Search.

The intuition here is localization. By using an "abstract map" of the search space, SDD partitions the graph so that when the algorithm expands a node, it only needs to look at a small, local neighborhood of previously visited nodes. This allows the system to keep only the relevant "active" portion of the search in RAM, while the rest of the massive graph stays on disk, effectively "localizing" memory references to prevent the thrashing caused by random disk seeks.

In the context of modern AI, the "memory wall" manifests in Approximate Nearest Neighbor Search (ANNS). Standard algorithms like HNSW are designed for RAM and fail when ported directly to SSDs because they rely on "pointer chasing"—jumping through a graph structure.

Recent work has moved toward tiered architectures that split the index into two parts:

  1. A RAM-resident "filter" or "coarse index": A lightweight representation used to quickly narrow down candidates.
  2. A Disk-resident "refinement" or "dense index": The full-fidelity data used for final re-ranking.

In Progressively Optimized Bi-Granular Document Representation for Scalable Embedding Based Retrieval, Hao Sun and Zheng Liu demonstrate this with BiDR, which uses sparse embeddings in RAM for global filtering and dense embeddings on disk for local discrimination. Similarly, Yifan Zhu and colleagues proposed the Dual-Index Query Framework (DQF) in Frequency-Aware Graph Construction and Search for Dynamic Vector Databases, which exploits the "power law" of queries by keeping "hot" items in a high-speed memory index while relegating the bulk of the data to disk.

Learned Functions and I/O Efficiency

A newer frontier involves replacing traditional index structures (like B-trees or Tries) with learned functions. In I/O Efficient Approximate Nearest Neighbour Search based on Learned Functions, Mingjie Li and Ying Zhang show that neural networks or linear regressions can be trained to map high-dimensional vectors directly to sorted lists on disk.

The intuition is that a mathematical function can "predict" where a piece of data is likely to be, allowing the system to jump directly to the correct block on disk. This reduces the number of "probes" or seeks required to find a neighbor, bridging the gap between the high-dimensional complexity of the data and the linear, block-based nature of physical storage.

The Future: Cloud-Native and Heterogeneous Storage

As we move toward trillion-scale retrieval, the field is evolving from single-machine SSD optimizations to cloud-native architectures. As Yitong Song and Christian S. Jensen discuss in Vector Search for the Future, the goal is to balance the "trilemma" of accuracy, latency, and cost. By treating RAM, SSDs, and remote cloud storage as a single, fluid hierarchy, these systems allow AI models to "remember" vast amounts of information without the prohibitive cost of keeping it all in volatile memory.

Papers in this version

Showing 60 of 77 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_scaling_retrieval_and_search_to_external_8a0d89d2,
  title = {Scaling Retrieval and Search to External Memory},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scaling-retrieval-and-search-to-external-memory/rdr_8a0d89d2025c4138b6c64d25ebb74c0c},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_scaling_retrieval_and_search_to_external_8a0d89d2_v1,
  title = {Scaling Retrieval and Search to External Memory},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scaling-retrieval-and-search-to-external-memory/rdr_8a0d89d2025c4138b6c64d25ebb74c0c/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}