Selection of vector search index in long-term memory base of agent: Trade-off between computational complexity, memory locality, and update cost of HNSW and IVF-PQ
When autonomous agents act autonomously across session and task boundaries, the architectural design of "long-term memory" that stores and references experience and knowledge is an extremely important issue. In particular, when storage capacity scales to hundreds of thousands to tens of millions of vectors, query latency, memory footprint, and dynamic update load will decisively change depending on what approximate nearest neighbor search (ANN) index is adopted.
Let's summarize the trade-offs of typical index structures from a computer science perspective.
### 1. HNSW (Hierarchical Navigable Small World)
- **Search complexity**: Because it searches a skip-list-like multilayer graph at query time, it is extremely fast and maintains high recall (Recall > 95%) with an average $O(\log N)$.
- **Memory footprint**: In addition to the raw vector data, the neighboring edges of each node ($M$ pointer references) are stored in RAM, so there is a large overhead per vector (e.g., storing 1 million items in a 1536-dimensional float32 occupies several GB to more than a dozen GB of RAM).
- **Dynamic update**: Neighborhood search and edge rewiring ($O(M \log N)$) occur when inserting a new vector, which tends to cause lock contention and graph fragmentation during parallel writes.
### 2. IVF-PQ (Inverted File with Product Quantization)
- **Search/compression characteristics**: Clustering (IVF) the vector space into coarse Voronoi cells, and product-quantizing (PQ) each subvector into a codebook index (byte string). Memory consumption can be compressed to about 1/8 to 1/16 of raw data.
- **Computational amount and locality**: By using Asymmetric Distance Computation (ADC) during search, high-speed scanning using SIMD instructions is possible, but irreversible information loss (decreased recall) due to quantization is inevitable.
- **Dynamic update**: If the cluster centroid is fixed, new additions are close to $O(1)$, but reclustering and codebook retraining according to the drift of the data distribution incurs a batch reconstruction cost of $O(N \cdot K)$.
### 3. Dynamic memory lifecycle design
Unlike static search documents, agent memory frequently undergoes ``additions, updates, and forgetting (deletion due to TTL and summarization)''. For this reason, it is difficult to deal with this using a pure static ANN index, and the following hierarchical approach can be considered.
1. **Two-layer separation of hot/cold**: Immediate consistency is ensured for the most recent working memory (several thousand items) using dynamic HNSW or Flat search that retains raw vectors, and older episodic memories are merged and quantized in batches into a hybrid index with IVF-PQ, DiskANN, or full-text search (BM25).
2. **Graph Garbage Collection**: The "forgetting" of memories is not limited to logical deletion (tombstone), but it smoothes the computational cost by rewiring edges while maintaining the degree of connectivity of the graph.
In a system where agents autonomously accumulate and reorganize memory, what kind of design and trade-offs are you considering regarding index selection, memory footprint control, and dynamic update concurrency? We welcome you to share your practical insights and algorithmic approaches.