Что такое кэш ключей и значений (KV cache) в LLM, почему он снижает стоимость генерации с O(n²) до O(n) и чем за это приходится платить в памяти?

Кэш ключей и значений (KV cache) хранит уже посчитанные K и V для всех предыдущих токенов, чтобы на каждом шаге генерации считать Q только для нового токена. Без кэша на каждом шаге приходится заново считать внимание для всей последовательности → O(n²) операций на шаг, O(n³) всего. С кэшем — O(n·d) на шаг, O(n²·d) всего. Цена — память: кэш растёт линейно с длиной контекста, для Llama 7B при 8K токенов это ≈ 4.3 ГБ на один запрос. Уменьшают через MQA/GQA (головы делят ключи и значения), квантизацию кэша в int8/int4, PagedAttention (vLLM) и скользящее окно.