Lexical search vs embeddings for code

Day 23: Lexical Search vs Embeddings for Code: Why Grep Often Wins

Your coding agent just edited the wrong file, and the model probably isn't to blame. More often, retrieval handed it context that looked right and wasn't. In my experience that's one of the most common ways agentic coding breaks in practice. Learn when to fetch code by exact name and when to fetch it by meaning, and you can fix a lot of wrong-file edits without touching the model.

1. The hook: the calculateInvoiceTotal incident

This one is a composite, but if you run coding agents you've probably seen it. The ticket reads: "Invoice totals are wrong when a discount and tax both apply. Fix calculateInvoiceTotal." The agent sits on top of a vector store built over the repo. It embeds the ticket and pulls the top 5 chunks.

• ▹Hit 1: `legacy/billing/invoice_v1.ts`, which has a `calculateInvoiceTotal`. It's deprecated and nothing calls it any more. But it's short and clean, so its embedding lands right next to the query.
• ▹Hit 2: `billing/__tests__/invoiceTotal.test.ts`. A test file that says 'invoice', 'total', 'discount' and 'tax' again and again.
• ▹Hit 3: `quotes/calculateQuoteTotal.ts`, a copy-paste sibling with almost the same body.
• ▹Missing from the top 5: `billing/invoice/totals.ts`, the live implementation. It's long, split across three chunks, and its discount logic sits in an imported helper.

The agent patches hit 1. Its tests pass, because nothing calls that code. Production doesn't change. Then a human fixes it in two minutes: grep the exact name, see that only one definition is imported anywhere, follow that import to the helper. The bug is in `applyDiscountBeforeTax`.

$ rg -n "calculateInvoiceTotal" --type ts
legacy/billing/invoice_v1.ts:12:export function calculateInvoiceTotal(...)   # defined, zero importers
billing/invoice/totals.ts:40:export function calculateInvoiceTotal(...)      # defined
billing/api/invoices.controller.ts:8:import { calculateInvoiceTotal } from '../invoice/totals'
billing/jobs/monthlyRun.ts:5:import { calculateInvoiceTotal } from '../invoice/totals'

# One hop: open totals.ts, follow its import
$ rg -n "applyDiscountBeforeTax" billing/
billing/invoice/discounts.ts:22:export function applyDiscountBeforeTax(...)   # <- actual bug

Which leaves an uncomfortable question. If one grep and one import hop beat our carefully tuned semantic retrieval, why did we put a vector store between the agent and the code at all?

2. Where Day 23 sits in the arc

Days 15–22 built semantic, hybrid and multi-hop retrieval, and almost every example was prose: docs, tickets, knowledge bases. Today we check whether those assumptions survive contact with source code. I'll assume you already know how embeddings and BM25 work.

3. Why code is different: meaning vs reference

In prose, two passages that say the same thing are interchangeable. Ask about refund policy and any paragraph explaining refund policy will do. Code doesn't work that way. What matters is which exact symbol gets referenced. Two near-identical functions are not substitutes: only one of them sits on the execution path your bug actually runs through.

So every piece of code has two neighbourhoods:

• ▹Embedding neighbours: code that looks similar. Clones, tests, deprecated versions, siblings in other modules, docs that describe it.
• ▹Graph neighbours: code that's causally connected. Its callers, its callees, the types it takes and returns, the module that imports it.

Hold onto this for the rest of the lesson. 'Similar' means 'could be confused with'. 'Causally connected' means 'change one and the other is affected'. A correct edit almost always needs the second kind. Embedding retrieval is built to return the first.

4. What the evidence says

The evidence here is decent, but it doesn't settle the question. Here's a quick survey, with the uncertainty left in:

