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 issue many retrievals per task.

The design must support natural-language intent queries ("where do we validate JWTs"), symbol lookup (validateToken), and graph-shaped questions ("find usages") under a tight retrieval latency budget and a commit-to-searchable freshness SLA — without shipping source to a third party if policy forbids it.

In the governed enterprise platform, this is the sibling of document RAG: same retrieval instinct, different artifact. Code is structured, cross-referenced, and constantly churning; treating it like PDFs produces a search system that feels smart in demos and wrong in the editor.

Why it is hard

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

1. Structure is meaning. A function is a natural retrieval unit; a fixed 512-token window that splits a function mid-body or glues two unrelated functions produces semantically broken chunks. Chunk boundaries must come from the parse tree, not a token counter.
2. Identifiers are exact-match tokens. getUserByEmail is one opaque token to an embedding but a precise handle to a symbol index. Most real developer queries contain at least one identifier — a pure-embedding system loses exactly those queries.
3. Meaning is non-local. What processOrder does depends on callees defined elsewhere; usages, definitions, and implementations are graph relations. Embeddings capture "what this text is about," not "what references this" — you need a symbol/reference index alongside vectors.
4. Churn is constant and localized. Thousands of commits/day touching ~0.1% of files daily — incremental indexing is the core engineering problem, where for prose RAG it is often an afterthought.

Prose-RAG defaults that each fail in a specific way:

This question separates engineers who have built RAG over documents from engineers who have built retrieval over a live codebase.

Requirements and scale

Clarifying questions (each tied to a design consequence)

1. Who queries, human or LLM agent? Agents issue 5–20 retrievals per task and tolerate ~100–300 ms; humans issue one and expect an IDE-fast experience. Agent traffic also changes what "good" is: the consumer is a context window, so ranking for usefulness-as-context beats click-ranking.
2. Monorepo or many repos, and how big? 30M LOC monorepo vs. 3k small repos changes sharding and permissions: per-repo ACLs matter in the multi-repo case.
3. Query types to support? Natural language "where do we validate JWTs" vs. symbol lookup validateToken vs. "find usages" — the last is a call-graph query embeddings cannot answer.
4. Freshness requirement? Search over yesterday's code misleads an agent editing today's. Commit-to-searchable SLA drives the whole indexing design.
5. Can code leave the environment? Embedding via external API vs. self-hosted model — many orgs forbid shipping source to a third party; also decides whether the vector store may hold plaintext snippets or only pointers.
6. Languages? Tree-sitter covers the mainstream; a Cobol tail gets line-based chunking fallback.

Requirements (assumed)

Capacity estimates

Explicit arithmetic:

• Tokens: 30,000,000 LOC × 40 tokens/line ≈ 1,200,000,000 tokens (1.2B).
• Chunks: at ~300 tokens/chunk average, 1.2B / 300 = 4,000,000 chunks.
• Vector storage: 768-dim int8 ≈ 768 bytes ≈ 0.75 KB raw; with HNSW overhead planning ~3 KB/vector order lands near 4M × 3 KB = 12 GB — matches ~12 GB int8 design figure for a 768-dim code model on one node + replica.
• Daily re-embed: 150,000 chunks/day / 86,400 ≈ 1.74 ≈ 2 chunks/s average — trivial if incremental; bursts need 10× headroom.
• Full rebuild: 1.2B tokens through ~2 GPUs in 4–6 hours (embedding-bound); blue/green only.

The design

AST-aware chunking

Parse with tree-sitter (one grammar per language, uniform API). Chunk rule:

• Each top-level function/method/class is a chunk.
• Oversized nodes split at child boundaries (a class into methods, a long function at block boundaries).
• Tiny adjacent nodes (imports, constants) merge up to a ~300–500-token budget.

Each chunk is embedded with a context header — file path, enclosing class, imports summary, docstring — because def process(self, item) is meaningless without knowing it is in billing/invoices.py. Measured effect in the literature (cAST): structure-aligned chunks beat fixed-size on both retrieval and downstream codegen benchmarks.

Two indexes, one query plane

• Symbol/keyword side: exact + trigram index over identifiers (handles getUserByEmail, camelCase splitting, substring matches — the Zoekt/GitHub-Blackbird family) plus a def/ref table from the extractor for go-to-definition and find-usages.
• Vector side: HNSW over chunk embeddings from a code-specific model for NL → code intent queries.
• A lightweight query classifier routes: identifier-shaped queries hit symbols first; NL queries fan out to both; results merge with reciprocal rank fusion, then a small cross-encoder reranks 100 → 20 (~40 ms). For agent consumers, an optional graph expansion step pulls definitions of symbols referenced by top hits — the retrieved function plus its immediate callees is a far better context block than the function alone.

Incremental re-indexing on commits — the deep-dive magnet

Maintain a Merkle tree of file-content hashes per branch head (the approach Cursor documents publicly). On push:

1. Compare trees root-down to find changed files in O(changed) not O(total).
2. Re-parse and re-chunk only those files.
3. Diff chunks by content hash so an edit touching one function re-embeds one chunk, not the file's twenty.
4. Deletes tombstone immediately; upserts land in the vector index's write buffer (searchable pre-merge in HNSW implementations with a WAL/buffer tier).

Branch handling: index main fully; serve feature-branch queries as main's index + an overlay of that branch's changed files, avoiding per-branch full copies.

