Embedding watermarks in AI-generated text

Factual Questions
61

Given the mind numbing size of the systems implementing these LLMs, storing everything they output would probably be a drop in the ocean. Since the AI companies train new systems in part based on previous user interactions, they probably already store everything. The trick would be searching it for close matches. Something the AI systems should be good at.

Hashing as we usually understand it wouldn’t work as one of the key features of hash algorithms is that they produce wildly different output for even the smallest of changes. OTOH, some sort of semantic structure analysis probably would lead to a very reduced search space. Which is how one would imagine an AI based search would work.
It could end up with an internal categorisation system that breaks all the output into simple classes. There are only so many
Dear John or
Dear esteemed Professor, I hope this finds you well. Please can I have more marks so I can pass this subject.
letters that have any meaningful difference.

62

I think AI LLM output already dwarfs the public Internet in size. You would need a search engine bigger than Google to do the look-ups.

63

One of the current ads shows someone reading his phone verbatim for a eulogy at a funeral, and he reads the line “should I say something serious here or insert a joke here to lighten the mood?”. Plently of anecdotes about people forgetting to remove prompts and LLM questions from their submitted essays. So presumably if someone actually reads the LLM output and simply deletes these giveaway sequences, the resultant text will not hash to the same as the original output.

The watermarking video was quite instructive, but as I noted - presumably the LLM continues learning and its weighting changes over time - so the same output “colours” may be different over time. Another issue is that if too much of the internet is becoming AI slop, then the LLMs are eating their own tail and poisoning the weightings. Plus, changing words will change the score for the LLM test, so there is not so much an absolute as a confidence level - this output is 97% likely to be AI. And then there’s the issue (as mentioned in a previousl post) that testing a string of text means the test goes essentially through the same calculation as the original composition each time, compunding the amount of computaion power a text could consume over its lifetime - particularly if each LLM has a different key and text weighting. And interesting test (if possible) would be to see how close each LLM word probablity is to competing models for a large random assortment of text.

64

The detector doesn’t have to re-run the LLM. Instead, for each word, it hashes the previous text and the secret key, then determines if the next word is a green or red word. The detector’s score is the based on how many green and red words are in the text.

This works across LLMs as long as:

  • they are using the same algorithm (e.g. synth-id)
  • they are using the same secret key
  • they are using the same tokenizer
65

Isn’t determining the score for each word exactly what the LLM does too? The detector would just remember the score, while the origianl composition would add that word to the text. Instead of “what words score - add that one” it’s what words score - was this one green in that?" Not a lot different computation.

AI companies would probably love this system if they get to charge by the megaFLOP.

66

(Jumping in here late, so excuse me if I missed some context from earlier).

The watermark happens in a different phase than the LLM generation. The inference itself, the part where the LLM searches its massive dataset to finish your sentence, is the expensive part. Adding the watermark to it afterward, comparing a few close synonyms to each other, is trivially cheap, like < 1% of the inference cost. (And inference itself is much cheaper than the initial training).

When you ask it a question like “How do I do this thing?”, it has to spend seconds (or minutes) coming up with a sentence like “To do this thing, you have to first put the thingamabob in the juicer, then flick your wrist towards Jupiter in order to summon the friendly mollusc.”

For each word in that sentence, some words are more “important” to the final answer — “Jupiter”, for example, could not have any reasonable synonyms. Exchanging it for “Saturn” might summon an angry bird instead. Thus, that’s not a good word for watermarking.

But in that sentence, many other words/phrases could be trivially replaced. “To do this…” could also be “In order to…” or “To start…”, etc. “Towards” could be “in the direction of” or “at”. These low-importance synonyms could each have their own scores:

  • “To do this” might be 44.1% preferred
  • “In order to” might be 43.9% preferred

All the watermarking algorithm has to do is to weight and bias those two choices against each other, per its secret internal list. Maybe it gives “In order to” a secret 20% boost. But it’s only ever looking at those synonyms against each other, not re-generating scores against the whole giant LLM training data. It does that over and over again across the whole sentence/paragraph/document. That entire process takes mere milliseconds.

And by the end (for a sufficiently long text), it is statistically almost impossible to have a false positive where a watermarked text was mis-identified as such; a person not having access to the secret list would not be able to know ALL the particular synonyms pairs that get secretly weighted. They might be able to guess one or two, by sheer dumb luck, but not hundreds of them across a whole document.

They already charge by the FLOP… that’s what usage-based, per-token pricing is. But watermarking is nearly free. Inference of a single word would cost a lot more than watermarking an entire document… by several orders of magnitude.

  • It is VERY expensive to train the LLM model to begin with
  • Inference (using that trained model to predict next words) is still pretty expensive
  • Adding a watermark to one synonym out of 10, based on a preexisting secret list, is trivially cheap (pretty much free) in comparison
67

Each model has a vocabulary of words (for example 256000 words). When the LLM wants to generate the next word, it calculates the probability for each word in the vocab. The output of the LLM is a list of 256000 probabilities (these are called logits). Most of these are near zero.

After the LLM, there is regular old software that picks one of these words to use. This is called sampling.

There’s lots of ways to do this:

  • greedy: you could always pick the word with the highest probability
  • random: you could pick a word at random, giving more weight to words with higher probability
  • top-k: you could only pick from the words with the highest probabilities
  • top-p: you could only pick from words that meet a minimum threshold probability
  • watermark: you could only pick from a subset of the words, where the subset is determined by a cryptographical algorithm

