🤖 machine learning

Greedy Multi-Path Block Verification for Faster Decoding in Speculative Sampling

Este trabajo demuestra que la verificación de bloques es óptima incluso considerando probabilidades fuera de la trayectoria y propone un método eficiente llamado verificación de bloques multi-trayectoria codiciosa (GBV), que mejora la eficiencia de los bloques en más del 30% y reduce los tiempos de decodificación en más del 15% en comparación con métodos existentes.

Autores originales: Rahul Thomas, Arka Pal

Publicado 2026-02-20

📖 4 min de lectura☕ Lectura para el café

CC BY 4.0

Autores originales: Rahul Thomas, Arka Pal

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

¡Claro que sí! Imagina que quieres escribir un cuento muy largo y complejo, pero eres un escritor muy lento porque tienes que pensar en cada palabra individualmente antes de escribirla. Eso es lo que hacen los modelos de Inteligencia Artificial (como los que generan texto) cuando "piensan" o decodifican: son muy precisos, pero lentos.

Este paper presenta una solución inteligente para acelerar este proceso sin perder calidad. Vamos a desglosarlo con analogías sencillas.

1. El Problema: El Escritor Lento y su Asistente

Imagina que tienes un Escritor Maestro (el modelo grande y potente) que escribe historias perfectas, pero tarda mucho en pensar cada palabra. Para acelerarlo, contratas a un Asistente Rápido (un modelo pequeño y barato).

El método antiguo (Muestreo Especulativo): El Asistente escribe rápido un borrador de 8 palabras. El Escritor Maestro revisa palabra por palabra. Si la primera palabra del Asistente está mal, el Maestro la descarta y empieza de nuevo. Si la segunda está mal, también la descarta.
- El problema: Si el Asistente falla en la primera palabra, todo el esfuerzo de escribir las otras 7 se pierde. Es como si un corredor de relevos tropezara en la salida y todo el equipo tuviera que volver a empezar.
La mejora anterior (Verificación de Bloque - BV): Los investigadores anteriores se dieron cuenta de que no debían revisar palabra por palabra, sino bloque por bloque. Si el Asistente escribe un bloque de 8 palabras, el Maestro revisa si el bloque en general tiene sentido. Si las primeras palabras son malas, pero las siguientes son buenas, el Maestro puede aceptar un trozo del bloque.
- Resultado: Es más rápido, pero sigue habiendo un límite. Si el Asistente es muy malo al principio, el Maestro sigue perdiendo tiempo.

2. La Nueva Idea: El Equipo de Asistentes (GBV)

Aquí es donde entra la propuesta de este paper: Verificación de Bloque Multi-Camino Codiciosa (GBV).

Imagina que en lugar de un solo Asistente, contratas a 4 Asistentes diferentes (4 caminos o "paths").

Los 4 Asistentes escriben sus propios borradores de 8 palabras al mismo tiempo (en paralelo).
El Escritor Maestro no revisa uno por uno. En su lugar, tiene un Juez Inteligente.
El Juez mira los 4 borradores y dice: "¡Espera! El borrador del Asistente #3 tiene las palabras más probables de ser correctas según mi experiencia. ¡Ese es el que vamos a usar!".
El Maestro solo revisa el borrador del Asistente #3. Como eligió el mejor candidato, es mucho más probable que acepte muchas palabras seguidas.

3. ¿Por qué es "Codiciosa" (Greedy)?

En informática, un algoritmo "codicioso" es uno que toma la mejor decisión posible en cada paso inmediato, sin preocuparse por el futuro lejano.

La analogía del camino: Imagina que estás en un bosque con 4 senderos. Quieres llegar a la meta lo más rápido posible.
- El método antiguo miraba un solo sendero y si se equivocaba, volvía.
- El nuevo método (GBV) mira los 4 senderos al mismo tiempo. En cada bifurcación, elige el camino que parece más prometedor en ese momento. No calcula matemáticas complejas para ver cuál es el camino perfecto absoluto (eso sería demasiado lento), sino que elige el "mejor candidato" rápidamente y sigue con él.

4. Los Resultados: ¿Qué ganamos?

