Dice-coefficient fuzzy match for failed SEARCH/REPLACE: turn a useless error into autocorrect
Agentic edit loops bleed on whitespace drift and one-character mismatches in SEARCH/REPLACE blocks. Replace 'SEARCH text not found' with the top-3 similar candidates scored by Dice's coefficient — the LLM autocorrects on the next iteration at the cost of one O(n*m) scan.
AppX team ·
Every agentic edit loop in production today — aider, Cline, Cursor's apply mode, Claude Code's surgical edits — runs on a SEARCH/REPLACE protocol. The LLM emits a block of text it expects to find in a file (SEARCH), and a block of text to substitute (REPLACE). The runner does the actual byte-level edit.
It's a beautiful protocol. It's also the source of one of the most common wasted-turn failures in agent loops: the SEARCH text doesn't match, the runner returns SEARCH text not found, and the LLM retries with a guess that's structurally identical to the first one. Architect turn, gone. Tokens, gone. The user watches a spinner.
The fix is embarrassingly cheap, and once you see it you cannot un-see it: when SEARCH fails, don't return not found. Return the top-3 fuzzy matches in the file with a similarity score and line range. The LLM treats those as feedback and almost always corrects on the next iteration. The cost is a single O(n·m) scan — milliseconds — instead of another full architect turn.
The protocol (SEARCH/REPLACE in 30 seconds)
The LLM emits an edit as two fenced blocks:
<<<<<<< SEARCH
const timeout = 5000;
=======
const timeout = 30000;
>>>>>>> REPLACE
The runner reads the target file, finds the SEARCH text by exact substring match, and replaces it with REPLACE. Surgical, no full-file rewrites, no diff parsing, no AST. It works because LLMs are very good at quoting the file they just read.
It works until something between the read and the write perturbs the file by a single character.
The failure mode
The class of failure isn't subtle once you start logging it. In rough order of frequency:
- Whitespace drift. The LLM normalizes indentation in its quote. Two spaces become four, or a tab becomes spaces. Byte mismatch.
- A trailing comma in a tuple or argument list that the LLM helpfully drops because it "looked cleaner."
- An extra blank line between a function and a comment, or a missing one.
- A formatter ran between turns. Prettier or ESLint --fix touched the file on save. The LLM's SEARCH is now stale by 50ms.
- Smart quotes vs straight quotes, or a stray Unicode space pasted from somewhere upstream.
In every one of these cases the LLM's SEARCH is semantically correct. It's pointing at the right region. It's off by one character, or one whitespace run, or one trailing comma. The user knows exactly what edit was meant. The runner does too, if you ask it the right question.
SEARCH text not found is the wrong question. It's a binary answer to a continuous problem.
Dice's coefficient (the math, briefly)
Dice's coefficient measures how similar two strings are by their character bigrams:
dice(A, B) = 2 * |bigrams(A) ∩ bigrams(B)|
─────────────────────────────────
|bigrams(A)| + |bigrams(B)|
Bigrams are overlapping 2-character windows. "hello" produces ["he","el","ll","lo"]. The intersection is multiset intersection — if a bigram appears twice in both strings, it counts twice.
Output is 0.0 (no overlap) to 1.0 (identical). No training, no model call, no embeddings. Five lines of code:
function dice(a: string, b: string): number {
if (a === b) return 1;
if (a.length < 2 || b.length < 2) return 0;
const bigrams = (s: string) => {
const m = new Map<string, number>();
for (let i = 0; i < s.length - 1; i++) {
const g = s.slice(i, i + 2);
m.set(g, (m.get(g) ?? 0) + 1);
}
return m;
};
const A = bigrams(a), B = bigrams(b);
let inter = 0, sizeA = 0, sizeB = 0;
for (const [g, n] of A) { sizeA += n; if (B.has(g)) inter += Math.min(n, B.get(g)!); }
for (const [, n] of B) sizeB += n;
return (2 * inter) / (sizeA + sizeB);
}
You can swap it for Levenshtein, Jaccard, or token-set ratio. Bigram Dice is the sweet spot for code: cheap, locality-aware, robust to small reorderings.
A 3-tier matching strategy
flowchart TD
S["SEARCH block"] --> T1{"Exact match?"}
T1 -->|yes| OK["Apply edit"]
T1 -->|no| T2{"Whitespace-normalized match?"}
T2 -->|yes| OK
T2 -->|no| T3{"Dice similarity ≥ threshold?"}
T3 -->|yes| OK
T3 -->|no| ERR["Return the closest near-miss<br/>in the error → LLM autocorrects"]
style OK fill:#13241a,stroke:#2ecc71,color:#d7f7e3
style ERR fill:#241f13,stroke:#e0a23a,color:#f7e8cf
Fuzzy is the fallback, not the default. Run it only when the cheap paths fail:
function findMatch(file: string, search: string) {
// Tier 1: exact substring. Cheap. ~95% of edits land here.
if (file.includes(search)) return { tier: 'exact', range: locate(file, search) };
// Tier 2: whitespace-normalized. Catches indent drift + formatter runs.
const norm = (s: string) => s.replace(/\s+/g, ' ').trim();
const idx = norm(file).indexOf(norm(search));
if (idx >= 0) return { tier: 'normalized', range: mapBackToOriginal(file, idx) };
// Tier 3: dice over sliding windows of similar length. Final fallback.
const candidates = slidingWindows(file, search.length);
const scored = candidates
.map(c => ({ ...c, score: dice(c.text, search) }))
.sort((a, b) => b.score - a.score)
.slice(0, 3);
return { tier: 'fuzzy', candidates: scored };
}
Tier 1 handles the vast majority. Tier 2 handles formatters. Tier 3 only runs when both fail — which means you pay the O(n·m) scan only on the turns that were going to fail anyway.
The error-message shape that makes the LLM autocorrect
This is the entire trick. The shape of the error becomes inline context for the LLM's next attempt.
Before — useless:
ERROR: SEARCH text not found in src/auth/service.ts
After — useful:
ERROR: SEARCH text not found in src/auth/service.ts.
Closest matches (fuzzy, ranked by similarity):
[0.92] lines 142-148:
if (user.tokenExpiresAt < Date.now()) {
await this.refreshToken(user);
return user;
}
[0.78] lines 201-207:
if (user.tokenExpiresAt <= Date.now() - GRACE_MS) {
await this.refreshToken(user, { force: true });
return user;
}
[0.61] lines 88-93:
if (session.expiresAt < Date.now()) {
await this.invalidate(session);
}
Re-emit SEARCH against the actual file content above.
The LLM reads its own near-miss back, sees the byte that drifted (a < vs <=, a missing space, a renamed variable), and corrects. In practice the score-0.85+ candidate is the right one nearly every time.
This works because LLMs are great at quoting and bad at guessing. Give them the real text and they will quote it.
Cost
Tier 3 on a 500-line file is ~3-5ms in any reasonable runtime. Compare that to one wasted architect turn: a full prompt round-trip on a frontier model, several thousand tokens, two-to-five seconds of latency, real money. The break-even is one prevented retry per thousand calls. The actual hit rate is much higher than that.
Worth considering as variants:
- LLM-supplied line anchors. Have the SEARCH block come with an optional
lineRange: "40-50"hint. Only fuzzy-match within ±10 lines of that band. Faster and more precise. - Token-based similarity for code-heavy SEARCH blocks where identifier overlap matters more than character overlap.
- Levenshtein for short SEARCH blocks (under ~20 chars) where bigrams are too coarse.
Takeaways
SEARCH text not foundis a binary answer to a continuous problem. Don't ship it.- Run tiers in order of cost: exact → whitespace-normalized → fuzzy. Most edits never leave tier 1.
- Dice's coefficient is five lines, no dependencies, no model call. It buys you a tier-3 fallback for free.
- The point isn't the algorithm. The point is the error message shape. Return ranked candidates with scores and line ranges, and the LLM autocorrects.
- One prevented architect retry per thousand calls pays for the entire scan budget. The real rate is much higher.