Or, more likely, some combination of these.

The neat thing about the watermark algorithm is that it only needs to consider the sampling phase – the software part and not the LLM part. Specifically, it only needs to consider which words are allowed (green) and which are not (red).

The algorithm to determine the list of green and red words can be complicated, it can use the previous words, and it can use a secret key, but it won’t end up being computationally expensive – certainly not compared to an LLM.

It’s been a while since I read the synth-id paper and the details of the tournament scoring are fuzzy, but the detector basically works the same way.

I assume the EU requires the detector to be free?

A couple of footnotes:

  1. I use the term words, but really it is tokens.
  2. During the sampling phase you adjust the probabilities as well. The term temperature refers to whether you scale the probabilities closer together (more creative) or apart (less creative).
  3. There’s lots of other ways to do sampling. For example, if you expect the LLM to output a JSON stanza, you can filter out invalid words and force it to create valid JSON.
68
  1. LLMs don’t search datasets to finish sentences
  2. text watermarks are added during inference, not afterward (image synthID is a separate step)
69

The inference is just the portion that invokes the LLM. After that there is a sampling phase that includes the watermarking.

70

Yes, I should have been precise. What I meant was that it happens during generation. It is not the case that the text is generated and then a watermarking pass goes over the generated text as happens in SynthID watermarking for images.

71

I’m trying to follow along.

Is there a basic set of phases generative AI goes through from prompt to output? If I’m not even asking the question properly, let me know.

72

This is potentially very complicated because there are a lot of different components that may or may not be present. Generally when you’re interacting with Claude or ChatGPT there is a harness, a system prompt, tool calls, your prompt, the context window of the conversation, etc.

If we’re just talking about the LLM part then you have:

  1. your prompt text
  2. conversion to tokens. Models may share tokenizers or have bespoke tokenizers
  3. forward pass through the model (inference) outputs a probability distribution over next possible tokens given the context window
  4. A sampler chooses a next token. Crucially, this is not necessarily the most likely next token.
  5. Usually you’ll have multiple token rollouts and then the sampler will chose a rollout vs just a the next token.
  6. Potentially “chain of thought” where the model’s internal prompt makes it question the rollout, refine itself, etc.
  7. Convert tokens to text and display to the user

eta watermarking would happen in steps 4 or 5 by upweighting tokens the watermarking algorithm prefers vs just what a base sampler would prefer.

73

Possible? Maybe. But not worth a damn. Watermarking is meant to be robust against heavy modification. You can take a watermarked image and crop it, stretch it, and saturate it, and it’ll still match the SynthID. Even a single pixel’s difference would cause a hash to change. There’s no point in storing a hash list, since the whole idea is to detect AI creations even if they’ve been modified.

74

But the question here is about text, not images.

75

Images and text are all just bytes. The entire point of a hash as we generally use them is to avoid clashes. A good hash function is such that a change of a single bit results in a hash that has no identifiable correlation with the hash of the original.

This doesn’t mean that a hash function could not be created that somehow encodes text into something with useful correlations. It just isn’t what is conventionally used as a hash. The difficulty is that whilst a conventional hash simply tries to create a nearly unique small fingerprint from the source, something that manages to hold information about the source is clearly constrained by the information available in the size of the hash. Even the most aggressive lossy compression algorithms are going to struggle to do anything useful. Something akin to a compression algorithm might yield a way of performing a preselection of recorded texts and thence to look for almost but not quite the same texts with a more brute force search. Which is why I was suggesting what would eventually become a huge list of every type of output text the AI has generated. (Given the number of “Dear esteemed professor” emails, clearly AI written, I used to get, they will almost certainly get their own category number.)

A conventional hash is great for deciding that two things are definitely not the same, or deciding that they are almost certainly exactly the same. Clashes in hashes is inevitable, so the next step is to always do a bytewise comparison to be sure. Different hashes are guaranteed to be from different sources.
Utility in detecting that two things are almost but not quite the same not so much.

76

Thank you. Sorry, I should’ve been too — I was describing it too loosely, for ease of understanding, but that just muddies the water even more. My bad on that, and thank you for the clarifications.

77

Yeah, that’s what I was trying to get at by saying “some sort of hash”. The conventional sorts of hashes probably wouldn’t be too much use, but it might be possible to come up with something hash-like that would work.

78

Hashes can be very sensitive to small edits, though. I think that’s the brilliance of the watermarking.

79

Also the watermark signal is in the data stream. There’s no massive database to maintain.

BTW, that was a nice summary of the stages of processing @Snarky_Kong

80

Right but it’s the same concept. The watermark needs to resist manipulated text. A hash is destroyed the second a person adds an extra space somewhere or even an invisible character. A watermark is distributed across the entire text. The user would have to change hundreds or thousands of tokens, depending on the size of the text, to defeat the watermark, and if they mutilated 95% of the text but left the other 5% alone, it would still be detected in that 5%.

A hash would be the weakest way to watermark text. The term of art is “fragile.” Fragile watermarks have their purposes, but it’s the opposite - to prove something is an unaltered original. The goal of the watermark is to prove it’s the “original” (i.e., an AI work) even if it’s been heavily altered.

Think of it this way. A hash lookup is like Alice saying to Bob “tell me the secret code phrase we agreed upon 20 years ago that means you’re who you say you are and that you’re not being followed.” If anything happened to Bob, in any way, he wouldn’t say the phrase. A watermark is like Alice identifying Bob by his dental records - it’s meant to work no matter what “they” did to Bob.