Can we Watermark Low-Entropy LLM Outputs?

Aquí presento un resumen técnico detallado del artículo "Can we Watermark Low-Entropy LLM Outputs?" (¿Podemos marcar con filigrana las salidas de baja entropía de los LLM?), escrito por Noam Mazor, Andrew Morgan y Rafael Pass.

1. El Problema: Limitaciones de las Filigranas Actuales

El artículo aborda un desafío crítico en la seguridad de los Modelos de Lenguaje Grande (LLM): la capacidad de marcar con filigrana (watermarking) sus salidas de manera indetectable y robusta.

• Indetectabilidad: El esquema no debe alterar la distribución de probabilidad de la salida del LLM. Un adversario sin la clave secreta no debe poder distinguir entre una salida natural y una marcada.
• Robustez: La filigrana debe sobrevivir a ataques de edición, como sustituciones, inserciones o borrados de tokens.
• La Brecha de Entropía: Trabajos recientes (Christ et al. [CG24], Golowich et al. [GM24]) han logrado esquemas robustos, pero bajo una suposición restrictiva: requieren que las salidas del LLM tengan una tasa de entropía constante alta. Específicamente, exigen que una fracción constante de los tokens en una subcadena larga tenga una entropía empírica de al menos $O(\log |T|)$, donde $|T|$ es el tamaño del alfabeto de tokens.
• El Caso Realista: En la práctica, muchos textos generados por LLMs (especialmente en dominios técnicos, respuestas deterministas o frases comunes) tienen baja entropía por token (cercana a 1 bit o incluso menor). Los esquemas existentes fallan en este régimen porque no pueden correlacionar tokens de baja entropía con un código pseudorrandómico sin introducir errores masivos o requerir suposiciones distribucionales fuertes.

2. Metodología y Enfoque Técnico

Los autores proponen un nuevo marco que permite la marca de filigrana en alfabetos grandes con una entropía mínima (solo se requiere que una fracción constante de tokens tenga 1 bit de entropía empírica), independientemente del tamaño del alfabeto.

Conceptos Clave:

1. Códigos Pseudorrandómicos (PRC): Se basan en la construcción de códigos que son indistinguibles del ruido aleatorio para un adversario computacionalmente limitado, pero que pueden corregir errores (robustez).
2. Hashing de Tokens: En lugar de convertir tokens grandes a binario (lo que aumenta la entropía requerida) o usar un alfabeto grande para el PRC (lo que también aumenta la entropía), el método propone:
   • Dividir la salida del LLM en bloques.
   • Asignar una función de hash aleatoria $h: T \to \{0, 1\}$ a cada bloque.
   • Mapear cada token generado a un bit (0 o 1) mediante este hash.
   • Intentar alinear el hash del token con el bit correspondiente del código PRC binario.

El Algoritmo de Marcaje (Watermarking):

Para generar el siguiente token $t$ y codificar un bit $c_i$ del PRC:

1. Muestrear dos tokens independientes $t_0, t_1$ de la distribución del LLM.
2. Caso de Éxito: Si $h(t_0) \neq h(t_1)$, seleccionar el token cuyo hash coincida con el bit objetivo $c_i$. Esto no sesga la distribución porque la elección depende de la aleatoriedad del hash y la distribución original.
3. Caso de Fallo: Si $h(t_0) = h(t_1)$, seleccionar un token al azar. Esto introduce un error con probabilidad 1/2, pero si la entropía es suficiente, la probabilidad de éxito es alta.

Manejo de la Entropía Baja y Reutilización de Hash:

• Reutilización de Hash: Para soportar borrados (deletions), se usa la misma función de hash $h$ para todo un bloque de tokens (en lugar de una nueva función por token). Esto permite al detector saber qué hash usar incluso si se borran tokens intermedios.
• Análisis de Robustez: Los autores demuestran que, aunque la reutilización de $h$ crea correlaciones, si existe una fracción constante de tokens con entropía $\ge 1$, la probabilidad de que el hash "divida" (split) los tokens es suficiente para mantener la tasa de error por debajo de 1/2, permitiendo la recuperación del código PRC.

3. Contribuciones Principales y Resultados

