Two Identical Chunks Are Not Always Duplicates

A code-search engine does not return files. It returns chunks, and the caller sees a short ranked list of them. Anything below the cut might as well not exist, so a slot spent twice on the same content is a slot taken from a different answer.

The witness is a query for Lock against the source of uv. The answer is uv's Lock struct, the type that models a lockfile. The top three results were instead three chunks from uv's benchmark scripts, one each for uv, Poetry and PDM, and all three opened with the same sentence: Resolve a modified lockfile using pip-tools. A sentence about pip-tools sitting on the Poetry and PDM helpers reads as written once and pasted twice. It mentions lockfiles, so each copy scored well, and because the copies barely differ, they scored about the same. Three slots went to one piece of content, and the definition the query was about fell below them.

The fix was a second deduplication key. A key here is a value computed from each chunk; chunks that produce the same value become candidates for collapsing into one result. vectr already had an exact key, the chunk's normalized text, which collapses chunks that are byte-identical after normalization. The new key reads only a chunk's leading docstring: its first three lines, normalized, and at least 20 characters long so that a blank or one-word comment never counts. When candidates collapse, the best-ranked one stays visible as the representative.

Keyed on the docstring alone, the rule merged a trait declaration with its own implementation, and it merged distinct constructors that happened to share a copy-pasted one-line summary. Sharing a docstring only shows that two chunks share a header. So the key was hardened with two gates, and a candidate collapses only when both pass:

1. Structural. If both chunks carry a recorded node type and the types differ, never collapse. A trait is never a near-duplicate of an impl, whatever the threshold.
2. Content. The two whole chunks, normalized, must score at least 0.75 on the similarity ratio of Python's difflib.

The cost of comparing every pair

Each candidate under a key was compared against every representative already kept under that key. When nothing collapses (fifty chunks that share a license header but differ in their bodies, say) the list of representatives grows with every candidate, and the loop makes on the order of n² comparisons. The 1.10.0 changelog records 3.1 seconds for 60 candidates sharing one key and 35.0 seconds for 200. Those two sizes come from the pipeline: 60 is the most candidates that reach this step after reranking, and 200 the ceiling when the reranker is off.

Capping each candidate at the first three representatives brought the same cases to 0.30 and 1.07 seconds. The cap fails in only one direction. A candidate that would have matched a representative past the cap is never compared with it and stays as its own result, so the worst case is a wasted slot, never a hidden answer.

Collapse also runs before the list is cut to the requested size, so slots freed by a collapse are refilled from the next distinct candidates. A dedup pass that ran after the cut would hand back fewer results than asked for and say nothing about it, which is the failure described in Filtering After Top-k Is a Silent Bug in RAG. With both gates and the cap in place, the key shipped enabled.

A later change added a second key for the mirror-image case: two chunks with different docstrings over near-verbatim bodies, which the docstring key cannot see at all. That key, near_dup_body, compared whole chunks, so the differing docstrings sat inside the comparison and dragged the ratio under its threshold. Stripping the leading docstring before comparing moved the key's own test pair from 0.765 to 0.958.

The same change found a larger defect underneath. Every ratio in this part of vectr was computed with SequenceMatcher's default setting, autojunk=True. The Python 3.12 documentation states the rule:

"If an item's duplicates (after the first one) account for more than 1% of the sequence and the sequence is at least 200 items long, this item is marked as 'popular' and is treated as junk for the purpose of sequence matching."

The current documentation presents junk handling as a heuristic for speed and for diffs that read better to people, whose ideal targets are "uninteresting or common items, such as blank lines or whitespace." That reading fits a line-by-line diff, where each item is a whole line and a line repeated dozens of times is usually blank or a lone brace. vectr was feeding it characters.

Why varied code survives autojunk and repetitive code does not

Popular characters are not deleted from the strings. They are removed from the index that the matcher searches when it looks for the longest common run, so a popular character can never start a match. It can still be absorbed into one: once a match has started on a rarer character, the algorithm extends it outward through any equal neighbours, popular or not.

In varied code, rare characters are everywhere: a bracket, an underscore, a capital letter, a quote. Nearly every stretch of shared text contains one, a match starts there and grows across the popular characters around it, and the ratio comes out right. In repetitive code, a long stretch can consist of nothing but popular characters. Once the first difference ends a match, nothing in the rest of the text can start a new one, and every identical character after that point counts as unmatched.

