💬 NLP

Deja Vu at Scale: Paraphrase-Robust Detection of Duplicate Gherkin Steps in Behaviour-Driven Software Testing with Sentence-Transformer Embeddings and a 1.1M-Step Open Benchmark

This paper addresses the maintenance costs of duplicate Gherkin steps in Behaviour-Driven Development by releasing a large-scale, cross-organisational benchmark of over 1.1 million steps and introducing a paraphrase-robust detector that combines exact, lexical, and semantic methods to identify and quantify significant eliminable redundancy.

Original authors: Ali Hassaan Mughal, Noor Fatima, Muhammad Bilal

Published 2026-06-15

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ali Hassaan Mughal, Noor Fatima, Muhammad Bilal

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the editor of a massive, collaborative cookbook. Thousands of chefs from different kitchens have contributed recipes. Over time, you notice a problem: the same instructions appear over and over again, just written slightly differently.

One chef writes: "Add two cups of flour."
Another writes: "Add 2 cups of flour."
A third writes: "Put in 2 cups of flour."

In the world of software testing, these instructions are called Gherkin steps. They are the "recipes" that tell a computer how to test a piece of software. The problem is that when these instructions are duplicated or slightly paraphrased, it becomes a nightmare to maintain. If you need to change a step (like changing "Add flour" to "Add almond flour"), you might have to hunt down and edit thousands of copies instead of just one.

This paper, titled "Déjà Vu at Scale," is about building a super-smart tool to find these duplicates, even when they are written in slightly different ways, and creating a giant library of examples to prove the tool works.

Here is the breakdown of what they did, using simple analogies:

1. The Problem: The "Déjà Vu" Effect

The authors found that in the software world, duplication is everywhere. They looked at 347 different software projects (like 347 different cookbooks) and found over 1.1 million instructions.

The Stat: They discovered that 80% of these instructions were exact copies of something else.
The Pain: If a company wants to fix a typo or change a rule, they might have to edit thousands of files. It's like trying to update a recipe in a cookbook where that recipe is written on 1,000 different pages in 1,000 different books.

2. The Solution: A "Smart Librarian"

The authors built a tool called cukereuse. Think of this tool as a super-librarian who can read the instructions and understand that "Add 2 cups" and "Add two cups" are the same thing, even if the spelling or spacing is different.

They didn't just use one trick; they used a four-layer defense system to catch duplicates:

The Exact Match: If two instructions are identical down to the last letter (like two photocopies), it catches them instantly.
The "Almost" Match: If the instructions are 90% the same (like "Add 2 cups" vs "Add two cups"), it catches those too.
The "Meaning" Match: This is the clever part. It uses AI (called Sentence Transformers) to understand the meaning. It knows that "The user clicks the button" and "Clicking the button by the user" mean the same thing, even if the words are totally different.
The Hybrid: It combines the "Almost" and "Meaning" checks to be extra sure.

3. The Proof: The "Gold Standard" Test

To prove their librarian was actually good, they didn't just guess. They created a giant test set:

They took 1,020 pairs of instructions.
Three different people (the authors) manually read them and decided: "Are these duplicates or not?"
They made sure everyone agreed on the answers (a high score called Fleiss' κ = 0.84, which is like a team of judges all agreeing on who won a contest).
The Result: Their "Meaning Match" tool was very good, but the "Almost Match" tool was the most reliable and honest, correctly identifying duplicates about 82% of the time without getting confused by the test rules.

4. The Big Discovery: The "Consolidation" Savings

The most exciting part of the paper is the math they did on the savings.

They found that in a typical software project, you could delete about 62.5% of the duplicate instructions and replace them with just one "master" instruction.
The Analogy: Imagine you have 100 pages of a cookbook. After using this tool, you realize you only need 37 unique pages. The other 63 pages are just copies. You can throw them away, making the book much thinner and easier to manage.
They linked this to ISO/IEC 25010, which is basically a global rulebook for "good software." They showed that cleaning up these duplicates makes software easier to change (Maintainability) and less likely to break (Reliability).

5. What They Released to the World

The authors didn't keep their findings to themselves. They released a "starter pack" for anyone who wants to do this research:

The Data: A massive collection of 1.1 million real-world instructions from public software projects.
The Test: The 1,020 pairs of instructions with the "gold standard" answers.
The Tool: The actual software code (cukereuse) that finds the duplicates.
The Rules: A guidebook on how they decided what counts as a duplicate.

Summary

In short, this paper says: "Software testing instructions are full of unnecessary duplicates, making them hard to manage. We built a smart tool that finds these duplicates (even when they are written differently), proved it works with a massive, high-quality test, and showed that fixing this could save software teams a huge amount of time and effort. We are giving all our tools and data away for free so others can use them."

What they did NOT claim:

They did not say exactly how much money this saves (because every company pays its workers differently).
They did not say this fixes all software quality problems, just the specific problem of duplicate instructions.
They did not claim their tool works on private, secret company data (since they only looked at public data).

Technical Summary: Déjà Vu at Scale

Problem Statement
Behaviour-Driven Development (BDD) suites, written in the Gherkin language, frequently accumulate step-text duplication. Prior research establishes that such duplication incurs significant maintenance costs, particularly when step definitions require renaming or refactoring across multiple occurrences. Existing detection techniques suffer from critical limitations: dynamic approaches (e.g., Binamungu et al., 2018–2023) require runnable test suites, making them infeasible for cross-repository scale; static approaches (e.g., Irshad et al., 2020–2022) are often confined to single organisations or lack step-level granularity. Consequently, there is a gap for a purely static, paraphrase-robust, step-level detector applicable to any repository, accompanied by a public benchmark for calibration.

Methodology
The authors present cukereuse, a static analysis tool and associated empirical study. The methodology is structured around three core components:

Corpus Construction:
- Discovery: Using the GitHub REST Search API, the authors identified repositories containing Gherkin files, filtering for those with $\ge$ 10 stars and excluding archived projects.
- Materialisation: 347 repositories were sparse-cloned, yielding 23,667 parsed .feature files and 1,113,616 Gherkin steps.
- Identity Definition: A step's identity is defined as the BLAKE2b hash of its whitespace-collapsed text, excluding keywords (Given/When/Then) and attached arguments (DocStrings/DataTables), while retaining parameters and literals. This mirrors the Cucumber runtime's resolution logic.
Detection Strategies:
The tool layers four strategies along a precision/compute-cost frontier:
- Exact: BLAKE2b hashing on normalized text.
- Near-Exact: Normalized Levenshtein ratio.
- Semantic: Sentence-BERT (SBERT) cosine similarity.
- Hybrid: A combination of SBERT cosine and a Levenshtein-band guard to filter noise.
Evaluation and Benchmarking:
- Labelled Benchmark: A dataset of 1,020 step pairs was manually labelled by three authors using a shared rubric (Fleiss' $\kappa$ = 0.84 on a 60-pair overlap).
- Circularity Control: To address the threat of score-based rubric rules (R1–R3) biasing the detector, a "score-free" second-pass relabelling protocol was introduced. This protocol uses deterministic text-rewriting rules (e.g., token-multiset identity, subsequence containment) without accessing similarity scores.
- Baselines: The study compares the proposed strategies against two classical lexical baselines: Token-set Jaccard (SourcererCC-style) and TF-IDF character n-gram cosine (NiCad-style).

Key Contributions

Largest Cross-Organisational Corpus: A dataset of 1.1 million Gherkin steps across 347 repositories, released with SPDX licence tags and a Gebru-style datasheet.
First Public BDD Benchmark: A 1,020-pair labelled benchmark with high inter-annotator agreement, designed specifically for calibrating duplicate detectors.
Score-Free Relabelling Protocol: A methodological contribution to bound the circularity between score-based detectors and score-based evaluation rubrics.
Consolidation-Savings Model: A quantitative model mapping detected clusters to ISO/IEC 25010 quality characteristics (specifically maintainability sub-characteristics like modifiability and reusability).
Open Source Tooling: The cukereuse tool, analysis pipeline, and all artefacts are released under permissive licences.

Results

Duplication Prevalence: The step-weighted exact-duplicate rate is 80.2%. The median repository has a duplication rate of 58.6%. The most frequent hybrid cluster ("the response status is 200 OK") appears 20,737 times across 2,245 files.
Detection Performance:
- Under the primary rubric, the semantic strategy achieved an F1 of 0.906, but this was identified as a stratification artefact (recall = 1.000 due to rubric rules).
- Under the score-free relabelling (the "honest" metric), the near-exact (Levenshtein) strategy performed best with an F1 of 0.822.
- The semantic strategy dropped to F1 = 0.772 under score-free labels, while lexical baselines reached F1 = 0.761 (Jaccard) and 0.799 (TF-IDF).
Consolidation Potential: The model estimates that 893,357 step-text occurrences (approx. 80% of the corpus) are amenable to consolidation under exact matching. On a median repository, 62.5% of step lines are eliminable.

Significance and Claims
The paper claims to close a specific, measurable gap in BDD-quality tooling by providing the first static, paraphrase-robust, cross-organisational duplicate-step detector. The significance lies not in claiming to solve all BDD quality issues, but in providing the necessary empirical artefacts (corpus, benchmark, and tool) to enable future research and practical application.

The authors explicitly state that the detected clusters map to ISO/IEC 25010 maintainability sub-characteristics (modifiability, modularity, reusability, analyzability, testability) and indirectly to reliability via drift prevention. However, the paper maintains modesty regarding economic impact: it quantifies the "eliminable surface" (lines of text) but does not translate these figures into monetary savings or person-hours, noting that such translation requires organisation-specific cost calibration which is outside the scope of the released data. The work serves as a foundational benchmark and toolset for the community to replicate, extend, and apply to their own codebases.