Lesson 14 - Vector Search and What ANN Buys You

Code: agentic-course/agentic/retrieval.py Tests: agentic-course/tests/test_retrieval.py Run it: python3 -m unittest tests.test_retrieval -v Concept: Vector Databases and ANN Search covers the theory and the interview framing, without code.

What you will build

• VectorStore — exact brute-force nearest-neighbour search, which is both the correct starting point and the baseline every approximate index gets measured against.
• Permission filtering that runs before ranking, and a demonstration of the recall it saves.
• A mental model of IVF, HNSW, and product quantization detailed enough to read a vector database’s tuning page as configuration rather than magic.
• An honest answer to “do we need a vector database”, including the case for not buying one.

The idea

Nearest-neighbour search over vectors has an embarrassingly simple exact algorithm: score every vector, sort, take the top k. That is VectorStore, and at the scale of a lesson it is both instant and correct.

It is worth writing that version first for a reason that outlasts the lesson. Once you move to an approximate index, you no longer know whether a missing result was missing because the document is genuinely a poor match or because the index did not look in the right place. The brute-force store answers that question. It is your ground truth: run both, compare the top k, and the overlap is your recall number.

Real-world analogy. Exact search is reading every book in the library. It always finds the right one, and it does not finish. An approximate index is the shelving system: you accept that occasionally the book you wanted was misfiled on the next shelf, in exchange for finishing today. The interesting engineering is in deciding how often you are willing to miss.

Exact search, in full

class VectorStore:
    def __init__(self, embedder: Embedder | None = None) -> None:
        self.embedder = embedder or HashingEmbedder()
        self.chunks: list[Chunk] = []

    def search(
        self,
        query: str,
        k: int = 5,
        permitted: frozenset[str] | None = None,
        min_score: float = 0.0,
    ) -> list[Hit]:
        qv = self.embedder.embed(query)
        candidates = [
            c for c in self.chunks if _permitted(c, permitted)
        ]
        scored = [
            Hit(chunk=c, score=cosine(qv, c.embedding or ()), retriever="dense")
            for c in candidates
        ]
        scored = [h for h in scored if h.score > min_score]
        scored.sort(key=lambda h: (-h.score, h.chunk.id))
        for i, h in enumerate(scored[:k]):
            h.rank = i + 1
        return scored[:k]

Three things are deliberate. The sort key is (-score, chunk.id), so ties break on a stable identifier rather than on insertion order — otherwise your results reshuffle between runs and every eval becomes flaky. Ranks are assigned from 1 after truncation, which matters in the next lesson because fusion combines by rank. And the candidate list is built before any scoring happens, which is the subject of the rest of this section.

Why exact search dies, and what replaces it

Brute force is O(n) in corpus size per query, with the constant set by your dimensionality. At ten thousand chunks nobody notices. At ten million vectors of a thousand dimensions each, one query touches roughly ten billion multiply-adds, and you are paying it on every request. Scanning the whole corpus stops being viable well before your corpus stops growing.

So production dense retrieval is approximate. And that single word is the mental shift this lesson exists for:

Recall stops being a guarantee and becomes a tunable service level objective.

You now own a dial. Turn it one way and queries are fast and sometimes miss the best match; turn it the other and they are slower and miss less. There is no setting that is correct in general — the right setting depends on whether a missed document means a slightly worse answer or a compliance incident. Which means you have to measure recall, against the brute-force baseline, on queries that look like your real traffic. Teams that skip this step do not get a guarantee; they get an unmeasured dial at whatever value the library shipped with.

The index families, at a mechanism level

You will configure these far more often than you implement them. What matters is the mechanism, because the mechanism explains the knobs.

Flat. No index. Exactly what VectorStore does — compare against everything. Perfectly accurate, linear. Use it below roughly a hundred thousand vectors, and keep it forever as the reference you measure against.

IVF — inverted file. Cluster the corpus once into nlist cells, each with a centroid. At query time, compare the query to the centroids only, pick the nprobe closest cells, and search exhaustively inside those. If nlist is 4096 and nprobe is 16 you have scanned about 0.4% of the corpus. The failure mode is geometric and worth picturing: a genuinely good match sitting just across a cell boundary you did not probe is invisible. nprobe is your recall dial, and it is a query-time parameter, so you can raise it for high-stakes queries without rebuilding anything.

