🤖 AI

Efficient and Scalable Provenance Tracking for LLM-Generated Code Snippets

This paper introduces SOURCETRACKER and its hybrid two-stage pipeline, HYBRIDSOURCETRACKER, which combines vector search with classical fingerprinting to enable scalable, high-precision provenance tracking for LLM-generated code by efficiently identifying potential training sources within billion-scale corpora.

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

Published 2026-05-28

📖 5 min read🧠 Deep dive

CC BY 4.0

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

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 a chef who just created a delicious new dish. You want to know if your recipe was inspired by a specific cookbook, or if you accidentally copied a famous chef's work word-for-word. Now, imagine that instead of a human chef, the "cook" is a super-smart AI (a Large Language Model) that has read billions of cookbooks.

The problem is: if the AI copies a recipe, it often changes the names of the ingredients (like swapping "sugar" for "sweetener") or rearranges the steps slightly. Traditional methods of checking for plagiarism are like a librarian who has to read every single page of every single cookbook in the world to find a match. If the library has billions of books, this librarian would take years to find the answer.

This paper introduces a new, super-fast system called SOURCETRACKER and a two-step process called HYBRIDSOURCETRACKER (HST) to solve this problem. Here is how it works, using simple analogies:

1. The Problem: The "Needle in a Billion-Haystack"

The authors explain that AI models sometimes "memorize" parts of the data they were trained on. When they generate code, they might spit out a snippet that is almost identical to a piece of code from their training data, even if they changed a few variable names.

The Old Way (Winnowing): Imagine trying to find a specific sentence in a library of billions of books by reading every book from start to finish. It's accurate, but it's incredibly slow. If the library grows, the time it takes grows with it (linear time).
The New Challenge: Modern AI training sets are so huge (billions of snippets) that the old "read everything" method is too slow to be useful.

2. The Solution: A Two-Stage Detective Team

The authors created a hybrid system that acts like a two-stage detective team to find the original source of the code quickly and accurately.

Stage 1: The "Smart Sniffer" (SOURCETRACKER)

First, they built a specialized AI model called SOURCETRACKER. Think of this as a highly trained dog that can smell a specific scent.

Instead of reading every word, this model turns a piece of code into a "scent profile" (a mathematical vector).
It uses a high-tech database (Qdrant) that acts like a super-fast map. Instead of searching the whole library, the dog sniffs the air and instantly points to the top 100 most likely books that match the scent.
Speed: This step is incredibly fast, taking only milliseconds even with billions of books, because it uses a "logarithmic" search (like finding a book in a library by checking the index, then the shelf, then the book, rather than reading every page).

Stage 2: The "Forensic Examiner" (Winnowing)

Once the "Smart Sniffer" has narrowed it down to the top 100 candidates, the second detective steps in. This is the classic Winnowing algorithm.

Think of this as a forensic expert who looks at the top 100 books and checks the fingerprints on the pages.
It compares the exact structure of the code to see if it's a match, even if some words were changed.
Because it only has to check 100 books instead of billions, this step is also very fast.

3. The Results: Fast and Accurate

The paper tested this system on a massive dataset of 10 million code snippets. Here is what they found:

Short Fragments: If the code snippet is very short (like a single sentence), the "Smart Sniffer" isn't perfect, and the old "Forensic Examiner" (Winnowing) is still better at finding the exact match.
Longer Fragments: If the code snippet is longer (60 words or more), the Hybrid System (HST) actually performs better than the old method alone. It finds the right source more often while staying super fast.
The "Almost Right" Matches: The authors also used another AI to judge the results. They found that even when the system didn't find the exact original code (the "Ground Truth"), it often found code that was very similar. This is useful because it tells the user, "Hey, this code looks like it came from this family of code, even if it's not the exact original."

4. Why This Matters

The paper argues that for AI-generated code to be ethical and legal, we need to know where it came from.

Transparency: This system helps users see if their AI-generated code is just a copy of someone else's work.
Scalability: It proves that you can check for plagiarism in a library of billions of books in the time it takes to blink, rather than waiting years.

The Catch

The authors are honest about the limitations:

You need the library: To use this system, you must have access to the original training data (the library of books). If the AI was trained on secret data you can't see, you can't track the source.
Creative changes: If the AI changes the code too much (not just renaming variables, but completely rewriting the logic), the system might struggle to find the connection.

In summary: The paper presents a "Smart Sniffer" + "Forensic Examiner" team that can instantly scan billions of code snippets to find the original source of AI-generated code, balancing speed with high accuracy, especially for longer pieces of code.

Technical Summary: Efficient and Scalable Provenance Tracking for LLM-Generated Code Snippets

