Resumen Técnico: SAECache – Evicción Consciente Semántica para Cachés de Prefijos en LLM

Declaración del Problema

La caché de prefijos en Modelos de Lenguaje Grande (LLM) tiene como objetivo reducir la latencia de inferencia (específicamente el Tiempo hasta el Primer Token, o TTFT) reutilizando estados de Clave-Valor (KV) de solicitudes que comparten prefijos de entrada. Sin embargo, la eficacia de la caché de prefijos está severamente limitada por la memoria GPU disponible, lo que hace necesaria una política de evicción para descartar bloques menos valiosos cuando se alcanza la capacidad máxima.

Las políticas de evicción existentes, como Least Recently Used (LRU) y Least Frequently Used (LFU), dependen principalmente de estadísticas de tiempo de acceso o frecuencia. Estos enfoques agnósticos al token tratan todos los bloques en caché de manera uniforme, ignorando dos dimensiones críticas de las cargas de trabajo de LLM:

1. Heterogeneidad Semántica: Diferentes tipos de tokens (por ejemplo, prompts del sistema frente a razonamiento de cadena de pensamiento) exhiben tasas de reutilización intrínsecas vastly diferentes.
2. Variabilidad de la Carga de Trabajo: Los patrones de reutilización difieren significativamente entre solicitudes planteadas de un solo turno (reutilización estructural) y conversaciones de múltiples turnos (reutilización temporal local de sesión), con intervalos entre turnos que siguen distribuciones distintas según el tipo de aplicación (por ejemplo, chat frente a flujos de trabajo de agentes).

Los autores observan que tratar un bloque de prompt del sistema de alto valor y un bloque de cadena de pensamiento de bajo valor como equivalentes cuando su recencia coincide conduce a una asignación de memoria subóptima. Además, las políticas de parámetros fijos fallan cuando cambian las composiciones de la carga de trabajo, causando una degradación del rendimiento de hasta 2.7× ante una discrepancia en la carga de trabajo.

Metodología: SAECache

Para abordar estas limitaciones, los autores proponen SAECache (Evicción Adaptativa Semántica para cachés de prefijos), una política que integra la estructura semántica de los tokens con la adaptación en línea a la carga de trabajo. El sistema opera mediante tres mecanismos centrales:

1. Arquitectura de Múltiples Colas con Enrutamiento Basado en Reglas

SAECache enruta los bloques KV a cuatro colas distintas basándose en sus patrones de reutilización dominantes, en lugar de una única cola global:

• Cola de Evicción Primero: Almacena bloques de bajo valor, incluidos tokens de fase de decodificación y bloques de prellenado sin plantilla con bajo potencial de reutilización. Estas se agotan primero.
• Cola Estructural: Almacena bloques KV de sesiones de un solo turno que dependen de estructuras de prompt compartidas (por ejemplo, plantillas de uso de herramientas, instrucciones de programación).
• Cola de Chat: Almacena bloques de múltiples turnos de sesiones conversacionales, modelando la reutilización temporal local de sesión.
• Cola de Agente: Almacena bloques de múltiples turnos de sesiones de agente/uso de herramientas, que exhiben contenido de tokens y distribuciones de intervalos de solicitud diferentes en comparación con el chat estándar.

Un predictor de sesiones de múltiples turnos ligero (un MLP de 3 capas que reutiliza los estados ocultos finales del modelo de servicio) resuelve la ambigüedad para la primera solicitud de una sesión, enrutándola a la cola de múltiples turnos apropiada si se predice una continuación, o a las colas estructural/de evicción primero en caso contrario.

2. Puntuación de Prioridad Local

Dentro de cada cola, los bloques se puntúan para la evicción basándose en una métrica compuesta $P(b)$:
$$P(b) = \alpha_q \cdot w_{\tau(b)} \cdot \frac{p_q(b)}{\Delta t_b}$$

• $\alpha_q$ (Peso de Cola): Un peso dinámico que refleja la eficiencia de aciertos reciente de la cola específica.
• $w_{\tau(b)}$ (Peso de Tipo de Token): Un peso aprendido específico para el tipo de token (por ejemplo, prompt del sistema, consulta del usuario, cadena de pensamiento) del bloque.
• $p_q(b)$ (Probabilidad de Supervivencia Local):
  • Para las colas de Chat/Agente: Calculada como la probabilidad de supervivencia $1 - F_{LN}(\Delta t_b; \mu_q, \sigma_q)$ bajo una distribución log-normal ajustada a los intervalos entre turnos de ese tipo de sesión.
  • Para la cola Estructural: Calculada como $1 - (o_b / o_{max})^\gamma$, donde $o_b$ es el desplazamiento del bloque y $\gamma$ es una potencia de decaimiento aprendida, priorizando los bloques anteriores en un prompt.
• $\Delta t_b$: El tiempo transcurrido desde el último acceso al bloque.

3. Aprendizaje en Línea Totalmente Adaptativo

