Agentic Editor · Study Guide

3. Codebase Indexing & Retrieval (RAG for Code)

What This Subsystem Is and Why It Exists

An agentic coding editor has to answer a brutally practical question on every request: "Out of the 2 million lines in this repo, which 50–500 lines does the model actually need to see right now?" Codebase indexing and retrieval is the subsystem that answers it.

It is RAG (Retrieval-Augmented Generation) specialized for source code: a pipeline that pre-processes a repository into a searchable form, then at query time fetches the most relevant snippets and stuffs them into the model's context window before generation.

The naive alternative — "just paste the whole repo into the prompt" — fails for three hard reasons:

  • Context limits. Even with large windows (GPT-4o ~128K tokens, Claude 3.5/4 200K, Gemini 1.5/2.5 up to 1M+), a serious monorepo is tens of millions of tokens. A 1M-line codebase is roughly 10–15M tokens. It physically does not fit.
  • Cost. You pay per input token. At, say, 3–15 per million input tokens, re-sending a 5M-token codebase on every keystroke or chat turn is economically insane. Retrieval cuts the input from millions of tokens to thousands.
  • Latency and quality. Bigger prompts are slower to process (time-to-first-token grows with input length) and lower quality. Models suffer from "lost in the middle" — they attend best to the start and end of a long context and lose facts buried in the middle. Feeding 200K tokens of mostly-irrelevant code actively degrades the answer versus feeding 8K tokens of exactly the right code.

Analogy: the model is a brilliant consultant who bills by the minute and can only hold a dozen documents in their hands at once. Retrieval is the paralegal who runs to the file room and hands them precisely the right dozen pages instead of wheeling in the entire archive.

How It Works, Step by Step

The system has two phases: offline indexing (build a searchable representation) and online retrieval (answer a query).

Phase 1: Building the Index

Step 1 — File walking. Recursively walk the repo, but respect ignore rules. Honor .gitignore, .cursorignore/.aiexclude-style files, plus built-in skips for node_modules, .git, dist, build, lockfiles, binaries, and giant generated files. This both shrinks the index and is a privacy/safety control (keep secrets and vendored code out). You typically cap file size (e.g. skip files > 1–2 MB) and detect binary vs text.

Step 2 — Chunking. You can't embed a whole 2,000-line file as one vector — embeddings have token limits (often 512–8192 tokens) and a single vector for a huge file is semantically mushy. So you split files into chunks. Two strategies:

  • Fixed-window chunking: slice every N lines or N tokens (e.g. 200–500 tokens) with some overlap (10–20%). Simple, language-agnostic, fast. Downside: it slices through the middle of a function, splitting a signature from its body and producing semantically broken fragments.
  • AST / syntax-aware semantic chunking: parse the file with Tree-sitter (a fast incremental parser with grammars for ~40+ languages) and cut on natural boundaries — whole functions, methods, classes, top-level blocks. Each chunk is a coherent unit. You attach metadata (file path, line range, symbol name, language). When a function is too big, you recursively split; when functions are tiny, you may pack siblings together. This is the modern best practice and what most serious tools converge on.

Analogy: fixed-window chunking is cutting a book into equal 2-page strips with scissors regardless of content; AST chunking cuts on chapter and paragraph boundaries so each piece stands on its own.

Step 3 — Embedding. Each chunk is run through an embedding model that maps text → a dense vector (e.g. 768, 1024, 1536, or 3072 dimensions). Semantically similar code lands near each other in vector space. Code-specialized or code-aware embeddings outperform generic text ones because they understand identifiers, syntax, and call patterns. Common choices: OpenAI text-embedding-3-small/large, Voyage AI's voyage-code-2/voyage-code-3 (explicitly code-tuned and used by some tools), Cohere embed, and open models like jina-embeddings-v2-code, BGE, or E5. Embedding is the expensive bulk step — you batch thousands of chunks per API call.

Step 4 — Store in a vector index. Vectors go into a vector store that supports Approximate Nearest Neighbor (ANN) search. Exact nearest-neighbor over millions of vectors is too slow, so you use approximate methods. The dominant algorithm is HNSW (Hierarchical Navigable Small World) — a multi-layer graph where search greedily hops toward the query, giving roughly O(log N) lookups with ~95–99% recall. Alternatives: IVF/IVF-PQ (inverted file + product quantization, used by FAISS) for memory efficiency at scale. Vector store options: FAISS (library), Qdrant, Pinecone, Weaviate, Milvus, pgvector (Postgres), LanceDB, ChromaDB, or an in-process embedded index.

