Efficient and Scalable Provenance Tracking for LLM-Generated Code Snippets

Andrea Gurioli; Davide D'Ascenzo; Federico Pennino; Maurizio Gabbrielli; Stefano Zacchiroli

Source-linked AI summary

Efficient and Scalable Provenance Tracking for LLM-Generated Code Snippets

Andrea Gurioli, Davide D'Ascenzo, Federico Pennino, Maurizio Gabbrielli, Stefano Zacchiroli

arXiv:2605.28510v2May 27, 2026cs.SEcs.AIcs.IR

TL;DR

LLM code generation can reproduce training examples, creating attribution and compliance concerns that are difficult to address with linear-time fingerprint search at billion-sample scale. The paper introduces SOURCETRACKER and HST, which combine vector retrieval with Winnowing re-ranking. HST matches Winnowing for 30-token adapted queries and outperforms it by up to 5.4% from windows of at least 60 tokens while retaining logarithmic query complexity.

Problem
LLMs may reproduce training data without attribution, while linear-time fingerprinting is inadequate for provenance tracking across billion-scale training corpora.
Method
HST combines SOURCETRACKER vector retrieval with Winnowing re-ranking to find likely source snippets efficiently.
Results
For windows larger than 60 tokens, HST outperforms Winnowing alone while preserving logarithmic search complexity.
Takeaways & Limitations
Integrating vector search with fingerprinting supports scalable, high-precision provenance tracking for LLM-generated code.
Takeaways & Limitations
The approach depends on having a suitable training set, while the degree and mechanism of LLM memorization remain poorly understood.

Abstract

from arXiv · show

Large language models (LLMs) for code completion and generation are increasingly used in software development, yet they may reproduce training examples verbatim and without authorship attribution, raising legal and ethical concerns around plagiarism and license compliance. Classical fingerprint-based plagiarism detectors based on fingerprinting, such as Winnowing, remain highly effective, yet the inspection requires comparing fragments of code to the entire training set, and their linear-time search makes them impractical for the billion-scale corpora used to train modern code LLMs. To bridge this gap, we introduce SOURCETRACKER, a 300M-parameter encoder tailored for code retrieval, together with a hybrid two-stage provenance-tracking pipeline HYBRIDSOURCETRACKER (HST). HST first narrows down a small set of candidate snippets via vector search, then re-ranks those candidates using Winnowing on exact fingerprints. We train and evaluate our system on a 10M-snippet subset of the THESTACKV2 dataset, with both verbatim and adapted snippets that emulate realistic identifier renaming. On an in vitro 100k-snippet search space with adapted queries, our hybrid approach reaches a mean reciprocal rank on par with Winnowing for 30-token fragments. Then, starting from windows >= 60 tokens, it consistently over-performs by up to 5.4% while preserving logarithmic-time query complexity. In a complementary evaluation using an LLM-based judge, we find that many retrieved snippets not labeled as ground truth are still highly similar to the expected sources, particularly with longer context windows, and thus remain useful for end users. Overall, our results demonstrate that integrating vector search with fingerprinting enables scalable, high-precision provenance tracking for code produced by LLMs.

I. INTRODUCTION

LLMs can reproduce training code, complicating attribution and license compliance as datasets reach billions of samples. HST addresses this by combining scalable vector retrieval with Winnowing-based exact matching.

LLMs may memorize and reproduce training examples verbatim, paraphrased, or with reiterated ideas.
Linear-time fingerprinting becomes inadequate for provenance tracking across billion-scale code-training datasets.
HST is designed to provide likely source snippets and authorship information while retaining logarithmic search complexity.
HST first retrieves 100 similar snippets through vector search, then re-ranks them with Winnowing using syntactic hash matching.
The system targets both exact and adapted matches, including context adaptation simulated through frequent word replacement.

A. Contributions

The paper contributes a code-retrieval encoder and a two-stage provenance system designed to combine scalable search with fingerprint-based detection. Its evaluation considers exact, renamed, near-miss, and semantic clone settings.

SOURCETRACKER is a 300M-parameter model fine-tuned to retrieve complete code snippets from small fragments.
HST sequentially applies SOURCETRACKER and Winnowing while targeting logarithmic search complexity and practical scalability.
Code clone taxonomy: Type 1 clones are exact code copies differing only in whitespace, comments, or layout.
Code clone taxonomy: Type 2 clones preserve syntax while changing identifiers, literals, types, or function names for domain adaptation.
Code clone taxonomy: Type 3 and Type 4 clones represent progressively broader modification, from changed statements to equivalent functionality with different syntax.

B. Winnowing and the MOSS engine

Winnowing provides the paper’s fingerprint-based plagiarism-detection baseline and the exact-match refinement stage of HST. MOSS uses indexed fingerprints to limit candidates before exact similarity re-ranking.

