LLM-Text Watermarking based on Lagrange Interpolation

Titolo: Watermarking per Testo Generato da LLM basato su Interpolazione di Lagrange

Autori: Jarosław Janas, Paweł Morawiecki, Josef Pieprzyk (Polish Academy of Sciences & CSIRO).

---

1. Il Problema

Con l'avanzamento rapido dei Modelli Linguistici su Grande Scala (LLM), è emersa una sfida critica: l'attribuzione del testo generato dall'IA. È fondamentale poter distinguere tra contenuti umani e machine-generated per combattere la disinformazione, le fake news, il plagio e l'impersonificazione.
L'obiettivo è sviluppare un sistema di watermarking digitale che permetta di tracciare l'origine del testo (specifico modello o utente) in modo affidabile, anche in presenza di modifiche o tentativi di rimozione da parte di un avversario. Le soluzioni esistenti spesso si limitano a segnali binari (acqua/non acqua) o richiedono modifiche al training del modello, rendendole meno pratiche o meno robuste.

2. Metodologia Proposta

Il paper propone uno schema di watermarking training-free (non richiede riaddestramento del modello) e model-agnostic (indipendente dall'architettura LLM), basato su concetti di algebra finite e interpolazione polinomiale.

Concetto Fondamentale

L'idea centrale è codificare il watermark come i coefficienti di un polinomio su un campo finito $GF(2^n)$.

• Caso Lineare: Il lavoro si concentra sul caso più semplice non banale, dove il polinomio è una retta: $f(x) = a_1x + a_0$. Il watermark è rappresentato dalla coppia $(a_0, a_1)$.

• Embedding (Inserimento):

  1. Si generano pseudo-casualmente coordinate $x$ basate sui token precedenti e una chiave segreta $K$ (tramite funzione hash).
  2. Si calcola la coordinata $y = f(x)$.
  3. I bit di $y$ vengono incorporati nel testo influenzando la selezione dei token. Il vocabolario viene diviso in due insiemi (simili ai concetti "Green/Red" tokens): se il bit è 0 si favorisce un insieme, se è 1 l'altro.
  4. Questo processo crea una serie di punti $(x, y)$ che giacciono tutti sulla stessa retta $f(x)$.

• Extraction (Estrazione):

  1. Il verificatore riproduce le coordinate $x$ usando la stessa chiave e hash.
  2. Decodifica i bit dai token per ricostruire le coordinate $y$, ottenendo un insieme di punti $P$.
  3. A causa del rumore stocastico (campionamento dell'LLM) o di attacchi avversari (cancellazione/inserimento di token), molti punti saranno errati (spuri).
  4. Il problema si riduce al Maximum Collinear Points (MCP): trovare il sottoinsieme massimo di punti che giacciono sulla stessa retta.
  5. Una volta identificata la retta dominante, si applica l'Interpolazione di Lagrange per recuperare i coefficienti originali $(a_0, a_1)$, ovvero il watermark.

Robustezza e Correzione degli Errori

• Il sistema è intrinsecamente robusto: anche se una frazione dei punti viene persa o corrotta, è sufficiente che un sottoinsieme sufficiente rimanga allineato per recuperare la retta.
• Viene introdotta una fase di correzione dei bit: durante l'estrazione, si generano varianti vicine (entro un raggio di Hamming $c$) dei punti recuperati per mitigare errori locali, aumentando la probabilità di trovare la retta corretta a scapito di un leggero aumento computazionale.

3. Contributi Chiave

1. Schema Multi-bit: A differenza di molti approcci precedenti che gestiscono solo un bit, questo metodo codifica un payload multi-bit (fino a 32 bit o più) come coefficienti di un polinomio.
2. Approccio Algebrico: L'uso dell'interpolazione di Lagrange su campi finiti ($GF(2^n)$) trasforma il problema di rilevamento in un problema geometrico risolvibile efficientemente (MCP).
3. Analisi Teorica: Fornisce un'analisi probabilistica rigorosa (Teorema 1) per calcolare la probabilità di allineamenti casuali (falsi positivi) in base alla dimensione del campo e al numero di punti, guidando la scelta dei parametri di sicurezza.
4. Efficienza: Lo schema è leggero, non modifica i pesi del modello e l'estrazione avviene in tempi molto brevi (frazioni di secondo).

4. Risultati Sperimentali

Gli autori hanno testato il metodo su modelli open-source (Llama 2-7B, Llama 3.2, Mistral 7B) utilizzando dataset come OpenGen, Essays e HC3.

• Accuratezza: Il metodo ha ottenuto tassi di corrispondenza (match rate) molto elevati, comparabili o superiori agli stati dell'arte (es. Fernandez et al., Wang et al.).
  • Per watermark da 16 bit: ~98.6% di successo.
  • Per watermark da 32 bit: ~85.9% di successo (con correzione bit).
• Confronto con altri metodi: I metodi basati su ricerca esaustiva diventano impraticabili (NA) per watermark lunghi, mentre l'approccio proposto scala bene.
• Resistenza agli Attacchi:
  • Sostituzione: Il sistema è robusto; le sostituzioni di token introducono solo rumore nei punti, ma la struttura della retta rimane rilevabile.
  • Inserimento/Cancellazione: Questi attacchi sono più dannosi perché causano una "desincronizzazione" dei blocchi, rendendo i punti successivi non allineati. Tuttavia, il sistema tollera un livello non banale di manipolazione (fino al 10% di modifiche) mantenendo una capacità di recupero accettabile.
• Qualità del Testo: L'uso di un bias sui logit ($\delta=6$) degrada minimamente la qualità del testo (perplessità), risultando quasi impercettibile per gli umani.

5. Significato e Implicazioni

Questo lavoro introduce un paradigma innovativo per il watermarking degli LLM, spostando l'attenzione dalla semplice statistica dei token alla struttura algebrica dei dati incorporati.

• Scalabilità: La capacità di estrarre watermark multi-bit senza riaddestramento lo rende adatto per applicazioni reali su larga scala.
• Flessibilità: Lo schema è estendibile a polinomi di grado superiore (non solo rette) per aumentare la capacità di dati o la robustezza, trasformando il problema in "Maximum Co-Polynomial Points".
• Sicurezza: Fornisce garanzie teoriche contro i falsi positivi e offre un compromesso controllabile tra robustezza e complessità computazionale.

In conclusione, il metodo proposto offre un equilibrio efficace tra sicurezza, efficienza e praticità, rappresentando un passo avanti significativo nella tracciabilità e nell'attribuzione dei contenuti generati dall'intelligenza artificiale.