Step 5 — Incremental sync via Merkle trees. Re-embedding the whole repo on every change is wasteful. The well-known solution (described publicly by Cursor) is a Merkle tree over the file system: hash each file, then hash hashes up the directory tree to a single root. To sync, compare the local Merkle tree to the indexed one; only subtrees whose hashes differ contain changed files. So a one-file edit means re-chunking and re-embedding just that file, not the repo. This is the same idea Git and Dropbox use to detect changes cheaply. Sync runs periodically (e.g. every few minutes) and on save.

Phase 2: Retrieval at Query Time

Step 1 — Form the query. The query might be the user's chat message ("why does auth fail on refresh?"), the current cursor location + open file, recently edited symbols, or the active error. Often you do query rewriting / expansion: a cheap model rewrites a vague question into a retrieval-friendly form or generates hypothetical code (a HyDE-style trick — embed a hypothetical answer rather than the question, since answer-shaped text sits closer to real code in vector space).

Step 2 — Hybrid retrieval. Run two retrievers in parallel:

  • Dense / semantic: embed the query, ANN-search the vector index, get top-k chunks by cosine similarity. Great for "find code that means this" even with different wording.
  • Sparse / lexical: exact and near-exact term matching via BM25 (a TF-IDF-family ranking function) or literal search via ripgrep/grep. Unbeatable when the user knows the exact symbol, error string, or filename. Embeddings are weak at rare tokens and exact identifiers; lexical nails them.

You fuse the two result sets, commonly with Reciprocal Rank Fusion (RRF), which combines rankings without needing comparable scores.

Step 3 — Reranking. Take the fused top ~50–100 candidates and run a cross-encoder reranker (e.g. Cohere Rerank, Voyage rerank, or a BGE reranker) that scores each (query, chunk) pair jointly. Cross-encoders are far more accurate than the bi-encoder embeddings used for the first pass, but too slow to run over the whole index — so you use cheap ANN to get candidates, then expensive reranking to pick the final top ~5–20. This two-stage "retrieve then rerank" funnel is the standard pattern.

Step 4 — Context assembly. Pack the winners into the prompt with structure the model can use: file path headers, line numbers, language fences, and often the surrounding scope (e.g. include the enclosing class signature even if only one method matched). You budget tokens deliberately — reserve room for the system prompt, the user's open file, tool definitions, and the model's output. You de-duplicate overlapping chunks and may expand a chunk to its full function. Ordering matters because of lost-in-the-middle: put the most relevant snippets at the edges.

Step 5 — Generate. The assembled prompt goes to the LLM, which now reasons over a tight, relevant slice of the codebase.

Engineering Challenges and Tradeoffs

  • Latency. The whole retrieval path (embed query → ANN → rerank → assemble) must finish in a few hundred milliseconds for chat, and even tighter for inline features. HNSW search is sub-millisecond; the embedding API round-trip and reranking dominate. You cache query embeddings and keep hot indexes in memory.
  • Cost. Embedding a large repo once can mean millions of chunks × an API call. Incremental Merkle sync keeps ongoing cost near-zero. Reranking adds per-query cost, so you cap candidate counts.
  • Index freshness vs. churn. During heavy editing, the index lags reality. You blend stale embeddings with live lexical search (ripgrep on the current file system) so exact matches are always current even if vectors are minutes old.
  • Chunk granularity tradeoff. Small chunks = precise matches but lost context; large chunks = more context but noisier vectors and wasted tokens. AST-aware variable-size chunks are the compromise.
  • Privacy. Source code is among a company's most sensitive assets. Sending it to a third-party embedding API is a non-starter for many enterprises. This shapes the entire architecture (below).
  • Scale. Monorepos with 10M+ lines, thousands of contributors, and constant commits stress both index size (hundreds of GB of vectors) and sync throughput. Server-side, multi-tenant indexing must isolate customers and handle branch divergence.

The Privacy Architecture

The interesting trick, publicly described by Cursor: they embed code server-side for speed and shared infrastructure, but they do not store your source code at rest. Instead they store:

  • the embedding vectors (which are lossy and hard — though not impossible — to invert back to source), and
  • obfuscated/relative file paths and line ranges rather than readable absolute paths.

At query time the client sends the query, the server returns matching chunk identifiers (path + line range), and the client reads the actual file contents locally to assemble the final context. So the plaintext lives on your machine; the cloud holds vectors and pointers. This is a deliberate balance between "fully local" (private but slower, no shared compute) and "upload everything" (fast but unacceptable to enterprises).

