Эпоха 6 · Генеративка и системы · 2024

54 Prefix Caching → CacheBlend

Automatic Prefix Caching (vLLM, 2024) · CacheBlend: Fast LLM Serving for RAG with Cached Knowledge Fusion · Yao, Li, Liu и др. · EuroSys ’25

🟧 оригинал выборочно~1.5–2 чоригинал ↗

Суть за 20 секунд. Переиспользовать KV-кэш вместо повторного prefill. Prefix caching: общий префикс (системный промпт, история диалога, few-shot) считается один раз и переиспользуется по хэшу блоков — это vLLM automatic prefix caching и «prompt caching» в API. CacheBlend идёт дальше: переиспользует KV ЛЮБЫХ кусков (RAG, не только префикс), досчитывая лишь малую долю токенов на «сшивку» → TTFT ×2.2–3.3, throughput ×2.8–5 без потери качества.

Контекст

Prefill — обработка всего входного контекста до первого сгенерированного токена — самая дорогая часть инференса на длинных входах (внимание O(n²)). При этом один и тот же текст гоняется через prefill снова и снова: общий системный промпт у тысяч запросов, та же история в каждом ходе диалога, одни и те же документы в RAG. Пересчитывать их KV каждый раз — расточительно.

Идея и механизм

Prefix caching. В каузальном внимании KV токена зависит только от него самого и предшествующих токенов — значит у запросов с общим ПРЕФИКСОМ его KV побитово одинаковы. vLLM режет последовательность на блоки и хэширует каждый по цепочке (хэш = токены блока + хэш всей предыстории); совпал хэш — переиспользуем готовый KV-блок и пропускаем его prefill, считая только некэшированный хвост. Прод-лаборатории продают то же самое как prompt caching (кэшированный вход дешевле).

CacheBlend. В RAG переиспользуемые куски — НЕ общий префикс: документы приходят в разном порядке и составе. KV куска, посчитанный изолированно, не видел остальных кусков (нет кросс-внимания) и стоит не на той позиции — наивная склейка роняет качество. CacheBlend переиспользует такие KV всё равно, но пересчитывает KV у малой доли токенов с наибольшим отклонением (HKVD — high KV-deviation), восстанавливая сшивку. Досчёт пайплайнится с загрузкой KV из хранилища → кэш можно держать на медленном большом сторадже без роста задержки.

линейная алгебра · системы Почему префикс точно переиспользуем, и что досчитывает CacheBlend

1. Префикс. Ключи и значения позиции i — функции скрытого состояния h_i, а оно под каузальной маской зависит лишь от токенов ≤ i:

K_i = W_K h_i, V_i = W_V h_i, h_i = f(x₁, …, x_i)

Если два запроса делят префикс x_1..k, то h_1..k совпадают → K_1..k, V_1..k идентичны. Их можно посчитать один раз. Для префикса длины k, переиспользуемого в R запросах, экономия prefill ≈ (R−1)·k токенов.

2. Не-префикс (CacheBlend). Пусть KV_i — кэш, посчитанный для куска изолированно, а KV^*_i — то, что дал бы полный prefill всей склейки. Отклонение:

Δ_i = ‖ KV^*_i − KV_i ‖ → пересчитать только top-r% токенов по Δ_i

Ключевое наблюдение: Δ РАЗРЕЖЕНО — у большинства токенов контекст меняет KV слабо, сильно «расходятся» немногие (на стыках кусков). Досчитав эти HKVD-токены на каждом слое, чинишь доминирующую ошибку до того, как она расползётся. Доля r — ручка размена: больше → ближе к полному prefill, дороже. Эмпирически малой доли хватает, чтобы качество не просело, а сам досчёт перекрывается загрузкой кэша.

Python Переиспользование KV: префикс по хэшу + сшивка CacheBlend

# 1) PREFIX CACHING: хэш-цепочка блоков → переиспользуем общий префикс
def block_hash(prev_hash, tokens):        # хэш = (история + токены блока)
    return hash((prev_hash, tuple(tokens)))

def reuse_prefix(req_blocks, cache):      # cache: hash -> физический KV-блок
    h, reused = None, 0
    for blk in req_blocks:
        h = block_hash(h, blk.tokens)
        if h in cache:
            blk.kv = cache[h]; reused += 1   # совпал хэш → пропускаем prefill
        else:
            break                            # дальше префикс расходится
    return reused                            # prefill только для некэшированного хвоста

