Can we Watermark Low-Entropy LLM Outputs?

Probleemstelling

De opkomst van Large Language Models (LLMs) heeft de noodzaak vergroot om AI-genererde content te kunnen onderscheiden van menselijke content. Een veelbelovende aanpak hiervoor is watermerking: het onopmerkelijk inbedden van een verborgen code in de output van een LLM.

Bestaande methoden voor onopmerkelijke watermerking (zoals Christ et al. [CGZ24, CG24] en Golowich et al. [GM24]) hebben echter een fundamentele beperking: ze vereisen dat de output van het LLM een hoge entropie heeft.

• Ze gaan er vaak van uit dat een constant fractie van de tokens een empirische entropie heeft van minimaal $O(\log |T|)$, waarbij $|T|$ de grootte van het token-alfabet is.
• In de praktijk genereren LLMs echter vaak tekst met lage entropie (bijvoorbeeld vaste zinspatronen, herhalingen of voorspelbare antwoorden), waarbij de entropie per token slechts een constante (bijv. 1 bit) kan zijn.
• Bestaande schema's falen in dit lage-entropie regime, omdat ze afhankelijk zijn van een groot alfabet of specifieke verdelingsaannames die in realistische scenario's niet gelden.

Het centrale vraagstuk van dit paper is: Kunnen we een onopmerkelijk en robuust watermerkschema construeren voor LLM-outputs met een groot token-alfabet, zelfs wanneer de per-token entropie slechts een kleine constante is?

Methodologie

De auteurs presenteren een nieuw framework dat een "tussenweg" vormt tussen eerdere werken die werken met binaire tokens en die met grote alfabetten. De kern van hun aanpak is als volgt:

1. Hashing van Tokens: In plaats van tokens direct te vertalen naar binaire bits (wat de entropie-eisen verhoogt) of een groot alfabet Pseudorandom Code (PRC) te gebruiken (wat ook hoge entropie vereist), hashen de auteurs elke output-token naar een enkel bit ($0$ of $1$) met behulp van een willekeurige hash-functie $h: T \to \{0, 1\}$.
2. Inbedding in Hash-waarden: Ze embedden een binaire Pseudorandom Code (PRC) codewoord in de reeks van gehashte bits.
   • Het schema genereert twee onafhankelijke steekproeven ($t_0, t_1$) uit de verdeling van het LLM.
   • Als $h(t_0) \neq h(t_1)$ ("succes"), wordt de token gekozen die overeenkomt met het te embedden bit van de PRC.
   • Als $h(t_0) = h(t_1)$ ("mislukking"), wordt een willekeurige token gekozen, wat een fout introduceert in het watermerk.
3. Blokbased Hashing: Om robustheid tegen deleties (verwijderingen) te garanderen, wordt niet voor elke token een nieuwe hash-functie gebruikt. In plaats daarvan wordt de output opgedeeld in blokken, en wordt voor elk blok één hash-functie hergebruikt voor alle tokens in dat blok. Dit maakt het mogelijk om blokken onafhankelijk te decoderen, zelfs als tokens zijn verwijderd.
4. Minimal Empirical Entropy: Het schema vereist slechts dat een constante fractie van de tokens in een voldoende lange substring een empirische entropie van 1 bit heeft. Dit is een veel zwakkere voorwaarde dan de eerdere $O(\log |T|)$ eis.

Belangrijkste Bijdragen en Resultaten

De auteurs construeren watermerkschema's die onopmerkelijk (computationeel onderscheidbaar van de originele output) en robuust zijn tegen diverse aanvallen, zelfs bij lage entropie.

1. Robuustheid tegen Random Substituties:

• Resultaat: Er bestaat een schema dat robuust is tegen een fractie van $(1/2 - \epsilon)$ willekeurige substituties.
• Aannames: Gebaseerd op de sub-exponentiële hardheid van het LPN-probleem (Learning Parity with Noise), dezelfde aanname als in eerdere werken.
• Voorwaarde: Alleen minimale empirische entropie (1 bit) is vereist.

2. Robuustheid tegen Random Substituties en Deleties:
De auteurs bieden twee routes voor robuustheid tegen deleties:

• Route A (Heuristische Aannames): Onder de aanname dat de output "natuurlijk" is (d.w.z. de fouten door het inbeddingsproces en substituties kunnen gemodelleerd worden als een binair symmetrisch kanaal), kan het schema robuust zijn tegen substituties en deleties. Dit generaliseert de "sufficiently variable" aanname uit eerdere werken.
• Route B (Zonder Heuristische Aannames): Als er een PRC bestaat die robuust is tegen adversariële substituties en random deleties, kan het schema robuustheid garanderen zonder extra aannames over de outputverdeling. De auteurs verwijzen naar recente werken ([CGG+25]) die dergelijke PRC's construeren (hoewel de tolerantie voor edits klein is).

3. Robuustheid tegen Adversariële Edits (Inserties/Deleties):

• Door te leunen op de PRC-construktie van [CGG+25] (gebaseerd op "permuted codes"), construeren de auteurs een schema dat robuust is tegen een constante fractie van willekeurige edits (inserties en deleties), zelfs bij lage entropie.
• Beperking: Voor deze vorm van robuustheid moet een groter deel van de totale output voldoende entropie hebben (niet slechts een substring), omdat een adversaryel de lage-entropie delen specifiek kan targeten.

Vergelijking met Bestaand Werk

Kenmerk	[CG24]	[GM24]	Dit Werk
Token Alfabet	Binaire vertaling	Groot alfabet	Groot alfabet
Entropie Vereiste	$O(\log |T|)$ (of aannames over Huffman)	$O(\log |T|)$ (polynomiaal in $\lambda$)	$O(1)$ (Constante entropie)
Robuustheid	Substituties (en deleties met aannames)	Edits (Sub, Del, Ins)	Substituties & Deleties (en Edits met nieuwe PRC)
Aanvalsniveau	Bit-niveau (na vertaling)	Token-niveau	Token-niveau (behoudt structuur)

Significantie

Dit paper is significant omdat het de theoretische barrière voor watermerking van LLMs doorbreekt in het laag-entropie regime, wat veel realistischer is voor natuurlijke taal dan de eerdere hoge-entropie eisen.

• Praktische Toepasbaarheid: Het schema behoudt de token-structuur van de output. Eerdere methoden die werken met binaire vertalingen maken de watermerking kwetsbaar voor aanvallen die op token-niveau plaatsvinden (zoals parafraseren of redactie), omdat een bit-flip in de vertaling niet noodzakelijk overeenkomt met een willekeurige token-verandering. Dit werk definieert "random substitution" direct op token-niveau.
• Onafhankelijkheid van Alfabetgrootte: De methoden zijn onafhankelijk van de grootte van het token-alfabet ($|T|$), wat essentieel is voor moderne LLMs met vocabulaires van tienduizenden tokens.
• Cryptografische Fundamenten: De resultaten zijn gebaseerd op standaard cryptografische aannames (zoals LPN) en bieden een solide theoretische basis voor toekomstige implementaties van onopmerkelijke watermerking in AI-systemen.

Kortom, de auteurs bewijzen dat het mogelijk is om LLM-outputs te watermerken die grotendeels voorspelbaar zijn (lage entropie), zolang er maar een klein deel van de output voldoende variatie vertoont, zonder de detecteerbaarheid of robuustheid te compromitteren.