• ▹Agentless (Xia et al., 2024) localises bugs hierarchically: a repo file tree to pick files, then class and function skeletons to pick elements, then exact edit locations. It got competitive results on SWE-bench Lite with no free-roaming agent at all. The localisation is structural and driven by names. Some configurations did add an embedding-retrieval step, but as a supporting signal, not the backbone.
• ▹SWE-agent (Yang et al., 2024) made the case that the agent-computer interface matters. Plain find_file, search_dir and search_file commands plus a file viewer gave strong results. Retrieval there is something the agent does step by step, not one precomputed lookup.
• ▹Claude Code's team has said publicly (Boris Cherny, in talks and interviews) that early versions tried a local vector database, then switched to agentic search with grep, glob and read. The reasons given: it worked better, and it avoided index staleness and security headaches. Sourcegraph has described moving Cody's enterprise context retrieval away from embeddings towards keyword search and other signals, citing scale and freshness. Both are practitioner reports, not controlled studies, so give them that much weight and no more.
• ▹Code-RAG benchmarks are mixed. CodeRAG-Bench (Wang et al., 2024) compared BM25 against several dense retrievers across code tasks. Larger dense retrievers often came out ahead, but BM25 held its own on some tasks, repository-level ones included. Which source helped (repo code, library docs, tutorials) also varied by task.
• ▹A benchmark caution. The DeepCodeSeek authors (arXiv 2509.25716) flag 'API leaks' in existing code-to-code retrieval benchmarks. My reading: the target API is already visible in the query context, so older scores may overstate retrieval quality, since the exact-name shortcut is baked into the test. Check the paper for their precise definition.
• ▹Exact-name tracing works, up to a point. A 2016 call-graph study (arXiv 1610.04594) built cross-codebase call graphs purely by matching class, method and property signatures and following those matches recursively. Against manual search it reached 78.26% accuracy. That's fair support for 'code is a graph of names'. It also means roughly a fifth of results still didn't match.

Dense retrieval does win in some cases, and you should know which ones:

• ▹When the identifier doesn't exist yet. DeepCodeSeek (arXiv 2509.25716) targets enterprise code (ServiceNow Script Includes) where the intended API usage is unclear, so there's often nothing to grep for. Its approach reached 87.86% top-40 retrieval accuracy. Look at how it got there, though: index expansion to predict the required APIs, plus a compact 0.6B reranker that beat a much larger 8B model at 2.5x lower latency. That's not generic 'embed and take top-k'.
• ▹When the knowledge isn't in the repo. EVOR (arXiv 2402.12317) goes after frequently updated libraries and long-tail languages, and reports 2–4x execution accuracy over baselines like Reflexion and DocPrompting. The gains came from evolving the query and the knowledge base together and pulling from diverse sources. That's iterative retrieval, not one-shot similarity. The abstract doesn't say whether the retriever is dense or lexical.
• ▹Vendor reports. Cursor has published claims that semantic codebase search improves its agent's results alongside grep. Yes, they have an index to sell. They also have a lot of real usage, and they frame semantic search as a complement to grep, not a replacement.

My honest reading: for finding where to edit in a repo you can access, lexical search plus reference-following is the strong default. Learned retrieval wins when the query has no anchor name, or when the knowledge lives outside the repo.

5. Three ways embeddings fail on code

Failure 1: near-duplicates crowd out the live code. Codebases are full of near-copies: v1 and v2 modules, vendored code, generated clients, test fixtures, code that agents copy-pasted last quarter. Cosine similarity can't tell you which copy is live. Short, clean, deprecated code can outscore the long live version, because the live one has soaked up years of edge-case fixes.

Query: "retry logic for webhook delivery"   (illustrative scores)
0.91  legacy/webhooks/retry.py        # removed from routing 8 months ago
0.89  tests/fixtures/fake_retry.py    # test double
0.87  vendor/somesdk/backoff.py       # third-party, not yours
0.81  webhooks/delivery/dispatcher.py # live: retry is 30 lines inside a 400-line class

