Lab VI4: Visualizing the Vector Space — Embeddings, HNSW, IVF Cells, and the Recall Frontier

Background

Every other page in this curriculum draws vector search with mermaid and ASCII. This lab makes you render the real thing — actual images from real data — because some facts about vector search only become obvious when you see them: that "meaning is geometry" is literally a cluster on a 2-D plot; that the recall–latency trade-off is a curve you can walk; that an HNSW graph really is sparse express lanes over a dense base layer; that IVF really does carve space into Voronoi cells and a query really does miss neighbours in cells it didn't probe.

You will produce five figures: (1) a 2-D projection of high-dimensional embeddings showing semantic clusters; (2) the recall-vs-latency frontier — the defining plot of ANN engineering — swept over ef_search; (3) an HNSW graph rendered by layer, built and exported from Java (Lucene's own graph) to Graphviz; (4) IVF Voronoi cells with a query and its probed cells highlighted; and (5) (optional) a PQ codebook grid showing quantization error. Plotting is Python (matplotlib/ scikit-learn/scipy/networkx — the pragmatic standard, already used by Lab K6); the HNSW graph itself comes from real Java, so you see the engine's structure, not a toy.

Why This Lab Matters for Contributors

• A recall complaint is abstract until you plot the frontier and see exactly where the operator's ef_search sits on it. This is the single most useful diagnostic artifact in ANN.
• Reviewing an HNSW or IVF change is far easier when you can render the structure before and after a patch and look at what changed — disconnected nodes, lopsided layers, empty cells.
• "Why did this query miss its true neighbour?" is answerable by drawing the Voronoi cells and the probed set. Several real k-NN recall issues reduce to a boundary effect you can see.
• It connects every prior VI lab to a picture: VI1's graph, VI2's IVF/PQ index, VI3's quantization error — all become figures here.

Prerequisites

• You've done Lab VI1 (build an HNSW graph in Java), VI2 (IVF/PQ), and VI3.
• Read Vector Search Foundations (the geometry and the recall@k definition you are about to visualize) and Lab K6 (recall/latency measurement).
• A Python env and a JDK. Graphviz (dot) for the Java HNSW render.

python3 -m venv ~/.venv-annviz && source ~/.venv-annviz/bin/activate
pip install numpy scikit-learn matplotlib scipy networkx hnswlib
# Graphviz CLI for the Java->DOT render:
#   macOS: brew install graphviz   |   Debian/Ubuntu: sudo apt-get install graphviz
dot -V

Note: hnswlib gives you a real HNSW with a tunable ef so the frontier plot is genuine, not simulated. If you cannot install it, Step 2 includes a dependency-free NumPy fallback and a path to plot real OpenSearch numbers straight from Lab K6's output.

Step-by-Step Tasks

Step 1 — See "meaning is geometry": project embeddings to 2-D

High-dimensional embeddings are unplottable directly, but PCA projects them to 2-D while preserving the largest-variance structure. Real semantic clusters survive the projection — that is the whole "meaning is geometry" claim, made visible.

# viz1_embeddings.py — project clustered high-dim vectors to 2-D.
import numpy as np
from sklearn.decomposition import PCA
import matplotlib.pyplot as plt

rng = np.random.default_rng(0)
d, per_cluster, n_clusters = 768, 60, 4
centers = rng.normal(scale=3.0, size=(n_clusters, d))            # 4 "topics" in 768-d
X = np.vstack([c + rng.normal(scale=1.0, size=(per_cluster, d)) for c in centers])
labels = np.repeat(np.arange(n_clusters), per_cluster)

X2 = PCA(n_components=2).fit_transform(X)                        # 768-d -> 2-d
plt.figure(figsize=(6, 6))
for c in range(n_clusters):
    pts = X2[labels == c]
    plt.scatter(pts[:, 0], pts[:, 1], s=14, label=f"topic {c}")
plt.legend(); plt.title("768-d embeddings projected to 2-D (PCA)\nproximity = similarity")
plt.tight_layout(); plt.savefig("viz1_embedding_pca.png", dpi=120)
print("wrote viz1_embedding_pca.png")

python3 viz1_embeddings.py

Four well-separated blobs: the ANN problem is "given a query point, find its blob-mates fast." If you have sentence-transformers installed, replace the synthetic X with embeddings of real strings (reuse the cat/kitten/tax-form examples from the k-NN warm-up) and watch semantically related sentences cluster. For an even sharper view of local neighbourhoods, swap PCA for t-SNE (from sklearn.manifold import TSNE; X2 = TSNE(n_components=2, perplexity=30).fit_transform(X)) — slower, but it preserves the near-neighbour structure ANN actually cares about.

Note: PCA is linear and preserves global variance; t-SNE/UMAP preserve local neighbourhoods but distort global distances. For "do my classes separate?" use PCA; for "what are the local neighbourhoods?" use t-SNE. Never read absolute distances off a t-SNE plot.

Step 2 — Plot the recall–latency frontier

This is the chart the whole curriculum builds toward. Build a real HNSW, sweep ef_search, and for each setting measure recall@k (against a brute-force ground truth — exactly the recall@k from the foundations chapter) and latency. Each ef is one point; connected, they are the frontier.

# viz2_frontier.py — the recall vs latency frontier of a real HNSW, swept over ef.
import time, numpy as np, matplotlib.pyplot as plt
import hnswlib

dim, N, Q, k = 128, 20_000, 200, 10
rng = np.random.default_rng(0)
data    = rng.random((N, dim)).astype("float32")
queries = rng.random((Q, dim)).astype("float32")

# Ground truth: exact top-k by brute force (the O(N*d) scan you approximate).
gt = np.empty((Q, k), dtype=int)
for i, q in enumerate(queries):
    dist = ((data - q) ** 2).sum(1)
    gt[i] = np.argpartition(dist, k)[:k]

index = hnswlib.Index(space="l2", dim=dim)
index.init_index(max_elements=N, ef_construction=200, M=16)     # M, ef_construction baked in here
index.add_items(data, np.arange(N))

recalls, latencies = [], []
for ef in [10, 20, 40, 80, 160, 320]:                          # the query-time knob
    index.set_ef(ef)
    t0 = time.perf_counter()
    labels, _ = index.knn_query(queries, k=k)
    ms = (time.perf_counter() - t0) / Q * 1e3                  # ms per query
    rec = np.mean([len(set(labels[i]) & set(gt[i])) / k for i in range(Q)])
    recalls.append(rec); latencies.append(ms)
    print(f"ef={ef:4d}  recall@{k}={rec:.3f}  {ms:.3f} ms/query")

plt.figure(figsize=(6, 5))
plt.plot(latencies, recalls, "o-")
for ef, x, y in zip([10,20,40,80,160,320], latencies, recalls):
    plt.annotate(f"ef={ef}", (x, y), textcoords="offset points", xytext=(6, -8), fontsize=8)
plt.xlabel("latency (ms/query)"); plt.ylabel(f"recall@{k}")
plt.title("The recall–latency frontier (HNSW, ef_search swept)")
plt.grid(True, alpha=0.3); plt.tight_layout(); plt.savefig("viz2_frontier.png", dpi=120)

python3 viz2_frontier.py

You get the canonical concave curve: cheap+low-recall in the lower-left, expensive+high-recall in the upper-right, with diminishing returns — the first slice of latency buys a lot of recall, the last slice buys almost none. That curve is the operational meaning of "tune ef_search." Overlay a second curve for a quantized index (PQ) and you'll see it shifted — lower recall at equal latency, which a rescoring pass pulls back up.

• No hnswlib? Replace the index with a dependency-free IVF simulation: k-means nlist centroids (sklearn.cluster.KMeans), and for each nprobe ∈ {1,2,4,8,16} scan only the nearest nprobe cells; recall vs nprobe (proxy latency = candidates scanned) gives the same frontier shape.
• Plot OpenSearch's real numbers instead of a library's: run Lab K6 at several index.knn.algo_param.ef_search values, capture recall and the took/p90, and feed those two arrays into the plt.plot above. Now the frontier is your actual cluster.

Step 3 — Render a real HNSW graph, by layer, from Java

The graph in the HNSW chapter is a schematic. Here you export Lucene's actual HnswGraph — the one the lucene engine builds — to Graphviz and render it, so you see the engine's real layer structure. Reuse the builder from Lab VI1; the new part is the walk-to-DOT exporter.

// HnswToDot.java — walk a built Lucene HnswGraph and emit Graphviz DOT, one cluster per layer.
// Construct `hnsw` exactly as in Lab VI1 (HnswGraphBuilder over your float[][] vectors);
// this snippet focuses on the export. API names are version-sensitive: verify with
//   grep -rn "getNodesOnLevel\|nextNeighbor\|numLevels\|seek" lucene/core/src/java/org/apache/lucene/util/hnsw/HnswGraph.java
import org.apache.lucene.util.hnsw.HnswGraph;
import static org.apache.lucene.search.DocIdSetIterator.NO_MORE_DOCS;
import java.nio.file.*;

static void exportDot(HnswGraph hnsw, Path out) throws Exception {
    StringBuilder dot = new StringBuilder("digraph HNSW {\n  rankdir=LR;\n  node[shape=circle,fontsize=8];\n");
    for (int level = hnsw.numLevels() - 1; level >= 0; level--) {     // top (sparse) -> bottom (dense)
        dot.append("  subgraph cluster_").append(level).append(" {\n")
           .append("    label=\"layer ").append(level).append("\"; color=gray;\n");
        HnswGraph.NodesIterator nodes = hnsw.getNodesOnLevel(level);
        while (nodes.hasNext()) {
            int node = nodes.nextInt();
            hnsw.seek(level, node);                                    // position cursor at node's neighbours
            int nb;
            while ((nb = hnsw.nextNeighbor()) != NO_MORE_DOCS) {       // iterate this node's edges
                dot.append("    \"L").append(level).append("_").append(node)
                   .append("\" -> \"L").append(level).append("_").append(nb).append("\";\n");
            }
        }
        dot.append("  }\n");
    }
    dot.append("}\n");
    Files.writeString(out, dot.toString());
    System.out.println("wrote " + out + " (" + hnsw.numLevels() + " levels)");
}

# Compile/run against your Lucene jars (same classpath as Lab VI1), then render:
#   javac -cp "$LUCENE_CP" HnswToDot.java && java -cp ".:$LUCENE_CP" HnswToDot   # builds graph + writes hnsw.dot
dot -Tpng hnsw.dot -o viz3_hnsw_layers.png

The render shows the defining HNSW shape: a sparse top layer (a few "express-lane" nodes with long-range edges) sitting over a dense layer 0 (every node, short-range edges). That is the skip-list-for-geometry the algorithm describes — now you can count the nodes per layer and confirm the geometric decay (~N/M fewer nodes each level up).

Tip: Want it in pure Python instead? Build a toy HNSW with networkx (or reuse hnswlib's graph via get_items) and nx.draw per layer. But exporting Lucene's own graph is the point — it's the structure the engine actually searches, and the exporter is a reusable debugging tool you can point at any built graph in a test.

Step 4 — Draw IVF Voronoi cells and a missed neighbour

IVF partitions space into Voronoi cells around centroids and probes only nprobe of them. In 2-D you can draw the actual cells and see the recall trade-off: a true neighbour in an unprobed cell is simply missed.

# viz4_ivf_voronoi.py — IVF cells, a query, its probed cells, and a missed neighbour.
import numpy as np, matplotlib.pyplot as plt
from scipy.spatial import Voronoi, voronoi_plot_2d

rng = np.random.default_rng(1)
centroids = rng.random((16, 2))            # nlist = 16 cells (k-means centroids, in 2-D)
points    = rng.random((400, 2))           # indexed vectors
q         = np.array([0.5, 0.52])          # the query
nprobe    = 3

vor = Voronoi(centroids)
fig, ax = plt.subplots(figsize=(6.5, 6.5))
voronoi_plot_2d(vor, ax=ax, show_vertices=False, line_colors="gray", line_alpha=0.5, point_size=0)
ax.scatter(points[:, 0], points[:, 1], s=8, c="lightgray")
ax.scatter(centroids[:, 0], centroids[:, 1], marker="x", c="red", label="centroids")
ax.scatter(*q, marker="*", s=260, c="blue", zorder=5, label="query")

probed = np.argsort(((centroids - q) ** 2).sum(1))[:nprobe]            # nearest nprobe centroids
for ci in probed:                                                     # highlight probed centroids
    ax.scatter(*centroids[ci], s=240, facecolors="none", edgecolors="green", linewidths=2)

# True nearest point vs. nearest point within the probed cells -> is the true NN missed?
cell_of = np.argmin(((points[:, None, :] - centroids[None, :, :]) ** 2).sum(2), axis=1)
true_nn = points[np.argmin(((points - q) ** 2).sum(1))]
mask = np.isin(cell_of, probed)
approx_nn = points[mask][np.argmin(((points[mask] - q) ** 2).sum(1))]
ax.scatter(*true_nn,  marker="o", s=120, facecolors="none", edgecolors="black", linewidths=2, label="true NN")
ax.scatter(*approx_nn, marker="o", s=120, facecolors="none", edgecolors="orange", linewidths=2, label="IVF NN (nprobe)")
ax.set_title(f"IVF: nlist=16, nprobe={nprobe}\nblue=query, green=probed cells, black=true NN, orange=IVF result")
ax.legend(loc="upper left", fontsize=8); plt.tight_layout(); plt.savefig("viz4_ivf_voronoi.png", dpi=120)
print("true NN missed?", not np.allclose(true_nn, approx_nn))

python3 viz4_ivf_voronoi.py
# Try nprobe=1 (often misses the true NN near a cell boundary) then nprobe=8 (almost always finds it).

When the true NN sits in a cell next to — but not inside — the probed set (a boundary effect), IVF returns the wrong neighbour. Raising nprobe lights up more cells and fixes it, at more distance computations: the recall–latency trade-off, now a picture. Sweep nprobe ∈ {1,2,4,8} and watch "true NN missed?" flip to False.

Step 5 (optional) — Visualize PQ quantization error

PQ replaces each sub-vector with its nearest codebook centroid. Plot one 2-D sub-space's codebook and draw each point to the centroid it snaps to — the segments are the reconstruction error PQ trades for compression.

# viz5_pq_cells.py — one PQ sub-space: points, codebook centroids, and quantization error segments.
import numpy as np, matplotlib.pyplot as plt
from sklearn.cluster import KMeans

rng = np.random.default_rng(2)
sub = rng.random((600, 2))                       # one 2-D PQ sub-space
km = KMeans(n_clusters=16, n_init=4, random_state=0).fit(sub)   # 16 centroids = nbits=4 codebook
codes, cents = km.labels_, km.cluster_centers_
plt.figure(figsize=(6, 6))
for i, p in enumerate(sub):
    c = cents[codes[i]]
    plt.plot([p[0], c[0]], [p[1], c[1]], color="lightgray", lw=0.5)   # error segment
plt.scatter(sub[:, 0], sub[:, 1], s=6, c="steelblue")
plt.scatter(cents[:, 0], cents[:, 1], marker="x", s=80, c="red")
plt.title("PQ sub-space: each point snaps to its codebook centroid (gray = quantization error)")
plt.tight_layout(); plt.savefig("viz5_pq_cells.png", dpi=120)

Smaller, tighter segments = lower error = higher recall; fewer centroids (smaller nbits) = longer segments = more compression, less recall. That visible trade-off is the quantization math you implemented, drawn.

Deliverables

• viz1_embedding_pca.png — high-dim embeddings projected to 2-D showing separated clusters.
• viz2_frontier.png — a recall-vs-latency frontier from a real HNSW (or real OpenSearch K6 numbers), annotated with the ef_search values.
• viz3_hnsw_layers.png — Lucene's actual HnswGraph rendered by layer from a Java exporter.
• viz4_ivf_voronoi.png — IVF cells with a query, its nprobe probed cells, and a true-vs-IVF neighbour, plus the printed "true NN missed?" at nprobe=1.
• A 4–6 sentence written reading of the frontier: where diminishing returns set in, and which ef_search you'd choose for a "recall@10 ≥ 0.95, lowest latency" target.

Troubleshooting

Expected Output

# Step 2 (shape, not exact numbers):
ef=  10  recall@10=0.71  0.012 ms/query
ef=  40  recall@10=0.94  0.031 ms/query
ef= 160  recall@10=0.99  0.092 ms/query
ef= 320  recall@10=1.00  0.171 ms/query     # diminishing returns: last doubling buys ~0.01 recall

# Step 4:
true NN missed? True     # at nprobe=1, often
true NN missed? False    # at nprobe=8

Stretch Goals

• Overlay quantized vs float32 frontiers on viz2: add an hnswlib index plus a PQ/SQ version (or two OpenSearch indices) and show the curve shift + how rescoring closes it.
• Animate ef_search: render viz4-style probed sets across an nprobe sweep into a GIF.
• Render before/after a patch: build the HNSW graph from a Lucene branch with and without a change to M/diversity heuristic, export both to DOT, and diff the layer structure visually.
• Real embeddings end-to-end: encode a few hundred real sentences with sentence-transformers, project them (Step 1), index them, and plot the frontier (Step 2) on genuine data.

Coding Exercises

This lab already ships Python plotting; these exercises make the visualizations graded and automated — a tested Java DOT exporter, a frontier harness that runs unattended, and two new figures — instead of one-off scripts. Mix Python (the plots) and Java (the exporter).

1. (warm-up) Assert the layer thinning your viz3 shows. Turn the Step-3 exportDot walk into a Java test that, alongside writing the DOT, returns an int[] nodesPerLevel and asserts each higher layer has fewer nodes than the one below (and roughly ~N/M fewer; a loose ratio bound holds despite randomness). This makes the picture's headline claim machine-checked — the same invariant you assert in Lab VI1 Exercise 2.

2. (warm-up, Python) Add a nprobe annotation sweep to viz4. Extend viz4_ivf_voronoi.py to loop nprobe ∈ {1,2,4,8}, save one PNG per value, and print the "true NN missed?" boolean for each — proving the boundary-effect flip from True to False as cells light up. Assert in the script that the miss rate is non-increasing in nprobe over, say, 50 random queries.

3. (core) A JUnit test for the DOT exporter — valid graph, every edge accounted for. Write a test that builds a tiny HNSW (reuse VI1's builder), runs exportDot to a temp file, and asserts: the output parses as a digraph, the number of -> edges equals the sum over all levels of each node's neighbour count (walk seek/nextNeighbor independently to count), and there are numLevels() subgraph cluster_ blocks. The exporter is a reusable review tool (Stretch Goal 3); a test makes it trustworthy to point at any built graph.

4. (core, Python) Automate the recall-frontier sweep as a reusable function. Refactor viz2_frontier.py into frontier(build_index, ef_values, queries, gt, k) -> (recalls, latencies) that works for any index object exposing set_ef/knn_query, then call it for two indices (float32 HNSW and a PQ/quantized one) and overlay both curves on one plot (Stretch Goal 1). Assert recall is monotonically non-decreasing in ef for each curve. Feed it the CSV emitted by Lab VI1's Frontier.java or Lab VI2's nprobe harness to plot the real engines' frontiers, not a library's.

5. (advanced) Render before/after a M/diversity patch and diff the structure. Build Lucene's HnswGraph twice — once stock, once with M halved (or the diversity predicate disabled, as in VI1 Exercise 5) — export both via Exercise 3's tested exporter, render with dot, and write a Python script that parses both DOT files and reports the per-layer node and edge-count deltas. This is the visual code review the lab argues for (Stretch Goal 3): you can see and quantify what a graph-construction change did.

6. (advanced challenge) A one-command figure pipeline tying VI1–VI3 together. Write a driver (a Makefile or a Python subprocess script) that: (a) runs the Java Frontier/DOT exporters to produce CSVs and .dot files, (b) renders all five figures plus the overlaid frontier from Exercise 4 and the quantization-error frontier from Lab VI3 Exercise 5, and (c) emits a single contact-sheet PNG (matplotlib subplots) captioned with the ef/nprobe/compression settings. Assert every expected output file exists and is non-empty. You now have a reproducible "show me the trade-offs" artifact — the diagnostic you'd attach to a recall-regression issue. Why each point on the frontier costs what it does is explained in native SIMD: faiss distance kernels.

Issues to Practice On

Visualization is the diagnostic layer for recall/latency bugs — the figures here are exactly what makes a recall report concrete. The repo is opensearch-project/k-NN.

Labels drift — list and pick (gh label list --repo opensearch-project/k-NN). k-NN commonly uses good first issue, bug, enhancement, Roadmap.

Representative issue patterns. (1) "Recall is fine on average but bad for some queries" — the per-query variance your viz4 boundary effect explains. Reproduce by plotting the frontier per query bucket, identify the cell-boundary or sparse-region queries, rg the nprobe/ ef_search defaults (grep -rn "nprobe\|ef_search\|DEFAULT" src/main/java), and propose a default or doc fix with a test pinning the worst-case bucket's recall. (2) "Benchmark numbers don't match between runs / engines" — reproduce with a fixed seed, render both frontiers (Exercise 4), and locate the measurement seam; the fix is usually a methodology or ground-truth bug plus a deterministic test.

Planted-bug exercise. In your exportDot (or a copy), change the loop bound to skip the top layer (level > 0 instead of level >= 0). The render still looks plausible — a graph with edges — but Exercise 3's edge-count test goes red because the total edges no longer match the independent seek/nextNeighbor count, and the subgraph count is one short. Note a quick eyeball of viz3_hnsw_layers.png would not catch a missing sparse top layer. Restore level >= 0, then keep the edge-and-cluster-count assertion as the regression that catches a truncated export. The lesson: a figure can look right and be wrong — only a structural assertion proves the export is complete.

Etiquette. Claim an issue before working it, reproduce first (fixed seed, brute-force ground truth), and every PR needs a test, a CHANGELOG.md entry, and a DCO sign-off (git commit -s). See community interaction.

Validation / Self-check

1. From viz2, define the recall–latency frontier in your own words and identify the diminishing-returns region. Which ef_search gives recall@10 ≥ 0.95 at the lowest latency?
2. In viz1, why do PCA-projected embeddings still cluster, and what would the plot look like for uniform random high-dimensional vectors (tie this to the curse of dimensionality)?
3. From viz3, how many nodes are on each HNSW layer, and does the count match the expected ~N/M geometric decay? What do the long top-layer edges do during a search?
4. From viz4, explain precisely why IVF misses a true neighbour at low nprobe, in terms of Voronoi boundaries, and what raising nprobe costs.
5. Which figure best explains a "recall is fine on average but bad for some queries" report, and why?
6. Why is plotting Lucene's real exported graph (Step 3) more useful for reviewing a change than a schematic — give one concrete review you could only do with the render.

When these hold, you can see every trade-off the k-NN curriculum has described. Return to Lab K6 to drive the frontier with real OpenSearch numbers, revisit the foundations with the pictures in mind, and read native SIMD to understand why each point on the frontier costs what it does.