Overlap-detection algorithms for the whole-draft × whole-corpus scan: benchmarks, costs, and where chroma/BERTopic fit

[prasadtalasila]

Context: the grounded-writing roadmap's Phase 1 (#110, #111, #112) builds a whole-draft × whole-corpus verbatim scan. Before implementing #110, we surveyed the overlap-detection benchmark literature — the PAN/CLEF text-alignment shared tasks (2012–2015 and the 2025 generative revival) and the MOSS/winnowing fingerprinting lineage — to pick algorithms deliberately rather than by habit. One constraint sharpens everything: the drafts this pipeline produces are LLM-written, so the guards must be strong against both exact copying and literal paraphrase (same sentence skeleton, synonyms swapped, function words shuffled) — the mode of reuse LLMs actually produce.

What the benchmarks say

• PAN 2013's winner on both quality and runtime (CoReMo, Torrejón & Ramos) used contextual n-grams with odd/even skip-grams — an exact-matching family. Well-engineered n-gram methods beat fancier ones on speed at comparable detection quality, and skip-grams + stemming tolerate the single-word edits that break plain n-gram runs.
• PAN 2014/2015's winner (Sánchez-Pérez et al.) used TF-IDF sentence similarity with recursive passage extension — the fuzzier family wins only when reuse is obfuscated.
• PAN 2025's generated-plagiarism task measured the LLM case directly: exact-matching approaches miss LLM-paraphrased reuse, and detection degrades further as paraphrase complexity rises. Embedding-based alignment (SBERT + local alignment, e.g. Smith–Waterman) is the validated answer for that tier.
• Winnowing (Schleimer, Wilkerson & Aiken — the MOSS algorithm) is the canonical index-compression result: keep the minimum hash per window of size w and detection of any match ≥ w+n−1 is still guaranteed, with the index shrinking to ~2/(w+1) of full size.

The dividing line for this project is its own rule: only deterministic checks may block. Exact and skip-gram matching are deterministic (gate-eligible); embedding similarity never is (advisory forever).

The consequence: a three-tier guard stack

