Resumen Técnico: Muestreo de Rechazo Adaptativo Restringido (CARS)

1. Planteamiento del Problema

Los Modelos de Lenguaje (LM) se despliegan cada vez más en aplicaciones que requieren salidas que satisfagan restricciones semánticas o sintácticas estrictas, como la generación de código sintácticamente válido, la adhesión a esquemas de datos o la producción de estructuras químicas. El desafío central en la generación restringida es equilibrar dos requisitos contrapuestos:

1. Fidelidad: Las muestras deben seguir la distribución condicional exacta del LM dado la restricción ($P_L$), en lugar de una aproximación.
2. Eficiencia: El método debe minimizar el número de pasadas hacia adelante (forward passes) del LM requeridas para generar muestras válidas.

Los enfoques existentes se dividen en tres categorías, cada una de las cuales falla en cumplir ambos criterios simultáneamente:

• Exacto pero Ineficiente: El Muestreo de Rechazo (RS) estándar produce muestras sin sesgo de la verdadera distribución restringida ($P_L$), pero descarta la gran mayoría de los candidatos en dominios estructurados (por ejemplo, tasas de aceptación <1%), lo que conduce a costos computacionales prohibitivos.
• Eficiente pero Sesgado: La Decodificación Restringida Codiciosa (GCD) impone la validez mediante el enmascaramiento de tokens inválidos durante la generación. Aunque es eficiente, distorsiona de manera demostrable la distribución condicional del LM, lo que a menudo degrada el rendimiento posterior y potencialmente impide la terminación.
• Asintóticamente Exacto pero Inestable: Métodos como MCMC o Monte Carlo Secuencial (SMC) convergen a la distribución correcta en el límite, pero no ofrecen una regla de parada fundamentada. Las muestras tempranas pueden estar arbitrariamente sesgadas, y la eficiencia depende fuertemente de la sintonización de hiperparámetros y del número de iteraciones necesarias para la estabilización.

El artículo argumenta que existe una brecha para un algoritmo que sea exacto (preservando la verdadera distribución) y amortizadamente eficiente (mejorando la eficiencia con el tiempo sin sacrificar la fidelidad), particularmente en dominios que requieren conjuntos diversos de muestras válidas como el fuzzing de programas y el descubrimiento molecular.

2. Metodología: Muestreo de Rechazo Adaptativo Restringido (CARS)

CARS es un algoritmo de muestreo exacto que combina la fidelidad del Muestreo de Rechazo con la eficiencia del recorte adaptativo. Se basa en el Muestreo de Rechazo Adaptativo (ARS), pero lo extiende aprovechando la estructura de las restricciones para podar no solo las muestras rechazadas, sino familias enteras de continuaciones inválidas.

Mecanismo Central

El algoritmo mantiene un conjunto de prefijos inválidos ($W$) descubiertos durante el proceso de muestreo. Utiliza una estructura de datos Trie para almacenar estos prefijos y redimensiona dinámicamente la distribución de muestreo ($R_W$) para evitarlos.

1. Inicialización: El algoritmo comienza con un conjunto vacío de prefijos inválidos ($W = \emptyset$).
2. Muestreo: En cada iteración, el algoritmo toma una secuencia de una distribución reponderada $R_W$. Esta distribución se deriva de la distribución original del LM $P$ mediante la normalización sobre secuencias que no extienden ningún prefijo en $W$.
   • Formalmente, para un prefijo $u$, la probabilidad de extenderlo a una secuencia válida se rastrea como $p_u$. Si $u$ extiende un prefijo conocido como inválido, $p_u = 0$.
   • La probabilidad de muestreo para un token $a$ dado el prefijo $u$ se ajusta: $R_W(ua | u) = P(ua | u) \cdot \frac{p_{ua}}{p_u}$.
3. Recorte Adaptativo (La Innovación Clave): Cuando se genera una muestra, CARS no solo registra la cadena rechazada (como en el ARS estándar). En su lugar, identifica todos los prefijos de la secuencia generada que violan la restricción y todas sus continuaciones inválidas.
   • Específicamente, si se genera una secuencia $w$, CARS añade al conjunto $W$ el prefijo más corto $u$ de $w$ que no pertenece al lenguaje válido $L$.
   • Crucialmente, también añade todas las extensiones $ua$ (donde $a$ es un token) tales que $ua \notin \text{prefix}(L)$.
   • Este proceso efectivamente "resta" la masa de probabilidad de subárboles enteros de continuaciones inválidas de los futuros sorteos.
4. Actualización: El Trie se actualiza para reflejar los nuevos prefijos inválidos, y los valores de probabilidad ($p_u$) se propagan hacia arriba. Esto asegura que los futuros muestreos nunca revisiten estos caminos inválidos, aumentando de forma monótona la tasa de aceptación.