Failure 2: chunk boundaries cut a function off from its context. The chunking from Day 16 splits files into windows. The function body lands in one chunk. Its imports, its return type and the constants it reads land in others. The agent gets a body that mentions `applyDiscountBeforeTax` and `TaxPolicy`, without the definitions or even the import lines that say where they come from. So the model fills the gap with a guess about what those names do.

// chunk 7 of totals.ts (retrieved)
export function calculateInvoiceTotal(inv: Invoice): InvoiceTotal {
  const sub = applyDiscountBeforeTax(inv.lines, inv.discount); // where is this from?
  return withTax(sub, TaxPolicy.forRegion(inv.region));        // what is TaxPolicy?
}
// chunk 1 (NOT retrieved) held the imports that answer both questions

Failure 3: staleness. An embedding index is a snapshot. The agent works on a live branch, which might hold its own edits from five minutes ago, the user's uncommitted changes, or a rename from this morning. The index happily returns code that has since been moved, renamed or deleted. SWE-Touch (arXiv 2608.02499) shows agents already struggle here without any index: when users inject conflicting edits into task-relevant code mid-task, resolve rates on SWE-bench Verified drop by 7.7 percentage points on average, and trajectory analysis tied the failures to limited awareness of the changing workspace, including not re-inspecting the repo enough. That paper didn't test retrieval methods. My inference is that a cached embedding index builds the same stale picture into your system, and it's expensive to refresh. Grep reads the working tree every time it runs.

6. Why agents with grep behave like senior engineers

Watch a senior engineer find their way around code they don't know. They don't ask 'what looks like this?' They search the exact name, open the file, read the imports, jump to a definition, find the callers, and go again. Each step uses a fact from the previous one to sharpen the next query.

This is the multi-hop retrieval from Days 21–22 with one key difference: every hop follows an exact reference instead of a fuzzy similarity jump. Each hop is either right or wrong, the agent can check which, and it reflects the current code. The agent also decides how far to go. It stops when it has the causal chain, not when it has filled k slots. That's why tool-using agents spend more tokens on exploration: they're paying context-window cost to buy precision. In my experience the trade is usually worth it. A wrong-file edit costs far more than a few extra reads.

This has a practical consequence for tool design. Give the agent tools that return exact, current, structured answers: `rg -n`, glob, read with line ranges, and, where you have one, 'go to definition' or 'find references' from a language server. A tool that returns 'the 5 chunks most like your question' is less useful for this job.

7. Where vectors still earn their keep

• ▹The query has no identifier yet. 'Where do we handle refund retries?' gives grep nothing to match, because the code might say `chargeback`, `reversal` or `compensate`. Semantic search over code and comments is a sensible way to get a first foothold.
• ▹Onboarding to an unfamiliar repo. Neither you nor the agent knows the vocabulary yet. A semantic search tells you what this codebase calls things.
• ▹Comments, docs, ADRs and READMEs. These are prose, so Days 15–22 apply directly. The 2508.08322 multi-agent workflow uses Elicit for literature retrieval and NotebookLM for document synthesis, and puts a separate Intent Translator in front of fuzzy requests before any coding agent touches code. One caveat: comments vary a lot in how much they help you understand the code. Classifying them as useful or not is a shared task in its own right (arXiv 2310.10275). So 'retrieved by comment meaning' can still hand you plausible but useless context.
• ▹Cross-language or renamed concepts. Think of a Python service and a Go service implementing the same idea under different names, or a concept that got renamed while the old names linger here and there.

The pattern: semantic search to find an entry point, then lexical search and reference-following for everything after. Once retrieval has given you a real identifier, stop asking 'what's similar?' and start asking 'what references this?'

Step 1 (semantic, once):  "refund retries" -> payments/compensation/ReversalScheduler.kt
Step 2 (lexical, loop):   rg ReversalScheduler -> callers, config, tests
                           open -> follow imports -> rg next name -> ...
Never go back to vectors for a name you already have.

8. Run it yourself: a one-afternoon experiment

Don't take this lesson's word for it, or any vendor's. Test it on your own repo.

