Hybrid Verified Decoding: Learning to Allocate Verification in Speculative Decoding

Resumen Técnico: Decodificación Verificada Híbrida

Planteamiento del Problema
La generación de Modelos de Lenguaje Extensos (LLM) está limitada por la naturaleza secuencial de la decodificación autorregresiva, donde cada nuevo token requiere un pase frontal completo sobre el prefijo actual y la caché de Clave-Valor (KV). La decodificación especulativa aborda esto proponiendo tokens candidatos mediante una fuente de "borrador" (draft) y verificándolos en un solo paso con el modelo objetivo. Sin embargo, la eficiencia de la decodificación especulativa depende de la "tasa de aceptación": el número de tokens propuestos que el modelo objetivo acepta.

Las fuentes de borrador libres de parámetros (por ejemplo, cachés de sufijos, recuperación) ofrecen propuestas de bajo costo al reutilizar continuaciones de los prompts o del historial de generación, pero sufren de una limitación crítica: un emparejamiento de caché que parece prometedor en un paso de generación puede resultar en un prefijo aceptado muy corto en el siguiente debido a variaciones dependientes del estado (por ejemplo, diferentes argumentos para una llamada a herramienta similar). Verificar un borrador de caché de bajo rendimiento incurre en una sobrecarga sin un aumento significativo de velocidad. Los métodos adaptativos existentes suelen ajustar las estructuras o presupuestos de los borradores, pero no predicen explícitamente el rendimiento (longitud aceptada) de un borrador de caché antes de comprometerse con la verificación.

Metodología: Decodificación Verificada Híbrida
Los autores proponen la Decodificación Verificada Híbrida, un marco que trata la selección del borrador como un problema de asignación de verificación guiado por el rendimiento. En lugar de verificar ciegamente cada borrador de caché o depender únicamente de un generador basado en modelos, el sistema predice la longitud aceptada esperada de un borrador de caché antes de la verificación.

1. Borrador de Doble Fuente: El sistema mantiene dos fuentes de borrador:
   • Generador Basado en Caché ($D_C$): Un mecanismo libre de parámetros (instanciado como SuffixDecoding) que propone continuaciones emparejando sufijos en el prompt de entrada y en el historial de generación.
   • Generador Basado en Modelo ($D_m$): Un generador aprendido (específicamente EAGLE3) utilizado como respaldo (fallback).
2. Predicción de Rendimiento: Antes de la verificación, un predictor de rendimiento ligero ($g_\theta$), implementado como un MLP (perceptrón multicapa), estima la longitud aceptada ($\hat{y}_t$) del borrador de caché actual.
   • Características: El predictor toma un vector de características en tiempo de ejecución ($\phi_t$) que incluye el emparejamiento del sufijo, la longitud del borrador, la posición de decodificación actual, el historial reciente e indicadores de estructura de tokens.
   • Regla de Decisión: Si el rendimiento predicho $\hat{y}_t$ supera un umbral $\tau$, el borrador de caché se envía para verificación. De lo contrario, el sistema recurre al generador basado en el modelo.
3. Entrenamiento mediante Replay de Trazas: El predictor se entrena mediante un procedimiento de reproducción (replay). Para cada posición de token en una traza de generación del modelo objetivo, el sistema reconstruye el estado, genera un borrador de caché y calcula la longitud aceptada "oráculo" ($y_t$) comparando el borrador contra la continuación real del modelo objetivo. El modelo se entrena mediante regresión para minimizar el error cuadrático entre la longitud predicha y la real.

Contribuciones Clave

• Formulación: El artículo formula la selección de borradores dependientes del estado como un problema de asignación de verificación guiado por el rendimiento, definiendo la "longitud aceptada" como la variable principal de rendimiento.
• Algoritmo: Introduce la Decodificación Verificada Híbrida, que cambia dinámicamente entre la generación de borradores basada en caché y la basada en modelos según una estimación de rendimiento previa a la verificación.
• Procedimiento de Entrenamiento: Propone un método de entrenamiento ligero basado en el replay que deriva señales de supervisión directamente de las trazas de generación sin requerir el entrenamiento de un modelo adicional para el predictor.
• Evaluación Exhaustiva: El método se evalúa en tres LLMs (Qwen3-8B, Qwen3-4B, Llama3.1-8B) y dieciséis conjuntos de datos que abarcan flujos de trabajo agénticos, codificación, generación estructurada y chat de código abierto.
• Integración de Sistema: Los autores proporcionan un análisis sistemático de las oportunidades de caché, los rendimientos de verificación y los costos de ejecución, incluyendo un prototipo de servicio vLLM para la validación del despliegue.

Resultados

• Desempeño: A través de 48 pares de modelo-conjunto de datos, la Decodificación Verificada Híbrida supera a la Decodificación Codiciosa (Greedy Decoding) en 47 casos y a SuffixDecoding en 46 casos.
• Aceleración (Speedup): El método logra una aceleración promedio de 2.73x sobre EAGLE3 (un fuerte baseline basado en modelos) en todas las configuraciones.
• Cargas de Trabajo Agénticas: El enfoque es particularmente efectivo en tareas agénticas y de edición de flujo de trabajo (por ejemplo, Delegate-52, InstructEdit), donde supera consistentemente a EAGLE3 y otros baselines. Estas cargas de trabajo se benefician de patrones estructurales recurrentes que la caché aprovecha, mientras que el predictor filtra los desajustes dependientes del estado.
• Eficiencia: El análisis muestra que el método reduce significativamente el número de ciclos de decodificación por cada 1,000 tokens (por ejemplo, de 571 para EAGLE3 a 200 para la Decodificación Verificada Híbrida en Llama3.1-8B) manteniendo costos por ciclo comparables a la generación basada en modelos.
• Precisión del Predictor: El predictor de rendimiento identifica con éxito borradores de alto rendimiento (definidos como longitud aceptada $\ge 6$) con una precisión que oscila entre el 78.2% y el 87.6% y una exhaustividad (recall) de entre el 61.4% y el 79.8% en diferentes modelos.

Significancia y Reivindicaciones
El artículo argumenta que el cuello de botella principal en la decodificación especulativa no es solo la calidad del borrador, sino el momento de la decisión de verificación. Al predecir el rendimiento de un borrador libre de parámetros antes de la verificación, la Decodificación Verificada Híbrida evita la sobrecarga de verificar emparejamientos de caché de bajo valor.

Los autores afirman que este enfoque apunta a la selección de borradores en tiempo de ejecución como una dirección prometedora para la decodificación especulativa. Demuestran que la estructura del prompt crea oportunidades de caché, pero los borradores de alto rendimiento se concentran en un pequeño subconjunto del espacio de borradores. El predictor aprendido aísla eficazmente estas oportunidades de alto valor, permitiendo que el sistema amortice los costos de verificación sobre prefijos aceptados más largos. Los resultados sugieren que, para cargas de trabajo estructuradas y agénticas, un enfoque híbrico guiado por la estimación de rendimiento puede superar significativamente a las estrategias puramente basadas en modelos o puramente basadas en caché.