HNSW — hierarchical navigable small world. Build a layered graph where each vector links to its neighbours, sparse long-range links at the top layers and dense local links at the bottom. Query by greedy descent: enter at the top, walk to whichever neighbour is closer to the query, drop a layer when you can improve no further, repeat. It is a skip list for geometry. Three knobs: M, how many neighbours each node keeps, and ef_construction, how hard the builder searches for good neighbours — both fixed at build time and both paid for in memory and index build time — plus ef_search, how wide the candidate queue is at query time, which is the recall dial you can change per query. HNSW is the default in most engines because it gives strong recall at low latency. Its costs are memory and churn, below.

Product quantization. A compression scheme, not a search structure, and usually layered on top of one. Split each vector into sub-vectors, learn a small codebook per slice, and store the codebook index instead of the raw floats. A 1024-dimension float32 vector is 4 KB; quantized aggressively it can be tens of bytes. Distances are then computed on the approximations, so you lose precision — which is why the standard pattern is quantized search to build a shortlist, then re-score that shortlist against the full-precision vectors. IVF-PQ is that combination and is what makes billion-scale corpora affordable at all.

Filtering, and the part that is easy to get wrong

Real queries are not pure vector queries. They are “documents matching this meaning, and owned by this tenant, and not archived, and which this caller may read”. Where that filter runs decides whether your search is correct.

flowchart LR
    Q1[Query plus caller grants]
    F1[Filter to permitted set]
    S1[Score the permitted set]
    R1[Top k fully populated]
    Q1 --> F1
    F1 --> S1
    S1 --> R1
    Q2[Query only]
    S2[Score every chunk]
    R2[Top k mixes visible and hidden]
    F2[Drop the hidden ones]
    R3[Short or empty result]
    Q2 --> S2
    S2 --> R2
    R2 --> F2
    F2 --> R3
    classDef edge fill:#6cf,stroke:#333,color:#000
    classDef service fill:#10b981,stroke:#065f46,color:#fff
    classDef data fill:#fbbf24,stroke:#92400e,color:#000
    class Q1,Q2 edge
    class F1,S1,S2,F2 service
    class R1,R2,R3 data

The top path pre-filters; the bottom path post-filters. Post-filtering is what you get by default from any system that treats the vector index as a black box returning k ids, and it silently destroys recall whenever the filter is selective. The top k is computed over everything, then thinned. If all the documents this caller may read happen to score below the cutoff, they are gone — and the caller sees a short list or an empty one, with no error and nothing in the logs.

Here is that failure with the real numbers from the repo’s corpus. Scored against the query "salary bands april", the four chunks come out hr at 0.5000, ship at 0.4082, and the other two at 0.0. Now ask for k=1 as a caller with no grants:

• Post-filter: top-1 is hr at 0.5. Strip it because the caller is not permitted. Result: empty.
• Pre-filter: hr was never a candidate, so top-1 is ship at 0.4082. Result: one hit.

Same data, same k, same permissions. One of them lost a perfectly valid result. That is why _permitted runs inside the candidate comprehension:

def _permitted(chunk: Chunk, permitted: frozenset[str] | None) -> bool:
    if not chunk.permissions:
        return True          # public
    if permitted is None:
        return False         # restricted and no grants supplied - deny
    return bool(chunk.permissions & permitted)

Note the default: a chunk with permissions and no grants supplied is denied. Fail closed. test_restricted_chunk_is_hidden_without_a_grant and test_permission_filter_runs_before_ranking are the two tests holding this down, and test_permissions_hold_through_the_hybrid_path proves it survives fusion.

Access control is filtering, not persuasion

This is the load-bearing security claim of the retrieval lessons. If a restricted chunk reaches the model’s context, it is disclosed — full stop. A system prompt saying “do not reveal HR documents” is not access control; it is a request, addressed to a component that can be talked out of things, about data it can already read. The only defensible design is that the chunk never enters the context.

