maximum-inner-product-search
Maximum Inner Product Search (MIPS) — the retrieval substrate behind an agent’s long-term memory in the 2023 agent anatomy (Weng 2023). The idea: external memory beats the finite attention span, so save each piece of information as an embedding in a vector store, and recall it by finding the stored vectors whose inner product with the query is largest.
Exact MIPS is too slow at scale, so the standard practice is approximate nearest neighbors (ANN): return approximately the top-k, trading a little accuracy for a large speedup.
The five ANN algorithms surveyed
| Algorithm | Core data structure / idea |
|---|---|
| LSH (Locality-Sensitive Hashing) | A hash function that maps similar items into the same bucket with high probability; far fewer buckets than inputs. |
| ANNOY (Approximate Nearest Neighbors Oh Yeah) | A forest of random projection trees — each non-leaf node is a random hyperplane splitting the space; search all trees toward the query and aggregate. Like a more scalable KD-tree. |
| HNSW (Hierarchical Navigable Small World) | Hierarchical layers of small-world graphs (“six degrees of separation”). Upper layers are coarse shortcuts; descend layer by layer, refining as you go. |
| FAISS (Facebook AI Similarity Search) | Assumes clustering in high-dimensional space; vector quantization partitions into clusters, search coarse-then-fine. |
| ScaNN (Scalable Nearest Neighbors) | Anisotropic vector quantization — quantizes a point so its inner product with the query is preserved, rather than picking the nearest centroid. In the recall@10-vs-speed comparison chart, ScaNN leads the Pareto frontier. |
(Further comparison: ann-benchmarks.com.)
Why it matters less than 2023 assumed
Weng’s framing made “long-term memory = vector store + ANN” the default agent-memory architecture of the AutoGPT era. The wiki’s 2026 agent-memory sources push back hard:
- Markdown + simple retrieval is enough at small/medium scale. Reach for a vector store only when the corpus exceeds a few thousand items and semantic-similarity matching is genuinely needed. The infra cost of a vector DB + RAG is non-trivial and rarely the early bottleneck.
- ChatGPT’s production memory (per the 2026 read) uses no vector DB / no RAG — just curated fact lists injected into the prompt.
- Chroma (vector-DB vendor) is where the modern thread lives; even there the interesting work is learned retrieval-side pruning, not just faster MIPS.
So this page is best read as the substrate, not the strategy: MIPS/ANN is how you do vector recall when you’ve decided you need it — but deciding you need it is the harder call. See agent-memory for the engineering trade-off.
Cross-link
- 2026-06-04-llm-powered-autonomous-agents — the source (Memory → MIPS section).
- agent-memory — the broader memory architecture; why vector retrieval is often overkill.
- chroma — the wiki’s vector-DB vendor entity.
- llm-agent — the anatomy this sits inside.