Optimal Multi-bit Generative Watermarking Schemes Under Worst-Case False-Alarm Constraints

Titolo

Schemi di Watermarking Generativo Multi-bit Ottimali sotto Vincoli di Falso Allarme nel Caso Peggiore

1. Il Problema

Il lavoro affronta la sfida di implementare il watermarking generativo multi-bit per i Large Language Models (LLM). A differenza dei metodi "zero-bit" attuali, che si limitano a rilevare se un testo è generato dall'AI, l'obiettivo qui è codificare messaggi specifici (multi-bit) all'interno del testo generato.

Il contesto è quello dei metodi di inferenza (che modificano il processo di campionamento senza riaddestrare il modello) e si opera sotto un vincolo rigoroso di falso allarme nel caso peggiore (worst-case false-alarm constraint). Questo significa che la probabilità di dichiarare erroneamente la presenza di un watermark su un testo non watermarked (generato da una distribuzione arbitraria $Q_X$) non deve superare una soglia $\alpha$, indipendentemente dalla distribuzione dei token.

L'obiettivo è minimizzare la probabilità di mancata rilevazione (miss-detection) per i messaggi watermarked, mantenendo il watermark "distortionless" (cioè, la distribuzione marginale dei token generati deve rimanere identica a quella originale del LLM).

2. Contesto e Critica al Lavoro Precedente

Gli autori analizzano un lavoro precedente di He et al. [11], che aveva proposto un limite inferiore teorico per la probabilità di errore di rilevazione e un costrutto (schema di codifica/decodifica) che affermava di raggiungere tale limite.

• Scoperta Critica: Gli autori dimostrano che lo schema proposto da He et al. è sub-ottimale e, in certi casi, invalido.
• Causa del Fallimento: Il fallimento è attribuito a un design del decodificatore eccessivamente restrittivo. La costruzione precedente utilizzava un insieme di chiavi e una funzione di decodifica che non potevano soddisfare le condizioni di ottimalità per tutte le distribuzioni di token, portando a un errore di rilevazione superiore al limite teorico.

3. Metodologia e Contributi Chiave

A. Formulazione del Problema

Il problema è formulato come un programma lineare. Gli autori definiscono formalmente un sistema di watermarking valido e distortionless, dove:

• $f$: Codificatore che mappa un messaggio $m$ e una distribuzione di token $P_X$ in una distribuzione congiunta su token e chiave segreta.
• $\gamma$: Decodificatore deterministico che, dato un token e una chiave, stima il messaggio.
• Vincoli:
  1. Invarianza della distribuzione marginale dei token (distortionless).
  2. Probabilità di falso allarme $\le \alpha$ per qualsiasi distribuzione di input.
  3. Minimizzazione del massimo errore di missed-detection tra tutti i messaggi possibili.

B. Il Limite Teorico (Teorema 1)

Viene confermato il limite inferiore per la probabilità di missed-detection $\beta^*$:
$$\beta^*[\alpha, P_X] = 1 - \sum_{x \in \mathcal{X}} \min\left(\frac{\alpha}{T}, P_X(x)\right)$$
dove $T$ è il numero di messaggi e $P_X(x)$ è la probabilità del token $x$.

C. Due Nuove Costruzioni Ottimali

Per dimostrare che questo limite è raggiungibile (Teorema di Achievability), gli autori propongono due nuove costruzioni di coppie (codificatore, decodificatore):

1. Costruzione A: Approccio di Decomposizione

   • Concetto: Scompone la distribuzione dei token $P_X$ in tre componenti: $P_X^{(1)} + P_X^{(2)} + P_X^{(3)}$.
   • Tecnica: Utilizza il concetto di vettori T-hot rappresentabili.
     • $P_X^{(1)}$: La parte "rappresentabile" viene distribuita uniformemente su chiavi specifiche (insieme ridotto di chiavi $Z_N^T$) utilizzando una struttura basata su permutazioni.
     • $P_X^{(2)}$: Gestisce le componenti residue a coda lunga tramite un'allocazione a "step-vector" su chiavi ancorate (anchored keys). Questo introduce uno squilibrio nelle somme delle righe.
     • $P_X^{(3)}$: Utilizzata per correggere lo squilibrio delle somme delle righe introdotto dalla seconda componente, garantendo l'invarianza necessaria.
   • Vantaggio: Utilizza un insieme di chiavi più piccolo.

2. Costruzione B: Approccio con Pseudo-Token

   • Concetto: Estende lo spazio dei token originali aggiungendo $n$ "pseudo-token" artificiali per rendere la distribuzione estesa $P'_X$ T-hot rappresentabile.
   • Tecnica:
     • Se la distribuzione originale non è T-hot rappresentabile, si aggiungono pseudo-token per bilanciare la massa di probabilità.
     • Si applica l'algoritmo di costruzione su questo spazio esteso.
     • Infine, i valori associati ai pseudo-token vengono mappati indietro nello spazio dei token originali, ridistribuendo la massa in proporzione alla parte residua della distribuzione.
   • Vantaggio: Concettualmente più semplice e diretto, ma richiede un insieme di chiavi potenzialmente più grande rispetto alla Costruzione A.

4. Risultati Principali

• Ottimalità Completa: Le due nuove costruzioni dimostrano di raggiungere esattamente il limite inferiore teorico stabilito, caratterizzando completamente le prestazioni ottimali del watermarking multi-bit generativo sotto vincoli di falso allarme.
• Smentita della Precedente Ottimalità: Viene provato matematicamente (tramite analisi del duale del problema di ottimizzazione) che la costruzione di He et al. non può raggiungere il limite ottimale in generale, fornendo un controesempio specifico.
• Analisi dei Trade-off:
  • La Costruzione A è più efficiente in termini di dimensione dell'insieme delle chiavi (segreto), ma richiede una logica di decomposizione e correzione dell'errore più complessa.
  • La Costruzione B è concettualmente più lineare (basata sull'estensione dello spazio), ma può richiedere un insieme di chiavi significativamente più grande, specialmente se la distribuzione dei token è molto disuniforme.

5. Significato e Implicazioni

Questo lavoro è fondamentale per il campo della sicurezza e della tracciabilità dell'IA generativa:

1. Fondamento Teorico: Fornisce la prima caratterizzazione rigorosa e completa dei limiti fondamentali del watermarking multi-bit, chiudendo il gap tra teoria e pratica.
2. Robustezza: Dimostra che è possibile codificare informazioni complesse (multi-bit) senza degradare la qualità statistica del testo (distortionless) e mantenendo garanzie di sicurezza forti contro falsi positivi, anche in scenari ostili.
3. Guida per l'Implementazione: Offre due approcci pratici (uno ottimizzato per la dimensione della chiave, l'altro per la semplicità algoritmica) che possono essere adottati per implementare sistemi di watermarking reali per LLM, superando le limitazioni degli approcci euristici precedenti.

In sintesi, il paper risolve un problema aperto nella teoria dell'informazione applicata all'IA, correggendo errori precedenti e fornendo costruzioni ottimali per la protezione e la tracciabilità dei contenuti generati dall'IA.