La inferencia en LLM es un problema de varios miles de millones de dólares. Nuestro nuevo artículo introduce un algoritmo SOTA en muestreo especulativo multiborrador, Global Resolution, que logra avances significativos en este problema. Desmenuzando a continuación 🧵👇

Un enfoque para la inferencia eficiente se denomina muestreo especulativo. Este utiliza un modelo barato de 'borrador' para producir 'conjeturas' sobre lo que tendría el modelo objetivo más grande.

Al aprovechar las eficiencias de paralelismo de las GPUs modernas, esto puede acabar reduciendo el número de pasadas hacia adelante del modelo objetivo en más de 5 veces.

El muestreo especulativo puede generalizarse para incluir múltiples conjeturas de varios modelos de borrador. Pero no está claro cuál es el mejor algoritmo para combinar estas múltiples conjeturas.

En el caso de un solo paso, trabajos previos han demostrado que la solución óptima puede encontrarse resolviendo un programa lineal de transporte óptimo, el OTLP.

Sin embargo, el OTLP es extremadamente difícil de resolver casi exactamente, ya que crece exponencialmente en tamaño de vocabulario. ¿Cómo podemos solucionarlo?

La clave es aprovechar la estructura adicional en la construcción del árbol de draft.

Trabajos previos [Hu et al.] demostraron que cuando el árbol de borrador se forma mediante muestreo i.i.d., dualizando el OTLP, el valor objetivo óptimo puede calcularse en tiempo casi lineal mediante minimización submodular.

Sin embargo, hasta nuestro trabajo, ningún método era capaz de resolver la solución que lograra este valor objetivo óptimo. Sin esta pieza que falta, todo lo que nos da el trabajo previo es la eficiencia del bloque, la máxima aceleración teórica. No nos dice cómo lograr esta aceleración.

Nuestro trabajo es el primero en reducir significativamente la dimensionalidad del OTLP, utilizando tres ideas.

Invertimos la dualización de la OTLP en trabajos previos [Hu et al.] con la holgura complementaria, para formular la OTLP como un problema de viabilidad de flujo.

Muchas de las restricciones de desigualdad de flujo son redundantes. Usando un algoritmo codicioso de la teoría polimatroide, podemos unir estos.

Este problema de flujo reducido tiene una solución que puede parametrizarse como el softmax de un vector de baja dimensión, y este vector puede calcularse mediante minimización convexa. Esto reduce la OTLP en variables V^{n+1} a un problema de minimización convexa en V variables.

Sin embargo, V puede ser bastante grande, por lo que en nuestro artículo aplicamos aproximaciones adicionales con la tasa de error del modelo objetivo acotada para reducir aún más el tiempo computacional.

Para muchos casos con V restringido a modelos top-k y n draft, como se muestra arriba, Global Resolution es el _único_ solucionador capaz de resolver el OTLP en un tiempo razonable.

Además, usando Global Resolution, podemos mejorar las tasas de aceptación de Llama y Gemma hasta en un 6%: En resumen, la Resolución Global es SOTA para una verificación óptima de múltiples borradores en la decodificación especulativa.

Todavía queda mucho trabajo por hacer aquí, ya sea relajando el entorno del iid o ampliando a varios pasos.