{"id":"f4e39aa7-c4e5-4f95-b5ba-f8a32c478413","arxiv_id":"1908.08266","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Near-duplicate passages in software documentation can be found interactively with a pattern-based search algorithm that provably reports all fragments sharing a sufficiently large common subsequence with the selected pattern.","lead":"An interactive tool finds near-duplicate passages in software documentation by letting a user highlight a meaningful pattern and then searching the document for similar fragments. The authors prove a formal guarantee that every near duplicate of the pattern appears in the output, and test the tool on 19 industrial documents.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 2 is false, so the published proof of Theorem 1 is invalid; Lemma 4's omitted proof adds a second unverified link.","rationale":"The reader correctly identifies the completeness proof as the load-bearing point, and correctly flags Lemma 4's omitted proof as a serious gap. The sharper issue is that one of the published proof's lemmas is demonstrably false, not merely unproved: Lemma 2's proof reverses the inequality supplied by Lemma 1, and the resulting bound fails on a concrete, valid near-duplicate pair. This invalidates the proof chain for Theorem 1 in addition to the missing Lemma 4. I did not find a counterexample to Theorem 1 itself; the available evidence suggests the theorem may be repairable, since the Phase 1 threshold still appears generous enough to accommodate a corrected bound. Therefore I keep the reader's CONDITIONAL verdict rather than rejecting the paper outright, but the requested revision becomes more urgent: the proof must be rebuilt, not just expanded.","tokens_in":13746,"tokens_out":22878,"duration_ms":245005,"concrete_test":"Re-derive Lemma 2 in §6.2 and apply it to p=0^60, g=1^24 0^36, k=0.6. These fragments form a near-duplicate group with archetype 0^36, and the paper's LCS edit distance gives d(g,p)=60+60−2·36=48, exceeding the claimed bound (1−0.6^2)·60=38.4. If this computation is reproduced, the published proof of Theorem 1 is invalid as written. A useful follow-up is an exhaustive search over binary strings up to a bounded length, enumerating all Def. 2 groups and checking criterion (2) on the Phase 2 output, to determine whether the theorem itself needs revision or only the proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In §6.2, Lemma 2's proof asserts 'According to lemma 1 we have |g| ≤ k|p|'. Lemma 1 actually gives k ≤ |g|/|p| ≤ 1/k, so the inequality used in the proof is reversed. This is not a harmless typo: the lemma's conclusion is false. Example: k=0.6, p=0^60, g=1^24 0^36. With archetype 0^36, p and g satisfy Def. 2, since the common archetype covers 60% of each fragment. Under the paper's LCS edit distance, d(g,p)=|p|+|g|-2·36 = 60+60-72 = 48, while the claimed bound is (1−k^2)|p| = 38.4. Lemma 3 uses this false bound to argue that Phase 1 captures every near duplicate, and Theorem 1 builds on Lemmas 3–5. Lemma 4's formal proof is also omitted. Thus the proof chain behind the central completeness claim is invalid as written. The theorem may still be true after repair, but the current formal argument does not establish it.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents an interactive process for detecting near-duplicate fragments in software documentation. The workflow uses a heat map of exact duplicates to guide a user in selecting a meaningful pattern, then runs a three-phase pattern-based search algorithm whose output the user can edit. The main formal contribution is a definition of a near-duplicate group (Definition 2), a completeness criterion (Equation (2)), and Theorem 1, which claims that for every near duplicate g of pattern p with similarity k, the algorithm's output R contains a fragment w with |g ∩ w| ≥ O_min(k). The paper also describes five optimizations, gives complexity estimates, and reports runtime and output-size experiments on 19 industrial documents.","tokens_in":13935,"tokens_out":6145,"duration_ms":59760,"significance":"If the completeness theorem were valid, the paper would make a useful contribution: it gives a precise formal notion of near duplicate for documentation and a matching algorithm with a worst-case coverage guarantee, which is rare in this area. The interactive design and the use of a duplicate heat map are sensible, and the experimental corpus of real documents is a strength. However, the central proof is not currently sound: Lemma 2 is false as stated, Lemma 4 is explicitly unproved, and the gap between the proven algorithm and the evaluated implementation is not accounted for. These issues are load-bearing for the main claim, so the paper needs substantial revision before the contribution can be accepted.","major_comments":[{"comment":"The proof of Lemma 2 uses the inequality |g| ≤ k|p|, attributing it to Lemma 1. Lemma 1 states k ≤ |g1|/|g2| ≤ 1/k, so with g2 = p it gives |g| ≥ k|p|, not |g| ≤ k|p|. The error is not cosmetic: the lemma itself is false. For k = 0.6, p = 0^60, and g = 1^24 0^36, the archetype 0^36 satisfies Definition 2 for p and g, but d(g,p) = 48, while (1 − k^2)|p| = 38.4. Since Lemma 3 uses Lemma 2 and Theorem 1 relies on Lemmas 3–5, the completeness theorem is not established by the submitted proof.","section":"Section 6.2, Lemma 2"},{"comment":"The proof of Lemma 4 is omitted, with the text stating 'We omit a formal proof due to its large size.' This lemma is load-bearing: phase 2 replaces each window w1 by a single shrunk fragment w2, and it is not obvious that the selected w2 preserves a sufficiently large intersection with every near duplicate contained in the original window. The main idea described in the paper (considering worst-case shrinkage to k|p| and corner positions) is not a proof. The completeness claim cannot be considered proven without a complete argument for this step.","section":"Section 6.2, Lemma 4"},{"comment":"Optimization 3 is admitted to break completeness in Note 1, yet the experimental section does not state which optimizations were enabled during the reported runs. If Optimization 3 was active, the evaluated implementation is not the algorithm whose completeness is claimed in Theorem 1. Moreover, the experiments report only runtime and output size; there is no ground-truth evaluation of precision or recall. Consequently, the paper does not provide empirical evidence that near duplicates are not missed or that the output is usable beyond being small enough for manual inspection.","section":"Section 6.3 and Section 8"},{"comment":"The paper says the longest common subsequence distance is used in the proofs and in the algorithm, but the implementation relies on Python's difflib library. difflib's sequence matching is a heuristic and is not guaranteed to compute the exact longest common subsequence distance. This creates a gap between the formal model and the evaluated implementation; the completeness theorem applies only if the distance used in the implementation is exactly the one defined in Section 3.1.","section":"Section 3.1"}],"minor_comments":[{"comment":"The phrase 'a pattern-based, and the proof of its completeness' is grammatically incomplete; the contribution list needs rewording.","section":"Abstract"},{"comment":"There is a duplicated article in 'we present an an approach for interactive detection of near duplicates'.","section":"Introduction"},{"comment":"The proof refers to 'according to (2)' when deriving |A|/|p| ≥ k; the relevant statement is Definition 2, not the completeness criterion in Equation (2).","section":"Section 6.2, Lemma 2 proof"},{"comment":"The complexity estimate in Theorem 3 is stated without proof ('We omit the proof due to its large volume'). If this is intended as a contribution, the proof should be supplied or the statement should be marked as conjectural.","section":"Section 7, Theorem 3"},{"comment":"The text 'convertation' should be 'conversion'. Also, the conclusion that most near-duplicate groups are small follows only indirectly from the experiments, since the experiments measure output size rather than the size of user-validated near-duplicate groups.","section":"Section 8"}],"recommendation":"major_revision","confidential_remarks":"The false Lemma 2 is a serious correctness issue in the central proof chain. If the authors can repair the proof or appropriately weaken the theorem, and supply the missing proof of Lemma 4, the paper could become acceptable. As it stands, the completeness guarantee is unsubstantiated, and the experimental section does not compensate for this because it does not measure detection quality against ground truth."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know about arXiv:1908.08266. The formal definition of near duplicates and the interactive search process are genuinely useful ideas. But the central completeness claim is not supported: Lemma 2 is false, and Lemma 4 has no proof. So the paper's main theorem, as written, does not hold.\n\nWhat is new: a parameterized definition of near duplicates that allows extension points at the ends, a three-phase pattern-based algorithm, and a completeness criterion O_min(k) bounding the overlap between any near duplicate and some output fragment. The interactive workflow, using a heat map of exact duplicates to guide pattern selection, is sensible and is a real step beyond blind heuristic search. The runtime measurements are useful: 90% of runs under two minutes, and most outputs under 100 items, which matches the practical need.\n\nNow the soft spots, in order of severity.\n\nFirst, the proof. Lemma 2 (Section 6.2) claims that any near duplicate g of p has d(g,p) <= (1-k^2)|p|. The proof uses Lemma 1 to say |g| <= k|p|, but Lemma 1 gives |g| <= |p|/k. The direction is reversed. And the claim is simply false: take k=0.6, p=0^60, g=1^24 0^36, with archetype 0^36. Both satisfy the near-duplicate condition, yet d(g,p)=48 while the bound is 38.4. Lemma 3 relies on that bound, and Lemma 4's proof is omitted entirely. So the chain leading to Theorem 1 breaks. The theorem might be repairable with a different bound, but as published the completeness guarantee is not established.\n\nSecond, the implementation. The paper says it uses difflib, but difflib's ratio is not the LCS distance used in the proofs. That's a gap between the math and the code.\n\nThird, Optimization 3 can break completeness, as Note 1 admits, and the evaluated algorithm probably includes it. That undercuts the practical force of the theorem even if the proof was fixed.\n\nFourth, the experiments report only runtime and output size. Without ground truth or a baseline, we can't judge precision or recall. The user study is also missing—the \"meaningfulness\" part isn't evaluated.\n\nWho is this for? Readers working on documentation clone detection will find the definition and process worth reading, and the runtime data is a useful datapoint. But I would not rely on the completeness claim until the lemmas are repaired.\n\nFor peer review: it deserves refereeing in the sense that the idea is worth engaging, and the flaws are fixable in a revision. I'd send it back for major revision rather than desk reject, but the current version should not be accepted as-is.","headline":"A useful formalization and interactive process, but the completeness proof has a false lemma and an omitted proof, so the central guarantee is unproven.","tokens_in":14520,"tokens_out":5414,"would_cite":false,"duration_ms":43855,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A pattern-based near-duplicate search algorithm for software documentation is proven complete: any true near duplicate of a chosen pattern always shares a guaranteed minimum overlap with some fragment in the output.","keywords":["near duplicate","software documentation","pattern-based search","edit distance","longest common subsequence","completeness theorem","interactive search","duplicate detection"],"falsifier":"Construct a small document containing a known near-duplicate group, run the algorithm, and check whether every $g$ in the group has some returned $w$ with $|g \\cap w| \\geq \\frac{|p|}{2}\\left(3k - \\frac{1}{k}\\right)$; a missed group falsifies Theorem 1. Since Lemma 4 is the unproved hinge, the decisive check is an exhaustive search over short strings for a case where shrinking discards the only fragment covering a near duplicate. A second, independent check compares the implemented edit-distance calculation with the true LCS distance on adversarial string pairs: any pair where the tool rejects a fragment that LCS distance would accept falsifies completeness for the implemented version.","tokens_in":13546,"feed_emoji":"🔍","tokens_out":11683,"duration_ms":92137,"temperature":0.7,"pith_summary":"Software documentation is full of copy/paste duplicates, and maintaining them is a chore. The paper argues that near-duplicate search should not be fully automatic: a user picks a meaningful 'pattern' fragment, and an algorithm then finds every text fragment that is a near duplicate of that pattern. The central claim is a completeness guarantee: for any chosen similarity level $k > 1/\\sqrt{3}$, the algorithm's output must contain, for every true near duplicate $g$, some fragment $w$ that overlaps $g$ in at least $\\frac{|p|}{2}\\left(3k - \\frac{1}{k}\\right)$ characters. If this holds, the interactive tool cannot silently miss a near duplicate, which would make duplicate management and documentation reuse practical on industrial documents.","feed_headline":"Proof shows duplicate search never misses a near duplicate","feed_subtitle":"A completeness theorem guarantees no near duplicate is missed, and industrial tests confirm interactive run times.","key_machinery":"The paper's central object is the near-duplicate group (Definition 2): an ordered set of non-overlapping text fragments that all contain the same ordered collection of substrings, the archetype, whose total length is at least a fraction $k$ of each fragment. The algorithm works in three phases: a sliding window of length $|p|/k$ sweeps the document and keeps windows whose longest-common-subsequence edit distance to $p$ falls below a computed threshold (Lemmas 2 and 3 ensure every true near duplicate sits inside some kept window); a shrinking phase narrows each window to the subfragment closest to $p$; and a filtering phase removes duplicate and contained fragments. The completeness criterion is expressed through $O_{\\min}(k) = \\frac{|p|}{2}\\left(3k - \\frac{1}{k}\\right)$, which increases with $k$ and becomes positive exactly when $k > 1/\\sqrt{3}$. The proof runs through Lemmas 1–5; Lemma 4, the claim that shrinking preserves the criterion, is stated with its proof omitted.","core_discovery":"On the paper's own terms, the discovery is a formal theorem: for any document $D$, pattern $p \\in D$, similarity $k \\in (1/\\sqrt{3},\\, 1]$, and any near-duplicate group $G$ of $p$ with similarity $k$, the three-phase pattern-based near-duplicate search algorithm returns a set $R$ such that every $g \\in G$ has some $w \\in R$ with $|g \\cap w| \\geq \\frac{|p|}{2}\\left(3k - \\frac{1}{k}\\right)$. This completeness criterion is a no-miss guarantee: the user will always find each true near duplicate in the output, possibly shifted or resized, because it must share a fixed minimum overlap with one of the returned fragments. The paper also claims the guarantee survives four of its five optimizations, and reports experiments on 19 industrial documents where the algorithm runs interactively and most outputs contain under 100 elements.","pith_inferences":["The proof skeleton—window containment via the triangle inequality plus a length-ratio bound—should generalize to other metric edit distances and to token-level alphabets, so the completeness argument may be portable beyond character-level LCS distance.","The experiments' observed overlaps exceed the pessimistic $O_{\\min}(k)$ bound, so in practice the tool may miss far less than the theorem guarantees; quantifying that excess overlap on more document types would refine the bound.","Replacing the user's manual pattern pick with an automatic selection from the heat map's maximum-temperature region would test whether the completeness guarantee still yields meaningful groups without human guidance.","The proven guarantee covers false negatives, not false positives; measuring precision on the industrial corpus—how many returned fragments are meaningful near duplicates—is the natural next step the authors leave open."],"forward_implications":["Users can trust that a near-duplicate search returns every true near duplicate for the chosen pattern and similarity, so manual review of the output is complete rather than a gamble.","Because $O_{\\min}(k)$ grows with $k$, demanding stricter similarity ($k \\geq 0.77$) guarantees each output/duplicate overlap exceeds half the pattern length, making results easier to recognize and validate by eye.","The preserved completeness under optimizations 1, 2, 4, and 5 means the performance improvements do not weaken the no-miss guarantee in practice; optimization 3 can occasionally break it, though rarely.","The complexity bound and experiments (90% of runs under two minutes, 84% of outputs under 100 elements) indicate that the interactive loop—choose pattern, search, edit results—is sustainable on documents up to a few megabytes.","A direct corollary of Lemma 1 is that all near duplicates of a pattern have lengths within a factor of $k$, so capping windows at $|p|/k$ is not ad hoc but a provable bound."],"supporting_citations":[{"why":"Establishes the edit-distance framework underlying the similarity measure.","marker":"[27]"},{"why":"Define the longest common subsequence distance used throughout the proofs.","marker":"[29, 30]"},{"why":"Proves the metric properties, including the triangle inequality Lemma 3 relies on.","marker":"[31]"},{"why":"Token-based exact-duplicate detector that builds the heat map guiding user pattern selection.","marker":"[20]"},{"why":"Earlier near-duplicate definition and search algorithm that this paper generalizes to a parameterized similarity k.","marker":"[16]"},{"why":"Standard-library implementation of edit distance used to compute d in the actual tool.","marker":"[34]"},{"why":"Skip-ahead string search technique behind Optimization 1, which keeps the completeness property while speeding up scanning.","marker":"[38]"}],"fun_headline_variants":["Completeness theorem guarantees no near duplicate is missed","Interactive search with a proof it never misses duplicates","Formal guarantee: near-duplicate search always finds them all","No-miss near-duplicate detection, proven and tested","Proof-based duplicate search: never overlooks a near match"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The completeness theorem rests on Lemma 4, which asserts that the shrinking phase never destroys the overlap required by the criterion, and the paper explicitly omits that proof; a second load-bearing premise is that the edit-distance measure in the implemented tool matches the longest-common-subsequence distance used in the proofs.","fun_headline_variants_meta":{"raw":{"variants":["Completeness theorem guarantees no near duplicate is missed","Interactive search with a proof it never misses duplicates","Formal guarantee: near-duplicate search always finds them all","No-miss near-duplicate detection, proven and tested","Proof-based duplicate search: never overlooks a near match"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00016,"raw_usage":{"total_tokens":1184,"prompt_tokens":848,"completion_tokens":336,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":464,"completion_tokens_details":{"reasoning_tokens":257}},"tokens_in":464,"tokens_out":336,"duration_ms":4008,"temperature":1.0,"reasoning_tokens":257,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:44:08.952657+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a small document containing a known near-duplicate group, run the algorithm, and check whether every $g$ in the group has some returned $w$ with $|g \\cap w| \\geq \\frac{|p|}{2}\\left(3k - \\frac{1}{k}\\right)$; a missed group falsifies Theorem 1. Since Lemma 4 is the unproved hinge, the decisive check is an exhaustive search over short strings for a case where shrinking discards the only fragment covering a near duplicate. A second, independent check compares the implemented edit-distance calculation with the true LCS distance on adversarial string pairs: any pair where the tool rejects a fragment that LCS distance would accept falsifies completeness for the implemented version.","supporting_citations":[{"cited_title":"Binary codes capable of cor- recting spurious insertions and deletions of ones / V","cited_arxiv_id":null,"evidence_quote":"Establishes the edit-distance framework underlying the similarity measure."},{"cited_title":"Algorithms on Strings, Trees, and Sequences / D","cited_arxiv_id":null,"evidence_quote":"Proves the metric properties, including the triangle inequality Lemma 3 relies on."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Token-based exact-duplicate detector that builds the heat map guiding user pattern selection."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Earlier near-duplicate definition and search algorithm that this paper generalizes to a parameterized similarity k."},{"cited_title":"— URL: https:// docs.python.org/3/library/difflib.html","cited_arxiv_id":null,"evidence_quote":"Standard-library implementation of edit distance used to compute d in the actual tool."},{"cited_title":"A fast string searching algo- rithm / Robert S","cited_arxiv_id":null,"evidence_quote":"Skip-ahead string search technique behind Optimization 1, which keeps the completeness property while speeding up scanning."}],"review_version":1}