Propiedades Teóricas

• Exactitud: CARS produce muestras exactamente de la distribución restringida objetivo $P_L$. El reponderaje asegura que la masa de probabilidad se redistribuya correctamente entre las secuencias válidas.
• Monotonicidad: La tasa de aceptación mejora de forma monótona a medida que el conjunto $W$ crece.
• Rendimientos Decrecientes: La masa de probabilidad esperada eliminada por muestra es no creciente. Esto sugiere un heurístico práctico: una vez que el trie deja de eliminar una masa de probabilidad significativa, la distribución puede "congelarse" para el muestreo subsecuente sin una pérdida significativa en la eficiencia.

3. Contribuciones Clave

1. Diseño de Algoritmo: Introducción de CARS, un nuevo algoritmo para la generación de LM restringida que logra la exactitud con eficiencia práctica al aprovechar la estructura de las restricciones para podar las continuaciones de prefijos inválidos.
2. Garantías Teóricas: Demostración de que CARS muestrea de la verdadera distribución restringida y que sus actualizaciones adaptativas aumentan monótonamente la probabilidad de obtener muestras válidas.
3. Validación Empírica: Demostración de que CARS supera a los métodos existentes en términos de eficiencia de muestreo (menos pasadas hacia adelante del LM por muestra válida) y diversidad de muestras en múltiples dominios.

4. Resultados Experimentales

Los autores evaluaron CARS en cuatro modelos (Llama-3.1-8B/70B, Qwen2.5-7B/14B) a través de tres dominios distintos:

A. Fuzzing Basado en Gramática

• Tarea: Generar semillas de programa diversas y válidas (JSON, SQL, XML) para maximizar la cobertura de código en fuzzers.
• Resultados: CARS alcanzó el objetivo de 100 muestras válidas con significativamente menos generaciones que RS, ARS y RSFT. Por ejemplo, en la generación de XML sin prompts de gramática, CARS requirió ~440 generaciones frente a >2,000 para RS/ARS (que no lograron alcanzar el objetivo).
• Impacto: Las semillas generadas por CARS condujeron a una mayor cobertura de líneas (7,985 líneas) en comparación con GCD (7,115) y MCMC (~7,965), demostrando que la fidelidad de la distribución se traduce en un mejor rendimiento posterior.

B. Síntesis Molecular

• Tarea: Generar cadenas SMILES válidas para clases químicas específicas (Acrilatos, Extensores de Cadena, Isocianatos).
• Resultados: CARS requirió 4.3× menos muestras que RS y 1.3× menos que ARS para generar 100 moléculas válidas. Logró los puntajes más altos de validez y diversidad entre los métodos exactos.
• Fidelidad: La divergencia KL de CARS fue 1.5× menor que la de MCMC y 1.8× menor que la de AWRS, indicando una adherencia superior a la verdadera distribución.

C. Generación de Text-to-SQL

• Tarea: Generar consultas SQL a partir de preguntas en lenguaje natural (conjunto de datos Spider).
• Resultados: CARS logró la mayor precisión de ejecución (0.578) entre todos los métodos. Requirió 1.85× menos muestras que RS y 1.28× menos que ARS.
• Comparación: Mientras que los métodos aproximados como GCD fueron más rápidos (1.00 muestras/consulta), sufrieron de una menor precisión (0.525). CARS ofreció el mejor equilibrio, superando a GCD en precisión, requiriendo solo 1.1× las muestras.

5. Significado y Reivindicaciones

El artículo afirma que CARS establece un nuevo estado del arte para el muestreo de la distribución exacta restringida de un LM. Su importancia radica en resolver el compromiso fundamental entre exactitud e eficiencia:

• A diferencia de RS, CARS es amortizadamente eficiente en la práctica, lo que lo hace viable para tareas que requieren muchas muestras diversas.
• A diferencia de GCD y otros métodos aproximados, CARS preserva la verdadera distribución del LM, asegurando que el rendimiento posterior (por ejemplo, cobertura de fuzzing, diversidad química, precisión de ejecución de SQL) no se vea comprometido por la distorsión de la distribución.

Los autores señalan que CARS es más efectivo cuando las restricciones son verificables por prefijos y altamente informativas para el recorte (por ejemplo, gramáticas de lenguaje independiente del contexto). En escenarios donde el espacio de entradas inválidas consiste en muchos subespacios de baja probabilidad independientes sin prefijos compartidos, las ganancias sobre ARS pueden ser más modestas, y los métodos aproximados podrían seguir siendo una alternativa práctica. Sin embargo, para la mayoría de las tareas de generación estructurada, CARS proporciona una solución con principios, exacta y eficiente.