Skip to content

English · Español

04 — Hacia PagedAttention (vista previa)

🇪🇸 La caché densa con pre-asignación a S_max funciona perfectamente para una sola secuencia, pero se rompe cuando hay muchos usuarios concurrentes con prompts de longitud distinta y duración impredecible. El problema es fragmentación de memoria, no rendimiento. PagedAttention (Fase 27) lo arregla copiando la idea de paginación del sistema operativo.

Esta página existe para plantar el enunciado de un problema, no para resolverlo. La Fase 22 implementa el caché denso; la Fase 27 implementa PagedAttention. Saber por qué el caché denso se rompe es lo que hace que la Fase 27 esté motivada en vez de ser arbitraria.

Lo que funciona en la Fase 22

Una sola secuencia. Pre-asignar tensores \((B, H, S_\text{max}, d_h)\) por capa. Añadir en slices. Listo.

Sin fragmentación. Sin copias. Sin reasignación. Coste de memoria: \(S_\text{max}\) filas aunque solo usemos \(S_\text{current}\) — pero a la escala de la Fase 22, ese overhead es despreciable. El MiniGPT de gramática decodificando "Yesterday I worked" desperdicia ~60 row-slots no usados × 64 bytes × 4 capas ≈ 16 KiB. Por debajo del ruido.

Esto vale para:

  • Un usuario a la vez.
  • Contexto máximo predecible.
  • Trabajos batch de larga duración (donde los bytes desperdiciados se amortizan).
  • Experimentos de juguete.

Lo que se rompe a escala de producción

Un sistema de serving real maneja muchas secuencias concurrentes de longitud impredecible, llegando y saliendo en momentos impredecibles. Tres cosas salen mal con el enfoque denso pre-asignado:

Problema 1: Desperdicio de memoria por secuencia subutilizada

Imagina \(B = 32\) usuarios concurrentes, cada uno con su propio caché pre-asignado a S_max = 8192. Presupuesto total de caché: \(32 \cdot S_\text{max}\) filas por capa. Si la secuencia media es solo de 512 tokens, 15/16 del caché está desperdiciado. En una GPU de 40 GB con 26 GB disponibles para caché, son 24 GB de memoria desperdiciada que podrías haber usado para más secuencias concurrentes.

Podrías intentar "ajustar el tamaño" de \(S_\text{max}\) de cada usuario al inicio de la sesión — pero no sabes la longitud final. El usuario podría generar 10 tokens o 10000. Predecir es un problema de ML separado que no quieres.

Problema 2: Defragmentación cuando las secuencias se van

El usuario 7 termina tras generar 437 tokens. Liberas su slot de caché. Ahora tienes un agujero del tamaño de \(S_\text{max}\) filas en medio de tu asignación densa. Si el usuario 33 llega queriendo S_max = 8192, puedes rellenar el agujero. Si el usuario 33 quiere S_max = 4096, te queda un agujero de 4096 filas que es más pequeño que cualquier otra petición querrá.

Esto es fragmentación externa. La solución clásica de OS es memoria virtual + paginación: dividir la memoria en páginas de tamaño fijo y dejar que una tabla de indirección mapee "posiciones lógicas de secuencia" a "ubicaciones físicas de página". Las páginas pueden liberarse y reusarse sin dejar agujeros — solo hay fragmentación interna (slack al final de la última página de cada secuencia), que está acotada por tamaño-de-página menos 1 por secuencia.

Problema 3: El batching de longitud variable rompe SIMD

Supón que los usuarios A, B, C están decodificando concurrentemente con longitudes de caché actuales \(S_A = 200\), \(S_B = 1500\), \(S_C = 60\). La GPU quiere hacer una atención por lotes: un kernel gigante que procese los tokens de A, B, C en paralelo.

Con un caché denso, el kernel o bien: - Hace padding a la longitud máxima (1500): desperdicia un factor de 1500/200 para A, 1500/60 para C. Desperdicio total 7.6×. - Usa ragged batching: requiere lógica de indexación extra en el kernel y rompe el acceso a memoria coalescido.