# 2) CACHEBLEND: переиспользуем KV любых кусков, сшивает малая доля токенов
def cacheblend(chunks_kv, model, r=0.15):
    kv  = concat(chunks_kv)                  # KV кусков, посчитанные раздельно
    dev = kv_deviation(kv, model)            # Δ: отклонение от полного prefill
    idx = topk(dev, int(r * len(dev)))       # HKVD — самые «расходящиеся» токены
    recompute(kv, idx, model)                # пересчитать только их (по слоям)
    return kv                                # ~качество полного prefill за долю счёта

Prefix caching: общий префикс считается один раз и переиспользуется по хэшу блоков. CacheBlend: переиспользует KV даже не-префиксных кусков, досчитывая лишь малую долю токенов (оранжевые) для восстановления кросс-внимания.

Аналогия. Prefix caching — это типовая вводная глава, отпечатанная один раз и вшитая во все методички: одинаковое начало не набирают заново. CacheBlend — сборка персонального ридера из заранее отпечатанных разделов: чтобы они читались как единый текст, не перепечатывают всё, а лишь заново набирают несколько фраз на стыках разделов. Дорогой полный набор заменяется дешёвой правкой швов.

Почему это важно

Переиспользование prefill — один из главных рычагов стоимости и латентности LLM в проде. Prefix caching уже везде: vLLM, TGI, коммерческие prompt-caching API (кэшированный вход в разы дешевле). CacheBlend снимает ограничение «только префикс», открывая дешёвый RAG и модульную сборку контекста («You Only Prefill Once»). Это та же мысль, что в vLLM (#49) и MLA из DeepSeek (#53): KV-кэш — узкое место инференса, и борьба идёт за то, чтобы считать, хранить и гонять его как можно меньше.

Связи

← живёт поверх49. vLLM / PagedAttention

Prefix caching строится на блочном KV-кэше из #49: те же физические блоки, только теперь они адресуются по хэшу содержимого и шерятся между запросами (а не только внутри одного). CacheBlend — следующий шаг той же линии: переиспользовать блоки, даже когда это не общий префикс.

← следствие архитектуры32. Transformer

KV-кэш вообще существует из-за каузального self-attention: KV токена зависит лишь от него и предыдущих. Именно поэтому KV общего префикса побитово одинаковы и переиспользуемы — прямое следствие архитектуры #32, а не отдельный трюк.

↔ дополняет53. DeepSeek V3 / R1

Две оси атаки на один боттлнек. MLA сжимает KV ВНУТРИ запроса (архитектурно, низкоранговый латент); prefix caching / CacheBlend переиспользуют KV МЕЖДУ запросами (системно). Складываются: меньше KV на запрос × реже его считать = дешёвый длинный контекст.

Вопросы пытливого ума

Если KV префикса переиспользуем точно, почему нельзя так же взять любой кусок текста?

Точно переиспользуем только ИСТИННЫЙ префикс — лишь у него предшествующий контекст тот же. KV любого внутреннего куска, посчитанный изолированно, (а) стоит не на своей позиции и (б) не видел предшествующих кусков — нет кросс-внимания. Наивно склеить такие KV — и модель «не связывает» куски, качество падает. Ровно эту дыру и закрывает CacheBlend выборочным досчётом малой доли токенов.

Почему хватает пересчитать ~15% токенов — ошибка же копится по слоям?

Потому что отклонение KV РАЗРЕЖЕНО: у большинства токенов реальный контекст меняет KV слабо, а сильно «расходятся» немногие (на стыках кусков, служебные позиции). Пересчитывая эти high-deviation токены на каждом слое, чинишь доминирующую ошибку до того, как она расползётся. Доля досчёта — ручка размена: больше процент → ближе к полному prefill, но дороже. Эмпирически малой доли достаточно, чтобы качество не просело.

Prefix caching экономит на ПОВТОРАХ — а если запросы почти не делят префикс?

Тогда выигрыша мало — это его честное ограничение. Зато он блестит там, где повтор массовый: общий системный промпт у тысяч запросов, многоходовые диалоги (та же история каждый ход), few-shot, агентные циклы. CacheBlend расширяет зону выгоды на RAG, где одни и те же документы возвращаются в разных комбинациях — уже не как общий префикс. Поэтому prompt caching и стал стандартной строкой в прайсе API.

Что читать в оригинале

Читать выборочно. Из vLLM — design-док про automatic prefix caching (хэширование блоков по цепочке, переиспользование по совпадению хэша). Из CacheBlend (arXiv 2405.16444, EuroSys ’25) — постановку (почему не-префиксные KV нельзя переиспользовать наивно), идею selective recompute по KV-deviation и пайплайнинг досчёта с загрузкой кэша из медленного хранилища.