Fast segmentation of watermarked texts from large language models through an epidemic change-point framework

Resumo Técnico: Segmentação Rápida de Textos com Marca d'Água de Grandes Modelos de Linguagem através de uma Estrutura de Mudança de Ponto Epidêmica

Definição do Problema
A proliferação de Grandes Modelos de Linguagem (LLMs) tornou necessária a criação de mecanismos robustos para detectar conteúdo gerado por máquina, visando abordar preocupações relativas à autenticidade, direitos autorais e integridade acadêmica. Embora esquemas de marca d'água — que inserem sinais estatísticos na geração de tokens usando chaves secretas — tenham sido desenvolvidos para detectar a presença de texto gerado por LLM, a tarefa mais refinada de localizar segmentos específicos com marca d'água dentro de um texto de fonte mista (contendo conteúdo tanto humano quanto gerado por máquina) permanece subexplorada. Os algoritmos de segmentação existentes frequentemente sofrem com uma complexidade computacional proibitiva, tornando-os inadequados para textos longos, ou carecem de garantias teóricas robustas à paráfrase e pós-edição. Além disso, os métodos atuais têm dificuldade em identificar eficientemente múltiplos intervalos com marca d'água disjuntos dentro de um único documento.

Metodologia: A Perspectiva de Mudança de Ponto Epidêmica
Os autores propõem o WISER (Watermark Identification via Segmenting Epidemic Regions), um algoritmo que reformula o problema de segmentação de marca d'água como um problema de detecção de mudança de ponto epidêmica.

1. Estatísticas de Pivô e Alternativas Elevadas: O método baseia-se em "estatísticas de pivô" ($Y_t$), que são funções dos tokens gerados e das chaves pseudoaleatórias. Sob a hipótese nula (tokens gerados por humanos/sem marca d'água), essas estatísticas seguem uma distribuição estacionária conhecida com média $\mu_0$. Sob a alternativa (tokens com marca d'água), as estatísticas exibem uma propriedade de "alternativa elevada", onde seu valor esperado é estritamente maior que $\mu_0$ por uma margem $d$, independentemente da Distribuição de Próximo Token (NTP) específica do LLM.
2. Modelagem Epidêmica: Diferente dos problemas de mudança de ponto padrão, onde um desvio persiste indefinidamente, a marca d'água cria intervalos "epidêmicos": a média das estatísticas de pivô desloca-se para cima para um segmento contíguo específico (a marca d'água) e retorna ao nível basal fora desse segmento.
3. Design do Algoritmo:
   • Estimador de Segmento Único: Para um patch com marca d'água, os autores adaptam um estimador que minimiza um excedente enviesado fora de um intervalo candidato. Ao subtrair um termo de buffer ($\rho \tilde{d}$) da soma das estatísticas fora do intervalo, o algoritmo penaliza a inclusão de tokens sem marca d'água enquanto recompensa a exclusão de tokens elevados com marca d'água.
   • Estratégia de Múltiplos Segmentos (WISER): Para lidar com múltiplos segmentos sem conhecimento prévio de sua contagem ($K$), o WISER emprega um pipeline de quatro estágios:
     • Bloqueio (Blocking): O texto é particionado em blocos. Blocos com somas que excedem um limiar $Q$ são retidos.
     • Descarte (Discarding): Componentes conectados de blocos retidos são formados. Componentes curtos (prováveis falsos positivos) são descartados com base em um limiar de comprimento ($c\sqrt{\log n}$).
     • Ampliação (Enlargement): As regiões conectadas restantes são expandidas por um fator de $\sqrt{n}$ para garantir que cubram totalmente os segmentos reais com marca d'água.
     • Busca Local Refinada (Refined Local Search): Dentro dessas regiões ampliadas, o estimador de segmento único é aplicado para localizar precisamente os pontos de início e fim.
   • Eficiência Computacional: Ao restringir o espaço de busca às regiões ampliadas derivadas da etapa de triagem, o WISER alcança uma complexidade computacional de $O(n)$, sendo o primeiro algoritmo de segmentação com garantia teórica de tempo linear.

Principais Contribuições

• Perspectiva Inovadora: O artigo estabelece uma conexão formal entre a localização de marca d'água e a detecção de mudança de ponto epidêmica, um framework anteriormente subutilizado neste domínio.
• Garantias Teóricas: Os autores fornecem limites de erro de amostra finita e provam a consistência do WISER para detectar múltiplos segmentos com marca d'água. O Teorema 3.1 estabelece que a diferença simétrica entre os intervalos estimados e reais converge para zero a uma taxa de $O((\rho \tilde{d})^{-1})$. O Teorema 4.1 estende isso para o caso de múltiplos segmentos, provando que o WISER identifica corretamente o número de segmentos e suas localizações com alta probabilidade conforme $n \to \infty$.
• Inovação Algorítmica: O WISER é o primeiro algoritmo a oferecer validade teórica comprovável para a localização de marca d'água de múltiplos segmentos gerais, mantendo a eficiência computacional de $O(n)$.
• Robustez: O método é projetado para ser agnóstico à arquitetura específica do LLM ou à NTP, baseando-se apenas nas propriedades das estatísticas de pivô e na hipótese de alternativas elevadas.

Resultados Experimentais
Experimentos numéricos extensos foram conduzidos em conjuntos de dados de referência (C4 News) utilizando vários LLMs (ex: OPT, Gemma, Llama-3, Mistral) e diversos esquemas de marca d'água (Gumbel, Transformação Inversa, Red-Green, Permute-and-Flip).

• Precisão: O WISER superou consistentemente as bases de comparação de última geração (Aligator, SeedBS-NOT, Waterseeker) em todas as métricas, incluindo Interseção sobre União (IoU), Precisão, Recall e F1-score. Em muitos cenários, o WISER alcançou um desempenho próximo ao estimador "Oracle" (que assume o conhecimento do número real de segmentos $K$).
• Velocidade: A análise de tempo de execução empírica confirmou a complexidade teórica de $O(n)$. O WISER foi significativamente mais rápido que os métodos concorrentes, que frequentemente exibiam escalonamento superlinear ou quadrático.
• Robustez: O algoritmo manteve alto desempenho sob níveis variados de dependência temporal na geração de tokens e demonstrou resiliência contra edições humanas (substituição, inserção, deleção) em textos de fontes mistas.

Significância e Alegações
O artigo posiciona o WISER como uma ferramenta crítica para moderação de IA e verificação de conteúdo. Os autores alegam que, ao unir a teoria estatística clássica (mudanças de ponto epidêmicas) com os desafios modernos da IA generativa, produziram uma solução que é simultaneamente teoricamente válida e computacionalmente eficiente.

A significância reside em preencher uma lacuna na literatura onde os métodos existentes eram ou muito lentos para implantação prática em documentos longos ou careciam de garantias estatísticas rigorosas. Os autores enfatizam que sua abordagem não requer conhecimento da arquitetura específica do LLM, tornando-a uma solução generalizável para detectar e localizar conteúdo com marca d'água em cenários do mundo real envolvendo texto misto humano-IA. O trabalho também destaca a utilidade das estatísticas de pivô para lidar com a natureza não estacionária das sequências de tokens com marca d'água, uma característica que o distingue da literatura de detecção de mudança de ponto padrão.