Recency/Frequency Adaptive KV Caching for Large Language Model Serving

Resumen Técnico: Almacenamiento en Caché KV Adaptativo por Recencia/Frecuencia para el Servicio de Grandes Modelos de Lenguaje

Planteamiento del Problema
Los sistemas de servicio de Grandes Modelos de Lenguaje (LLM) enfrentan desafíos significativos en la gestión de los cachés de Clave-Valor (KV) debido al crecimiento del tamaño de los modelos y las longitudes de contexto, lo que sobrecarga la capacidad de la memoria GPU limitada. Si bien el almacenamiento en caché de prefijos y la reutilización son críticos para reducir la computación redundante y mejorar el rendimiento (throughput), las estrategias de gestión existentes dependen predominantemente de políticas de desalojo de Menos Recientemente Utilizado (LRU). Los autores argumentan que LRU es insuficiente para los patrones de acceso diversos y complejos que se encuentran en las cargas de trabajo de LLM del mundo real. Específicamente, LRU no logra distinguir entre solicitudes que exhiben una fuerte localidad temporal (acceso reciente) y aquellas que actúan como "puntos calientes" (acceso frecuente a través de diferentes usuarios o sesiones). Esta limitación provoca que cargas de trabajo no relacionadas se desalojen mutuamente de sus cachés, degradando las tasas de acierto (hit rates) y aumentando la latencia, particularmente en escenarios como la Respuesta a Preguntas (QA) basada en documentos y las conversaciones de múltiples turnos.

Metodología
Para abordar estas limitaciones, el artículo propone integrar el algoritmo de Almacenamiento en Caché de Reemplazo Adaptativo (ARC) en el marco de servicio vLLM. La metodología introduce una estrategia híbrida de recencia-frecuencia que asigna dinámicamente el espacio del caché entre bloques KV accedidos recientemente y frecuentemente.

Los componentes técnicos centrales incluyen:

1. Estructura de Doble Cola: El caché se divide lógicamente en dos colas:
   • L1 (Cola de Recencia): Contiene elementos accedidos una sola vez (compuesta por el caché físico $T1$ y el caché fantasma $B1$).
   • L2 (Cola de Frecuencia): Contiene elementos accedidos múltiples veces (compuesta por el caché físico $T2$ y el caché fantasma $B2$).
   • Los elementos en la cola de recencia son promovidos a la cola de frecuencia tras un segundo acierto.
2. Caché Fantasma (Ghost Caching): El sistema utiliza "cachés fantasmas" ($B1$ y $B2$) que almacenan únicamente metadatos (no bloques KV completos) de los elementos desalojados. Estos cachés rastrean el historial de desalojos.
   • Si una solicitud falla en el caché principal pero acierta en un caché fantasma, esto sirve como una señal de retroalimentación. Un acierto en $B1$ sugiere que la cola de recencia ($T1$) es demasiado pequeña, mientras que un acierto en $B2$ sugiere que la cola de frecuencia ($T2$) necesita una expansión.
3. Partición Dinámica: Basándose en los aciertos en el caché fantasma, el algoritmo ajusta dinámicamente el tamaño de los cachés físicos $T1$ y $T2$ manteniendo un tamaño total de caché fijo. Esto permite que el sistema se adapte a los cambios en la carga de trabajo, como la aparición de nuevos puntos calientes o cambios en los patrones de actividad del usuario.
4. Integración: La estrategia opera al nivel de bloque KV (por ejemplo, 16 tokens), alineándose con el mecanismo de atención paginada (paged attention) utilizado en los sistemas de servicio modernos. Está diseñada para ser libre de parámetros e integra directamente con el módulo de desalojo (evictor) de vLLM.

Contribuciones Clave

• Política de Desalojo Adaptativa: El artículo presenta la primera aplicación de ARC al servicio de LLM, yendo más allá de las políticas estáticas basadas en la recencia hacia un enfoque híbrido dinámico.
• Adaptabilidad de la Carga de Trabajo: El método demuestra la capacidad de equilibrar automáticamente los recursos de caché entre los patrones de acceso reciente y frecuente sin ajuste manual.
• Interpretabilidad: A diferencia de los enfoques basados en aprendizaje que requieren entrenar predictores, este método ofrece una clara interpretabilidad respecto a cómo se asigna el espacio del caché basándose en el historial de acceso.
• Implementación de Código Abierto: Los autores proporcionan una implementación de código abierto integrada con vLLM, disponible para uso de la comunidad e investigación adicional.

Resultados Experimentales
Los autores evaluaron el método propuesto contra la línea base estándar de vLLM LRU y una variante de dos colas estática (DBL) utilizando dos tipos principales de carga de trabajo:

1. QA de Documentos Sintéticos: Utilizando los conjuntos de datos QuALITY y WikiQA con muestreo de solicitudes con distribución de Zipf.
   • Tasa de Acierto (Hit Rate): Mejoró hasta un 10.8% (QuALITY) y un 7.8% (WikiQA) en comparación con LRU.
   • Tiempo al Primer Token (TTFT): Se redujo hasta un 12.6% (QuALITY) y un 7.9% (WikiQA).
   • Las mejoras fueron más pronunciadas en tamaños de caché más pequeños, donde las decisiones de desalojo son más frecuentes.
2. Conversación del Mundo Real: Utilizando una traza del Conjunto de Datos Anónimo Qwen-Bailian (43,058 solicitudes).
   • Tasa de Acierto: Mejoró entre un 1.1% y 2.1%.
   • TTFT: Se redujo entre un 1.0% y 2.0%.
   • El estudio observó que el dimensionamiento adaptativo se volvió cada vez más beneficioso a medida que los tamaños de caché crecían, capturando cambios de carga de trabajo a gran escala que las políticas estáticas pasaron por alto.
3. Inferencia por Lotes (Batch Inference): Los experimentos variando los tamaños de lote en el conjunto de datos QuALITY mostraron que la ventaja relativa de ARC sobre LRU persistió y aumentó ligeramente con tamaños de lote más grandes, manteniendo una reducción del 5–7% en el TTFT.

Significancia y Reivindicaciones
El artículo afirma que la gestión adaptativa del caché KV es un mecanismo práctico y efectivo para mejorar el rendimiento del servicio de LLM. Al capturar patrones de reutilización más allá de la simple recencia, el método propuesto mejora las tasas de acierto del caché y reduce la latencia en diversas cargas de trabajo. Los autores enfatizan que su enfoque se generaliza bien a la inferencia por lotes y proporciona una base para futuros sistemas que manejen patrones de acceso complejos y cambiantes sin la sobrecarga de los predictores basados en entrenamiento. El trabajo sugiere que la partición dinámica de los recursos de caché es un paso crítico hacia un despliegue de LLM más eficiente en entornos de producción.