Detecting Duplicated Code With Embeddings

Every clone detector answers a different question, and the reason embeddings became interesting is narrow and specific: they are the first cheap tool that finds duplication with no shared text at all. Knowing which of the four clone types you are hunting decides whether you need one.

The four clone types

The taxonomy comes from the clone detection literature and is worth using precisely, because vendors and blog posts use “duplicate” to mean any of the four. Chanchal Roy and James Cordy’s survey of clone detection techniques set out the version everyone now cites: Roy, Cordy and Koschke, Science of Computer Programming, 2009.

• Type-1 — identical apart from whitespace, layout and comments. A normalising hash finds all of these and misses none.
• Type-2 — identical up to renamed identifiers, literals and types. Normalise every identifier to a placeholder token, hash the result, and again you get exact recall.
• Type-3 — a copy with statements added, deleted or changed. Now exactness fails: you need a similarity measure and a cut-off, and the cut-off is a judgement call.
• Type-4 — functionally equivalent, textually unrelated. A recursive factorial and an iterative one. A retry loop written with a for and one written with a while and a decrementing counter. No amount of token normalisation connects these.

Where an embedding earns its place

For Type-1 and Type-2, an embedding is strictly worse than a hash: slower, approximate, and it can only ever recover what a exact method already got completely. If your duplication problem is copy-paste within one language, run the normalising hash and stop. It costs nothing and it has no false negatives.

The value starts at Type-3 and is decisive at Type-4. An embedding model that has seen a large corpus of source places two fragments near each other when they play the same role, and role survives rewriting. That is also the honest limit: the model has no execution semantics. It is matching on surface regularities that correlate with behaviour — identifier names, control-flow shape, the library calls involved, the docstring if you kept it. Two functions named normalise_email that do genuinely different things will sit close together, and there is no threshold that separates them.

So an embedding-based detector is a candidate generator. It proposes pairs a lexical tool would never propose, at the cost of proposing pairs that are not clones at all. The design question is what you do with a candidate, not how good the model is.

Picking a threshold, worked

Cosine similarity between normalised code embeddings does not have a universal cut-off, and any page that gives you one is guessing. What it does have is a shape you can exploit. Take a few hundred functions from your own repository, embed them, and compute the similarity of every pair. Two distributions are superimposed: a large one of unrelated pairs and a small tail of real relationships. Your threshold is where the tail separates.

The mechanical part is calibration, and it is cheap. Construct known positives without labelling anything by hand: take fifty functions, make a Type-2 copy of each by renaming every local variable, and embed both. The similarity of a function to its own renamed copy is the ceiling your model can reach on this corpus. Then take fifty random pairs from different modules as known negatives. If renamed copies score above 0.94 and random pairs cluster around 0.70, a threshold anywhere in the gap is defensible and you can state why.

# calibration sketch — the numbers you get are yours, not ours
ceiling = mean(cos(emb(f), emb(rename_locals(f))) for f in sample)
floor   = mean(cos(emb(a), emb(b)) for a, b in random_cross_module_pairs)
# report both. a threshold quoted without these two numbers is meaningless,
# because both move with the model, the chunk size and the language mix.

One trap makes the floor deceptively high: if you embed raw file text, every fragment in the same language shares its import block, licence header and brace style, and everything looks similar to everything. Strip comments and headers before embedding and the floor drops sharply, which widens the gap you are trying to find.

The pair count is quadratic

A repository with 200,000 functions has just under 2 × 10¹⁰ unordered pairs. At any plausible rate of similarity computation that is not a job you run nightly, and it is the reason clone detection is an approximate-nearest-neighbour problem rather than a matrix problem.

The standard structure is: index every function vector in an ANN index, then for each function retrieve its top k neighbours and consider only those pairs. That turns 2 × 10¹⁰ comparisons into 200,000 × k. With k = 20 that is four million candidate pairs, which is tractable, and the cost is that any clone not in a function’s top 20 is invisible. For a graph-based index the recall loss is small relative to the loss you already accept from the threshold — see how an HNSW index trades recall for speed for what that parameter is actually doing.

Deduplicate the output before a human sees it. Clone families are transitive in practice: if A ≈ B and B ≈ C you will surface three pairs describing one duplicated idea. Union-find over the surviving pairs collapses them into clusters, and a cluster of nine copies is a far more actionable report than thirty-six pairs.

Verifying a candidate

Because the embedding is a candidate generator, a verification stage is what makes the output usable. Verification is cheap now, because it runs on thousands of pairs rather than billions.

Parse both fragments and compare structure. Normalise identifiers to positional placeholders and compare the token streams — that reclassifies anything which is really a Type-2 clone and lets you report it with certainty rather than a score. Compare the sets of called functions and the arity of each. Compare cyclomatic complexity. None of this is semantic equivalence, which is undecidable, but each check either promotes a candidate to “provably the same up to renaming” or explains in one line why the pair is not interesting.

Two categories should be filtered before review, not after: generated code and vendored dependencies. Both are duplicated by design, both are enormous, and both will otherwise dominate every report you produce. Exclude them by path at index time. The wider version of that problem — duplication across services and repositories, where nobody owns the decision to merge — is a different problem with a different fix, and comparing two versions of a single function over time is a third.