From AGI Friday's Nerd Interlude
The Pony Machine: An LLM Watermarking Allegory
How to encode a key bit — “watermark present” vs “no watermark” — into the output of a random distribution without changing that distribution. All the words in this interactive explainer are human-generated by Daniel Reeves.
- person
- special example person
- winner
- village resident
- below the cutoff
- village size
- —
- below cutoff
- —
- probability under pure chance
- —
-
Start with a thousand random people
Each person has a random 9-digit ID number. The magic machine will, perfectly fairly, pick a random subset of a hundred people to receive a pony. Everyone has a 1/10 chance of getting one.
-
People are initially sorted by bare ID number
Which is to say they're a big random smear.
-
Apply the secret transmutation of ID numbers and re-sort
The machine has a secret cipher mapping each digit of an ID number to a random digit.
Secret cipher wheel
Example
… → …
a particular person's ID number before and after applying the cipher
-
Select the lucky pony recipients
From the list of newly sorted-by-transmuted-ID people, give ponies to the first hundred people on that list. That's fair — their IDs and the transmutations were random. Key fact for later: those with the lowest transmuted IDs are the winners.
-
Off they go into the desert
The pony recipients go form a village in the desert where you encounter them. Did they come from the magic machine? Without the secret cipher their ID numbers appear totally random. But with the secret cipher the transmuted IDs are suspiciously low. How suspicious? Check out the evidence...
-
(Optional) have new people with ponies wander in an out
This is just to show how robust the watermark is. As long as the village has enough people from the pony machine, we can still detect that. Note that everyone has a pony regardless, we're just trying to tell if a given collection of pony owners came, in part, from the magic machine. (This, with major simplifications, is like seeing a collection of words and asking if an LLM was involved in choosing them.)
Have people wander in and out:
Evidence
- village size
- —
- below cutoff
- —
- fraction below cutoff
- —
- probability under pure chance
- —
expected by pure chance: 10%
- expected by chance
- randomly drawn villages
- our village
Villages drawn randomly (no pony machine) have ~10% of people with ID numbers below the cutoff. Our village has way more (unless the watermark gets washed out).
Climbing Mount Improbablemore probable → less probable
The Math
If the village were assembed by pure chance, the count of people with ID numbers below the cutoff would be X ∼ Binomial(n, 1/10). The probability of seeing this count equal to or greater than a particular k is:
P(X ≥ k) = Σi=kn C(n, i) · (1/10)i · (9/10)n−i
With village size n = — and number of people, k, below the cutoff = — we have p ≈ — that this could happen by chance. That p only needs to be 10-5 for you to be 99.999% sure the watermark is present.