SAECache elimina el ajuste manual actualizando todos los parámetros en línea mediante un bucle de retroalimentación unificado basado en estadísticas de aciertos/fallos en la caché:

• Pesos de Tipo de Token: Actualizados mediante Promedio Móvil Exponencial (EMA) basados en las tasas de "fallo tras evicción" y las tasas de aciertos generales.
• Parámetros Log-Normales ($\mu, \sigma$): Estimados en línea utilizando Estimación de Máxima Verosimilitud (MLE) sobre los tiempos de acceso observados para las colas de chat y agente.
• Potencia de Decaimiento de Posición ($\gamma$): Aprendida a partir de las correlaciones entre la posición del bloque y las tasas de aciertos en la cola estructural.
• Pesos de Cola ($\alpha_q$): Actualizados basándose en la relación de tokens aciertos a capacidad asignada para cada cola, escalada por un parámetro de temperatura.

Contribuciones Clave

1. Caracterización Empírica: Un estudio sistemático que revela que la reutilización de tokens varía hasta en 756× entre tipos de tokens (92.3% para prompts del sistema frente a 2.2% para cadena de pensamiento) y que los intervalos entre turnos siguen distribuciones log-normales específicas de sesión en lugar de decaimientos exponenciales simples.
2. Política SAECache: Una política de evicción de múltiples colas consciente de la semántica que desacopla mecanismos de reutilización heterogéneos (estructural frente a temporal) y asigna prioridades distintas a los tipos de tokens.
3. Adaptación en Línea: Un marco de aprendizaje que ajusta automáticamente las distribuciones temporales, el decaimiento de posición y los parámetros de ponderación sin intervención manual, adaptándose a cambios en la composición de la carga de trabajo.
4. Evaluación Exhaustiva: Experimentos extensos en conjuntos de datos del mundo real (ShareGPT, LMSys, Chatbot-Arena) que demuestran robustez frente a cargas de trabajo heterogéneas.

Resultados Experimentales

Evaluado en una implementación vLLM con Qwen2.5-1.5B-Instruct en una GPU NVIDIA A40, SAECache se comparó con LRU (línea base de producción) y Caché de Prefijos Aprendida (LPC).

• Mejora en TTFT: SAECache logró una mejora de 1.4× a 2.7× en TTFT sobre líneas base de estilo de producción en cargas de trabajo heterogéneas.
• Tasa de Aciertos en Caché: SAECache consistentemente logró las tasas de aciertos en caché más altas, mejorando en 4.8–5.9 puntos porcentuales sobre la línea base más fuerte (LRU o LPC) en todas las configuraciones probadas.
• Resiliencia ante Discrepancia de Carga de Trabajo: Las alternativas de parámetros fijos sufrieron hasta una degradación de 2.7× en TTFT cuando la composición de la carga de trabajo se desviaba de la traza de entrenamiento. SAECache mantuvo un rendimiento estable adaptando sus parámetros en línea.
• Estudios de Ablación:
  • La ponderación consciente del tipo de token contribuyó con una mejora adicional del 23%.
  • La ponderación adaptativa de colas contribuyó con la mayor ganancia, un 39%.
  • El timing log-normal y el aprendizaje de decaimiento de posición proporcionaron ganancias adicionales del 14% y 12%, respectivamente.
• Sobrecarga: El predictor de sesiones de múltiples turnos es altamente eficiente, requiriendo solo ~1M de parámetros (frente a 118M para el modelo de incrustación de LPC) y logrando un 8.8× mayor rendimiento de inferencia.

Significado y Afirmaciones

El artículo afirma que la evicción de caché de prefijos no debe tratar todos los bloques en caché de manera uniforme, incluso cuando comparten estadísticas similares de recencia o frecuencia. Los autores afirman que la semántica del token, la estructura del prompt y el tipo de sesión son impulsores fundamentales de la reutilización que las políticas existentes no logran capturar.

El significado de SAECache radica en su capacidad para:

1. Cerrar la brecha entre las políticas heurísticas estáticas y la realidad dinámica y semántica del servicio de LLM.
2. Eliminar el ajuste manual, haciendo que el sistema sea robusto ante cambios en la carga de trabajo (por ejemplo, de tráfico centrado en chat a tráfico centrado en uso de herramientas) sin reentrenamiento ni ajuste de parámetros.
3. Demostrar que la evicción fina y consciente de la semántica es una elección de diseño crítica para un servicio eficiente de LLM, particularmente en entornos con alta presión de caché y patrones de solicitud heterogéneos.

Los autores señalan que, aunque SAECache destaca en cargas de trabajo de múltiples turnos y mixtas, su sobrecarga puede reducir ligeramente el rendimiento en regímenes dominados por un solo turno (por ejemplo, Chatbot-Arena), donde los beneficios de tasas de aciertos más altas no compensan completamente los costos de gestión, destacando la necesidad de estrategias adaptativas que puedan escalar con las características de la carga de trabajo.