El artículo presenta cuatro teoremas principales (y sus corolarios) que establecen la viabilidad de la marca de filigrana en baja entropía bajo diferentes supuestos de robustez:

A. Robustez contra Sustituciones Aleatorias (Teorema 1 / Corolario 1)

• Resultado: Se construye un esquema indetectable y robusto contra una fracción $(1/2 - \epsilon)$ de sustituciones aleatorias.
• Requisito de Entropía: Solo se necesita que una fracción constante de tokens tenga 1 bit de entropía empírica.
• Suposición: Basado en la dureza subexponencial del problema LPN (Learning Parity with Noise), asumiendo la existencia de un PRC binario robusto.

B. Robustez contra Sustituciones y Borrados Aleatorios (Teorema 2 / Corolario 2)

• Resultado: Extensión para soportar borrados aleatorios además de sustituciones.
• Suposición Adicional: Requiere la suposición heurística de que el prompt es "natural" (o que los errores introducidos por el esquema de marcaje y las sustituciones siguen un canal simétrico binario). Esto evita casos patológicos como el "ataque de emojis" (insertar emojis deterministas que tienen entropía cero).

C. Robustez sin Suposiciones Heurísticas (Teorema 3 / Corolario 3)

• Resultado: Si existe un PRC binario robusto contra sustituciones adversarias y borrados aleatorios, entonces existe un esquema de marcaje para LLMs de baja entropía robusto contra estos ataques sin necesidad de suposiciones heurísticas sobre el prompt.
• Estado Actual: Actualmente no se conoce una construcción de PRC binario con esta robustez completa, pero el teorema establece la reducción teórica.

D. Robustez contra Ediciones Adversarias (Teorema 4 / Corolario 3)

• Resultado: Utilizando la construcción de PRC de [CGG+25] (basada en "códigos permutados"), se logra robustez contra una fracción constante de ediciones adversarias (inserciones, borrados, sustituciones).
• Costo: Se requiere que una fracción constante de la salida completa (no solo una subcadena) tenga entropía suficiente, ya que un adversario podría atacar selectivamente las partes de baja entropía.

4. Comparación con Trabajos Previos

Característica	[CG24] (Christ & Gunn)	[GM24] (Golowich & Moitra)	Este Trabajo (Mazor et al.)
Alfabeto	Binario (o reducción a binario)	Grande (Polinomial)	Grande (Directo)
Requisito de Entropía	$O(\log |T|)$ o suposiciones fuertes	$O(\log \lambda)$ (Alta)	$O(1)$ (Constante/Baja)
Robustez	Sustituciones (aleatorias/adversarias)	Ediciones (Adversarias)	Sustituciones/Borrados/Ediciones
Estructura de Ataque	Manipulación de bits	Manipulación de tokens	Manipulación de tokens (Realista)
Suposiciones	LPN	PRF débiles locales	LPN / Códigos Permutados

5. Significado e Impacto

1. Viabilidad Práctica: Este trabajo cierra la brecha entre la teoría de la marca de filigrana y la realidad de los LLMs. Demuestra que no es necesario que el texto generado sea altamente aleatorio para marcarlo, lo cual es crucial para aplicaciones reales donde el contenido puede ser técnico, repetitivo o determinista.
2. Preservación de Estructura: A diferencia de los enfoques anteriores que reducen los tokens a bits (rompiendo la estructura semántica del token), este método opera a nivel de token, preservando la estructura natural del lenguaje y definiendo ataques de sustitución de manera más realista (ej. sinónimos, redacción).
3. Fundamento Teórico: Establece nuevas reducciones entre la robustez de códigos pseudorrandómicos binarios y la marca de filigrana en alfabetos grandes, proporcionando un camino claro para futuros avances si se mejoran las construcciones de PRC.
4. Seguridad: Proporciona garantías de indetectabilidad computacional, asegurando que la marca no degrade la calidad del modelo ni sea visible para usuarios legítimos, mientras ofrece resistencia contra intentos de eliminación de la marca.

En resumen, el artículo demuestra que es posible marcar con filigrana salidas de LLMs de baja entropía de manera segura y robusta, superando las limitaciones de entropía de los trabajos anteriores mediante el uso inteligente de funciones de hash y códigos pseudorrandómicos binarios.