The committed test fixture behind the first row of the table below makes this concrete. It is a three-line Rust function followed by the comment // implementation line repeated fifteen times, 392 characters in all, and its partner differs only in the first comment's last word (note for line). Twelve characters are popular, and they are exactly the characters of the repeated comment. The matcher finds one block, the 65 characters from the start of the function to the changed word. The 323 identical characters after that word, on both sides, go unmatched. The ratio is 2 × 65 / 784 = 0.166.

Body	Length	Default ratio	autojunk=False
Repetitive	392 chars	0.166	0.995
Varied	251 chars	0.996	0.996
Repetitive	150 chars	0.993	0.993

The distortion needs both conditions. Under 200 characters the heuristic never engages, and on varied code it changes nothing, which is why it went unnoticed. On long, repetitive code it reports two nearly identical bodies as barely similar at all.

The code autojunk distorts is the code dedup must not touch

Long, repetitive code is what templates produce: field accessors, dispatch handlers, parameterized tests, generated client methods. Call it templated code. It is also the code a near-duplicate rule must never collapse, because every instance is a distinct symbol with its own name. The metric was wrong in exactly the region where being wrong kept the system safe. It scored template instances as dissimilar, so they never reached 0.75, so they never collapsed.

The 0.75 threshold was chosen by measuring real pairs. Near-duplicates shaped like the uv witness scored about 0.85 to 0.89, and two constructors sharing only a boilerplate doc line about 0.53, so 0.75 sat with margin on both sides. A trait and its impl sharing a doc comment scored about 0.86, inside the duplicate range; that pair is why the node-type gate exists, since no cutoff on this ratio could keep it apart. All of these numbers were measured with the default autojunk in place.

Correcting the metric and keeping 0.75 collapses the fifty accessors into a single result. That was measured, and the fix was split accordingly. autojunk=False went in only where it changes no shipped behaviour: the near_dup_body key, which ships disabled, and that key's guard. The enabled docstring key keeps the wrong parameter on purpose, with the finding written as a comment at the call site. The correct change pairs the corrected metric with a threshold re-measured on real corpora, in one commit, or it does not happen.

A threshold is calibrated against a metric, including the metric's errors, so the two behave as one object. Fix the metric and the old number means something different; the pair has to be measured again together. The same thing happens whenever the model under a tuned constant changes. vectr shows a warning when no result looks like a confident match, triggered by a score floor that was tuned against one cross-encoder. The 1.12.0 changelog records that swapping in a different reranker left that constant stale.

For anyone running difflib over source text, the check is mechanical. Find every SequenceMatcher that leaves autojunk at its default and can see a second argument of 200 or more elements. For each threshold downstream of one, find the pairs it was tuned on, re-score them with the flag off, and move the flag and the threshold in the same change.

Budget for the flag, too, since the heuristic exists for speed. With popular characters left in the index, every space and every e in the second string is a position the matcher walks. Timed under Python 3.11 on one machine, a single ratio on the 664-character normalized accessor pair takes 0.76 ms with the default and 17.6 ms with autojunk=False; on a 2,685-character pair, 3.9 ms against 170 ms. The three-representative cap from Section 01 bounds how many comparisons run per candidate. The corrected metric still has to be costed against that budget before it ships on an enabled key, or compared over tokens or lines instead of characters, which shortens the sequences.

If templated code is the hazard, the obvious guard is to recognise it. Two bodies that are the same code with different values in the slots, accessor_0 in one and accessor_1 in the other, are instances of a template and should never collapse. The guard went through three versions.

Digits, then edit operations, then masking

The first version fired when most of the differing characters were digits. It caught accessor_0 against accessor_1 and missed get_name against get_email, which differ in letters and are just as distinct.

The next version walked the diff's edit operations and required every changed span, on both sides, to consist only of letters, digits and underscores. A pure insertion or deletion has an empty side, so it failed the test. That tied the guard's verdict to how the aligner happened to line the strings up. name against phone is four characters against five, the aligner has to insert something, and the rule rejected the very shape it was built to catch. On one fixture it flagged name/email and missed name/phone, name/address, email/phone, email/address and phone/address. name/email passed only because the aligner matched their shared a and paired the remaining letters as substitutions.

The shipped version drops alignment entirely:

SLOT = re.compile(r"[A-Za-z_][A-Za-z0-9_]*|\d+")   # identifier or bare number

def same_shape_different_slots(a, b):
    return a != b and SLOT.sub("\x00", a) == SLOT.sub("\x00", b)

Every identifier-like token and every bare number becomes one placeholder, and the masked forms are compared. No alignment is involved, so the length of a token cannot change the answer. Token-based clone detectors such as CCFinder make a similar move, replacing identifiers before they compare so that renamed copies still match.