Which means permitted must come from the caller’s authenticated identity, never from anything the model produced. Demo scenario 4 runs exactly that comparison:

support agent  grants=['none']   comp-bands visible: no   got=['shipping']
hr user        grants=['hr']     comp-bands visible: YES  got=['comp-bands', 'shipping']

Same query, same corpus, same k. The only variable is the grant set, and the restricted chunk appears or does not. Run it with python3 demo.py.

Churn, memory, and cost

Updates and deletes are where graph indexes hurt. HNSW is built on the assumption that its neighbour lists are good. Delete a node and you tear holes in the graph, so implementations typically tombstone rather than truly remove — the vector stops being returned but keeps consuming memory and keeps distorting traversal. Enough churn and recall degrades measurably, with no error anywhere; the fix is a periodic rebuild, which you should plan for rather than discover. IVF tolerates churn better because a delete only touches one cell’s posting list, though heavy drift eventually makes the centroids wrong and wants a re-cluster. If your corpus is genuinely append-mostly, this barely matters. If documents are edited constantly, it is a primary selection criterion.

Memory is the real cost driver. Vectors are dense floats and HNSW wants them resident — raw storage is dimensions times 4 bytes times count, plus graph overhead that scales with M. A million 1024-dimension vectors is about 4 GB of raw vectors before the index. Ten million is 40 GB, and you are now sizing instances rather than choosing libraries. This is the pressure that makes quantization and disk-based indexes like DiskANN interesting: they trade a little recall for an order of magnitude in resident memory, which is frequently the right trade.

Do you need a dedicated vector database at all? Often, no — and this question deserves asking before the procurement conversation, not after. If your corpus is in the low millions and you already run Postgres, pgvector gives you vector search in the system that already holds your data, your transactions, your backups, your access control, and your on-call rotation. If you already run OpenSearch or Elasticsearch for logs or product search, the k-NN support is there and BM25 is in the same index, which makes the hybrid search of the next lesson nearly free. A separate vector store is a second datastore to keep consistent with the first, and consistency between them becomes your problem — the classic symptom is a document deleted from Postgres that is still being retrieved and quoted to users a week later. Buy the dedicated store when scale, filtered-search performance, or recall tuning genuinely demand it.

Treat this as a starting shape, not a spec sheet. Index support and filtering behaviour in this space change release to release — verify against current documentation before you commit, and benchmark on your corpus with your filters, because filtered recall is exactly where published numbers stop transferring.

Exercise

Add a restricted chunk to a VectorStore, prove it is invisible without the grant and visible with it, and write down why pre-filtering matters.

Success criterion: the script runs and both assertions hold, and you can say what the post-filtered version would have returned.

Checkpoint

Why keep brute-force search around once you have an ANN index?

It is your correctness baseline. Approximate indexes return a top k, not the top k, and the only way to know your recall is to compare against exact results on representative queries. Without that comparison you have an untuned dial and no idea what it is set to.

What does it mean that recall becomes an SLO?

Approximate search trades accuracy for speed, so the share of true neighbours you retrieve is now a number you choose, measure, and can regress. ef_search for HNSW and nprobe for IVF are the query-time dials; both let you spend latency to buy recall on the queries that justify it.

Why must the permission filter run before ranking?

Post-filtering computes the top k over everything and then removes what the caller cannot see, so a selective filter can empty the result set even when permitted matches exist. With the repo corpus at k=1, post-filtering returns nothing while pre-filtering returns ship at 0.4082. The loss is silent — no error, no log line.

Why is a system prompt a bad place to enforce document access?

Because a chunk in the context is already disclosed. Instructing the model not to reveal it asks a component that can be argued with to keep a secret it can read. Filter at retrieval using the caller’s authenticated grants, and never let the model choose whose documents it reads.

When is not buying a vector database the right call?

When your corpus is in the low millions and you already operate Postgres or OpenSearch. pgvector and k-NN give you vector search inside the system that already holds your data, transactions, backups, and access control — and OpenSearch additionally gives you BM25 in the same index for free. A separate store adds a consistency problem you now own.

Theory and interview framing: Become an AI Engineer