Los autores probaron esto con modelos reales (como Llama-3) y descubrieron cosas increíbles:

Más eficiencia: Lograron aceptar más palabras por cada vez que el Escritor Maestro "piensa". En lugar de aceptar 3 palabras, a veces aceptan 4 o 5.
Más velocidad: El tiempo total para generar un texto bajó más de un 15%.
El punto dulce: Usar 3 o 4 asistentes (K=3 o K=4) es el mejor equilibrio. Si usas demasiados, el tiempo que tardas en coordinar a todos los asistentes anula la velocidad ganada.

En resumen

Este paper nos dice: "No te limites a un solo asistente rápido. Pide a varios que trabajen en paralelo, elige al que parece más listo en cada momento, y deja que el experto revise solo esa opción."

Es como si en lugar de pedirle a un solo chef que cocine un plato complejo, le pidieras a 4 ayudantes que preparen los ingredientes y tú, el chef maestro, solo revises el plato que parece más delicioso antes de servirlo. ¡El resultado es una cena lista mucho más rápido!

La conclusión final: Esta técnica (GBV) es la nueva forma más rápida y eficiente de hacer que las IAs generen texto, especialmente cuando se les pide que sean muy precisas o cuando se les pide que "piensen" con menos temperatura (más lógica y menos creatividad aleatoria).

1. El Problema

El objetivo central es acelerar la decodificación autoregresiva de Grandes Modelos de Lenguaje (LLMs). Dado que la inferencia en GPUs está limitada por el ancho de memoria y no por la capacidad de cómputo, el Muestreo Especulativo (Speculative Sampling) se utiliza para generar múltiples tokens por llamada al modelo objetivo (target).

Muestreo Especulativo Estándar: Un modelo "borrador" (draft) genera una secuencia de $L$ tokens. El modelo objetivo verifica cada token de forma independiente. Si un token es rechazado, toda la secuencia posterior se descarta. Esto crea un cuello de botella: si el primer token tiene baja probabilidad de aceptación, no hay aceleración, incluso si los siguientes son aceptados.
Verificación de Bloques (Block Verification - BV): Una mejora reciente que verifica prefijos completos en lugar de tokens individuales, mejorando la eficiencia. Sin embargo, la BV estándar solo utiliza una sola ruta de borrador y se limita a las probabilidades "en la ruta" (on-path).
Limitación Actual: Aunque existen métodos de múltiples rutas (multi-path), la mayoría son ineficientes o no aprovechan completamente la información de las distribuciones fuera de la ruta seleccionada para optimizar la verificación.

2. Metodología

Los autores proponen un marco teórico basado en Programación Lineal (LP) para encontrar el algoritmo de verificación óptimo y derivan una aproximación eficiente llamada Verificación de Bloques Múltiples con Codicia (GBV).

A. Formulación mediante Programación Lineal (LP)

LP Agnóstico a la Información (Single-Path): Los autores formulan un LP que encodifica las aceleraciones factibles para algoritmos de verificación válidos. Demuestran que, incluso con acceso a las distribuciones conjuntas completas (fuera de la ruta), la Verificación de Bloques (BV) sigue siendo óptima para una sola ruta. Esto indica que la restricción de "coincidencia de prefijos" (prefix-matching) es el verdadero cuello de botella, no la falta de información.
LP Multi-Path: Extienden el LP al caso donde el modelo borrador genera $K > 1$ $K > 1$ rutas candidatas i.i.d. (independientes e idénticamente distribuidas).
- Descubren que, en este escenario, el conocimiento de las distribuciones fuera de la ruta sí puede mejorar la eficiencia.
- Demuestran que el algoritmo óptimo consiste en seleccionar probabilísticamente una de las $K$ rutas (mediante una regla $\Gamma$ ) y ejecutar BV sobre esa ruta con una distribución de borrador sesgada ( $q_\Gamma$ ).
- El problema de encontrar la regla óptima $\Gamma$ es un problema de optimización no lineal intratable que requiere conocer las distribuciones conjuntas completas.

B. Aproximación Greedy (GBV)

Dado que la solución óptima es intratable, proponen una clase de algoritmos de aproximación codiciosos (greedy):

