Что такое KV cache в LLM, почему он сокращает inference с O(n²) до O(n), и какие у него memory tradeoffs?

KV cache хранит уже посчитанные K и V для всех предыдущих токенов, чтобы на каждом шаге autoregressive generation считать Q только для нового токена. Без кеша на каждый шаг повторно считаем attention для всей последовательности → O(n²) compute на шаг, O(n³) total. С кешем — O(n·d) на шаг, O(n²·d) total. Цена — memory: cache растёт линейно по контексту, для Llama 7B с 8K context ≈ 4.3 GB на sample. Снижают через MQA/GQA, int8/int4 quantization KV, PagedAttention (vLLM), sliding window.