• ▹Ground truth: pick 20 real closed tickets. Mix bug fixes with small features, and include some that name identifiers and some written in plain English. For each one, record the files the merged PR actually changed, ignoring lockfiles and snapshots. Check out the parent commit, not HEAD, so the agent can't see the fix.
• ▹Setup A, vector-only: the agent's only search tool is top-k over your embedding index, plus read.
• ▹Setup B, grep-only: rg, glob and read. No index.
• ▹Setup C, semantic entry then grep: one semantic search call allowed at the start, then only rg, glob and read.
• ▹Same model, same prompt, same token budget. Run each ticket at least twice per setup, because agents are noisy.

{
  "ticket": "BILL-412",
  "setup": "C",
  "run": 2,
  "ground_truth_files": ["billing/invoice/discounts.ts"],
  "files_opened": ["billing/invoice/totals.ts", "billing/invoice/discounts.ts"],
  "first_hit_step": 3,
  "hops_to_target": 2,
  "files_edited": ["billing/invoice/discounts.ts"],
  "wrong_file_edits": 0,
  "localisation_hit": true,
  "tests_pass": true,
  "tokens": 41200
}

How to read the results without fooling yourself:

• ▹Primary metric: localisation hit rate. Did the agent edit at least one ground-truth file? How many files did it edit outside the ground truth? Wrong-file edits are the expensive failure, so count them separately.
• ▹Split by query type. If 15 of your 20 tickets already name the function, grep will win easily and you've learned less than you think. That's the API-leak problem again, this time in your own test set.
• ▹Check the index was fresh. If you built it last week, Setup A is partly measuring staleness. That's realistic, but say so in the write-up.
• ▹Twenty tickets give you a direction, not statistical significance. A 3-ticket gap is noise. Look for big, consistent differences, and read 5 failing transcripts per setup. The transcripts usually teach you more than the numbers do.

9. The decision rule

| Query type                          | Repo state   | Recommended retrieval                                |
|-------------------------------------|--------------|------------------------------------------------------|
| Has identifier (name, path, error)  | Fast-moving  | Lexical + reference-following. No index.             |
| Has identifier                      | Stable       | Lexical + reference-following (index adds little)    |
| Natural language only               | Fast-moving  | Semantic entry (fresh-ish index or docs) -> lexical  |
| Natural language only               | Stable       | Semantic entry -> lexical                            |
| Cross-cutting concept / renamed /   | Either       | Hybrid (BM25 + dense) with a reranker for entry,     |
|   cross-language / docs & ADRs      |              |   then lexical for every hop after                   |

On cost: grep is always current, needs no infrastructure, and with ripgrep it's fast on most repos. An embedding index needs chunking, embedding calls, storage, and a way to re-index on every commit or branch. Even refreshed incrementally, it lags the uncommitted working tree the agent is actually editing. Put a fleet of agents on many branches and you either keep an index per branch or accept that agents will retrieve code that doesn't exist on their branch. Budget for that before you build the index, not after.

10. Carry into Day 24

If retrieval over code is really a walk over a graph of exact names, today's walk still starts in the dark. The agent greps, guesses, and feels its way forward one hop at a time. A senior engineer doesn't start like that. They already carry some map of the system in their head. So the next question is what map the agent should start from, and who builds and maintains it. That's Day 24.

Extend your knowledge

• ▹Read the Agentless paper (Xia et al., 2024, 'Agentless: Demystifying LLM-based Software Engineering Agents'). Focus on the hierarchical localisation stage: file, then element, then line.
• ▹Read SWE-agent (Yang et al., 2024) on agent-computer interfaces, and compare its search commands with the tools your own agent exposes.
• ▹Skim CodeRAG-Bench (Wang et al., 2024) for the BM25 vs dense comparisons, and note which retrieval sources (repo code, library docs, tutorials) helped on which tasks.
• ▹Run the 20-ticket experiment from Section 8 on your main repo and keep the transcripts. You'll need them again on Day 24.