KV-кэширование

Материал из MachineLearning.

Версия от 12:09, 26 июня 2026; Mihail Mishin (Обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Статья написана с использованием LLM DeepSeek-V3 и проверена участником М. Мишин 15:09, 26 июня 2026 (MSD)
Промпт приводится полностью в Обсуждение:KV-кэширование


Содержание

Определение и основная идея

KV-кэширование (англ. Key-Value caching) — это механизм оптимизации инференса авторегрессионных трансформеров, при котором для каждого слоя и каждой головы внимания сохраняются проекции ключей (K) и значений (V) всех ранее обработанных токенов. Благодаря этому на каждом шаге генерации вычисляются только ключ и значение для нового токена, а для внимания используются кэшированные векторы, что превращает квадратичную по длине последовательности сложность в линейную.

В основе подхода лежит простое, но критическое наблюдение: после того как для токена вычислены K и V, они не изменяются при добавлении новых токенов. Следовательно, их можно сохранить и использовать на всех последующих шагах декодирования. Без кэша каждый шаг генерации требовал бы пересчёта ключей и значений для всех предыдущих токенов, что приводило бы к кубической сложности на всю последовательность (\mathcal{O}(n^3)). С кэшем эта сложность падает до квадратичной (\mathcal{O}(n^2)), а на практике ускорение достигает 3–5 раз и более.

Ключевым понятием является повторное использование — единожды вычисленные проекции служат для всех последующих запросов. Это позволяет реализовать эффективный инференс моделей с контекстными окнами в сотни тысяч и миллионы токенов.

Математическая формализация

Пусть на входе последовательность длины n. На каждом слое трансформера для токена i вычисляются: Q_i = X_i W_Q, \quad K_i = X_i W_K, \quad V_i = X_i W_V.

В фазе prefill (первичная обработка промпта) все токены обрабатываются параллельно, и для всех i=1\ldots n векторы K_i, V_i сохраняются в кэш. В фазе decode (авторегрессивная генерация) на каждом шаге t для нового токена вычисляются Q_t, K_t, V_t, K_t и V_t добавляются в кэш, а внимание вычисляется как:

\text{Attention}(Q_t, K_{1:t}, V_{1:t}) = \text{softmax}\left(\frac{Q_t K_{1:t}^\top}{\sqrt{d_k}}\right) V_{1:t}.

Здесь K_{1:t} и V_{1:t} — матрицы, составленные из кэшированных ключей и значений всех токенов с 1-го по t-й.

Сложность вычислений:

Без кэша: на каждом decode-шаге требуется \mathcal{O}(t^2) операций (пересчёт всех K и V и вычисление внимания), что для всей последовательности длины n даёт \mathcal{O}(n^3) операций.

С кэшем: на фазе prefill выполняется \mathcal{O}(n^2) операций (однократно), а на каждом decode-шаге — \mathcal{O}(t) операций (только внимание для нового запроса против кэшированных ключей). Итоговая сложность всей генерации составляет \mathcal{O}(n^2).

Объём памяти для кэша (в битах):

\text{Size}_{\text{KV}} = 2 \times L \times H \times d_h \times n \times b,

где L — число слоёв, H — число голов внимания, d_h — размерность головы, n — длина последовательности, b — разрядность представления (например, 16 для FP16). Для модели с 70 млрд параметров и контекстом 128K токенов кэш может занимать свыше 40 ГБ, что сопоставимо с весом модели.

Механизм работы: prefill, decode и роль кэша

Инференс авторегрессионной модели традиционно разделяется на две фазы:

Фаза Prefill

Модель получает входной промпт. Все токены промпта обрабатываются параллельно в одном прямом проходе. Вычисляются Q, K, V для каждого токена, и все K, V сохраняются в KV-кэш. Выходом фазы является скрытое состояние последнего токена, используемое для предсказания первого генерируемого токена. Эта фаза — единственный этап, на котором вычисления имеют квадратичную сложность по длине промпта, но она выполняется однократно.

Фаза Decode

На каждом шаге генерации:

  1. Модель принимает последний сгенерированный токен.
  2. Для этого токена вычисляются Q_{\text{new}}, K_{\text{new}}, V_{\text{new}}.
  3. K_{\text{new}} и V_{\text{new}} добавляются в конец кэша.
  4. Внимание вычисляется с использованием Q_{\text{new}} и всех сохранённых K и V.

Таким образом, каждый decode-шаг требует лишь одного матричного умножения Q K^\top размера 1 \times t (текущий запрос против всех кэшированных ключей), а не t \times t. Это и даёт линейную сложность на шаг. По сути, процесс представляет собой последовательное накопление кэша: на каждом шаге к существующему набору ключей и значений добавляется новая пара, после чего запрос текущего токена взаимодействует со всем накопленным множеством.

Мотивация использования: снижение латентности и рост пропускной способности

KV-кэш даёт следующие ключевые преимущества:

  • Снижение латентности — каждый шаг генерации требует только одного прямого прохода через слои для нового токена, а не для всей последовательности. Для длинных контекстов ускорение может достигать десятков раз.
  • Рост пропускной способности — в пакетном режиме (batch inference) кэш позволяет обрабатывать множество запросов параллельно с разделением вычислений для общих промптов.
  • Экономия вычислительных ресурсов — по оценкам, кэширование сокращает объём повторных вычислений на 70–90% для типичных рабочих нагрузок.

Однако платой за это является экспоненциальный рост потребления памяти, что порождает целый класс методов оптимизации.

Классификация стратегий оптимизации KV-кэша

Современные подходы к управлению KV-кэшем можно разделить на пять основных направлений.

Вытеснение (Cache Eviction)

Удаление «неважных» токенов из кэша на основе эвристик (веса внимания, частоты обращений, позиции). Примеры: H2O (вытеснение по весам внимания), SnapKV, Ada-KV. Позволяют сократить кэш в 2.7–5.7 раз с незначительной потерей точности.

Сжатие (Cache Compression)

Уменьшение размера каждого элемента кэша:

  • Квантование — снижение разрядности (FP16 → INT8, INT4, 1-bit). Исследования показывают, что квантование часто эффективнее сокращения размерности: INT4 сохраняет точность, близкую к FP16.
  • Сокращение размерности — проецирование ключей и значений в пространство меньшей размерности (например, через PCA или обученные проекции).
  • Разрежённое представление — хранение только ненулевых компонент.

Гибридная память (Hybrid Memory)

Комбинирование быстрой (VRAM) и медленной (CPU RAM, диск) памяти. Важные токены хранятся в VRAM, менее важные — выгружаются. При необходимости выгруженные токены могут быть перевычислены (Recomputation).

Новые механизмы внимания

Архитектурные модификации, уменьшающие размер кэша по определению:

  • Multi-Query Attention (MQA) — все головы разделяют один ключ и одно значение.
  • Grouped-Query Attention (GQA) — головы группируются, и каждая группа разделяет ключи/значения (компромисс между MHA и MQA).
  • Cross-Layer Attention (CLA) — разделение ключей и значений между соседними слоями.
  • Layer-Condensed KV Cache — запросы всех слоёв работают с ключами и значениями только верхнего слоя.

Комбинированные стратегии

Сочетание нескольких методов (квантование + вытеснение + гибридная память) в адаптивных пайплайнах. Оптимальная стратегия зависит от контекста, аппаратуры и типа нагрузки.

Связь с другими методами оптимизации инференса

KV-кэширование часто применяется совместно с другими техниками ускорения и сжатия, однако принципиально отличается от них.

  • Сравнение с FlashAttention. FlashAttention оптимизирует вычисления внимания за счёт IO-aware подхода, уменьшая количество обращений к медленной памяти, но не изменяет объём хранимых данных. KV-кэш, напротив, хранит промежуточные результаты, сокращая число операций. Они взаимодополняют друг друга: FlashAttention может эффективно вычислять внимание с кэшем.
  • Сравнение с квантизацией. Квантизация уменьшает разрядность весов и активаций, сокращая память и ускоряя умножения. В контексте KV-кэша квантизация применяется непосредственно к сохранённым ключам и значениям. Это два ортогональных подхода, которые часто комбинируются.
  • Сравнение с прунингом. Прунинг удаляет избыточные веса модели, уменьшая её размер. KV-кэш не изменяет модель, а оптимизирует процесс инференса. Прунинг может быть применён к модели перед использованием кэша для ещё большего ускорения.

Таким образом, KV-кэш — это не альтернатива, а дополнительный слой оптимизации, который может сочетаться с любыми другими методами.

Современные вызовы и актуальные подходы

Рост контекстных окон

Контекстные окна LLM стремительно растут: от тысяч до миллионов токенов. При линейном росте кэша с длиной последовательности это создаёт огромное давление на память. Индустрия ищет решения, позволяющие удерживать кэш в разумных пределах даже для сверхдлинных контекстов.

Баланс между сжатием и точностью

Каждый метод сжатия вносит искажения. Квантование может привести к росту перплексии, вытеснение — к потере критически важной информации. Современные исследования стремятся к адаптивным стратегиям, где степень сжатия зависит от слоя, головы и даже позиции токена.

Аппаратные ограничения

Пропускная способность памяти часто становится узким местом: даже если кэш помещается в VRAM, его чтение может доминировать над временем вычислений. Это стимулирует разработку специализированных форматов хранения (страничный, блочный) и аппаратно-ориентированных алгоритмов.

Актуальные научные подходы

  • Постоянный размер кэша (constant-size). Работы последних лет (например, TConstFormer, MorphKV) стремятся сделать размер кэша независимым от длины последовательности за счёт периодического обновления состояния или агрегации.
  • Продвинутое квантование. Методы вроде OCTOPUS (октаэдральная параметризация) и SpectralQuant (эйгенспектральное сжатие) достигают коэффициентов сжатия до 6.55× при сохранении качества. AsymKV показывает возможность 1-битного квантования при асимметричной настройке для ключей и значений.
  • Адаптивное сжатие. KV-Latent проецирует ключи и значения в латентное пространство с уменьшенной размерностью, требуя менее 1% дополнительного обучения. TaDA — метод без дообучения, адаптирующий точность квантования к чувствительности слоёв.
  • Межслойное разделение. Cross-Layer KV-Cache Sharing использует общие ключи и значения между слоями без дообучения, а SkipV1Former применяет skip-соединения от первых value-голов.
  • Аппаратно-ориентированные подходы. ScaleKV учитывает различные потребности в кэше на разных слоях и масштабах. KV-Direct предлагает хранить residual-векторы вместо ключей и значений, перевычисляя последние по требованию.

Форматы хранения и библиотеки

Форматы

  • Непрерывный (contiguous) — все KV-пары хранятся в одном тензоре размера `[batch, seq_len, num_heads, head_dim]`. Прост, но приводит к фрагментации при динамическом росте.
  • Страничный (paged) — ключевая инновация vLLM. Кэш разбивается на страницы фиксированного размера, что устраняет фрагментацию и позволяет эффективно управлять памятью.
  • Блочный (blocked) — вариация страничного подхода.

Библиотеки и движки

  • vLLM — де-факто стандарт для высокопроизводительного инференса, реализует PagedAttention.
  • FlashAttention / FlashInfer — оптимизированные ядра внимания, работающие с KV-кэшем.
  • Hugging Face Transformers — базовая поддержка через параметр `use_cache=True`.
  • ARGUS — академический менеджер KV-кэша с 7-уровневой страничной организацией и динамическим квантованием.

Заключение

KV-кэширование является необходимым компонентом инференса авторегрессионных трансформеров, обеспечивающим снижение вычислительной сложности с \mathcal{O}(n^3) до \mathcal{O}(n^2) за счёт сохранения и повторного использования проекций ключей и значений ранее обработанных токенов. Данный механизм позволяет достичь линейной сложности на каждом шаге декодирования, что делает возможным практическое применение моделей с большими контекстными окнами. Основной платой за ускорение является линейный рост объёма занимаемой памяти, который для современных LLM при длинных последовательностях становится доминирующим фактором, ограничивающим масштабируемость.

См. также

Литература

  • Vaswani A., Shazeer N., Parmar N., Uszkoreit J., Jones L., Gomez A. N., Kaiser Ł., Polosukhin I. Attention Is All You Need // NeurIPS, 2017. arXiv:1706.03762 — основополагающая работа, вводящая архитектуру трансформера и механизм масштабированного внимания, на котором базируется KV-кэширование.
  • Kwon W., Li Z., Zhuang S., Sheng Y., Zheng L., Yu C. H., Gonzalez J., Zhang H., Stoica I. Efficient Memory Management for Large Language Model Serving with PagedAttention // SOSP, 2023. arXiv:2309.06180 — оригинальная работа о системе vLLM и страничном управлении KV-кэшем, устраняющем фрагментацию памяти.
  • Dao T., Fu D. Y., Ermon S., Rudra A., Ré C. FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness // NeurIPS, 2022. arXiv:2205.14135 — метод IO-оптимизированного вычисления внимания, часто применяемый совместно с KV-кэшем для повышения производительности.
  • Shazeer N. Fast Transformer Decoding: One Write-Head is All You Need // arXiv, 2019. arXiv:1911.02150 — введение Multi-Query Attention (MQA), радикально сокращающего размер KV-кэша за счёт разделения ключей и значений между головами.
  • Ainslie J., Lee-Thorp J., de Jong M., Zemlyanskiy Y., Lebrón F., Sanghi S. GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints // EMNLP, 2023. arXiv:2305.13245 — представление Grouped-Query Attention (GQA) как компромисса между MHA и MQA, широко используемого в современных LLM.
  • Zhang Z., Sheng Y., Zhou T., Chen T., Zheng L., Cai R., Song Z., Tian Y., Ré C., Barrett C., Wang Z., Chen B. H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models // NeurIPS, 2023. arXiv:2306.14048 — метод вытеснения токенов из KV-кэша на основе весов внимания (Heavy-Hitter), позволяющий сократить кэш в несколько раз с минимальной потерей точности.
  • Salfati S. Quantization Dominates Rank Reduction for KV-Cache Compression // arXiv, 2026. arXiv:2604.11501 — сравнительное исследование методов сжатия, показывающее преимущество квантования перед сокращением размерности для сохранения качества генерации.
  • Xu Y., Khaira N. K., Singh T. KV Cache Optimization Strategies for Scalable and Efficient LLM Inference // arXiv, 2026. arXiv:2603.20397 — всесторонний обзор стратегий оптимизации KV-кэша с классификацией по методам вытеснения, сжатия и архитектурным модификациям.
  • Boss M., et al. OCTOPUS: Optimized KV Cache for Transformers via Octahedral Parametrization // arXiv, 2026. arXiv:2605.21226 — метод сжатия на основе октаэдральной параметризации, достигающий высоких коэффициентов сжатия без потери точности.
  • Li Y., et al. SnapKV: LLM Knows What You Are Looking for Before Generation // arXiv, 2024. arXiv:2404.14469 — метод вытеснения, использующий веса внимания на этапе prefill для определения важных токенов, эффективный для сверхдлинных контекстов.

Категории

Источник — «http://www.machinelearning.ru/wiki/index.php?title=KV-%D0%BA%D1%8D%D1%88%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5»
Личные инструменты