The alternative is fully local embedding (run a small embedding model on-device, keep the vector DB on disk). Continue, some Aider setups, and JetBrains' local features favor this — maximal privacy, zero data egress, at the cost of slower indexing and weaker models on a laptop CPU/GPU.

Concrete Technologies and Numbers That Matter

  • Context windows: 128K (GPT-4o), 200K (Claude), up to 1M+ (Gemini 2.5). A 1M-line repo ≈ 10–15M tokens — still doesn't fit.
  • Chunk sizes: typically 200–800 tokens, 10–20% overlap for fixed windows.
  • Embedding dims: 256–3072; bigger = more expressive but more storage and slower search.
  • Parser: Tree-sitter, ~40+ language grammars, incremental (re-parses only edited regions in microseconds-to-milliseconds).
  • ANN: HNSW, ~O(log N), 95–99% recall; tunable via M (graph degree) and efSearch (search breadth).
  • Fusion: Reciprocal Rank Fusion, score = Σ 1/(k + rank), k≈60.
  • Sync: Merkle tree diff — O(changed files), not O(repo).
  • Retrieve→rerank funnel: ANN top-100 → cross-encoder → top-10.
  • Tooling: Tree-sitter, FAISS/Qdrant/Pinecone/pgvector/LanceDB, BM25 (Lucene/Tantivy), ripgrep, Cohere/Voyage rerankers.