Problem Statement
The proliferation of Large Language Models (LLMs) for code completion and generation (e.g., Codex, CodeLlama, StarCoder) has introduced significant legal and ethical challenges regarding plagiarism and license compliance. LLMs can "recite" training data, reproducing code verbatim or with minor adaptations (e.g., identifier renaming) without attribution. While classical fingerprinting techniques like Winnowing (used in the MOSS system) are effective for plagiarism detection, they rely on linear-time search algorithms. This approach is computationally impractical for modern pre-training corpora, which often exceed billions of samples. Existing scalable solutions, such as infinity-gram retrieval, offer logarithmic time complexity but remain highly sensitive to noise and code adaptation, failing to detect non-verbatim similarities common in LLM outputs.

Methodology
The authors propose HYBRIDSOURCETRACKER (HST), a hybrid two-stage provenance-tracking pipeline designed to balance scalability with high detection accuracy. The system integrates vector database retrieval with traditional fingerprinting:

SOURCETRACKER (Stage 1): A 300M-parameter bidirectional encoder, fine-tuned using Contrastive Language-Image Pre-training (CLIP) loss. The model is trained to align the vector representations of small code fragments with their corresponding complete source snippets. It utilizes a dataset of 10 million code snippets from THESTACKV2. During training, the model is exposed to both verbatim copies (Type 1 clones) and "adapted" fragments where frequent identifiers are probabilistically replaced with random strings (Type 2 clones) to simulate domain adaptation.
- Retrieval: At inference, a code fragment is encoded and queried against a Qdrant vector database (using HNSW indexing) to retrieve the top 100 most similar candidate snippets. This stage operates with logarithmic time complexity ( $O(\log N)$ ) relative to the dataset size.
Winnowing Re-ranking (Stage 2): The top 100 candidates retrieved by SOURCETRACKER are subjected to the Winnowing algorithm. This stage generates syntactic fingerprints (hashes) for the candidates and the query fragment, re-ranking them based on exact Jaccard similarity of their fingerprint sets. By limiting the Winnowing process to a fixed-size candidate set (100 items), the overall system maintains logarithmic time complexity while leveraging the noise resilience of fingerprinting.

Key Contributions

SOURCETRACKER Model: The release of a 300M-parameter encoder specifically fine-tuned to retrieve complete code snippets from small fragments, capable of handling both verbatim and adapted code.
HST Pipeline: The introduction of a hybrid methodology that sequentially combines vector search and Winnowing. This approach provides theoretical guarantees of logarithmic search time complexity while achieving detection performance comparable to, or exceeding, traditional fingerprinting methods.
Dual Evaluation Framework: The paper employs a dual evaluation strategy:
- Ground Truth Metrics: Using Recall@N and Mean Reciprocal Rank (MRR) against a known subset of THESTACKV2.
- LLM-Based Judge: Utilizing an LLM (Qwen3 Coder) to assess the semantic similarity of retrieved snippets that were not ground truth, acknowledging that "errors" in strict retrieval may still represent relevant sources of inspiration.

Results
The system was evaluated on a 10M-snippet subset of THESTACKV2, with search spaces ranging from 1,000 to 100,000 samples.

Performance vs. Window Size: For small fragments (≤30 tokens), Winnowing alone remains highly effective. However, for window sizes ≥60 tokens, HST and SOURCETRACKER consistently outperform Winnowing alone, with HST showing up to a 5.4% improvement in Mean Reciprocal Rank (MRR).
Scalability: While Winnowing exhibits linear time complexity, creating a bottleneck for large datasets, HST maintains logarithmic complexity. Extrapolated results suggest query latencies remain in the millisecond range even for datasets containing billions of samples.
Robustness: The hybrid approach demonstrates resilience to identifier renaming (Type 2 clones). The LLM-based judge evaluation revealed that even when the system fails to retrieve the exact "golden" source, it often retrieves snippets with high semantic similarity (scoring 2.0–2.6 on a 5-point scale for larger windows), suggesting the system identifies relevant influences even when exact matches are obscured.
Comparison with OLMOTRACE: The authors found that while OLMOTRACE (a suffix-array based approach) is efficient, it struggles with context windows larger than 15 tokens, failing to capture contextual similarities that HST successfully identifies.

Significance and Claims
The paper claims that integrating vector search with fingerprinting enables scalable, high-precision provenance tracking for code produced by LLMs. The authors argue that this approach addresses the critical need for transparency and ethical attribution in software development.

However, the authors remain modest regarding the limitations and broader implications:

Dependency on Training Data: The system's applicability is contingent on the availability of the specific training dataset used to generate the code.
Nature of "Errors": The paper highlights that retrieved snippets not labeled as ground truth may still be highly similar to the source, suggesting that strict ground-truth evaluation might underestimate the system's utility for end users seeking sources of inspiration.
Call for Transparency: The authors conclude that relying solely on the internal memorization tendencies of LLMs is precarious. They advocate for the release of training datasets and their underlying sources as a de facto requirement for enabling effective provenance tracking and authorship attribution.