1. Exact tier (verbatim_check fingerprints one source per run, from scratch: build a disk-cached corpus-wide n-gram index keyed by ledger hashes #110 + Verbatim reuse from uncited sources and connective prose is invisible: add a whole-draft x whole-corpus scan mode #111): inverted word-8-gram index over the whole corpus; whole-draft sliding scan; gap-tolerant seed-extend merging recovers near-verbatim runs with 1–2 edited words. Deterministic → blockable in Phase 2.
2. Deterministic light-paraphrase tier (proposed follow-on PR): stemmed, stopword-filtered odd/even skip-grams in the same index framework — the CoReMo design. Catches synonym swaps and inflection changes while staying objective. Start advisory, promote with evidence.
3. Embedding literal-paraphrase tier (proposed follow-on PR): embed draft segments, k-NN against the existing chroma collection, flag high-cosine + low-lexical-overlap pairs — the PAN-validated paraphrase signature. Advisory only, by construction.

Because the drafts are LLM-written, tiers 2–3 move up from "someday" to immediately after #111 — ahead of where the original roadmap parked paraphrase detection.

Candidates by descending implementation effort, with value

#	Algorithm (pedigree)	Effort	Value to chitragupta
1	SBERT embeddings + Smith–Waterman alignment (PAN-validated)	Weeks — tuning, FP management	High for tier 3; zero for #110 (can never block; needs exact-tier reports to tune against)
2	Sánchez-Pérez adaptive TF-IDF sentence similarity (PAN 2014/15 winner)	1–2 weeks	Moderate-low: built for obfuscated pairs; overkill for a closed-corpus exact scan; competes with skip-grams for tier 2 and loses on determinism-adjacent simplicity
3	Generalized suffix array/automaton	~1 week, heavy memory engineering	Low: finds matches below the 8-word floor, which the design deliberately excludes
4	Greedy String Tiling + Karp–Rabin (JPlag/YAP3)	Days	Low-moderate: pairwise algorithm; 1-vs-500 needs the inverted index anyway
5	CoReMo skip-grams + stemming (PAN 2013 winner)	Days	High — the tier-2 guard; deterministic paraphrase tolerance
6	Winnowing (MOSS)	Days on top of full index	Moderate, deferred: a 5–10× size lever with a hard guarantee; the right move at book scale, unnecessary at ~500 papers where the full index fits in RAM
7	Seed-and-extend gap-tolerant merging	~1 day	High — belongs in #111's run merging
8	Full inverted 8-gram index + rolling hash (#110 as specified)	2–3 days	Highest value-per-effort: exact, complete recall ≥ n, deterministic, the substrate every other row plugs into

Merits and resource requirements

Corpus scale for the numbers: 501 PDFs, ~13,400 pages, ~7M words.

Guard	Catches	Misses	Can it block?	Compute / RAM / disk	Extra deps
Inverted 8-gram index (#110)	All verbatim reuse ≥8 words, any source, with run length + page	Any single-word edit breaks a run	Yes — exact	Build: one pass, minutes, pure Python; ~100 MB RAM; ~60–120 MB disk; near-zero re-run	None (stdlib)
Gap-tolerant seed-extend merge (#111)	Near-verbatim runs with 1–2 edited words per gap	Rewrites beyond small gaps	Yes	Negligible on top of the index	None
Stemmed odd/even skip-grams (CoReMo)	Literal LLM paraphrase: synonym swaps, inflection, function-word shuffles	Genuine restatement in new structure	Yes in principle; start advisory	~2–3× fingerprint volume → ~200–300 MB disk; vendor a ~150-line Porter stemmer	None
Winnowing (MOSS)	Same as exact tier, guaranteed ≥ w+n−1	Exact run boundaries (seeds need re-extension)	Yes	Index shrinks to ~2/(w+1) of full	None
TF-IDF sentence similarity (Sánchez-Pérez)	Moderately obfuscated reuse	Heavy paraphrase; threshold-sensitive	No — judgment-thresholded	Minutes, ~100 MB	None, but real tuning effort
Chroma embedding tier (high cosine + low lexical overlap)	The strongest literal-paraphrase guard (PAN-validated)	— but false-positives on standard technical phrasing	Never — model-dependent	Draft embed + queries: seconds–1 min CPU; corpus side already paid by the enrich layer	The 6 GB enrich venv (already optional)
Greedy String Tiling	Maximal exact tiles, pairwise	Paraphrase; scaling	Yes	O(n²)-ish per pair × 500 sources	None
Suffix array	Exact matches at any length	Below-floor matches are noise by design	Yes	~300–500 MB RAM, high complexity	None

Can this be built on the existing chroma collection and BERTopic?

Not #110 itself — deliberately — but chroma is exactly the substrate for tier 3, and BERTopic fits neither.

Why #110 cannot sit on chroma:

1. Wrong primitive. Cosine over 200-word chunks answers "is this about the same thing", not "which 11 words are identical, from which citekey, on which page". Verbatim run boundaries cannot be recovered from embeddings; you would end up implementing the n-gram index on top of the heavier machinery. The chunks also carry no page metadata.
2. Layering. The enrichment layer is optional by contract — nothing above needs it, the venv is ~6 GB, every skill falls back when it is absent. The scan is meant to be gate-eligible in Phase 2, and a blocking check cannot depend on an optional layer. verbatim_check fingerprints one source per run, from scratch: build a disk-cached corpus-wide n-gram index keyed by ledger hashes #110 belongs to the corpus layer: stdlib, bare python3, ledger-keyed.
3. Determinism. The chroma collection is namespaced per embedding model precisely because vectors change when embedding_model changes — chroma-based findings would change on a config edit, breaking the ledger-hash reproducibility contract and the only-deterministic-checks-block rule.

Where chroma does fit — tier 3 is nearly free on today's infrastructure: the corpus side is already embedded, incremental re-embedding by text hash is already built (embed_index.py), and get_client_and_model() is the reuse seam. The tier: chunk the draft with the same chunk_text(), embed with the same model, query the collection per segment, flag high-cosine/low-lexical-overlap pairs, then page-locate matched chunks through the passages ladder. Advisory, gated on content/chroma/ existing — the same fall-back shape the skills already use.

BERTopic: no. content/topics.json has no consumer, assignments are unstable between runs and whole-corpus-recomputed, and topic granularity is far too coarse for overlap. Its only conceivable role — prefiltering candidate sources — is worthless at ~500 documents, where the exact index checks every source in one lookup.

Proposed sequence

#110 (exact index) → #111 (scan + gap-tolerant merge) → #112 (wiring + adversarial fixtures) → new PR: deterministic skip-gram channel (the tokenizer_version cache-key field in #110's design exists for exactly this) → new PR: chroma advisory tier feeding the same findings format.

The concrete implementation plan for #110 is posted on that issue.