Vector Embeddings, Approximate Nearest Neighbor Search, HNSW, and Hybrid Retrieval

Learning outcomes

Treat embeddings and ANN indexes as measurable retrieval structures: define the vector/model contract, similarity metric, exact baseline, HNSW concepts, recall/latency/memory tradeoffs, filtering, and hybrid lexical+vector ranking.

1. An embedding is a model-produced representation, not meaning itself

An embedding maps an object—text, image, user, product, or other item—into a fixed-dimensional numeric vector according to a particular model and preprocessing pipeline. Similar objects are intended to occupy nearby regions under a chosen similarity metric such as cosine similarity, dot product, or Euclidean/L2 distance. The contract includes model name/version, input normalization, vector dimension, metric, and re-embedding policy. Vectors created by incompatible models or preprocessing pipelines should not be compared as if they lived in the same semantic space.

2. Exact k-NN is the correctness baseline

An exact k-nearest neighbor (k-NN) query computes similarity to every eligible vector (or uses an exact index) and returns the mathematically closest k under the metric. At large scale, scanning all vectors is expensive in CPU and memory bandwidth, so systems use approximate nearest neighbor (ANN) structures that inspect only a subset of candidates. Approximation creates a quality/performance tradeoff. The correct evaluation compares ANN results with an exact ground truth on representative queries and reports recall@k, latency percentiles, candidate/visited work, memory, build time, and update behavior.

3. AtlasMart lab: make the mechanism observable

Save the following as lesson4_vector_ann.py and run it with python lesson4_vector_ann.py. It uses only deterministic in-memory data and mutates no external service.

import math, re, heapq

products = {
 "p1":{"title":"red road running shoe","vec":(0.99,0.10),"category":"footwear"},
 "p2":{"title":"waterproof trail running shoe","vec":(0.94,0.22),"category":"footwear"},
 "p3":{"title":"hiking boot outdoor grip","vec":(0.78,0.48),"category":"footwear"},
 "p4":{"title":"wireless studio headphones","vec":(0.05,0.99),"category":"audio"},
 "p5":{"title":"wireless earbuds","vec":(0.12,0.96),"category":"audio"},
 "p6":{"title":"fitness smart watch","vec":(0.58,0.58),"category":"wearable"},
}
query = (1.0, 0.12)

def cosine(a,b):
    dot=sum(x*y for x,y in zip(a,b))
    na=math.sqrt(sum(x*x for x in a)); nb=math.sqrt(sum(y*y for y in b))
    return dot/(na*nb)

def exact_knn(k=3, category=None):
    rows=[]
    for pid,p in products.items():
        if category and p["category"] != category: continue
        rows.append((cosine(query,p["vec"]),pid))
    rows.sort(reverse=True)
    return [pid for _,pid in rows[:k]]

# A tiny deterministic graph-search simulator. It is HNSW-inspired, not HNSW.
graph = {
 "p4":["p5","p6"], "p5":["p4","p6"], "p6":["p4","p5","p3"],
 "p3":["p6","p2"], "p2":["p3","p1"], "p1":["p2"]
}

def approx_graph_search(expansions, k=3):
    entry="p4"; seen={entry}; frontier=[(-cosine(query,products[entry]["vec"]),entry)]
    visited=[]
    for _ in range(expansions):
        if not frontier: break
        neg,pid=heapq.heappop(frontier); visited.append(pid)
        for nxt in graph[pid]:
            if nxt not in seen:
                seen.add(nxt)
                heapq.heappush(frontier,(-cosine(query,products[nxt]["vec"]),nxt))
    candidates=seen
    ranked=sorted(((cosine(query,products[p]["vec"]),p) for p in candidates),reverse=True)
    return [p for _,p in ranked[:k]], len(candidates), visited

exact=exact_knn()
print("exact top3:", exact)
for budget in (1,2,4,6):
    approx, seen, visited = approx_graph_search(budget)
    recall=len(set(approx)&set(exact))/len(exact)
    print(f"approx budget={budget} top3={approx} recall@3={recall:.2f} candidates={seen} expanded={visited}")
print("exact footwear top3:", exact_knn(category="footwear"))

