🔢 mathematics

LLM-Text Watermarking based on Lagrange Interpolation

This paper proposes a robust LLM text watermarking scheme that embeds author identity as $f(x)$ values corresponding to pseudorandomly generated $x$ -coordinates on a straight line, enabling the recovery of multi-bit author information even after heavy adversarial redaction by solving the Maximum Collinear Points problem.

Original authors: Jarosław Janas, Paweł Morawiecki, Josef Pieprzyk

Published 2026-02-27

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jarosław Janas, Paweł Morawiecki, Josef Pieprzyk

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 have a magical pen that can write perfect stories, essays, or emails. This pen is an AI (specifically, a Large Language Model). It's so good at writing that it's becoming hard to tell if a human wrote a story or if the AI did.

This creates a problem: How do we know who (or what) wrote a piece of text? Is it a real person, or is it a robot trying to spread fake news or steal credit?

The authors of this paper, Jarosław, Paweł, and Josef, have invented a clever way to hide a secret signature inside the AI's writing. They call this a "watermark," but instead of a visible stamp, it's a hidden mathematical pattern.

Here is how their method works, explained with simple analogies:

1. The Secret Recipe: Drawing a Straight Line

Imagine you and a friend have a secret code. You decide that your secret signature is a straight line drawn on a giant piece of graph paper.

The line follows a simple rule: $y = ax + b$.
The numbers $a$ and $b$ are your secret key (the watermark).

In the real world, you can't just draw on the text. So, the authors use a trick:

They pick random spots on the graph paper (these are the x-coordinates).
They calculate where the line should be at those spots (the y-coordinates).
They then hide these coordinates inside the AI's writing.

2. Hiding the Clues: The "Green and Red" Tokens

How do you hide a number in a sentence? You do it by slightly nudging the AI's choices.

Imagine the AI is about to write the next word. It has a list of 50,000 possible words it could choose.

The secret code says: "For this specific moment, if the hidden number is 0, pick a word from the Red list. If it's 1, pick a word from the Green list."
The AI doesn't know it's doing this; it just thinks it's choosing a word that fits the context. But because the authors "tilted the scales" (biased the probabilities), the AI is slightly more likely to pick a word from the correct list.

By doing this for many words, they embed a long string of 0s and 1s that, when decoded, reveals the coordinates of points on that secret straight line.

3. The Detective Work: Finding the Line

Now, imagine a detective (the verifier) receives the text. They don't know the secret line, but they have the secret key to find the "x" spots.

Reconstruct: They look at the words, decode the "Green/Red" choices, and get a bunch of points $(x, y)$ .
The Problem: Because the AI is a bit random, and because a bad guy might try to edit the text (delete words, swap words), some of these points will be wrong. They will look like scattered dots all over the graph paper.
The Solution (The Magic Trick): The detective looks for the longest straight line that passes through the most dots.
- Even if 50% of the dots are scattered noise (fake points), the real secret line will still have the most dots sitting on it.
- This is called the Maximum Collinear Points problem. It's like looking at a messy room full of confetti and finding the one straight line of marbles that someone carefully placed.

Once they find that line, they can read the equation ($y = ax + b$). The numbers $a$ and $b$ are the watermark, proving who wrote the text.

Why is this special?

It's Robust: If a bad guy tries to edit the text (delete a paragraph, change a few words), they might destroy some of the "dots." But as long as enough dots remain to form the straight line, the watermark survives. It's like trying to erase a straight line drawn on a foggy window; if you wipe away a few spots, the line is still visible.
It's Fast: Finding the line is a math problem computers can solve very quickly, even for long texts.
It's Invisible: The text still reads perfectly naturally. Humans can't tell the difference.

The Analogy of the "Broken Puzzle"

Think of the text as a puzzle. The authors have hidden a few special puzzle pieces that, when put together, form a straight stick.

Normal text: Just a pile of random puzzle pieces.
Watermarked text: A pile of random pieces, but with a hidden stick made of special pieces.
The Attack: A hacker tries to smash the puzzle or swap pieces.
The Defense: Even if the hacker breaks the puzzle, as long as they don't break every single piece of the stick, you can still find the stick and prove it was there.

Summary

This paper proposes a way to stamp AI text with a hidden, mathematical "straight line" signature. Even if someone tries to scrub the text clean, the signature is so resilient that the "line" will still stand out among the noise, allowing us to prove, "Yes, this text came from an AI, and here is the proof."

1. Problem Statement

The rapid adoption of Large Language Models (LLMs) has created a critical need for text attribution. As LLMs generate human-like text, it becomes increasingly difficult to distinguish between human and machine-generated content. This poses risks regarding:

Misinformation and Fake News: Attributing false narratives to specific sources.
Plagiarism: Users claiming AI-generated content as their own.
Accountability: The inability to trace text back to a specific user or model instance in high-stakes domains (e.g., journalism, education).

Existing watermarking techniques often struggle with robustness against adversarial editing (e.g., token substitution, insertion, or deletion) or require complex model retraining. The authors aim to develop a training-free, model-agnostic scheme that can embed a multi-bit watermark and recover it even if the text is partially tampered with.

2. Methodology