Winnowing selects representative hashes that remain robust to minor syntactic and formatting changes.
The algorithm canonicalizes code, forms overlapping k-grams, hashes them, and retains minimum hashes from sliding windows as fingerprints.
MOSS engine: MOSS stores document fingerprints in an inverted index and prioritizes rare query hashes to build compact candidate sets.
Evaluation targets: Type 1 and Type 2 clones are used to represent verbatim replication and identifier-changing domain adaptation in LLM-generated code.
HST integration: HST combines vector-database retrieval with Winnowing to address large-dataset retrieval while preserving fingerprint-based refinement.

A. Dataset

The study uses a 10-million-snippet THESTACKV2 subset and trains an encoder to retrieve full snippets from fragments. Vector indexing with HNSW supports logarithmic search relative to dataset size.

Dataset: The dataset contains 10,000,000 randomly sampled THESTACKV2 code snippets, with fragments tied to their original complete snippets.
Encoder: The encoder is fine-tuned to retrieve syntactically similar complete snippets from small code fragments through vector representations.
Encoder: SOURCETRACKER uses the first nine MoSE layers, totaling 300M parameters, to produce 1024-dimensional document vectors.
Training: Training uses CLIP loss to increase cosine similarity for matching fragment-snippet pairs and decrease it for nonmatching pairs.
Vector search: Qdrant uses HNSW approximate nearest-neighbor retrieval with average search complexity O(log N).
Baseline: The Winnowing baseline uses k = 5, w = 4, truncated SHA-1 hashes, and a retrieval budget of 64 hash inspections per query.

D. HYBRIDSOURCETRACKER (HST)

HYBRIDSOURCETRACKER combines fast vector retrieval with Winnowing-based re-ranking to preserve fine-grained similarity assessment while scaling logarithmically. It returns likely source snippets and associated metadata for provenance tracking.

HST sequentially combines SOURCETRACKER with Winnowing to improve code-similarity evaluation.SOURCETRACKER accelerates the first lookup phase, while Winnowing provides fingerprint-based re-ranking.
Top-100 vector candidates are retrieved by cosine similarity in logarithmic time, leaving the second stage with constant-time analysis.The reduced candidate set preserves the overall logarithmic complexity.
Winnowing re-ranks the candidates using Jaccard similarity over shared fingerprints for finer-grained similarity assessment.This token-level comparison improves ranking and detection efficacy.
The two-stage design balances high-speed coarse detection with exact token-level comparison and retrieval performance.
HST produces ranked likely-original snippets that can be paired with authorship or licensing metadata.The retrieved sources may have been adapted before generating the output.
The evaluation varies dataset size, window length, and clone type while comparing HST with Winnowing alone and SOURCETRACKER.Dataset sizes range from 1000 to 100 000 samples, and window lengths range from 7 to 480 tokens.

A. Evaluation metrics

The evaluation uses Recall@N and MRR to measure whether relevant snippets are retrieved and how highly the first relevant result is ranked. Figure 3 compares first-stage retrieval performance between SOURCETRACKER and Winnowing across dataset sizes and clone variants.

1) Recall@N: Recall@N measures the fraction of queries with at least one relevant item among the top-N retrieved results.Higher Recall@N indicates that an original snippet appears within the top-N candidates.
1) Recall@N: Figure 3 reports SOURCETRACKER at R@100 and Winnowing at R@1, averaged across dataset sizes from 1000 to 100 000 samples.Solid lines represent exact-match variants, while dashed lines represent alwaysreplacement variants.
1) Recall@N: SOURCETRACKER consistently matches or exceeds Winnowing in the plotted first-stage retrieval comparison.The comparison is intended to determine how many candidates HST should retrieve initially.
2) Mean Reciprocal Rank (MRR): MRR measures the average reciprocal rank of the first relevant result across queries.Higher MRR corresponds to higher-ranked relevant matches, which are desirable for authorship attribution.

B. Baselines

The baselines show that performance depends on window and dataset size, while HST combines vector retrieval with Winnowing to retain accuracy at scalable search complexity.

Below 15 tokens, both baselines perform poorly, while Winnowing is more resilient to larger search spaces and smaller windows.
SOURCETRACKER performs on par or better than Winnowing for windows exceeding 60 tokens, whereas Winnowing is more robust across smaller windows and larger datasets.
HST sequentially applies SOURCETRACKER retrieval and Winnowing re-ranking to combine efficient lookup with fingerprint-based effectiveness.
At windows of at least 30 tokens, HST matches Winnowing, and above 60 tokens both HST and SOURCETRACKER outperform Winnowing.
HST maintains logarithmic complexity because Qdrant retrieves a constant top-100 candidate set before Winnowing re-ranks it in constant time.

D. The OLMOTRACE solution

OLMOTRACE provides logarithmic-time exact matching, but its verbatim dependence limits contextual retrieval for longer fragments. The comparisons therefore emphasize HST’s stronger performance beyond short windows and the difficulty of interpreting judge-based errors.

