Can we Watermark Low-Entropy LLM Outputs?

1. O Problema

A marcação de água (watermarking) em modelos de linguagem grandes (LLMs) é uma solução promissora para distinguir conteúdo gerado por IA do conteúdo humano. O objetivo ideal é criar um esquema que seja:

1. Indetectável: A distribuição de saída do LLM não deve ser alterada perceptivelmente (o conteúdo marcado deve ser computacionalmente indistinguível do não marcado).
2. Robusto: O marca d'água deve sobreviver a ataques adversariais que tentam removê-lo através de substituições, inserções ou deleções de tokens.

A Limitação Atual: Trabalhos recentes (como Christ et al. [CG24] e Golowich et al. [GM24]) conseguiram criar esquemas indetectáveis e robustos, mas sob uma suposição forte: a saída do LLM deve ter alta entropia.

• Especificamente, eles exigem que uma fração constante dos tokens tenha uma entropia empírica de pelo menos $O(\log |T|)$, onde $|T|$ é o tamanho do vocabulário de tokens.
• Isso significa que, para vocabulários grandes, os tokens precisam ser altamente imprevisíveis.
• O Desafio: Em cenários realistas, muitos tokens gerados por LLMs têm baixa entropia (próxima de 1 bit ou menos), como em frases comuns, respostas determinísticas ou textos técnicos repetitivos. Os métodos existentes falham nesses regimes de baixa entropia, pois não conseguem correlacionar a saída do modelo com o código de marcação sem introduzir viés detectável ou erros excessivos.

O artigo investiga: É possível criar um esquema de marcação de água indetectável e robusto para LLMs com grande vocabulário, mesmo quando a entropia por token é apenas uma constante pequena (independente do tamanho do vocabulário)?

---

2. Metodologia e Abordagem Técnica

Os autores propõem uma nova construção baseada em Códigos Pseudoaleatórios (PRC - Pseudorandom Codes) que opera diretamente no nível de tokens do LLM, evitando a redução direta para binário que aumenta a exigência de entropia.

Conceitos Chave:

• PRC (Código Pseudoaleatório): Um código onde o codetexto é indistinguível de aleatoriedade verdadeira para um adversário, mas pode ser recuperado mesmo após erros (substituições/deleções).
• Hashing de Tokens: Em vez de converter tokens diretamente para bits (o que exigiria alta entropia), o esquema utiliza uma função de hash aleatória $h: T \to \{0, 1\}$ para mapear cada token do vocabulário grande para um bit.
• Estratégia de Blocos: O texto de saída é dividido em blocos. Para cada bloco, é gerada uma nova função de hash $h$ (que é parte da chave secreta). Todos os tokens dentro de um mesmo bloco usam a mesma função de hash.

O Algoritmo de Marcação (Watermarking):

Para gerar o próximo token $t$ e codificar um bit $c_i$ do PRC:

1. O modelo amostra dois tokens independentes, $t_0$ e $t_1$, da distribuição condicional do LLM.
2. Calcula-se $h(t_0)$ e $h(t_1)$.
3. Caso de Sucesso ($h(t_0) \neq h(t_1)$): O algoritmo seleciona o token cujo hash corresponda ao bit do PRC ($c_i$). Isso codifica o bit sem viés na distribuição do token.
4. Caso de Falha ($h(t_0) = h(t_1)$): O algoritmo seleciona um dos tokens aleatoriamente. Isso introduz um erro na codificação com probabilidade 1/2, mas não altera a distribuição marginal do token (mantendo a indetectabilidade).

Análise de Robustez:

• Entropia Mínima: O esquema exige apenas que uma fração constante dos tokens tenha entropia empírica $\ge 1$. Isso garante que, para esses tokens, a probabilidade de $t_0 = t_1$ seja baixa, aumentando a chance de "sucesso" na codificação.
• Resistência a Substituições Aleatórias: O artigo prova que, mesmo com substituições aleatórias (onde um adversário troca tokens por outros baseados em distribuições arbitrárias), a taxa de erro esperada no PRC permanece abaixo de 1/2, desde que a entropia mínima seja satisfeita.
• Resistência a Deleções: Ao reutilizar a mesma função de hash $h$ para um bloco inteiro, o esquema permite a recuperação do código mesmo se alguns tokens forem deletados, pois o detector pode tentar decodificar o bloco restante usando a mesma $h$.