The mask is coarse, and knowingly so. Keywords match the identifier pattern, so return x and yield x mask to the same thing, and so do two comments that differ by one word. Each of those errors labels a real difference as a template slot and keeps the two chunks apart, which for a guard whose only job is to prevent collapse is the cheap direction to be wrong in, for the same reason the comparison cap is.

Wired into the enabled key, the guard broke the case the key exists for

The masking guard works. It was then wired into the enabled docstring key, to protect that key the same way, and it broke the uv witness. The Poetry and PDM helpers differ in the function name and in the tool named inside the command. Masked, they are the same shape with different slots, exactly like the accessors. The guard shielded them from collapse, and the Lock definition was crowded out again.

The change was reverted. The case that must collapse and the case that must not are structurally identical, so no rule that reads the characters of the two bodies can separate them. Two tests are kept failing on purpose rather than deleted, marked xfail. Their fixtures differ only in a type name or only in a string literal, and they carry a shared docstring, so the enabled key collapses them on its own ratio gate and never consults the guard.

Where the three keys stand

Key	What it compares	Ships	Similarity gate	Templated guard
Exact	Whole chunk, normalized	Enabled	Byte equality	Not needed
Docstring	First three docstring lines as the key, then the whole normalized chunk	Enabled	Ratio ≥ 0.75 with default autojunk, kept on purpose; node types must match; at most 3 representatives compared	Tried and reverted
near_dup_body	Body with the leading docstring stripped	Disabled	Ratio ≥ 0.95 with autojunk=False; node types must match	Masking guard

The negative result is more useful than the guard, because it says where the answer is not. Two older fields have faced the same question, and each answered it correctly for its own task.

Code clone types: how clone research classifies copies

Clone research sorts clones by how their text differs. The standard taxonomy, as stated in Roy, Cordy and Koschke's 2009 comparison of clone detectors:

Type	Definition
Type-1	Identical code fragments except for variations in whitespace, layout and comments.
Type-2	Syntactically identical fragments except for variations in identifiers, literals, types, whitespace, layout and comments.
Type-3	Copied fragments with further modifications such as changed, added or removed statements, in addition to the Type-2 variations.
Type-4	Two or more code fragments that perform the same computation but are implemented by different syntactic variants.

The copied helpers and the generated accessors are both Type-2 clones. Clone research also has a stricter test than vectr's mask. The same survey notes that most tools replace every identifier with one placeholder, as the masking guard does, while Baker's Dup encodes each identifier by position so that it finds only consistently renamed clones, where every occurrence of a name maps to the same replacement throughout. Both pairs pass that test as well: poetry becomes pdm everywhere it appears, and 3 becomes 7 everywhere it appears.

For clone research, grouping both pairs is the right verdict, because its task is maintenance. In the survey's words, "if a bug is detected in a code fragment, all fragments similar to it should be checked for the same bug." A bug in one template instance is probably in all fifty, and a tool that groups them is doing its job.

Clone research also found that the textual type does not settle whether a clone is a problem. Kapser and Godfrey grouped the clones they studied by the motivation behind them (forking, templating, customization) and argued that duplication is often a reasonable design choice. Motivation is a fact about how the code came to exist, and it is not in the characters.

Near-duplicate detection on the web: shingling and simhash

Web search removes near-identical pages with shingling and similarity hashing. Broder's resemblance measure takes the shingle sets of two documents and computes r(A, B) = |S(A) ∩ S(B)| / |S(A) ∪ S(B)|. Charikar's simhash maps a document to a short fingerprint so that similar documents differ in few bits, and Manku, Jain and Das Sarma found 64-bit fingerprints with a tolerance of 3 differing bits workable for a repository of 8 billion pages. On the web the textual rule is mostly right: a reader after a page's content is served by any copy, and which copy to show is a separate question about provenance.

Code search is neither task

The question "is B a duplicate of A?" is really "would this reader lose anything if shown A instead of B?" For the uv helpers, the reader wanted the lockfile type, and any one helper was as useful as another, which is to say barely useful. For the accessors, a reader looking for accessor_7 loses everything if shown accessor_3. The two pairs look the same and get opposite answers, because the answer depends on the pair and on what the reader needs.

The limit case needs no similarity score at all. Two classes that each define the same one-line __repr__, printing the class name and an id through self.__class__.__name__, produce two chunks whose text can be byte-identical. They are still two symbols, and a reader asking how the second class prints itself needs the second one. A key that reads only the chunk's characters has no way to see which class a chunk sits in.