OLMOTRACE uses suffix arrays, maximal span detection, and BM25 ranking to provide scalable logarithmic-time exact matching.
HST matches or exceeds baseline performance for windows larger than 30 tokens while retaining logarithmic-time retrieval through Qdrant indexing.
OLMOTRACE performs strongly at 7-token windows but struggles with larger fragments because verbatim matching misses contextual similarity.
Longer context windows improve LLM-judge ratings for retrieved non-ground-truth snippets, with average ratings increasing from 1.3 to 2.6.
For 7-to-30-token true contexts, the judge more often assigns 4 out of 5, making similarity assessment less reliable.

VI. DISCUSSION

HST combines Winnowing’s detection strength with vector retrieval to improve scalability, with the strongest retrieval results appearing for longer fragments. The discussion also emphasizes that evaluation should account for useful near-matches and that applicability depends on access to suitable training data.

Method: HST integrates a fine-tuned encoder with Winnowing, combining logarithmic-time retrieval with fingerprint-based re-ranking.The encoder narrows the search before Winnowing refines candidates.
Performance: ≥30-token windows yield the best combined efficacy and efficiency for the sequential HST approach.
Performance: SOURCETRACKER is particularly effective beyond 120 tokens, whereas Winnowing remains more robust for small windows and large datasets.Longer contexts provide richer semantics for encoder-based retrieval.
Performance: For windows larger than 60 tokens, HST outperforms Winnowing alone while retaining both methods’ representation capabilities.
Evaluation: Identifier replacement degrades performance mainly for snippets outside the ground truth, motivating evaluation beyond exact ground-truth matches.
Limitations: The approach requires a suitable, accessible training set, and the evaluation argues for combining ground-truth results with related-suggestion quality.

VII. RELATED WORK

Related work establishes that LLMs can memorize, reproduce, and be judged for similarity to training data, while prior studies motivate scalable provenance tracking for code authorship attribution. The paper distinguishes its focus by targeting code and billion-scale evaluation requirements.

LLM plagiarism: LLMs may reproduce training data verbatim, paraphrase it, or repeat underlying ideas, creating plagiarism and copyright concerns for generated code.
Memorization: Prior work links memorization to model capacity, duplication frequency, and context length, with discoverability depending on revealing inputs.
Detection methods: LLM-based judges have achieved above-80% binary plagiarism-classification accuracy on a corpus covering verbatim, paraphrase, and summary cases.
Research scope: This study focuses on identifying similarities between LLM outputs and training data for code authorship attribution rather than efficacy alone.
Research scope: Efficient provenance tracking must address training corpora containing billions of files, where exhaustive comparison becomes impractical.

B. Code plagiarism detection and clone detection

Code plagiarism detection has traditionally relied on effective fingerprinting, but linear scaling and sensitivity to adaptation limit its use on modern LLM corpora. HST addresses this tension by combining vector retrieval with Winnowing and presenting likely source snippets to users.

Fingerprinting: Winnowing selects representative fingerprints that remain robust to minor syntactic or formatting modifications.
Scalability: Winnowing-based systems operate linearly with dataset size, which becomes a bottleneck as LLM training corpora exceed billions of samples.
Provenance quality: Existing code-generation systems can provide many non-relevant provenance links, with Gemini producing up to 48% unrelated links in one analysis.
Prior scalable retrieval: Prior infinity-gram retrieval achieved logarithmic query complexity and traced outputs against 4.6 trillion training tokens, but relied on verbatim matches.
Hybrid approach: HST combines vectorial lookup with Winnowing to retain fingerprinting effectiveness while achieving logarithmic search complexity and reducing sensitivity to noise.
Application: HST searches the training corpus after generation and presents similar snippets with metadata such as authorship information, subject to training-data access.

A. Future work

Future work calls for broader, standardized evaluation beyond the current 10M-snippet study and its Type-1 and Type-2 clone focus. Proposed directions include harder clone categories, adaptive fragmenting, richer similarity objectives, and shared benchmarks.

Scope: The current evaluation uses a 10M-snippet dataset and search spaces up to 100k documents, leaving broader validation open.
Clone coverage: Future evaluations should include Type-3 near-miss clones and, where feasible, Type-4 semantic clones beyond verbatim and identifier-renamed fragments.
Fragment design: Adaptive window sizing based on code characteristics and semantically meaningful units such as functions or basic blocks could improve robustness.
Evaluation objectives: LLM-judge results motivate ranking by graded similarity or semantic relatedness rather than exact ground-truth recall alone.
Benchmarking: Standardized benchmarks should cover multiple languages, Type-1 through Type-4 modifications, realistic LLM samples, and evaluation at scale.
Reproducibility: SOURCETRACKER weights and the replication package are publicly available, while THESTACKV2 access remains subject to dataset-license terms.