How Leading Products Actually Implement It

  • Cursor: The reference implementation of "RAG for code." Server-side embeddings, Merkle-tree sync, stores vectors + obfuscated paths (not source), client-side context assembly. Hybrid retrieval and a codebase index you can see building in the UI. Increasingly blends this with agentic search.
  • GitHub Copilot: For chat/agent it uses a mix. Historically inline completions relied on local context heuristics (open files, neighboring tabs) rather than a vector index. Copilot Chat/Enterprise added GitHub Code Search integration — GitHub's own scalable index over the repo — plus embeddings, so retrieval leans on GitHub's existing infrastructure rather than a local vector DB.
  • VS Code (Copilot-based): The @workspace participant builds a workspace index; commonly implemented as local embeddings for smaller repos and remote GitHub code-search-backed retrieval for larger ones, plus AST/symbol info from the language server.
  • Zed: Has shipped semantic/embedding-based search alongside fast native lexical search; emphasizes speed and a tight local-first feel. Leans heavily on Tree-sitter (which Zed's team are core contributors to) for syntax-aware operations.
  • JetBrains (AI Assistant / Junie): Leverages the IDE's deep static analysis and PSI (Program Structure Interface) — full symbol graphs, type info, find-usages — which is a structured alternative/complement to embeddings. Local indexing fits their privacy-conscious enterprise base.
  • Sourcegraph (Cody): Comes from a code-search heritage. Strong on precise structural/lexical search and the SCIP/LSIF code-graph (cross-repo go-to-definition, references). Cody combines this graph + embeddings + keyword search; well-suited to giant multi-repo enterprises.
  • Continue (open source): Configurable, local-first. Bundles a local vector index (often LanceDB/SQLite) with pluggable embedding providers; you choose local vs. API models. Good window into how the pipeline actually works.
  • Aider (open source, CLI): Notably avoids a vector index. It builds a repo map — a Tree-sitter-derived, ranked outline of files, symbols, and signatures (ranked with a PageRank-style graph) — and feeds that map plus files you explicitly add. A great example of "structure over embeddings."
  • Claude Code (Anthropic CLI): The flagship of the agentic-search-instead-of-index approach. No precomputed embedding index by default; the agent uses tools — grep/ripgrep, glob, file read, and shell — to iteratively explore the repo the way a human would. Trades upfront indexing cost for flexible, always-fresh, on-demand search.
  • Windsurf (Codeium): Built around "Cascade" with a retrieval engine (marketed as M-Query/Riptide) over an indexed codebase; combines embeddings-based retrieval with AST awareness, emphasizing whole-codebase context for its agent.

The key divergence: precomputed vector index (Cursor, Windsurf, Copilot Enterprise, Continue) vs. structural maps / code graphs (Aider, Sourcegraph, JetBrains) vs. agentic on-demand search (Claude Code, and increasingly everyone's agent mode). Most mature products now do a hybrid of all three.

The newest trend questions whether you need a vector index at all. With cheaper, faster, smarter models and large context windows, you can hand the model tools (grep, find, read_file, list_dir) and let it search iteratively: it greps for a symbol, reads the hits, follows imports, greps again — converging on the right files like a developer. Advantages: always fresh (no stale index), no embedding infra, no privacy headache from uploading vectors, and the model's reasoning guides the search. Disadvantages: more LLM round-trips (latency, token cost) and the agent can get lost. Reality in 2025–2026: a hybrid — embeddings/structure for a fast first guess at "where to look," then agentic grep/read to verify and expand. Claude Code popularized the pure-agentic end; Cursor and Windsurf blend index + agent.

Failure Modes and Mitigations

  • Stale index after edits. Mitigation: Merkle sync on save + always layer live ripgrep over current files so exact matches are never stale.
  • Bad chunking splits a function. Mitigation: AST/Tree-sitter chunking on syntactic boundaries; expand a matched chunk to its full enclosing scope before sending.
  • Embedding misses exact identifiers/error strings. Mitigation: hybrid retrieval — BM25/grep catches what dense vectors miss; fuse with RRF.
  • Lost in the middle / context dilution. Mitigation: rerank to a small top-k, order best chunks at the edges, keep the prompt tight rather than maximally full.
  • Retrieval returns plausible-but-wrong code (semantic false positives). Mitigation: cross-encoder reranking, and let the agent verify by reading/running before trusting.
  • Privacy leakage. Mitigation: honor .gitignore/ignore files, store vectors + obfuscated paths not source, offer local-only embedding and self-hosted/enterprise indexing, exclude secrets and .env.
  • Index build cost/time on huge monorepos. Mitigation: batch embeddings, incremental Merkle indexing, quantize vectors (PQ), shard per repo/branch.
  • Multi-repo / cross-service questions. Mitigation: code graph (SCIP/LSIF, Sourcegraph-style) for cross-repo references that embeddings alone can't link.
  • Wrong-branch context. Mitigation: key the index by branch/commit, or fall back to live file reads which always reflect the working tree.

Interview Talking Points

  • Retrieval exists because repos are tens of millions of tokens — context limits, per-token cost, and "lost in the middle" quality decay make "paste the whole repo" impossible.
  • Index build = walk files (honor .gitignore) → chunk (AST/Tree-sitter beats fixed-window) → embed with a code-tuned model → store in an ANN index (HNSW).
  • Merkle-tree sync re-embeds only changed files — same trick as Git/Dropbox.
  • Retrieval is hybrid: dense embeddings (semantic) + sparse BM25/ripgrep (exact), fused with Reciprocal Rank Fusion, then a cross-encoder reranker narrows top-100 → top-10. "Retrieve then rerank."
  • Cursor's privacy model: embed server-side but store only vectors + obfuscated paths, assemble plaintext context client-side.
  • Products diverge three ways: vector index (Cursor, Windsurf), structural/code-graph (Aider repo map, Sourcegraph SCIP, JetBrains PSI), and agentic grep/read (Claude Code). Modern systems blend them.
  • The frontier shift: with big context windows and tool use, let the agent search iteratively instead of (or alongside) a precomputed index — always fresh, no privacy headache, but more round-trips.

Likely Interview Q&A

Q1. Why not just put the whole codebase in the prompt now that context windows are 1M tokens? Three reasons. (1) Scale: a real monorepo is 10M+ tokens, still bigger than any window. (2) Cost: you pay per input token on every turn, so re-sending millions of tokens repeatedly is prohibitive. (3) Quality and latency: models exhibit "lost in the middle," attending poorly to the center of huge contexts, and time-to-first-token grows with input length — so 8K tokens of exactly right code beats 200K tokens of mostly-irrelevant code on both speed and accuracy.

Q2. Fixed-window vs. AST-aware chunking — which and why? AST-aware (Tree-sitter) chunking, in general. Fixed windows are simple and language-agnostic but slice through functions, separating a signature from its body and producing semantically broken vectors. AST chunking cuts on syntactic boundaries — functions, classes, blocks — so each chunk is a coherent, self-contained unit, and you can attach symbol/line metadata. You fall back to splitting oversized functions and packing tiny siblings. The cost is needing a parser per language, which Tree-sitter solves with 40+ grammars.

Q3. Explain hybrid retrieval and why you need both halves. Dense embedding search finds code that means the same thing even with different wording — great for conceptual queries. But embeddings are weak on rare tokens, exact identifiers, and error strings. Sparse lexical search (BM25 or literal ripgrep) nails those exact matches. Running both and fusing the rankings (Reciprocal Rank Fusion) covers each method's blind spot. Then a cross-encoder reranker re-scores the combined candidates jointly for final precision.

Q4. How does incremental re-indexing work without re-embedding everything? Build a Merkle tree over the file system: hash each file, then hash hashes up the directory tree to a root. To detect changes, compare local vs. indexed Merkle roots; differing hashes propagate up only along paths containing changed files. So you re-chunk and re-embed just the changed files — O(changes), not O(repo). Same mechanism Git and Dropbox use. Cursor has publicly described this.

Q5. How do you handle the privacy concern of indexing proprietary code? Several layers. Honor .gitignore and ignore files, and exclude secrets/.env/binaries. For cloud indexing, follow Cursor's model: embed server-side for speed but store only the vectors and obfuscated relative paths, never plaintext source at rest; at query time return chunk identifiers and let the client read the real files locally to build the prompt. For maximum privacy offer fully local embedding with an on-device model and local vector DB, plus self-hosted/enterprise deployments. Embeddings are lossy and hard to invert, but treat them as sensitive anyway.

Q6. What's the modern alternative to a precomputed vector index, and what's the tradeoff? Agentic search: give the model tools (grep/ripgrep, glob, read_file) and let it explore iteratively — grep a symbol, read hits, follow imports, repeat — like a human developer. Claude Code popularized this. Upside: always fresh (no stale index), no embedding/vector infrastructure, no uploaded-vector privacy problem, and the model's reasoning steers the search. Downside: more LLM round-trips means higher latency and token cost, and the agent can wander. Most products now hybridize: a fast index/structural map to guess where to look, then agentic grep/read to verify and expand.

Q7 (system design). Design codebase retrieval for a 5,000-developer company with a 20M-line monorepo, hundreds of commits/day, strict data-residency rules. I'd separate concerns. Storage/residency: self-hosted or VPC-deployed indexing so no code leaves their cloud; per-team access controls mirroring repo permissions. Index: server-side embeddings with a code-tuned model into a sharded ANN store (Qdrant/Milvus with HNSW, PQ-quantized vectors to fit hundreds of GB). Key the index by commit/branch so branch divergence and stale-branch context are handled. Sync: Merkle-tree incremental indexing triggered by CI/post-commit hooks, so hundreds of daily commits only re-embed touched files; a background reconciler repairs drift. Retrieval: hybrid — HNSW dense + a Lucene/Tantivy BM25 index + live ripgrep on the checked-out tree for freshness — fused with RRF, then a cross-encoder rerank to top-k. Cross-repo/structure: add a SCIP/LSIF code graph (Sourcegraph-style) so cross-service references resolve, which embeddings alone can't do. Latency: keep hot indexes in memory, cache query embeddings, cap rerank candidates. Scale-out: multi-tenant isolation, per-repo shards, and rate-limited embedding workers. The design balances freshness (Merkle + live grep), precision (hybrid + rerank), residency (self-host), and cost (quantization + incremental sync).

Q8 (tradeoff). Your retrieval keeps returning plausible but wrong snippets and users lose trust. How do you diagnose and fix it? First, build an eval set of real queries with known-correct files and measure recall@k and precision@k to localize the failure: is the right chunk not in the candidate set (retrieval recall problem) or present but ranked low (ranking problem)? Recall problems: check chunking (functions split?), add the lexical/grep arm if exact identifiers are missed, widen ANN efSearch/top-k, consider query rewriting/HyDE. Ranking problems: add or upgrade the cross-encoder reranker, since bi-encoder cosine similarity is coarse. Context problems: expand matched chunks to full enclosing scope, de-dup, and reorder to fight lost-in-the-middle. As a safety net, shift toward agentic verification: let the model read and, where possible, run/lint candidate code before relying on it, and cite file/line so users can spot-check. Trust often recovers more from visible citations + verification than from a marginally better embedding model.

Q9. Why use a two-stage retrieve-then-rerank funnel instead of one strong model over everything? Because the accurate model is the slow one. Cross-encoders score a (query, chunk) pair jointly and are far more precise, but they must run per candidate — too expensive over millions of chunks. Bi-encoder embeddings precompute one vector per chunk, so ANN search over the whole index is sub-millisecond but coarser. The funnel uses cheap ANN to cut millions → ~100 candidates, then spends the expensive cross-encoder only on those to pick the final ~10. You get near-cross-encoder precision at near-ANN cost — a classic accuracy/throughput tradeoff resolved by cascading.

Built from Markdown · 22 pages · Read it aloud and burn it in.