Philosophy has a name for the principle a text rule leans on. Leibniz's identity of indiscernibles, in the Stanford Encyclopedia's phrasing, is the thesis that "there cannot be two objects that differ only numerically": things alike in every property are one thing, not two. A text-similarity rule applies it with one property standing in for all of them, so two chunks that agree in text are treated as one while differing in their names, their callers and their reasons for existing.

What would separate the two classes are facts a text comparison never sees. None of them is wired into vectr's deduplication today. Each is a candidate with its own way of failing, and each needs measuring before it ships.

Copy or instance: the symbol graph

A copy is the same content placed in several files by hand. An instance is one definition among many produced from a template. The symbol graph can ask the question the vectr commit names as missing: are the containing symbols distinct definitions, each referenced by its own name, or copies of one piece of content? Fifty accessors are fifty definitions, and code that reads a field calls the accessor for that field by name. The benchmark helpers are launched by a benchmark runner, and library code has no reason to call any one of them by name.

This signal breaks on generated API clients. Their public methods may have no callers inside the repository at all, because the callers are the client's users, so in the graph they look exactly like the helpers. A reference count can only shift the odds.

The file's role and generated-code markers

Scripts, fixtures and benchmark helpers usually live apart from library modules, in directories whose names say so. Generated files usually announce themselves. Go's toolchain documents a convention: a generated file carries a line matching ^// Code generated .* DO NOT EDIT\.$ before its first non-comment text. vectr already recognises generated files by path (protobuf outputs, minified bundles, generated/ directories) and uses that to demote them in ranking. The dedup path does not consult it.

The history

A copy has a moment in version control when content was duplicated from somewhere else. git blame -C attributes lines to the file they were copied from (repeat the flag to search harder), and git diff --find-copies does the same for whole files. Generated code has a generator instead, and usually a build step that runs it.

The query

If the query names an identifier that distinguishes two chunks, they are not duplicates for that query, whatever their text. The check is cheap: take the tokens where the two chunks differ, split identifiers into their parts so that "accessor 7" in a query still matches accessor_7, and look for any of them in the query. If none appears, showing one templated instance with a note that forty-nine similar ones exist may be exactly right. The price is that the decision now depends on the query, so it cannot be computed once at index time.

Fold instead of delete

Whatever the decision, it can be made reversible for the reader. Show one representative with "and N similar", keep the others one step away, and the result slots go to other answers without any claim that the others do not exist. A wrong fold costs the reader one click to expand; a wrong deletion costs the answer.

vectr's result renderer does half of this today. A representative carries (+N more identical), but the collapsed chunks' locations are not kept, so they cannot be opened, and the label says "identical" for chunks the docstring key only judged near-identical. A real fold is the only one of these changes that needs no new signal, and it is the one I would ship first.

Policy	Concept query: "how is the lockfile defined?"	Instance query: "where is accessor_7 used?"
Keep all	Three helper copies take three slots; the Lock struct is pushed down.	Fine: every accessor is still there.
Collapse by text	Fine: one helper, and the struct is visible.	Forty-nine accessors are gone; accessor_7 survives only if it happened to be the representative.
Fold	One helper row, "+2 similar"; the struct is visible.	One accessor row, "+49 similar", openable; or no fold at all, because the query names accessor_7.

The argument makes three claims that a measurement could break.

No threshold works. On a corpus with substantial generated or templated code, every text-similarity threshold will either leave copied-content clutter in the results or collapse distinct template instances. The measurement is a threshold sweep over a labelled set containing both classes. Half of that set exists: vectr's autojunk benchmark carries ten templated pairs in five shape families and reports, for each, which of the thresholds 0.75, 0.80, 0.85, 0.90, 0.95 and 0.99 would collapse it. The other half, labelled copies taken from real corpora, has not been built.

One structural signal does. Adding whether the two chunks define distinct symbols with their own references should separate the classes where text cannot. The same labelled set would measure it, and generated API clients, whose methods have no callers inside the repository, are where it should fail first.

Folding wins on mixed traffic. On a workload that mixes concept queries ("how is the lockfile defined?") with instance queries ("where is accessor_7 used?"), folding should beat both collapsing and keeping everything, since each of those loses one query type outright.

Three copied scripts must collapse into one result, and fifty generated accessors must not. Their text has the same shape, so no rule that reads the text can tell them apart. Whether two chunks are duplicates depends on what they are and who is asking, and that information lives outside the characters.

Text similarity keeps a smaller job: proposing which chunks might be folded together. Deciding whether they should be needs the symbol graph, the file, the history or the query. Until one of those has been measured against labelled pairs, the defensible default for two look-alike chunks is a fold the reader can open, labelled "similar" rather than "identical".