Commit-to-searchable p95 target: 30 s (parse ~1 s, embed ~2 s for a typical diff; the budget is queue headroom for merge-train bursts — provision for 10× average). The 4–6 h full rebuild path stays available for embedding-model upgrades as a blue/green swap. SLA requirement is commit-to- searchable < 60 s; 30 s p95 leaves headroom.

Serving path — latency budget

p95 without graph expand: 40 + 30 + 40 + 90 = 200 ms (ANN and symbol in parallel → max(30,40)=40). With graph expand: 200 + 60 = 260 ms < 300 ms target.

Evaluation

Golden set of 300+ (query → expected file:line spans), three slices scored separately — NL intent, identifier lookup, find-usages — because a mean over slices hides regressions in one. recall@10 and MRR per slice on every chunker/model/fusion change.

Online: click-through position for humans; for agents the metric that matters is task-level — did the coding agent's edit succeed with retrieved context — sampled via agent-trace review, since snippet-level relevance can look fine while the agent starves for the one callee it needed. Mine zero-click and agent-retry queries weekly into the golden set.

Key decisions and tradeoffs

The flows

Flow A — Natural-language query (human or agent)

1. Query classifier labels NL intent.
2. Embed query; fan out to vector ANN and symbol/trigram in parallel.
3. Reciprocal rank fusion → cross-encoder rerank 100 → 20.
4. Optional graph expansion for agent mode (defs/callees of top hits).
5. Return ranked snippets with file:line.

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

Flow B — Identifier / find-usages query

1. Classifier detects identifier shape (or explicit find-usages intent).
2. Symbol/trigram and def/ref table are primary; vectors optional for ranking context.
3. Return exact defs/refs with file:line — no approximate substitution for usages lists.

Breaks when: symbol extractor missed a language construct, or someone routes usages through ANN.

Flow C — Commit incremental index

1. Git commit/merge event → Merkle diff of file hashes.
2. Parse only changed files; re-chunk; content-hash diff chunks.
3. Re-embed changed chunks only; tombstone deletes; update def/ref.
4. Searchable within tens of seconds (p95 ~30 s; SLA < 60 s).

Breaks when: git events drop (index divergence), or content-hash treats renames as full logical churn (accepted cost — re-embed throughput provisioned above average).

Flow D — Embedding model upgrade

1. Full 4–6 h rebuild into shadow index.
2. Slice-wise eval gate (NL / identifier / usages).
3. Cut over; keep old index for instant rollback.

Breaks when: cutover without per-slice metrics (mean recall hides a dead identifier path).

Failure modes and degradation

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

Common drill-downs

Why not just grep? It's a monorepo, ripgrep is fast.

Concede the half-truth: for identifier queries, lexical search is excellent — that's why the design keeps a trigram/symbol index and routes those queries to it. Grep fails on intent queries ("where do we throttle outbound webhooks") where the vocabulary in the query appears nowhere in the code, and on ranking (10k matches, no relevance order). The design is grep + structure + embeddings, not embeddings instead of grep.

An engineer renames a function used in 400 files. What does your index do?

The defining file re-chunks and re-embeds (~1 chunk). The 400 call sites changed one token each — content hashes differ, so those chunks re-embed too (~400 chunks, ~30 s through the queue). The def/ref table updates transactionally with the symbol extractor pass. Point out the subtlety: embeddings of semantically unchanged callers churn — content-hash diffing can't tell a rename from logic change; that's accepted cost, and it's why re-embed throughput is provisioned above average churn.

Embeddings capture "what code is about" — how do you answer "what breaks if I change this"?

You don't, with vectors — that's the def/ref graph's job, and it must be exact, not approximate: a 95%-recall usages list is a broken refactor. Keep impact queries on the symbol side entirely; use embeddings only for discovery-shaped questions. Knowing which questions must never be answered probabilistically is the distinction that matters in practice.

How does this change if code can't be sent to any external API?

It's already designed for that: self-hosted embedding model (open-weight code embedders are competitive), vector store in VPC. Extra hardening if required: store embeddings + file:line pointers only, hydrate snippet text from the git host at query time under the caller's credentials — the index then never holds plaintext, which also solves per-path ACLs (hydration fails for unauthorized files; filter hits by the caller's repo grants before hydration to avoid oracle leaks via result counts).

Your NL recall is fine but agents still retrieve useless context. Why?

Snippet relevance ≠ context sufficiency: the agent got the right function but not its helper, or five near-duplicate hits from generated code crowding out the one distinct file. Fixes: graph expansion of top hits, near-duplicate collapse at rank time, and evaluating on agent task success rather than recall@k alone.

Test yourself

Go deeper

• The technology behind GitHub's new code search — GitHub Engineering — Blackbird: ngram indexing and sharding for exact code search at extreme scale; the lexical half of this design.
• Securely indexing large codebases — Cursor — the Merkle-tree incremental sync and privacy-preserving indexing pipeline this design borrows.
• How Cody understands your codebase — Sourcegraph — context-fetching for a production coding assistant, including their move away from pure embeddings.
• cAST: Enhancing Code Retrieval-Augmented Generation with Structural Chunking via Abstract Syntax Tree — the measured case for AST-aligned chunking over fixed-size.

Where this connects

• Enterprise RAG — same hybrid + eval discipline over prose documents; contrast chunking and freshness assumptions.
• Hybrid search — RRF and when lexical wins — the mechanism behind symbol+vector fusion.
• Agent foundations — how coding agents consume retrieval as multi-step context, not single-shot search.
• Open source and self-hosting — serving the code embedding model inside the VPC.