---

3. Principais Contribuições e Resultados

Os autores apresentam quatro teoremas principais (e seus corolários) que estabelecem a viabilidade da marcação de água em baixa entropia sob diferentes suposições de segurança:

1. Robustez contra Substituições Aleatórias (Teorema 1/Corolário 1):

   • Assumindo a dureza subexponencial do problema LPN (Learning Parity with Noise), é possível construir um esquema robusto contra uma fração $(1/2 - \epsilon)$ de substituições aleatórias.
   • Requisito de Entropia: Apenas uma fração constante de tokens com 1 bit de entropia empírica (independente de $|T|$).

2. Robustez contra Substituições e Deleções Aleatórias (Teorema 2/Corolário 2):

   • Estende o resultado anterior para incluir deleções.
   • Condição: Requer uma suposição heurística adicional de que o prompt gera erros "consistentes" (modeláveis como um canal simétrico binário) ou assume a existência de um PRC binário robusto a substituições adversariais e deleções aleatórias.
   • Resultado: Robustez contra $(1/2 - \epsilon)$ de substituições e $(1 - \epsilon')$ de deleções.

3. Robustez contra Edits Adversariais (Teorema 3/Corolário 3):

   • Se existir um PRC binário robusto a substituições adversariais e deleções aleatórias, o esquema funciona sem suposições heurísticas sobre a variabilidade do texto.
   • Limitação: Ainda não há construção conhecida de PRC binário com essa robustez extrema para uma grande fração de deleções, mas o framework é válido.

4. Robustez a Edits Arbitrários (Teorema 4/Corolário 4):

   • Utilizando uma construção recente de PRC baseada em "códigos permutados" (permuted codes) de [CGG+25], que suporta uma pequena fração de edits adversariais.
   • Resultado: Um esquema robusto a uma fração constante de edits adversariais (inserções, deleções, substituições) para qualquer saída com entropia mínima.
   • Custo: Exige que uma fração maior do texto inteiro (não apenas um substring) tenha entropia suficiente, pois um adversário poderia atacar especificamente a substring de alta entropia.

---

4. Significado e Impacto

• Quebra de Barreira de Entropia: Este trabalho é o primeiro a demonstrar que a marcação de água indetectável e robusta é possível em regimes de baixa entropia (entropia constante), eliminando a dependência de $O(\log |T|)$ exigida por trabalhos anteriores.
• Realismo Prático: Ao operar diretamente no nível de tokens e não em uma representação binária reduzida, o esquema preserva a estrutura semântica do texto. Ataques como "paraphrasing" (troca de sinônimos) ou "redação" (remoção de palavras) são modelados como substituições de tokens, tornando a robustez mais relevante para cenários do mundo real do que a robustez contra flips de bits em uma codificação binária.
• Flexibilidade de Assunções: O trabalho oferece um espectro de soluções: desde esquemas que dependem de suposições heurísticas (como a "variabilidade suficiente" do texto) até esquemas que dependem apenas de suposições criptográficas padrão (como LPN), permitindo que a comunidade escolha o equilíbrio entre segurança e requisitos de modelo.
• Aplicabilidade: Permite a detecção de IA em textos que anteriormente seriam impossíveis de marcar, como respostas curtas, listas, ou textos técnicos onde a previsibilidade (baixa entropia) é alta.

Em resumo, o artigo avança significativamente o estado da arte em marcação de água para IA, provando que é possível proteger a autoria de conteúdo gerado por LLMs mesmo quando o conteúdo é altamente previsível, desde que se utilize a estrutura correta de hashing e códigos pseudoaleatórios.