• vectr CHANGELOG, entries 1.12.0 ("Retrieval and ranking") and 1.10.0. The stripped-body ratios, the autojunk table, the fifty-to-one collapse, the reverted guard, the hardened docstring key and its latency measurements.
• vectr commit 126e73d, "Harden near-duplicate docstring dedup against false collapse". The two gates, the uv Lock witness, and the margins measured for the 0.75 threshold.
• vectr commit a499494, "Bound near-dup dedup comparison cost per doc_key". The per-key representative cap, its failure direction, and why 60 and 200 are the relevant candidate counts.
• vectr commit 27bf972, "compare stripped bodies for near-duplicate dedup, and find the autojunk defect". The discovery of the defect, the split fix, and the note on tests that share the product's assumption.
• vectr commit bc8b9f4, "harness for the DEF-C autojunk threshold". The measured three-row table and the correction that the defect needs both length and repetition.
• vectr commit 370b6f3, "alignment-independent templated-body guard, and why it cannot fix DEF-C". The rename fixture, the masking rule, the reverted wiring, and the missing signal.
• vectr source: agent/searcher.py (the collapse loop and the call-site comment), agent/chunk_quality.py (the docstring key, the masking guard, generated-file detection), tests/test_defc_autojunk_harness.py (the 392-character fixture), tests/test_indexer_searcher.py (the witness fixtures, the fifty-accessor fixture scored in Section 02, and the two xfail tests) and integrations/mcp_server/_dispatch.py (the "+N more identical" render).
• Python documentation, difflib, Python 3.12 (the "Automatic junk heuristic" paragraph) and the current difflib page ("Junk heuristic"). The popularity rule, its framing as a heuristic for speed and readable diffs, the caution that ratio() can depend on argument order, and the Ratcliff and Obershelp lineage.
• Roy, C. K., Cordy, J. R., Koschke, R. "Comparison and evaluation of code clone detection techniques and tools: A qualitative approach." Science of Computer Programming 74(7), 2009, pp. 470-495. doi:10.1016/j.scico.2009.02.007. The Type-1 to Type-4 definitions, the maintenance rationale for grouping clones, and the contrast between single-placeholder identifier normalization and Baker's consistent-renaming scheme.
• Baker, B. S. "On finding duplication and near-duplication in large software systems." WCRE 1995, pp. 86-95. doi:10.1109/WCRE.1995.514697. Dup, the token-based detector that finds parameterized, consistently renamed clones.
• Kapser, C., Godfrey, M. W. "'Cloning Considered Harmful' Considered Harmful." WCRE 2006, pp. 19-28. doi:10.1109/WCRE.2006.1. Extended as "'Cloning considered harmful' considered harmful: patterns of cloning in software," Empirical Software Engineering 13(6), 2008, pp. 645-692, doi:10.1007/s10664-008-9076-6. Clone patterns grouped by motivation: forking, templating, customization.
• Broder, A. Z. "On the resemblance and containment of documents." Compression and Complexity of Sequences 1997, pp. 21-29. doi:10.1109/SEQUEN.1997.666900. Shingling and the resemblance measure.
• Charikar, M. S. "Similarity estimation techniques from rounding algorithms." STOC 2002, pp. 380-388. doi:10.1145/509907.509965. The locality-sensitive fingerprint known as simhash.
• Manku, G. S., Jain, A., Das Sarma, A. "Detecting near-duplicates for web crawling." WWW 2007, pp. 141-150. doi:10.1145/1242572.1242592. Simhash at the scale of 8 billion pages, with 64-bit fingerprints and k = 3.
• Carbonell, J., Goldstein, J. "The use of MMR, diversity-based reranking for reordering documents and producing summaries." SIGIR 1998, pp. 335-336. doi:10.1145/290941.291025. Maximal marginal relevance and its query-free redundancy term.
• Clarke, C. L. A., Kolla, M., Cormack, G. V., Vechtomova, O., Ashkan, A., Büttcher, S., MacKinnon, I. "Novelty and diversity in information retrieval evaluation." SIGIR 2008, pp. 659-666. doi:10.1145/1390334.1390446. Information nuggets and the α-nDCG gain vector.
• Rodriguez-Pereyra, G. "The Identity of Indiscernibles." Stanford Encyclopedia of Philosophy. The statement of the principle quoted in Section 05.
• The Go command documentation, "Generate Go files by processing source". The generated-code marker convention.
• Git documentation, git-blame (the -C option) and git-diff (--find-copies). Line-level and file-level copy detection in version control.
• uv, scripts/benchmark/src/benchmark/resolver.py. uv's benchmark suite, which times uv against other Python packaging tools.