Clasificación Global: Se ordenan todas las posibles secuencias candidatas según una regla global.
Selección: Se selecciona la ruta mejor clasificada entre las $K$ muestreadas.
Verificación: Se ejecuta BV sobre esa ruta seleccionada utilizando una distribución de borrador sesgada calculada heurísticamente.

Para hacer esto eficiente y práctico (sin necesidad de distribuciones fuera de la ruta), proponen una regla de clasificación basada en árboles:

Se ordenan los tokens localmente en cada prefijo basándose en la relación $p(x|c)/q(x|c)$ (probabilidad objetivo sobre borrador).
Esto induce un orden lexicográfico global sobre las rutas.
Esta regla permite calcular la distribución sesgada $q_\Gamma$ de manera eficiente utilizando solo valores "en la ruta", resultando en el algoritmo GBV.

3. Contribuciones Clave

Optimalidad de BV en Single-Path: Prueban formalmente mediante un LP que la Verificación de Bloques es óptima incluso si se tiene acceso a toda la información de las distribuciones objetivo y de borrador, siempre que se mantenga la restricción de salida de prefijo.
LP Multi-Path y Descomposición: Establecen un LP para el escenario multi-ruta y demuestran que cualquier algoritmo válido multi-ruta se puede descomponer en una selección de ruta seguida de una verificación de bloque en una ruta única con distribución sesgada.
Algoritmo GBV: Desarrollan una aproximación greedy eficiente que no requiere información fuera de la ruta, logrando aceleraciones significativas.
Justificación Teórica: Proporcionan fundamentos teóricos para la regla de clasificación basada en árboles utilizada en GBV, mostrando su conexión con algoritmos greedy de politroides.

4. Resultados Experimentales

Los experimentos se realizaron en modelos como OPT, Qwen-3 y Llama-3 con diferentes tamaños de borrador y datasets (GSM8K, HumanEval, MATH500).

Eficiencia de Bloque (Block Efficiency):
- GBV mejora la eficiencia de bloques en más del 30% en comparación con la BV estándar (single-path).
- La mejora es más pronunciada al pasar de $K=1$ a $K=2$ o $K=3$ , con retornos decrecientes para $K=4$ .
Tiempo de Pared (Walltime):
- GBV reduce los tiempos de decodificación en más del 15% en comparación con BV.
- En Llama-3 70B, GBV supera a los métodos de verificación multi-ruta más avanzados (SOTA) en más de un 15% de rendimiento (throughput).
Impacto de la Temperatura:
- A temperaturas bajas (ej. 0.2), GBV con múltiples rutas ( $K>1$ ) supera significativamente a la BV estándar, mientras que a temperatura 1.0, la BV estándar puede ser competitiva o superior en ciertos modelos grandes (como Qwen-3), dependiendo del costo de la inferencia del borrador.
Longitud del Borrador ( $L$ ):
- Se encontró que $L=8$ es un punto óptimo. Aumentar $L$ a 16 o 24 mejora ligeramente la eficiencia de bloques pero degrada drásticamente el tiempo total debido a que el cuello de botella se desplaza hacia la generación de la secuencia de borrador.

5. Significado e Impacto

Nueva Línea Base: GBV establece un nuevo estado del arte (SOTA) para la decodificación especulativa, especialmente en configuraciones de baja temperatura y modelos grandes.
Eficiencia Teórica y Práctica: El trabajo cierra la brecha entre la teoría de la eficiencia óptima (LP) y la implementación práctica, demostrando que las aproximaciones codiciosas pueden acercarse mucho al óptimo sin el costo computacional de resolver problemas no lineales complejos.
Adaptabilidad: Proporciona directrices claras sobre cuándo usar múltiples rutas ( $K$ ) y qué longitud de bloque ( $L$ ) elegir según el modelo objetivo, el modelo borrador y la temperatura de muestreo, optimizando el equilibrio entre ancho de banda y cómputo.

En resumen, el paper introduce GBV, un método que combina una formulación teórica rigurosa con una implementación eficiente para acelerar significativamente la inferencia de LLMs, superando a los métodos existentes tanto en eficiencia de tokens generados como en tiempo de respuesta real.