Не так давно лимиты на использование 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:

На один токен:

2 × 80 × 8 × 128 × 2 = 327,680 байт ≈ 320 КБ

Масштабируем:

Таблица выше для BF16 KV-Cache. FP8 даёт те же оценки, но вдвое меньше: ~160 КБ на токен и ~20 ГБ на 128K. В полностью FP8-инференсе KV автоматически будет FP8. Если веса в INT4, K/V обычно считается в FP16. Перевести кеш на FP8 можно через --kv-cache-dtype fp8 в vLLM, произойдет отдельное сжатие кэша с небольшой потерей точности. FP8 KV часто даёт 2× пропускную способность без смены карты.

Сравнение с другими моделями

Примечательно: 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.

При наивном подходе на коротких запросах (реальная длина 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 имеет 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.

Выбор размера блока

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 делает обе работы:

1. Tiled IO-aware вычисление (FlashAttention — online softmax, минимум походов к HBM)

2. 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 (новые промпты). На каждом шаге:

1. Запланировать все ожидающие decode-запросы (по 1 токену каждый — дёшево)

2. Оставшийся бюджет (max_num_batched_tokens) — заполнить prefill-чанками

3. Если чанк не влезает — разбить дальше

Пример: промпт 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 на блок.

Процесс при поступлении запроса:

1. Вычислить хэш для каждого блока по token ID запроса

2. Искать каждый хэш в таблице, начиная с блока 0

3. Первый промах → отсюда начинается prefill

4. Все блоки до промаха → cache hit, физические блоки переиспользуются (ref_count++)

Конкретный пример

Системный промпт: 2000 токенов. Размер блока: 16. Получается 125 блоков.

Запрос 1 (кэш пуст):

• 125 блоков системного промпта + 13 блоков пользовательского сообщения (200 токенов)

• Полный prefill: все 138 блоков вычислены с нуля

• После завершения: блоки остаются в хэш-таблице с ref_count = 0

Запрос 2 (тот же системный промпт, другое сообщение):

• Хэши первых 125 блоков → все найдены в таблице

• Cache hit: 125 блоков переиспользованы, ref_count 0 → 1

• Prefill только для 200 новых токенов (13 блоков)

• Экономия: 2000 токенов prefill-вычислений пропущено + ~625 МБ KV-данных не пересчитано

Вытеснение

Блоки с ref_count == 0 остаются в памяти пока есть место. Когда свободных блоков нет — вытесняется LRU-блок с ref_count == 0.

Ключевой инвариант: кэшированные блоки immutable. KV-данные блока никогда не модифицируются после записи. Новые токены при decode всегда идут в свежие блоки. Хэш блока полностью определяет его содержимое — инвалидация кэша не нужна.

Когда APC помогает

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-данные между нодами — разберём во второй части.