The proposed scheme encodes a watermark as the coefficients of a polynomial over a finite field and embeds a sequence of points lying on this polynomial into the generated text.

A. Core Concept: Lagrange Interpolation & Collinearity

Watermark Representation: The watermark $W$ is represented as coefficients $(a_0, a_1)$ of a linear function $f(x) = a_1x + a_0$ over a Galois Field $GF(2^n)$ .
Embedding Strategy:
1. Point Generation: The system generates pseudo-random $x$ -coordinates using a hash of the previous token and a secret key.
2. Y-Coordinate Calculation: It computes $y = f(x)$ , which yields an $n$ -bit value.
3. Token Biasing: For each bit of the $y$ -value, the vocabulary is pseudo-randomly split into two sets ( $V_0$ for bit 0, $V_1$ for bit 1). The LLM's logits are biased to prefer tokens from the set corresponding to the bit value.
4. Sequence: This process repeats, embedding a stream of points $(x_i, y_i)$ that all lie on the line $f(x)$ .
Extraction Strategy:
1. Point Recovery: The verifier regenerates $x$ -coordinates using the same hash function and secret key. It attempts to recover $y$ -coordinates by checking which vocabulary set the generated tokens belong to.
2. Noise Handling: Due to sampling stochasticity and adversarial edits, some recovered points will be incorrect (spurious).
3. Maximum Collinear Points (MCP): The verifier treats the recovered points as a 2D dataset and solves the Maximum Collinear Points problem to find the line passing through the largest number of points.
4. Reconstruction: Once the dominant line is identified, Lagrange Interpolation is applied to the points on that line to recover the coefficients $a_0$ and $a_1$ , thus retrieving the watermark.

B. Bit Correction Mechanism

To mitigate bit-level noise (where a token is sampled from the wrong set), the authors introduce a lightweight bit-correction step. During extraction, the algorithm enumerates candidate $y$ -values within a small Hamming radius of the recovered bits. This trades a small amount of runtime for significantly improved recall, ensuring valid points survive verification.

3. Key Contributions

Training-Free & Model-Agnostic: The method does not require retraining the LLM or modifying its weights; it operates solely at the logit level during inference.
Multi-Bit Watermarking: Unlike binary watermarks (watermarked vs. not), this scheme embeds a payload of $2n$ bits (e.g., 16, 24, or 32 bits) by encoding them as polynomial coefficients.
Robustness to Partial Editing: By framing the problem as finding the "best fit" line among noisy data (MCP), the scheme can recover the watermark even if a significant fraction of the embedded points are corrupted or deleted, provided enough valid points remain collinear.
Theoretical Security Analysis:
- The authors provide a probabilistic upper bound (Theorem 1) on the likelihood of random points forming a collinear line (false positives) in $GF(2^n)^2$ .
- They derive design guidelines for field size ( $n$ ) and block length to ensure the False Positive Rate (FPR) remains below a desired threshold (e.g., 1%).
Scalability: The extraction algorithm (MCP) has a time complexity of $O(N^2)$ , which is efficient for typical text lengths and scales predictably.

4. Experimental Results

The authors evaluated the scheme using Llama 2-7B, Llama 3.2, and Mistral 7B models on the OpenGen, Essays, and HC3 datasets.

Performance vs. State-of-the-Art:
- The method achieved match rates comparable to top existing methods (e.g., ~98% for 16-bit watermarks).
- For 32-bit watermarks, the proposed method achieved 85.9% match rate, outperforming several baselines that dropped significantly or became infeasible (NA) due to exponential extraction time.
Adversarial Robustness:
- Substitution Attacks: The scheme showed high resilience. Since substitutions do not disrupt block alignment, the MCP algorithm could still identify the correct line despite bit noise.
- Insertion/Deletion Attacks: These are more damaging as they cause desynchronization (misalignment of blocks). While the scheme is not fully robust against heavy insertion/deletion, it tolerates a non-trivial level (up to 10% modification) before performance degrades significantly.
Efficiency: Extraction time was measured in fractions of a second on a single PC, even with bit correction enabled.
Text Quality: Using a logit bias of $\delta=6$ , the impact on text perplexity and human-perceived quality was found to be negligible, consistent with state-of-the-art findings.

5. Significance and Future Work

Significance: This work introduces a novel algebraic approach to text watermarking, leveraging finite field arithmetic and computational geometry (collinearity) to create a robust, multi-bit attribution tool. It bridges the gap between cryptographic security and practical NLP application.
Limitations: The current implementation focuses on linear functions ( $f(x)$ ). It is less robust against massive desynchronization (heavy paraphrasing or translation) and relies on the assumption that enough valid points survive to dominate the MCP search.
Future Directions:
- Higher-Degree Polynomials: Extending the scheme to use polynomials of degree $t-1$ to encode more complex structures (solving the Maximum Co-Polynomial Points problem).
- Multiple Lines: Embedding multiple lines to concatenate longer watermarks.
- Enhanced Robustness: Developing better synchronization mechanisms to handle insertion/deletion attacks more effectively.

In conclusion, the paper presents a mathematically rigorous and practically efficient watermarking scheme that offers a strong balance between security, capacity, and robustness, making it a viable candidate for real-world LLM attribution.