LLM-Text Watermarking based on Lagrange Interpolation

1. O Problema

O avanço rápido dos Modelos de Linguagem de Grande Escala (LLMs) criou uma necessidade crítica de atribuição de autoria para textos gerados por IA. É fundamental poder distinguir entre texto humano e texto gerado por máquina para combater desinformação, notícias falsas, plágio e uso indevido de identidade.

O desafio central é desenvolver um método de marcamento digital (watermarking) que:

• Seja robusto contra edições adversárias (como substituição, inserção ou exclusão de tokens).
• Permita a recuperação de uma carga útil de múltiplos bits (não apenas um sinal binário de "marcado/não marcado").
• Seja eficiente e não requeira o re-treinamento do modelo (model-agnostic).

2. Metodologia Proposta

Os autores propõem um esquema de marcação que utiliza conceitos de campos finitos e geometria algébrica para codificar a marca d'água.

Conceito Central: Interpolação de Lagrange e Pontos Colineares

A ideia fundamental é representar a marca d'água como os coeficientes de um polinômio (no caso básico, uma linha reta) sobre um campo finito $GF(2^n)$.

• A Marca ($W$): É codificada como os coeficientes de uma função linear $f(x) = a_1x + a_0$, onde $W = (a_0 || a_1)$.
• Pontos de Dados: O algoritmo gera uma sequência de pontos $(x, y)$ que satisfazem essa função, ou seja, $y = f(x)$.
• Inserção (Embedding):
  1. Para cada bloco de tokens gerados, um valor $x$ é gerado pseudo-aleatoriamente usando uma função hash criptográfica (baseada no token anterior e uma chave secreta).
  2. O valor $y = f(x)$ é calculado.
  3. Os bits de $y$ são embutidos no texto enviesando a seleção de tokens (logits). O vocabulário é dividido aleatoriamente em dois conjuntos ($V_0$ e $V_1$) para cada bit; se o bit for 0, os logits de $V_0$ são aumentados, e vice-versa.
• Extração (Extraction):
  1. O verificador recupera os pontos $(x, y)$ do texto gerado seguindo o mesmo processo determinístico de hash.
  2. Devido a ruídos de amostragem ou ataques adversários, alguns pontos recuperados serão incorretos (ruído).
  3. O problema de encontrar a marca d'água original é transformado no Problema dos Pontos Máximos Colineares (Maximum Collinear Points - MCP): encontrar a linha que passa pelo maior número de pontos no plano $GF(2^n) \times GF(2^n)$.
  4. Uma vez identificada a linha com o maior número de pontos, aplica-se a Interpolação de Lagrange para recuperar os coeficientes originais ($a_0, a_1$), que constituem a marca d'água.

Mecanismos de Correção

Para lidar com erros de bits (ruído), o sistema utiliza uma etapa de correção de bits leve durante a extração. Isso envolve enumerar candidatos dentro de um pequeno raio de Hamming (tentando corrigir até $c$ bits errados por bloco) para aumentar a probabilidade de recuperar pontos válidos para o algoritmo MCP.

3. Principais Contribuições

1. Esquema Livre de Treinamento: O método é agnóstico ao modelo, aplicável a qualquer LLM sem necessidade de modificar seus pesos ou dados de treinamento.
2. Carga Útil de Múltiplos Bits: Diferente de muitos métodos que apenas indicam a presença de uma marca, este esquema codifica informações significativas (coeficientes de polinômios).
3. Resiliência Parcial: O esquema é inerentemente robusto a edições parciais. Mesmo que uma fração dos pontos seja corrompida ou removida, desde que um subconjunto suficiente permaneça colinear, a marca pode ser recuperada.
4. Análise Probabilística Rigorosa: Os autores fornecem uma análise teórica (Teorema 1) que estabelece limites superiores para a probabilidade de colinearidade espúria (falsos positivos) em campos finitos, guiando a escolha do tamanho do campo ($n$) e do comprimento do bloco.
5. Eficiência Computacional: A extração utiliza algoritmos de MCP otimizados (baseados em hash) com complexidade $O(N^2)$, permitindo tempos de extração de frações de segundo.

4. Resultados Experimentais

Os autores avaliaram o método em modelos como Llama 2-7B, Llama 3.2-3B e Mistral-7B, utilizando os conjuntos de dados Essays e HC3.

• Taxa de Correspondência (Match Rate): O método alcançou taxas de recuperação muito altas (acima de 90% para marcas de 16 a 24 bits) e competitivas com o estado da arte (como os métodos de Qu et al. e Fernandez et al.).
  • Para marcas de 16 bits, a taxa foi de 98,6%.
  • Para marcas de 32 bits, a taxa foi de 85,9% (ainda superior a vários concorrentes que falharam ou tiveram desempenho muito baixo em tamanhos maiores).
• Robustez a Ataques:
  • Substituição: O método é altamente robusto, pois a substituição de tokens apenas introduz ruído nos pontos, mas não desalinha a estrutura.
  • Inserção/Deleção: O método é mais vulnerável a esses ataques, pois eles causam dessincronização (desalinhamento dos blocos de tokens), gerando muitos pontos espúrios. No entanto, o sistema ainda tolera um nível não trivial de manipulação (até 10% de tokens modificados) antes de falhar completamente.
• Qualidade do Texto: O viés nos logits ($\delta = 6$) utilizado não degrada significativamente a qualidade do texto (perplexidade) ou a fluidez percebida por humanos, comparável a métodos existentes.
• Tempo de Extração: A extração é extremamente rápida (fração de segundo), escalando de forma previsível.

5. Significância e Conclusão

Este trabalho apresenta uma nova abordagem para a segurança de LLMs, unindo teoria dos campos finitos e problemas geométricos computacionais para criar uma marca d'água robusta e de alta capacidade.

• Inovação: A transformação do problema de extração de marca d'água em um problema de "Pontos Máximos Colineares" é uma contribuição teórica e prática significativa, permitindo a recuperação de dados mesmo na presença de ruído e edições.
• Aplicabilidade: A natureza leve e sem treinamento do esquema facilita sua adoção imediata em sistemas de produção.
• Futuro: Os autores sugerem extensões para polinômios de grau superior (para aumentar a capacidade de carga) e o uso de múltiplas linhas para cargas úteis ainda maiores, embora isso aumente a complexidade computacional da recuperação.

Em resumo, o método oferece um equilíbrio flexível entre eficiência, segurança e robustez, sendo uma ferramenta promissora para a atribuição de autoria e combate à desinformação na era da IA generativa.