# Hybrid lexical + vector scoring over the exact candidate set for clarity.
def terms(text): return set(re.findall(r"[a-z0-9]+", text.lower()))
qterms=terms("waterproof trail running")
rows=[]
for pid,p in products.items():
    lexical=len(qterms & terms(p["title"]))/len(qterms)
    vector=cosine(query,p["vec"])
    hybrid=0.55*lexical+0.45*vector
    rows.append((hybrid,pid,round(lexical,3),round(vector,3)))
rows.sort(reverse=True)
print("hybrid top3:", rows[:3])

4. HNSW is a navigable proximity graph with a hierarchy

Hierarchical Navigable Small World (HNSW), introduced by Malkov and Yashunin, builds layered proximity graphs. Search starts in sparse upper layers to approach the query region quickly, then descends into denser layers and explores candidates near the current best results. Implementations expose parameters with names such as M (roughly graph connectivity), ef_construction (build-time exploration), and ef_search or analogous candidate controls. Exact names/defaults vary. More connections or exploration can improve recall but increase memory, build cost, query work, or latency. The lab intentionally uses a tiny HNSW-inspired graph search only to make the recall mechanism observable.

5. Filtering changes ANN behavior

A production query often requires “semantically similar shoes, but tenant=t1, in stock, category=footwear, and visible in this market.” A vector engine must combine ANN exploration with structured filtering. Applying a filter after ANN can return fewer than k eligible results; applying it during exploration may require visiting more graph nodes. Elasticsearch 9.5.2 documents that filtered HNSW search can switch strategies and that num_candidates is a principal speed/accuracy control. Treat such details as product-specific and benchmark with the real filter selectivity distributions that your workload produces.

6. Hybrid retrieval uses independent evidence channels

Lexical search is good at exact names, rare identifiers, phrases, and term-specific relevance. Vector search is useful for semantic similarity when the embedding model captures the intended relation. Hybrid retrieval combines lexical and vector candidates/scores, often with filters and reranking. The lab uses a transparent weighted combination only for teaching. Production systems should normalize incomparable score scales carefully, validate ranking quality with labeled judgments or business metrics, and prevent the vector signal from overriding hard authorization, availability, price, or regulatory constraints.

7. Production judgment

Use ANN only after defining quality targets and an exact evaluation set. Record embedding model/version, dimension, metric, index algorithm, build/search parameters, quantization, filter strategy, shard count, replica count, memory/page-cache assumptions, and dataset distribution. Measure recall@k and p95/p99 latency together; a faster index with unacceptable recall is not “better.” Plan re-embedding/reindex migrations when models change, protect vectors if they encode sensitive user behavior, and monitor index freshness. HNSW can be memory-intensive; current Elasticsearch documentation recommends enough memory/page cache for efficient operation. Approximate retrieval is a search optimization, not a correctness oracle.

Wrong approach: benchmark ANN latency without an exact quality baseline

Verification, cleanup, and production checklist

Verification is the deterministic program output plus the conceptual checks below. Cleanup is deleting the local lesson4_vector_ann.py file; the lab creates no sockets, databases, containers, credentials, indexes, or cloud resources. In production, additionally record authoritative-versus-derived ownership, source/index versions, refresh or projection lag, p95/p99 read/write latency, index size and write amplification, shard/index-key skew, rebuild throughput, ANN recall where applicable, tenant/authorization tests, backup/rebuild evidence, current security advisories, and edition/license constraints before relying on a product-specific feature.

References

Foundational statements use primary research or standards where appropriate. Version-sensitive implementation examples use current official documentation and remain explicitly scoped to the cited product/version.

• Malkov & Yashunin — HNSW — Foundational HNSW paper/preprint.
• Elasticsearch — kNN search — Current exact/approximate kNN, filtering, HNSW, candidate, and hybrid-search documentation.
• OpenSearch — Creating a vector index — Current OpenSearch HNSW/vector-index implementation example.
• OpenSearch 3.8.0 — Current release snapshot: 3.8.0, released 2026-08-04, Apache License 2.0.
• Elasticsearch 9.5.2 — Current release snapshot: 9.5.2, released 2026-08-20.