Не так давно лимиты на использование Claude Code резко уменьшились, и люди стали лучше считать свои токены. Я не стал исключением, поэтому первым делом собрал информацию по использованию токенов в своих сессиях и посмотрел, что и сколько бы стоило, если бы отправлял это через API.
Как человек, который занимается темой LLM уже несколько лет, я поймал себя на мысли, что не до конца осознаю, почему Cache Read и Cache Write столько стоят и что вообще стоит за этими цифрами. Так появилась идея разобраться со всей этой темой основательно: повторить основы и выйти на "PRO" уровень, где мы понимаем логику и цену кеша на масштабе. Своим исследованием я решил поделиться через серию статей:
Текущая статья покрывает базовое понимание KV-Cache: как он создаётся и используется в рамках одного GPU.
Вторая часть серии разберёт распределённый KV-Cache: проблемы, логику и фреймворки масштабирования за рамки одного GPU.
1. Prefill и Decode — два разных мира
Вопрос: Каждый шаг генерации LLM — это одно и то же?
Представьте: промпт на 4096 токенов, модель должна сгенерировать 100 токенов. Без кэширования каждый шаг генерации пересчитывает K и V проекции для всех предыдущих токенов:
Шаг 1: K, V для токенов 1..4097 → 4097 проекций Шаг 2: K, V для токенов 1..4098 → 4098 проекций ... Шаг 100: K, V для токенов 1..4196 → 4196 проекций Суммарно: 100 × 4096 + (100 × 101)/2 ≈ 414,650 проекций
На 70B такой объём матричных умножений стоит неприлично дорого по времени и вычислительным ресурсам, а почти всё это повторные вычисления одних и тех же K, V.
Как устроено на самом деле
Инференс LLM делится на две фазы с разным вычислительным профилем.
Prefill обрабатывает весь промпт за один forward pass. Все токены известны заранее — модель вычисляет полную матрицу attention параллельно. Эта фаза compute-bound: GPU в основном занят арифметикой. Результат — KV-представления для каждого токена промпта и логиты первого генерируемого токена.
Decode — авторегрессивная фаза. Каждый новый токен требует отдельного forward pass. Один Q-вектор нового токена вычисляет attention со всеми предыдущими K. Эта фаза memory-bound: GPU в основном ждёт, пока данные KV-Cache прочитаются из HBM (вид памяти GPU). Вычислений мало — один вектор против матрицы.
KV-Cache — решение в лоб: сохранять K и V тензоры с каждого шага, на каждом новом шаге вычислять проекцию только для одного нового токена и добавлять результат в кэш.
Шаг 1: K, V для токена 4097, append → O(1) новых проекций Шаг 2: K, V для токена 4098, append → O(1) новых проекций ... Шаг 100: K, V для токена 4196, append → O(1) новых проекций Суммарно: 100 проекций вместо 414,650
Влияние на production-метрики
Разница между фазами определяет три ключевые метрики:
TTFT (Time To First Token) — определяется длительностью prefill. Длинный промпт = долгий TTFT. Это latency, которую пользователь видит как «задержку перед ответом».
ITL (Inter-Token Latency) — определяется скоростью decode. Один forward pass на токен. Это определяет, насколько «плавным» кажется потоковый вывод.
Throughput — сколько токенов в секунду система генерирует суммарно по всем запросам. Здесь ключевой вопрос — сколько запросов можно обрабатывать одновременно, а это зависит от того, сколько KV-Cache влезает в память.
Prefill выигрывает от больших батчей токенов (GPU загружен вычислениями). Decode выигрывает от больших батчей запросов (GPU загружен чтением KV-Cache, и больше запросов = лучшая утилизация bandwidth). Обе фазы делят ресурсы GPU, и это противоречие приводит к chunked prefill (раздел 6).
Prefill — compute-bound параллельная обработка. Decode — memory-bound последовательная генерация. KV-Cache превращает O(n·m + m²) повторных вычислений в O(m), но создаёт проблему хранения, которую разбирают следующие секции.
2. KV-Cache: цена памяти
Вопрос: Сколько памяти на самом деле занимает KV-Cache?
KV-Cache хранит K и V проекции для каждого токена, каждого слоя, каждой KV-head. Формула:
KV-Cache = 2 × num_layers × num_kv_heads × d_head × seq_len × dtype_bytes
Считаем для Llama 3.1 70B:
Параметр | Значение |
|---|---|
num_layers | 80 |
num_kv_heads | 8 (GQA: 8 KV heads на 64 query heads) |
d_head | 128 |
dtype | BF16 (2 байта) |
На один токен:
2 × 80 × 8 × 128 × 2 = 327,680 байт ≈ 320 КБ
Масштабируем:
Длина контекста | KV-Cache на запрос | Это как… |
|---|---|---|
4,096 | 1.25 ГБ | Half Life |
32,768 | 10 ГБ | Fallout: New Vegas |
131,072 (128K) | 40 ГБ | Dota 2 |
Таблица выше для BF16 KV-Cache. FP8 даёт те же оценки, но вдвое меньше: ~160 КБ на токен и ~20 ГБ на 128K. В полностью FP8-инференсе KV автоматически будет FP8. Если веса в INT4, K/V обычно считается в FP16. Перевести кеш на FP8 можно через --kv-cache-dtype fp8 в vLLM, произойдет отдельное сжатие кэша с небольшой потерей точности. FP8 KV часто даёт 2× пропускную способность без смены карты.
Сравнение с другими моделями
Модель | Тип | Слои | KV-heads | d_head | KV на токен (BF16) | 128K контекст |
|---|---|---|---|---|---|---|
Llama 3.1 70B | Dense | 80 | 8 | 128 | 320 КБ | 40 ГБ |
Qwen3-8B | Dense | 36 | 8 | 128 | 144 КБ | 18 ГБ |
Qwen3-235B-A22B | MoE | 94 | 4 | 128 | 188 КБ | 24 ГБ |
MiniMax M2.5 | MoE | 62 | 8 | 128 | 248 КБ | 32 ГБ |
Примечательно: Qwen3-235B-A22B — 235 миллиардов параметров, но благодаря агрессивному GQA (всего 4 KV-head, соотношение 16:1) её KV-Cache на токен меньше, чем у Llama 70B. MiniMax M2.5 при 230B параметров имеет 248 КБ/токен — тоже меньше Llama 70B благодаря меньшему числу слоёв (62 vs 80). Архитектурные решения по числу слоёв и KV-heads напрямую определяют стоимость инференса.
GQA: 8× сокращение
Llama 70B использует Grouped-Query Attention (GQA) — всего 8 KV heads вместо 64 query heads. Каждая KV head обслуживает 8 query heads. Это сразу сокращает KV-Cache в 8 раз.
Без GQA: 2 × 80 × 64 × 128 × 2 = 2,621,440 байт ≈ 2.5 МБ на токен 128K контекст → 320 ГБ KV-Cache → не влезает ни на один GPU
Для средне-жирных моделей класса 70B GQA — по сути стандартный способ удержать KV-cache в разумных пределах. При полном Multi Head Attention и тех же 64 query heads объём KV вырос бы примерно в 8 раз, и на типичном 1 GPU сетапе длинный контекст стал бы крайне тяжёлым по памяти, окна уже в тысячи токенов давили бы на KV заметно сильнее, а длины порядка 128K без агрессивного шардинга оказались бы практически недостижимы.
Проблема наивного выделения памяти
Простейший подход — заранее выделить непрерывный буфер max_seq_len × 320 КБ для каждого запроса. Если max_seq_len = 4096, а реальная генерация остановилась на 200 токенах — 95% выделенной памяти потрачено впустую. Команда vLLM обнаружила, что такой подход тратит впустую 60–80% памяти KV-Cache на реальных нагрузках.
Разница между 36 и 8 одновременными пользователями. Между $4 и $18 за миллион токенов.
Давайте посчитаем конкретнее. H100, 80 ГБ. Веса Llama-70B в INT4: ~35 ГБ. Активации, буферы, overhead положим 3 ГБ. Остаётся 42 ГБ под KV-Cache.
Подход | Контекст 4K | Контекст 32K | Контекст 128K |
|---|---|---|---|
Наивный (alloc на max_seq_len = 4K) | ~33 запроса (при средней утилизации 50%) → 16 эффективных | 4 запроса → 2 эффективных | 1 запрос |
Идеальный (alloc точно по факту) | 33 запроса | 4 запроса | 1 запрос |
При наивном подходе на коротких запросах (реальная длина 200–500 токенов) вы теряете половину и больше — потому что выделили 4K на каждый, а используется малая часть. Решение — PagedAttention (раздел 4).
KV-Cache может быть больше весов модели. При длинных контекстах это главный потребитель GPU-памяти, а наивное управление ей теряет большую часть потенциального throughput.
3. Вспомним FlashAttention:
Вопрос: FlashAttention — это приближённые вычисления? И он решает проблему KV-Cache?
FlashAttention вычисляет точный attention и решает проблему вычисления attention. Хранение KV-Cache — отдельная задача.
Стандартный attention:
Промежуточная матрица Q · K^T на этапе prefill имеет размер [seq_len × seq_len]. При 128K контексте:
131,072 × 131,072 × 2 байта (BF16) = 32 ГБ — на одну head, на одном слое
У Llama-70B 64 query heads и 80 слоёв:
32 ГБ × 64 × 80 = 163,840 ГБ ≈ 160 ТБ
160 терабайт промежуточных данных, если материализовать все матрицы одновременно. Ваш GPU имеет 80 ГБ. На практике наивная реализация обрабатывает по одному слою, но даже так: при 128K контексте одна attention-матрица для одной head на одном слое — 32 ГБ. Это уже не влезает. При 4K токенах: 32 МБ на head — технически влезает, но стандартная реализация делает 4 захода к HBM для каждой такой матрицы, что неэффективно.
Стандартная реализация записывает эту матрицу в HBM, читает обратно для softmax, записывает результат softmax, снова читает для умножения на V. Четыре похода в медленную память для матрицы, которая не нужна после вычисления.
Tiling и online softmax
Ключевое наблюдение Tri Dao (2022): проблема attention на GPU — это не вычисления, а перемещение данных. У GPU два уровня памяти:
Память | Объём (A100) | Bandwidth | Роль |
|---|---|---|---|
HBM | 80 ГБ | ~2 ТБ/с | Основная память, хранит всё |
SRAM | ~20 МБ | ~19 ТБ/с | On-chip, в ~10× быстрее |
A100 имеет 312 TFLOPS BF16-вычислений и 2 ТБ/с bandwidth. Соотношение: ~156 операций на байт. Если алгоритм выполняет меньше 156 операций на каждый прочитанный байт — он упирается в bandwidth, а не в compute. Стандартный attention именно такой: гигантские чтения/записи матрицы, относительно мало арифметики на прочитанный элемент.
Алгоритм tiling с online softmax
FlashAttention никогда не материализует полную N × N матрицу. Вместо этого Q, K, V обрабатываются блоками (tiles):
# Pseudocode: FlashAttention forward pass # Q, K, V в HBM, размер блока B_r (по Q) и B_c (по K,V) O = zeros(N, d) # выходной тензор в HBM m = -inf(N) # running max по строкам l = zeros(N) # running sum по строкам for j in range(0, N, B_c): # внешний цикл по K,V блокам K_j = load(K[j : j+B_c]) # загрузить K-блок в SRAM V_j = load(V[j : j+B_c]) # загрузить V-блок в SRAM for i in range(0, N, B_r): # внутренний цикл по Q блокам Q_i = load(Q[i : i+B_r]) # загрузить Q-блок в SRAM O_i = load(O[i : i+B_r]) # загрузить текущий результат m_i = load(m[i : i+B_r]) # загрузить текущий max l_i = load(l[i : i+B_r]) # загрузить текущую сумму # --- всё дальше в SRAM --- S_ij = Q_i @ K_j.T / sqrt(d) # локальные attention scores m_new = max(m_i, rowmax(S_ij)) # обновить running max P_ij = exp(S_ij - m_new) # локальные attention weights l_new = l_i * exp(m_i - m_new) + rowsum(P_ij) # обновить running sum # пересчитать ранее накопленный результат + добавить новый вклад O_i = O_i * (l_i * exp(m_i - m_new) / l_new) + (P_ij / l_new) @ V_j store(O[i : i+B_r], O_i) # записать результат в HBM store(m[i : i+B_r], m_new) store(l[i : i+B_r], l_new)
Математически тонкая часть — online softmax. Softmax требует глобального max и глобальной суммы экспонент, но мы видим K-блоки по одному. Решение: поддерживать running max m и running sum l, при каждом новом блоке пересчитывать накопленный результат через соотношение exp(m_old - m_new). После обработки всех блоков результат математически идентичен полному attention. Никаких приближений.
Почему больше FLOP’ов = быстрее
Контринтуитивный факт: FlashAttention выполняет больше операций с плавающей точкой, чем стандартный attention. Пересчёт масштабов на каждом тайле — дополнительные умножения и экспоненты. Но алгоритм всё равно быстрее, потому что bottleneck — bandwidth, не compute.
Грубая арифметика для A100 при N=4096, d=128:
Стандартный attention: ~33M обращений к HBM (доминирует N²)
FlashAttention: ~4.3M обращений к HBM
IO-сложность:
Стандартный: O(N·d + N²) обращений к HBM
FlashAttention: O(N²·d²·M⁻¹) обращений к HBM, где M — размер SRAM
Оба подхода масштабируются как O(N²), но с радикально разными константами. У FlashAttention множитель d²/M — для A100 с d=128 и M≈20 МБ это ≈0.0008. На практике при N = 128K это означает разницу в тысячи раз по числу обращений к HBM. Tri Dao доказал matching lower bound: никакой алгоритм точного attention не может быть асимптотически лучше по IO.
Чего FlashAttention НЕ делает
FlashAttention оптимизирует вычисление attention — как быстро и экономно перемножить Q с кэшированными K,V. Выделение памяти, фрагментация, переиспользование блоков между запросами — за пределами его ответственности. KV-Cache остаётся в HBM между шагами decode; FlashAttention ускоряет kernel, который его читает. Управлением памяти занимается PagedAttention.
4. Вспомним PagedAttention:
Вопрос: PagedAttention — это альтернатива FlashAttention?
PagedAttention — техника управления памятью: где в GPU-памяти лежат K и V тензоры. FlashAttention и PagedAttention — ортогональные решения разных проблем, и современные системы используют оба одновременно.
Без PagedAttention каждый запрос получает непрерывную область памяти под KV-Cache. Два типа потерь:
Внутренняя фрагментация. Буфер выделяется на max_seq_len токенов. Если запрос использует 200 из 4096 — 95% потеряно. Средние потери на реальных нагрузках: 60–80% (данные vLLM).
Внешняя фрагментация. По мере поступления и завершения запросов свободная память дробится на мелкие несмежные куски. Суммарно свободных 10 ГБ — но ни одного непрерывного блока на 1.25 ГБ для нового запроса.
Проблема, решённая для CPU RAM десятилетия назад. Решение — виртуальная память с пейджингом.
Блоки и block table
KV-Cache делится на блоки фиксированного размера. Каждый блок хранит K и V для фиксированного числа токенов (по умолчанию — 16). Блоки не обязаны быть смежными в GPU-памяти.
Block table — аналог page table в ОС — маппит логические блоки последовательности на физические адреса в GPU-памяти.
Пошаговый пример
Запрос: промпт на 1024 токена, генерация 10 токенов. Размер блока: 16.
Prefill:
1024 / 16 = 64 блока
Block manager выделяет 64 физических блока из пула. Они разбросаны по GPU-памяти — это нормально.
Block table: логический блок 0 → физический 417, блок 1 → физический 23, блок 2 → физический 891, …
Все 64 блока заполняются KV-данными из prefill forward pass.
Decode, токен 1025:
Блок 63 (токены 1009–1024) — полон, 16/16 слотов.
Выделяется блок 64. Токен 1025 записывается в слот 1/16.
Decode, токены 1026–1034:
Токены заполняют слоты 2–10 блока 64. После генерации: 10/16 слотов занято.
Итого:
Выделено: 65 блоков × 16 слотов = 1,040 слотов Использовано: 1,034 токена Потери: 6 слотов (0.6%)
Наивный подход с max_seq_len = 2048:
Выделено: 2,048 слотов Использовано: 1,034 токена Потери: 1,014 слотов (49.5%)
С 0.6% до 49.5% — разница в ~80× по потерям памяти.
В терминах throughput: при наивном подходе на 42 ГБ свободной памяти с max_seq_len = 2048 мы можем разместить 42 ГБ / (2048 × 320 КБ) ≈ 67 запросов. Но если средняя реальная длина — 500 токенов, эффективно используется лишь 500/2048 = 24% памяти, и мы могли бы обслужить 67 / 0.24 ≈ 280 запросов. PagedAttention приближает нас к этим 280.
Выбор размера блока
Размер блока | Плюсы | Минусы |
|---|---|---|
1 токен | Нулевая фрагментация | Огромная block table, больше overhead |
16 токенов | Хороший баланс; макс. 15 потерянных токенов (~4.8 КБ) | — |
256 токенов | Мало блоков, меньше overhead | До 255 потерянных токенов (~80 КБ) на запрос |
16 — дефолт в vLLM. Совпадает с естественной гранулярностью GPU: размер тайла attention kernel, требования к выравниванию памяти. Размер блока больше 16 может быть оправдан для очень длинных последовательностей, где block table становится заметной.
Copy-on-Write для parallel sampling
Когда один промпт порождает несколько вариантов ответа (parallel sampling, beam search), KV-блоки общего префикса не копируются. Обе последовательности ссылаются на одни и те же физические блоки через reference counting. Если одна из них должна изменить разделяемый блок — сначала копируется (copy-on-write). Оригинал остаётся нетронутым.
Это экономит до 55% памяти при beam search (данные из оригинальной статьи PagedAttention). При parallel sampling экономия скромнее — 6–10%.
PagedAttention — виртуальная память для GPU, которая решает задачу фрагментации и выделения памяти.
5. Как vLLM объединяет FlashAttention и PagedAttention
Вопрос: У vLLM есть отдельный PagedAttention kernel?
Современный vLLM делегирует вычисление attention внешним, высокооптимизированным бекендам. FlashAttention теперь нативно поддерживает параметр block_table — kernel знает, что KV-данные лежат в разбросанных блоках, и собирает их самостоятельно. Один fused kernel делает обе работы:
Tiled IO-aware вычисление (FlashAttention — online softmax, минимум походов к HBM)
Scattered page reads (PagedAttention — чтение KV из физических блоков)
Нет отдельного «PagedAttention kernel» — есть FlashAttention kernel, который понимает paged memory.
Помимо FlashAttention, vLLM поддерживает FlashInfer — альтернативный backend со своими оптимизированными ядрами и paged KV support. Для AMD и Intel GPU есть Triton-based backend — кросс-платформенная реализация на Triton.
Как это выглядит в коде
На верхнем уровне вызов при decode:
output = flash_attn_with_kvcache( q=query, # [batch, 1, num_heads, d_head] k_cache=kv_cache_k, # [num_physical_blocks, block_size, num_kv_heads, d_head] v_cache=kv_cache_v, # [num_physical_blocks, block_size, num_kv_heads, d_head] block_table=block_table, # [batch, max_num_blocks] — int32 physical block IDs cache_seqlens=seq_lengths, # [batch] — реальная длина каждого запроса )
block_table — мост между PagedAttention (где лежат данные) и FlashAttention (как вычислять). Kernel использует его, чтобы собрать K,V из разбросанных блоков в SRAM-тайлы, вычислить attention и записать результат — всё в одной fused операции.
6. Chunked Prefill: проблема не в памяти
Вопрос: Зачем нужен chunked prefill, если FlashAttention справляется с любой длиной?
FlashAttention справляется с attention любой длины — он O(N) по памяти. Chunked prefill решает три других проблемы.
Проблема 1: не даём одному prefill «съесть» весь шаг
В батче на одном шаге GPU обрабатывает и prefill, и decode. Если новый промпт на 100K токенов прогнать одним forward, этот шаг занимает долго (на H100 для Llama-70B полный prefill такого масштаба часто порядка 2–5 с — зависит от настроек). Пока шаг не закончен, decode всех остальных запросов не двигается: в интерфейсе это выглядит как пауза в потоковой генерации. Чанки укладываются в общий бюджет токенов на шаг рядом с decode — очередь снова становится «живой».
Проблема 2: KV резервировать порциями, а не разом
FlashAttention снимает пик внутри attention; отдельный вопрос — сколько KV-блоков нужно зарезервировать под один запуск. Для Llama-70B грубо ~320 КБ на токен KV: 100K токенов ≈ 31 ГБ под кэш. Запросить всё сразу при уже занятой памяти рискованно. Чанк 2048 токенов — порядка 640 МБ за раз; между чанками другие сессии успевают завершиться и отдать блоки.
Проблема 3: ниже пик по активациям вне attention
В остальных частях слоя (MLP, нормализации, проекции) промежуточные активации масштабируются с числом токенов в этом forward. Один проход на 100K даёт высокий пик; тот же промпт чанками по 2048 — примерно в ~50× меньший пик на шаг (при той же длине чанка).
Как это работает
Scheduler ведёт две очереди: decode (текущие генерации) и prefill (новые промпты). На каждом шаге:
Запланировать все ожидающие decode-запросы (по 1 токену каждый — дёшево)
Оставшийся бюджет (
max_num_batched_tokens) — заполнить prefill-чанкамиЕсли чанк не влезает — разбить дальше
Пример: промпт A на 10K токенов, max_num_batched_tokens = 2048
Step 1: [A: chunk 1, 2048 prefill] + [B: 1 decode] → B получает токен Step 2: [A: chunk 2, 2048 prefill] + [B: 1 decode] → B получает токен Step 3: [A: chunk 3, 2048 prefill] + [B: 1 decode] → B получает токен Step 4: [A: chunk 4, 2048 prefill] + [B: 1 decode] → B получает токен Step 5: [A: chunk 5, 1808 prefill] + [B: 1 decode] → A prefill завершён Step 6: [A: 1 decode] + [B: 1 decode] → оба генерируют
Без чанков B заблокирован на шаги 1–5. С чанками — стабильный inter-token latency на каждом шаге. При промпте 100K шагов было бы ~49, но принцип тот же.
Это часть подхода continuous batching: в отличие от static batching (группа стартует и завершается вместе), continuous batching динамически добавляет и удаляет запросы из батча на каждом шаге.
Параметр max_num_batched_tokens
Этот параметр — главная ручка настройки chunked prefill. Он контролирует, сколько токенов (суммарно prefill + decode) scheduler может запланировать за один шаг.
Маленькое значение (512–1024): decode-запросы почти никогда не ждут, ITL стабильный. Но prefill длинных промптов растягивается на много шагов → высокий TTFT.
Большое значение (4096–8192): prefill быстрее, TTFT ниже. Но decode-запросы конкурируют за бюджет с крупными prefill-чанками → ITL может подскочить.
Типичный дефолт (2048): разумный баланс для большинства нагрузок.
В production значение подбирается под конкретные latency SLO. Если SLO на ITL — 50ms, а SLO на TTFT — 5s, можно позволить крупные чанки. Если SLO на ITL — 20ms (real-time приложения) — чанки должны быть мельче.
7. Тот самый Cache Read
Вопрос: Чем Automatic Prefix Caching отличается от обычного кэша?
KV по умолчанию в батч-планировщике — рабочая память текущих запросов: после завершения генерации физические блоки обычно возвращаются в пул, и новый запрос с тем же префиксом снова проходит prefill с нуля. APC добавляет межзапросное хранение: вычисленные KV-блоки остаются в глобальной хэш-таблице и переиспользуются при следующих обращениях, пока их не вытеснит нехватка памяти (LRU среди блоков без активных ссылок).
Обычный key-value кэш (в смысле структуры данных) потребовал бы отдельный lookup на каждый блок и независимую валидацию. APC устроен иначе благодаря hash chaining.
Системный промпт на 2000 токенов. 1000 запросов в минуту. Без кэширования:
2000 токенов × 320 КБ × 1000 запросов = 625 ГБ KV-данных в минуту пересчитывается заново
Это ~625 МБ GPU-памяти на KV-Cache системного промпта, вычисляемые с нуля на каждый запрос. При ~200 мс на prefill 2K токенов на Llama-70B (H100, INT4) — 200 секунд чистого compute в минуту, или ~3.3 минуты вычислений на каждую минуту реального времени. Параллелизм помогает, но compute тратится на уже известный результат.
Hash chaining
Хэш каждого KV-блока включает все предшествующие токены, а не только токены этого блока:
hash(block_i) = hash(token_ids[0 .. last_token_of_block_i])
Критическое свойство: если хэш блока 5 совпал у двух запросов, блоки 0–4 гарантированно совпадают — потому что хэш блока 5 включает все токены от начала. Одно совпадение хэша валидирует весь префикс.
Почему не хэшировать токены каждого блока по отдельности? Потому что одни и те же 16 токенов на разных позициях имеют разные KV-значения. Causal attention: KV для токена зависит от всех предыдущих. Токены [“Say”, “My”, “Name”, …] на позиции 100 дадут совсем другие K и V, чем те же токены на позиции 500. Включая полный префикс в хэш, мы гарантируем: совпадение хэша = идентичные KV-данные.
Глобальная хэш-таблица
Плоская хэш-таблица: block_hash → physical_block_id. Никаких деревьев, никаких trie. O(1) lookup на блок.
Процесс при поступлении запроса:
Вычислить хэш для каждого блока по token ID запроса
Искать каждый хэш в таблице, начиная с блока 0
Первый промах → отсюда начинается prefill
Все блоки до промаха → cache hit, физические блоки переиспользуются (ref_count++)
Конкретный пример
Системный промпт: 2000 токенов. Размер блока: 16. Получается 125 блоков.
Запрос 1 (кэш пуст):
125 блоков системного промпта + 13 блоков пользовательского сообщения (200 токенов)
Полный prefill: все 138 блоков вычислены с нуля
После завершения: блоки остаются в хэш-таблице с
ref_count = 0
Запрос 2 (тот же системный промпт, другое сообщение):
Хэши первых 125 блоков → все найдены в таблице
Cache hit: 125 блоков переиспользованы,
ref_count0 → 1Prefill только для 200 новых токенов (13 блоков)
Экономия: 2000 токенов prefill-вычислений пропущено + ~625 МБ KV-данных не пересчитано
Вытеснение
Блоки с ref_count == 0 остаются в памяти пока есть место. Когда свободных блоков нет — вытесняется LRU-блок с ref_count == 0.
Ключевой инвариант: кэшированные блоки immutable. KV-данные блока никогда не модифицируются после записи. Новые токены при decode всегда идут в свежие блоки. Хэш блока полностью определяет его содержимое — инвалидация кэша не нужна.
Когда APC помогает
Сценарий | Эффект APC |
|---|---|
Общий длинный системный промпт | Огромная экономия — prefill только для user-части |
RAG с повторяющимися документами | Хорошая экономия при cache hit на общие чанки |
Parallel sampling (N ответов на 1 промпт) | Полное переиспользование KV промпта |
Каждый запрос уникален, короткий контекст | Минимальная польза |
Высокое давление на память | Блоки вытесняются до переиспользования |
APC и chunked prefill: взаимодействие
APC работает на уровне полных блоков (16 токенов). Если промпт обрабатывается через chunked prefill (чанками по 2048 токенов), блоки заполняются и хэшируются по мере обработки чанков. Частично заполненный блок не хэшируется — он ещё mutable. Только когда блок полон (все 16 слотов заняты), он становится immutable и попадает в хэш-таблицу.
Это означает, что APC-выигрыш от chunked prefill реализуется чанк за чанком: после первого чанка (2048 токенов = 128 блоков) эти 128 блоков уже в кэше. Если второй запрос с тем же префиксом появится до завершения prefill первого — он получит частичный cache hit на уже обработанные чанки.
Проектное решение: хэш-таблица vs trie
Альтернативный подход — хранить кэшированные последовательности в trie (prefix tree). Каждый узел — токен, путь от корня — последовательность. Lookup — спуск по дереву.
Проблемы trie:
Pointer chasing: каждый шаг — случайный доступ к памяти. При глубине 2000 токенов — 2000 последовательных обращений к HBM.
Сложность вытеснения: нельзя просто удалить лист — нужно проверить, не используется ли путь другим запросом.
Параллельный доступ: сложнее обеспечить корректность при конкурентных модификациях.
Плоская хэш-таблица с chain hashing: O(1) lookup, O(1) вытеснение (удалить запись), O(1) вставка. Всё за счёт одного наблюдения: хэш блока N уже включает всю информацию о блоках 0…N-1.
Hash chaining обеспечивает O(1) валидацию всего префикса через один lookup. Immutability блоков исключает необходимость в инвалидации. Плоская хэш-таблица вместо trie даёт простоту и скорость.
8. Параллельные запросы: почему нет race condition
Вопрос: Что происходит, когда два запроса с одним префиксом приходят одновременно?
Естественное опасение: два запроса с одним системным промптом, оба попадают на prefill. Кто записывает блоки в кэш? Будет ли гонка за хэш-таблицу?
Однопоточный scheduler
Scheduler vLLM — однопоточный. Одна нить, один шаг за раз. Никаких параллельных модификаций block table или хэш-таблицы. Целый класс race condition’ов исключён архитектурой.
Сценарий 1: оба запроса в одном шаге планирования
Кэш пуст, оба запроса попали в один batch. Что происходит:
Оба запроса выполняют prefill для общего префикса. KV-вычисление дублируется — это неизбежно, потому что forward pass выполняется для обоих.
Но физическая память не дублируется: block manager через reference counting может направить обе block table на одни и те же физические блоки.
После этого шага блоки в кэше. Все следующие запросы — cache hit.
Сценарий 2: запросы в разных шагах
Запрос 1 уже обработан (или частично обработан через chunked prefill). Запрос 2 приходит позже:
Lookup по хэшам находит кэшированные блоки запроса 1
Полный cache hit для общего префикса
Никакого дублирования ни вычислений, ни памяти
Сценарий 3: нужно изменить разделяемый блок
Speculative decoding может скорректировать токен в разделяемом блоке. Copy-on-write: блок копируется перед записью. Оригинал не трогается.
Ключевой момент: immutability кэшированных блоков означает, что нет потребности в инвалидации. Блок записан — он корректен навсегда (для данного набора токенов). Нет сценария, в котором один запрос может испортить данные другого.
Однопоточный scheduler + immutable блоки + copy-on-write = корректность без блокировок. Compute может дублироваться (оба prefill в одном batch), но память нет.
9. Потолок одного инстанса
Вопрос: Достаточно ли добавить реплик за load balancer для масштабирования?
Throughput масштабируется, эффективность кэша — нет.
8 реплик за round-robin load balancer. Системный промпт: 2000 токенов (125 блоков по 16 токенов).
Каждая реплика кэширует системный промпт независимо: 8 копий × 625 МБ = 5 ГБ суммарной GPU-памяти на один системный промпт Cache hit rate на реплику: первый запрос на каждую реплику — промах. При равномерном распределении: период прогрева кэша в 8× дольше. Эффективная cache hit rate ≈ 1/N от одного инстанса (на начальном этапе).
При 10 разных системных промптах × 8 реплик = 80 независимых кэширований. 50 ГБ суммарных потерь памяти на дублирование. И это только системные промпты без учёта RAG-документов, few-shot примеров и прочих общих префиксов.
Что нужно
Два направления решения:
Prefix-aware routing: направлять запросы с одинаковым префиксом на одну и ту же реплику. Вместо round-robin использовать hash по prefix -> реплика. Кэш на каждой реплике становится «тёплым» для своего набора префиксов.
Distributed KV-Cache: дать репликам обмениваться KV-данными. Cache miss на реплике A -> получить блоки с реплики B по сети вместо пересчёта.
Эти задачи решают llm-d (Kubernetes-нативная архитектура для prefix-aware routing LLM-инференса) и LMCache (передача KV-Cache между инстансами через сеть или общее хранилище).
Для контекста: передать 625 МБ KV-данных по 200 Gbps RDMA-сети — ~25 мс. Пересчитать prefill для 2000 токенов на H100 — ~100–200 мс. Сеть выигрывает в 4–8×, если KV-данные уже вычислены на другой реплике. Это базовая экономика distributed KV-Cache.
N реплик с round-robin = N копий одного и того же кэша. Prefix-aware routing и distributed KV-Cache — необходимые условия для эффективного масштабирования. Без них добавление реплик масштабирует throughput, но убивает cache efficiency.
Заключение
Вернёмся к скриншоту из начала. Cache Write и Cache Read из Claude Code — это prefix caching на стороне Anthropic: механизм, аналогичный APC из раздела 7. Системные инструкции, описание инструментов, история диалога — длинный повторяющийся префикс. При первом запросе KV-блоки вычисляются с нуля (Cache Write). При следующих — переиспользуются (Cache Read). OpenAI работает по тому же принципу: кэшированные входные токены стоят вдвое дешевле.
На масштабе провайдера, обслуживающего миллионы запросов, встаёт вопрос из раздела 9: где хранить все эти KV-блоки. GPU HBM — быстро, но 80 ГБ на карту заканчиваются за десятки запросов с длинным контекстом. CPU DRAM — на порядок больше по объёму, но на порядок медленнее по доступу. NVMe — ещё дешевле и лучше по емкости, но задержка растёт дальше. Выбор уровня в этой иерархии памяти определяет и latency кэш-попадания, и стоимость хранения, и в конечном счёте цену за токен, которую видит пользователь.
Как устроить эту иерархию, как маршрутизировать запросы к репликам с нужным кэшем и как передавать KV-данные между нодами — разберём во второй части.
