k-Nearest Neighbors (k-NN)

The integer 'k' specifies the number of nearest neighbors to retrieve. It is the algorithm's primary hyperparameter and controls a fundamental bias-variance trade-off.

• Small k (e.g., 1):
  • High variance, low bias.
  • Sensitive to noise and outliers.
  • Produces complex decision boundaries.
• Large k (e.g., 20):
  • Low variance, higher bias.
  • Smoothes over local noise.
  • Produces simpler, more generalized boundaries.
• In agentic retrieval, k balances precision (is the single most relevant result found?) against recall (are all relevant contexts retrieved?).

A naive, brute-force k-NN implementation has a time complexity of O(n * d) per query, where n is the number of stored vectors and d is their dimensionality. This becomes prohibitive for large-scale memory systems.

• Query Complexity: Linear scaling with dataset size.
• Curse of Dimensionality: Performance degrades in very high-dimensional spaces as distance metrics lose discriminative power.
• Scalability Solution: This limitation is the primary reason Approximate Nearest Neighbor (ANN) algorithms like HNSW or IVF were developed. They trade a small, controlled amount of accuracy for orders-of-magnitude faster retrieval.

For supervised tasks, k-NN determines an output based on the labels of the retrieved neighbors.

• Classification: Uses a majority vote among the k neighbors. Ties may be broken by distance (closer neighbor gets more weight) or randomly.
• Regression: Computes the average (mean) of the target values of the k neighbors. A distance-weighted average is a common refinement.
• Relevance for Agents: In Retrieval-Augmented Generation (RAG), this concept translates to aggregating context from multiple retrieved documents. The agent's 'vote' is the synthesis of information from the top-k memory chunks.

k-NN is sensitive to the scale of features (vector dimensions). Features with larger ranges dominate the distance calculation.

• Requires Normalization: Feature scaling (e.g., Min-Max, Standardization) is a critical preprocessing step for consistent results when using metrics like Euclidean distance.
• Embedding Implications: Modern embedding models (e.g., from sentence-transformers) typically produce unit vectors (normalized to length 1). This makes cosine similarity equivalent to the dot product and the natural choice, as it is inherently scale-invariant.
• Failure Mode: Without proper normalization or metric alignment, retrieval results will be skewed and semantically meaningless.

A specialized database management system optimized for storing, indexing, and performing similarity search on high-dimensional vector embeddings. It provides the persistent, scalable backend for k-NN and ANN operations in agentic memory systems.

• Core Functions: Manages vector indexes (e.g., HNSW, IVF), handles metadata filtering, and supports CRUD operations on vector collections.
• Key Differentiator: Unlike traditional databases, it is built for the unique workload of nearest neighbor search, offering optimized storage, caching, and distributed querying (sharded indexes).
• Use Case: The foundational infrastructure for Retrieval-Augmented Generation (RAG), semantic search, and long-term memory for autonomous agents.

The most common similarity metric used with k-Nearest Neighbors (k-NN) in semantic search. It measures the cosine of the angle between two non-zero vectors in an inner product space, providing a score between -1 and 1.

• Key Property: It is invariant to vector magnitude, focusing solely on orientation. This makes it ideal for comparing text embeddings where the semantic meaning is encoded in the vector's direction, not its length.
• Calculation: For vectors A and B, cosine similarity = (A · B) / (||A|| * ||B||).
• Alternative Metrics: Euclidean distance (L2), Manhattan distance (L1), and Maximum Inner Product Search (MIPS) are used depending on the embedding model and application.

A retrieval strategy that combines the results of semantic search (vector/k-NN) and keyword search (lexical/sparse retrieval like BM25) to improve overall recall and relevance. It addresses the limitations of either method used alone.

• Rationale: Vector search captures semantic meaning but can miss exact keyword matches. Keyword search finds literal term matches but fails on synonyms or paraphrases.
• Fusion Method: Results from both searches are combined using algorithms like Reciprocal Rank Fusion (RRR) or weighted scoring.
• Agentic Application: Provides more robust memory retrieval for agents, ensuring they find information whether it matches the query's exact terms or its conceptual intent.

A two-stage retrieval process where a broad set of candidate documents is first retrieved (e.g., via fast k-NN or ANN search) and then re-scored by a more powerful, computationally expensive model to produce the final precision ranking.

• Second-Stage Model: Typically uses a cross-encoder—a transformer model that jointly processes the query and a candidate document pair to produce a direct relevance score. This is more accurate but too slow to run on an entire corpus.

• Workflow: 1) Retrieve top 100-200 candidates with k-NN. 2) Rerank those 100-200 with the cross-encoder. 3) Return the top 10 final results.

• Outcome: Dramatically improves the precision of the final results presented to an LLM in a RAG pipeline or to an agent making a decision.