Can we Watermark Low-Entropy LLM Outputs?

1. Il Problema

L'articolo affronta la sfida di watermarking (filigrana digitale) per le uscite dei Large Language Models (LLM) in scenari di bassa entropia.

• Contesto: Esistono già metodi per watermarkare l'output degli LLM in modo che sia indistinguibile dalla distribuzione originale (watermarking "invisibile" o undetectable) e robusto contro le modifiche.
• Limitazione degli approcci esistenti: Le opere recenti (es. Christ et al., Golowich et al.) richiedono che l'output dell'LLM abbia un alto tasso di entropia. Nello specifico, richiedono che una frazione costante dei token abbia un'entropia empirica di almeno $O(\log |T|)$, dove $|T|$ è la dimensione dell'alfabeto dei token.
• La sfida reale: In molti scenari pratici (es. risposte deterministiche, frasi comuni, o testi con vocabolario ristretto), l'entropia per token è molto bassa (spesso vicina a 1 bit o costante), indipendentemente dalla grandezza dell'alfabeto. Gli schemi attuali falliscono o richiedono assunzioni distributive forti in questi casi, rendendo impossibile il watermarking robusto per testi "poveri" di entropia.

2. Metodologia e Approccio Tecnico

Gli autori propongono un nuovo schema di watermarking basato su Codici Pseudo-Random (PRC) che funziona anche quando l'entropia per token è solo una costante (es. 1 bit), senza dipendere dalla dimensione dell'alfabeto $|T|$.

Concetti Chiave:

1. PRC (Pseudorandom Error-Correcting Codes): Utilizzano codici che sono sia indistinguibili dal caso vero (pseudocasuali) sia capaci di correggere errori (robusti).
2. Hashing dei Token: Invece di convertire i token in una rappresentazione binaria (che aumenterebbe artificialmente il requisito di entropia), lo schema mappa ogni token dell'alfabeto grande $T$ in un singolo bit tramite una funzione di hash casuale $h: T \to \{0, 1\}$.
3. Embedding a Blocchi:
   • L'output dell'LLM viene diviso in blocchi.
   • Per ogni blocco, viene generata una singola funzione di hash $h$ (riutilizzata per tutti i token del blocco) e un codice PRC binario da incorporare.
   • Meccanismo di Embedding: Per generare il token successivo:
     1. Si campionano due token indipendenti $t_0, t_1$ dalla distribuzione dell'LLM.
     2. Se $h(t_0) \neq h(t_1)$ ("caso di successo"), si seleziona il token il cui hash corrisponde al bit del codice PRC da inserire.
     3. Se $h(t_0) = h(t_1)$ ("caso di fallimento"), si seleziona un token a caso (introducendo un errore potenziale).
   • Questo processo preserva la distribuzione originale dell'LLM (garantendo l'invisibilità) perché, in media, la selezione non introduce bias.

Gestione della Robustezza:

• Sostituzioni Casuali: Lo schema dimostra che anche se un avversario sostituisce casualmente una frazione dei token, l'errore introdotto nel codice PRC rimane sotto la soglia di correzione, purché esista una frazione costante di token con entropia $\ge 1$.
• Cancellazioni (Deletions): Per gestire le cancellazioni, lo schema riutilizza la stessa funzione di hash per un intero blocco. Questo permette al rilevatore di tentare la decodifica su qualsiasi sotto-sequenza residua del blocco, anche se alcuni token sono stati rimossi.
• Assunzioni:
  • Per la robustezza contro sostituzioni e cancellazioni casuali, lo schema richiede o un'assunzione euristica (l'output è "sufficientemente variabile" per modellare gli errori come un canale binario simmetrico) oppure l'esistenza di un PRC binario robusto contro sostituzioni avversariali e cancellazioni casuali.

3. Contributi Chiave

1. Riduzione del Requisito di Entropia: Dimostrano che è possibile watermarkare in modo robusto e invisibile anche quando l'entropia empirica dei token è una costante (es. 1 bit), eliminando la dipendenza da $\log |T|$ richiesta dalle opere precedenti.
2. Robustezza a Livello di Token: A differenza degli approcci che riducono tutto a bit (dove una modifica di un bit può corrompere l'intero token), il loro metodo opera direttamente a livello di token, rendendo la robustezza più significativa per attacchi pratici come il parafrasi o la censura.
3. Nuovi Teoremi di Costruzione:
   • Costruiscono uno schema robusto contro sostituzioni casuali (basato sulla durezza sub-esponenziale di LPN).
   • Costruiscono uno schema robusto contro sostituzioni e cancellazioni casuali (con assunzioni aggiuntive o nuovi PRC).
   • Estendono la robustezza a un sottoinsieme di modifiche avversariali (edit distance) utilizzando recenti costruzioni di PRC basate su "codici permutati".

4. Risultati Principali

Gli autori formalizzano i seguenti risultati (riassunti nei Teoremi 1-4 e Corollari):

• Teorema 1 (Sostituzioni Casuali): Esiste uno schema di watermarking computazionalmente indistinguibile e robusto contro una frazione $(1/2 - \epsilon)$ di sostituzioni casuali, assumendo la durezza sub-esponenziale di LPN (Learning Parity with Noise), anche per output con entropia minima costante.
• Teorema 2 (Sostituzioni e Cancellazioni Casuali): Esiste uno schema robusto contro sostituzioni e cancellazioni casuali, sotto l'assunzione euristica che l'output sia "naturale" (errori distribuiti in modo coerente) o con PRC specifici.
• Teorema 3 (Senza Assunzioni Euristiche): Se esiste un PRC binario robusto contro sostituzioni avversariali e cancellazioni casuali, allora esiste uno schema di watermarking per grandi alfabeti con entropia minima costante robusto contro sostituzioni e cancellazioni casuali, senza bisogno di assunzioni euristica sull'output.
• Teorema 4 (Robustezza agli Edit): Utilizzando la costruzione di PRC di [CGG+25] (basata su codici di Reed-Solomon permutati), ottengono uno schema robusto contro una frazione costante di edit avversariali (inserzioni/cancellazioni), sebbene richieda una lunghezza di substring di entropia minima più ampia.

5. Significato e Impatto

• Praticità: Questo lavoro colma un divario critico nella sicurezza dell'IA. Molti testi generati dall'IA (o modificati da essa) possono avere bassa entropia (es. elenchi, risposte brevi, testi tecnici). Gli schemi precedenti fallivano in questi casi; il nuovo metodo rende il watermarking applicabile a un'ampia gamma di scenari reali.
• Flessibilità: Non richiede che l'LLM produca testi "caotici" o ad alta entropia per essere tracciabile.
• Sicurezza: Fornisce garanzie teoriche (basate su ipotesi crittografiche standard come LPN) contro avversari che tentano di rimuovere la filigrana tramite editing, parafrasi o cancellazione di parti del testo.
• Apertura Futura: Identifica che la robustezza completa contro una frazione grande di cancellazioni avversariali senza assunzioni euristica rimane una sfida aperta, ma offre una direzione chiara basata sull'evoluzione dei codici PRC.

In sintesi, il paper dimostra che la bassa entropia non è un ostacolo insormontabile per il watermarking invisibile degli LLM, proponendo una tecnica basata sull'hashing dei token che bilancia efficienza, sicurezza e robustezza pratica.