De cualquier modo, la eficiencia del batching cae bruscamente a medida que crece la varianza en las longitudes de secuencia. Los workloads modernos de serving tienen enorme varianza de longitud (piensa en completaciones de 5 tokens vs generaciones de 10000 tokens en el mismo batch).

La idea de PagedAttention (un párrafo, la Fase 27 la deriva)

Tomar prestada la paginación de la memoria virtual del OS:

  1. Trocear el KV cache en bloques de tamaño fijo de \(B_\text{block}\) tokens cada uno (típico \(B_\text{block} = 16\)).
  2. Mantener, por secuencia, una block table: una lista de índices físicos de bloque que mapean "el i-ésimo bloque de la secuencia lógica de esta secuencia" a "bloque físico X en memoria GPU".
  3. Para extender una secuencia un token: si el último bloque actual tiene sitio, escribir en él. Si no, asignar un bloque físico nuevo y actualizar la block table.
  4. Para liberar una secuencia: liberar sus bloques físicos (vuelven a una free list).
  5. El kernel de atención toma la block table como argumento; hace los gathers internamente.

Propiedades:

  • Sin fragmentación externa. Todos los bloques son del mismo tamaño; los bloques libres son intercambiables.
  • Fragmentación interna acotada. Cada secuencia desperdicia como mucho \(B_\text{block} - 1\) filas en su último bloque. Con \(B_\text{block} = 16\), eso son como mucho 15 filas por secuencia — despreciable comparado con \(S_\text{max} - S_\text{current}\) del denso.
  • El batching de longitud variable se vuelve natural. Los bloques de cada secuencia son independientes; el kernel solo recorre la block table de cada secuencia.
  • Compartición de prefijos gratis. Dos secuencias con el mismo prompt pueden compartir sus bloques iniciales vía reference counting — gran win para eval por lotes y beam search.

Los detalles a nivel de kernel (¿cómo indexa un CUDA block en una gather-list de punteros eficientemente? ¿cuál es la historia del memory-coalescing?) son material de las Fases 27 y 24.

Lo que deberías llevarte de la Fase 22 sobre la Fase 27

Cuando leas "PagedAttention" más adelante:

  1. No deberías sorprenderte de que exista. Caché denso + serving de longitud variable = fragmentación. La solución es paginación. Esto es mecánico.
  2. Deberías entender que sus FLOPs e intensidad aritmética son idénticas a la versión densa — la paginación es una optimización de layout de memoria, no de cómputo. Habilita batching, que sube la intensidad vía la amortización del FFN derivada en 03-decode-as-memory-bound.md.
  3. Deberías esperar un overhead de factor constante por la indirección de la block table (gather extra por kernel) intercambiado por un win de throughput de 2–4× por tamaños de batch alcanzables más altos. El paper de vLLM reporta este compromiso exacto.

Lo que la Fase 22 construye hacia la Fase 27

Concretamente:

  • La clase KVCache en src/minicache/cache.py tiene un cursor y una cota S_max. La Fase 27 la subclasará en PagedKVCache con una block_table en vez de un cursor. La superficie del API de la clase base (append, read, reset) debería diseñarse de modo que la subclase sea un reemplazo drop-in.
  • El cambio del API de atención en la Fase 15 (que toma un argumento opcional cache) mantiene PagedAttention como una futura superficie de API, no un fork.

Este es exactamente el tipo de decisión de API mirando al futuro que el BLUEPRINT.md señala como pregunta abierta — ver src/minicache/BLUEPRINT.md §Open Questions.

Lo que esta página NO cubre

  • El algoritmo o kernel real de PagedAttention. Fase 27.
  • Scheduling de continuous batching. Fase 33.
  • Detalles de reference counting para compartición de prefijos. Fase 27 / 36.

Referencias hacia adelante

Conceptos nombrados aquí, definidos en otro sitio: - Matemática de PagedAttention → docs/phase-27-modern-attention/theory/ - Kernels gather de CUDA → docs/phase-24-cuda-triton/theory/ - Continuous batching → docs/phase-33-inference-serving/ - Compartición de prefijos / beam search → docs/phase-36-frontier-architectures/

Siguiente: terminada la teoría. Pasa a lab/00-derive-cache-size.md — un ejercicio en papel para confirmar que la fórmula ha aterrizado antes de escribir cualquier código.