Design: Semantic Code Search

The problem

Design semantic search over a company's codebase — or the retrieval layer for an AI coding assistant over a ~30M-LOC monorepo. Users are both humans in an IDE and LLM agents that fire many retrievals per task.

It must support natural-language intent ("where do we validate JWTs"), symbol lookup (validateToken), and graph questions ("find usages") under a tight retrieval latency budget and a commit-to-searchable freshness SLA. If policy forbids shipping source outside the VPC, embeddings must be self-hosted too.

In the governed enterprise platform, this is the sibling of document RAG: same retrieval instinct, different artifact. Treat code like PDFs and the system feels smart in demos and wrong in the editor.

Why it is hard

Code is not prose. Four properties break document-RAG defaults.

Structure is meaning. A function is a natural retrieval unit. Fixed 512-token windows that split a function mid-body or glue two unrelated ones produce broken chunks. Boundaries must come from the parse tree, not a token counter.

Identifiers are exact-match tokens. getUserByEmail is one opaque token to an embedding but a precise handle to a symbol index. Most developer queries contain at least one identifier, so pure embeddings lose exactly those queries.

Meaning is non-local. What processOrder does depends on callees defined elsewhere. Embeddings capture "what this text is about," not "what references this."

Churn is constant and localized. Thousands of commits a day may touch only ~0.1% of files. Incremental indexing is the core problem; for prose RAG it is often an afterthought.

Requirements and scale

Clarifying questions (each tied to a design consequence)

1. Who queries — human or agent? Agents issue 5–20 retrievals/task at ~100–300 ms; ranking optimizes for context sufficiency, not click MRR.
2. Monorepo or many repos? Decides sharding and per-repo ACLs.
3. Which query types? NL vs. symbol vs. find-usages — the last is a call-graph query embeddings cannot answer.
4. Freshness? Commit-to-searchable SLA drives indexing; stale code misleads agents.
5. Can code leave the environment? External embed API vs. self-hosted; plaintext vs. pointers.
6. Languages? Tree-sitter for the mainstream; obscure tails get line-window fallback.

Requirements and capacity (assumed)

Illustrative monorepo math (re-derive for your corpus):

At ~20 QPS this is not a throughput problem. It is a chunking, hybrid routing, and freshness problem.

The design

AST-aware chunking

Parse with tree-sitter (one grammar per language, uniform API). Each top-level function, method, or class is a chunk; oversized nodes split at child boundaries; tiny siblings merge up to a ~300–500-token budget. Embed each chunk with a context header — file path, enclosing class, import summary, docstring — because def process(self, item) is meaningless without knowing it lives in billing/invoices.py. Structure-aligned chunks beat fixed-size windows on retrieval and codegen; cAST is the measured case (see Go deeper).

Two indexes, one query plane

1. Symbol / keyword. Exact + trigram index over identifiers (camelCase splitting, substring matches — the Zoekt / GitHub Blackbird family) plus a def/ref table for go-to-definition and find-usages. Trigrams are overlapping character n-grams; they make fuzzy identifier lookup cheap at monorepo scale.
2. Vector. HNSW over chunk embeddings from a code-specific embedder for NL → code intent. Self-host an open-weight code model when source cannot leave.
3. Classifier + fusion. Identifier-shaped queries hit symbols first; NL fans out to both. Merge with reciprocal rank fusion, then a cross-encoder reranks 100 → 20 (~40 ms). For agents, optional graph expansion pulls defs of symbols in top hits — function plus immediate callees beats the function alone.

Pure dense retrieval is not enough. The lexical/symbol half is half the product, not a fallback.

Incremental re-indexing — the deep-dive magnet

Maintain a Merkle tree of file-content hashes per branch head (the approach Cursor documents). It hashes every file, then each directory from its children, so a root-to-leaf walk finds changed files in O(changed), not O(total). On push: compare trees → re-parse only changed files → diff chunks by content hash (one-function edits re-embed one chunk, not twenty) → unchanged hashes hit an embed cache → deletes tombstone immediately; upserts land in the vector write buffer.

Branches: index main fully; serve feature branches as main + an overlay of changed files. Commit-to-searchable p95 ~30 s (parse ~1 s, embed ~2 s typical; rest is 10× burst headroom). SLA is < 60 s. Keep the 4–6 h full rebuild for model upgrades as a blue/green swap.

Serving path and evaluation

Parallel symbol + ANN: p95 without expand = max(30, 40) + 40 + 90 = 200 ms. With expand: 260 ms < 300 ms.

Golden set of 300+ (query → expected file:line), scored as three slices — NL, identifier, find-usages — because a mean hides regressions in one path. Online: click position for humans; task success from agent traces. Mine zero-click and agent-retry queries weekly.

Key decisions and tradeoffs

The flows

Flow A — Natural-language query

Classifier labels NL → fan out to ANN + symbol/trigram → RRF → cross-encoder 100 → 20 → optional graph expand for agents → ranked snippets with file:line.

Breaks when: headers omit path/class, fusion over-weights dense on identifier-heavy NL, or generated code crowds top ranks.

Flow B — Identifier / find-usages

Classifier detects identifier shape → symbol/trigram and def/ref primary → exact defs/refs. No approximate substitution for usages lists.

Breaks when: extractor missed a construct, or usages are routed through ANN.

Flow C — Commit incremental index

Git event → Merkle file-hash diff → parse changed files → content-hash diff chunks → re-embed changed only; tombstone deletes; update def/ref → searchable in tens of seconds (p95 ~30 s).

Breaks when: git events drop (index divergence), or renames re-embed as full churn (accepted cost — provision above average).

Flow D — Embedding model upgrade

Full rebuild into a shadow index → per-slice eval gate → cut over; keep old index for rollback.

Breaks when: cutover on mean recall only (hides a dead identifier path).

Failure modes and degradation

Index divergence is the characteristic failure: the index looks healthy while serving yesterday's truth. Heartbeat reconciliation is not optional.

Common drill-downs

Why not just grep? For identifier queries, lexical search is excellent — that is why symbols are first-class. Grep fails on intent queries where the query vocabulary is absent from the code, and on ranking (10k matches, no order). The design is grep + structure + embeddings.

A rename touches 400 call sites. Defining file: ~1 chunk re-embeds. Call sites each change one token → ~400 chunks re-embed (~30 s). Content hashes cannot tell a rename from a logic change — accepted cost; provision re-embed above average.

Code cannot leave the VPC. Self-hosted embedder and in-VPC store are already assumed. Extra hardening: store only embeddings + file:line; hydrate from git under caller credentials. Filter hits by grants before hydration to avoid oracle leaks via result counts.

NL recall is fine; agents still get useless context. Snippet relevance ≠ context sufficiency: right function, missing helper; or near-duplicates crowd the distinct file. Fix with graph expansion, near-duplicate collapse, and task-success eval — not recall@k alone.

Test yourself

Go deeper

• The technology behind GitHub's new code search — Blackbird ngram indexing; the lexical half of this design.
• Securely indexing large codebases — Cursor — Merkle-tree incremental sync, syntactic chunks, content-hash embed caching.
• How Cody understands your codebase — Sourcegraph — production context fetching, including the move away from pure embeddings.
• cAST: Structural Chunking via AST — measured AST-aligned chunking gains on retrieval and codegen.

Where this connects

• Enterprise RAG — same hybrid + eval discipline over prose; contrast chunking and freshness.
• Hybrid search — RRF and when lexical wins.
• Agent foundations — coding agents as multi-step retrieval consumers.
• Open source and self-hosting — serving the code embedder inside the VPC.