SPB Git

spb/wp30_uqo

Public
32.1 KB

# Literature audit — Group 2 (KV-cache compression primary sources)

WP30 — "Cache Compression and Knowledge Transfer in Multi-Agent Systems" Access date for every URL below: 2026-10-29. Nothing in this file comes from memory: every statement is traceable to a page fetched on that date (arXiv abstract page, arXiv HTML full text, GitHub page, raw file on raw.githubusercontent.com, GitHub REST API, or — for venue confirmation only — the NeurIPS proceedings / Microsoft Research page, marked "secondary").

Conventions:

  • "arXiv Comments" = the Comments field on the abstract page (the only place arXiv itself states a venue).
  • "Question-access class" = whether the compression policy observes the question/instruction when it decides what to keep (relevant to the paper's question-blind vs question-aware distinction).
  • GitHub metadata (license SPDX id, default branch, stars, latest commit SHA/date) was read from https://api.github.com/repos/<owner>/<repo> and /commits?per_page=1.

# 1. KIVI — kivi2024

Fetched: https://arxiv.org/abs/2402.02750 · https://arxiv.org/html/2402.02750v2 · https://github.com/jy-yuan/KIVI · raw README.md, models/llama_kivi.py, requirements.txt, quant/setup.py, scripts/long_test.sh, example.py · GitHub API.

Field Verified value
Exact title KIVI: A Tuning-Free Asymmetric 2bit Quantization for KV Cache
Authors (as listed on arXiv) Zirui Liu, Jiayi Yuan, Hongye Jin, Shaochen Zhong, Zhaozhuo Xu, Vladimir Braverman, Beidi Chen, Xia Hu
Venue / status ICML 2024 — arXiv Comments field reads "ICML2024"; repo description "[ICML 2024] KIVI…"; README update 2024.05.01 "KIVI has been accepted by ICML 2024".
Year 2024 (v1 Feb 2024)
arXiv revisions v1 2024-02-05 ; v2 2024-07-25 (latest)
Subjects cs.CL; cs.LG; cs.PF
Repository https://github.com/jy-yuan/KIVI — exists, public, not a fork, linked from the arXiv abstract. Default branch main, 438 stars, created 2024-02-02.
Latest commit 876b4d2d08e3b1d5f70d0969c299d8c7c42ddfb6 — 2025-11-20
License MIT (GitHub API SPDX MIT; README: "The code is released under the MIT License.")
Checkpoints None needed/provided: tuning-free method applied at load time to HF checkpoints (Llama-2, Llama-3/3.1, Mistral, LongChat; Falcon in paper).

Supported backends / environment (verified in repo files):

  • PyTorch + custom CUDA extension (quant/setup.py builds kivi_gemv via torch.utils.cpp_extension.CUDAExtension, sources csrc/gemv_cuda.cu) + Triton kernel for packing (quant.new_pack.triton_quantize_and_pack_along_last_dim; requirements.txt pins triton==2.1.0).
  • requirements.txt pins torch==2.1.2, transformers==4.36.2, flash-attn==2.5.6, accelerate==0.25.0, nvidia-*-cu12 wheels. README update 2025.01.18: "KIVI implementation with GQA and compatible with transformers 4.43" (Llama-3 support).
  • models/llama_kivi.py asserts "currently KIVI is only available for flash-attn" in the flash variant; prefill runs standard _flash_attention_forward on unquantized K/V, quantization fills the cache afterwards.
  • Apple Silicon / MPS: not mentioned anywhere (CUDA + Triton + flash-attn required → CUDA-only as released). A faithful MLX/MPS re-implementation must re-create the quantizer and the mixed-precision attention in plain tensor ops.

Core algorithm (implementation-grade):

  1. Asymmetric uniform round-to-nearest quantizer per group: zero-point z = min(X), scale s = (max(X) − min(X)) / (2^B − 1), Q = round((X − z)/s), dequant Q·s + z; B = 2 (KIVI-2) or 4 (KIVI-4), set independently for K (k_bits) and V (v_bits).
  2. Keys: per-channel quantization, grouped along the token dimension. Keys are transposed to [b, h, head_dim, tokens] and packed along the last (token) axis, so one (scale, zero) pair covers group_size consecutive tokens of one channel (triton_quantize_and_pack_along_last_dim(key_states.transpose(2,3), group_size, k_bits)). Motivation (paper): a few channels have outlier magnitudes; per-channel confines the error.
  3. Values: per-token quantization, grouped along the channel dimension. No transpose; each token's head_dim channels are split into groups of group_size with their own (scale, zero), so newly quantized tokens can be appended along the token axis.
  4. Full-precision residual window residual_length (R). Prefill: keys keep the last t mod R tokens in fp16 (key_states[:, :, :-(t % R), :] quantized), values keep the last R tokens in fp16. Decode: new keys accumulate in a fp16 buffer and the whole block is quantized at once when it reaches R (asserted R % group_size == 0); values use a sliding queue: when the fp16 buffer reaches R+1 the oldest token is popped and quantized (value_states_full[:, :, :1, :]).
  5. Attention at decode = concat(cuda_bmm_fA_qB_outer(q, K_quant, scales, zeros), q·K_fullᵀ) / sqrt(d) → mask → softmax → cuda_bmm_fA_qB_outer(P_quant, V_quant, …) + P_full·V_full.
  6. Hyperparameters: paper main setting group size G = 32, residual length R = 128, 2-bit; example.py uses k_bits=v_bits=2, group_size=32, residual_length=32. Ablation (paper): G = 128 degrades GSM8K noticeably; R ∈ {32, 96, 128} similar, R = 64 worst.

Original evaluation setting: Llama-2-7B/13B, Falcon-7B, Mistral-7B (appendix adds Llama-3-8B-Instruct, Mistral-7B-Instruct-v0.2, LongChat-7B-v1.5-32K); LM-Eval tasks CoQA, TruthfulQA, GSM8K; LongBench (15 tasks in repo); 5-digit passkey retrieval at 12k context. Results: KIVI-2 ≤ ~2 % accuracy drop on Llama/Mistral; 2.6× lower peak memory (weights included), up to 4× larger batch, 2.35×–3.47× throughput (Llama-2-7B, ShareGPT workloads, one A100-80GB). Falcon-7B (multi-query attention) needs KIVI-4.

Stated limitations (paper has no dedicated section; collected from text): fake 2-bit quantization without the fp16 window collapses on GSM8K (window essential for reasoning); Falcon's already small MQA cache limits gains; quantization overhead during prefill/decode not yet fused with preceding ops (future work); only Llama and Mistral families supported in code; CUDA kernels required.

Question-access class: Not a selection method — content- and question-agnostic. KIVI keeps every token and reduces precision uniformly; nothing in the policy reads the query or the question. In our taxonomy it is "question-blind by construction", and it is orthogonal/combinable with eviction methods (the paper itself positions it that way; KVCache-Factory also lists it under "Quantization").


# 2. SnapKV — snapkv2024

Fetched: https://arxiv.org/abs/2404.14469 · https://arxiv.org/html/2404.14469v2 · https://github.com/FasterDecoding/SnapKV · raw snapkv/monkeypatch/snapkv_utils.py, pyproject.toml, experiments/LongBench/pred_snap.py, experiments/LongBench/config/ablation_c1024_w32_k7_maxpool.json, config/model2path.json · GitHub API · (secondary) https://proceedings.neurips.cc/paper_files/paper/2024/hash/28ab418242603e0f7323e54185d19bde-Abstract.html.

Field Verified value
Exact title SnapKV: LLM Knows What You are Looking for Before Generation
Authors (as listed on arXiv) Yuhong Li, Yingbing Huang, Bowen Yang, Bharat Venkitesh, Acyr Locatelli, Hanchen Ye, Tianle Cai, Patrick Lewis, Deming Chen
Venue / status arXiv page: no Comments field → no venue stated by arXiv. Repo README cites it only as "arXiv preprint arXiv:2404.14469". Secondary confirmation (fetched): NeurIPS proceedings list it in Advances in Neural Information Processing Systems 37 (NeurIPS 2024), Main Conference Track, DOI 10.52202/079017-0722. → Record as "NeurIPS 2024 (proceedings page; not stated on arXiv/repo)".
Year 2024
arXiv revisions v1 2024-04-22 ; v2 2024-06-17 (latest)
Subjects cs.CL; cs.AI
Repository https://github.com/FasterDecoding/SnapKV — exists, public, not a fork. The arXiv abstract page does not link any repository (abstract mentions a "HuggingFace implementation" without URL); the expected URL was fetched directly and its README/BibTeX match the paper (same title, same 9 authors). Default branch main, 336 stars, created 2024-03-23.
Latest commit e216ddc84c5bd210378cbdbbba12ba02102aa640 — 2025-07-10
License Apache-2.0 (GitHub API SPDX Apache-2.0; pyproject.toml classifier "License :: OSI Approved :: Apache Software License").
Checkpoints None (training-free monkey-patch on HF checkpoints). model2path.json lists Llama-2-7b-chat, LongChat-7b-v1.5-32k, Mistral-7B-Instruct-v0.1/0.2, Mixtral-8x7B-Instruct-v0.1, LWM-Text-Chat-1M, LWM-Text-1M, Llama-2-7B-32K-Instruct, etc.

Supported backends / environment:

  • PyTorch + HF transformers via monkey patches replace_llama(), replace_mistral(), replace_mixtral() (snapkv/monkeypatch/). README: "tested with transformers==4.37.0", requirements "transformers>=4.36" and "flash-attn==2.4.0"; pyproject.toml declares transformers>=4.34, torch unpinned, requires-python>=3.9. README warns compatibility with newer transformers still needs checking.
  • No torch/CUDA version pin; flash-attn dependency implies CUDA. Apple Silicon / MPS not mentioned. The core selection in snapkv_utils.py is plain PyTorch (matmul, softmax, avg_pool1d/max_pool1d, topk, gather) and is therefore portable in principle.

Core algorithm (from snapkv_utils.py, class SnapKVCluster.update_kv, prefill only):

  1. Constructor defaults window_size=64, max_capacity_prompt=256+64, kernel_size=5, pooling='avgpool' (asserts max_capacity_prompt − window_size > 0); init_snapkv fallback when the config lacks fields: window_size=32, max_capacity_prompt=2048, kernel_size=5, pooling='avgpool'.
  2. Asserts key_len == query_len (prefill). If q_len < max_capacity_prompt: return K/V unchanged.
  3. Observation window = last w = window_size prompt tokens. Scores: attn = softmax_fp32( Q[-w:] · Kᵀ / sqrt(d) + causal mask on the w×w window block ) → shape (b, h, w, L).
  4. Voting: attn_weights_sum = attn[:, :, -w:, :-w].sum(dim=-2) → (b, h, L−w) = attention mass each prefix token receives from the window queries.
  5. Clustering/pooling: F.avg_pool1d or F.max_pool1d with kernel_size, padding = kernel_size // 2, stride = 1 (length-preserving).
  6. Per-head top-k: indices = pooled.topk(max_capacity_prompt − w, dim=-1).indices (independent per head and per layer; indices not re-sorted by position); gather K/V of the prefix at those indices.
  7. Output cache = concat([K_selected, K[-w:]]), same for V → exactly max_capacity_prompt tokens per head. No update during decoding (header comment: "will not update in inference mode"). num_key_value_groups accepted but unused → caller handles GQA.
  8. Experimental hyperparameters (paper + configs): Needle-in-a-Haystack (LWM-Text-Chat-1M) window 16, kernel 5, capacity 1024; LongBench window 32, kernel 7, max-pool, capacities 1024/2048/4096 (ablation_c{1024,2048,4096}_w32_k7_maxpool.json); Command-R window 64, kernel 13, capacity 4096. Paper §5.2: max- vs avg-pooling perform similarly.

Original evaluation setting: LWM-Text-Chat-1M, LongChat-7b-v1.5-32k, Mistral-7B-Instruct-v0.2, Mixtral-8x7B-Instruct-v0.1, Command-R (35B); LongBench (16 datasets), Needle-in-a-Haystack, LongEval-Lines, RAG/citation (internal Cohere), QASPER (parallel decoding); 3.6× generation speedup, 8.2× memory efficiency at 16K tokens; 380K-token context on one A100-80GB with negligible NIAH drop.

Stated limitations (paper §6): scope "primarily confined to the generative aspect"; cannot extend a model's long-context ability if the base model already struggles; does not address prompt-processing (prefill) cost/memory. Repo TODO: prompt-phase compression, "reduplication" experiments.

Question-access class: Question-aware. The observation window is "the last segment of the prompt"; §4.2.1 describes it as "the instructions and their corresponding responses", and the core finding is "Pattern can be identified before generation": the attention pattern of the last window predicts the generation-time pattern. §4.2.2 reports high hit rates whether the instruction is placed before or after the context, i.e. the method is robust but still conditions on whatever ends the prompt. In LongBench prompt templates the question/instruction is at the end, so SnapKV as evaluated sees the question. In our question-blind protocol (compress before the question is appended) the window would contain the last context tokens, not the question — this must be stated explicitly when SnapKV is used as a baseline.


# 3. PyramidKV — pyramidkv2024

Fetched: https://arxiv.org/abs/2406.02069 · https://arxiv.org/html/2406.02069v4 (two chunks) · https://github.com/BartsLab/PyramidKV · raw BartsLab README.md, LICENSE, requirements.txt, run_longbench.py, pyramidkv/pyramidkv_utils.py · https://github.com/Zefan-Cai/KVCache-Factory · raw KVCache-Factory pyramidkv/pyramidkv_utils.py, run_longbench.py, requirements.txt · GitHub API · (secondary) https://www.microsoft.com/en-us/research/?p=1149160.

Field Verified value
Exact title PyramidKV: Dynamic KV Cache Compression based on Pyramidal Information Funneling
Authors (as listed on arXiv, v4) Zefan Cai, Yichi Zhang, Bofei Gao, Yuliang Liu, Yucheng Li, Tianyu Liu, Keming Lu, Wayne Xiong, Yue Dong, Junjie Hu, Wen Xiao (11). ⚠ Author-list discrepancy: the BartsLab README BibTeX lists "…Wayne Xiong, Yue Dong, Baobao Chang, Junjie Hu, and others" and the Microsoft Research page lists Baobao Chang instead of Yucheng Li. Use the arXiv v4 list; flag in the paper if cited by venue version.
Venue / status arXiv page: no Comments field; BartsLab README BibTeX: "journal={CoRR}, year={2024}"; KVCache-Factory README: "arXiv preprint arXiv:2406.02069". Secondary (fetched): Microsoft Research publication page tags it COLM 2025 (July 2025). → Record as "COLM 2025 (Microsoft Research page; not stated on arXiv/repo)".
Year 2024 (v1 June 2024; v4 May 2025)
arXiv revisions v1 2024-06-04 ; v2 2024-06-16 ; v3 2024-10-03 ; v4 2025-05-15 (latest)
Subjects cs.CL; cs.AI
Repository (asked) https://github.com/BartsLab/PyramidKV — exists but is a 0-star fork of Zefan-Cai/KVCache-Factory (GitHub API fork: true, parent: Zefan-Cai/KVCache-Factory), created 2024-11-16, latest commit 506c866a876bdcc7ca4f2f73aa7f856a8c666479 dated 2024-11-05 → a frozen snapshot of the pre-rename code. Its README still says "git clone https://github.com/Zefan-Cai/PyramidKV.git".
Repository (canonical) https://github.com/Zefan-Cai/KVCache-Factory — README News 2024-11-28: "Project renamed to KVCache-Factory"; "started from PyramidKV"; 1 392 stars; latest commit 68cd9551a63fedf362ddb0edb008badd04c24996 — 2026-08-12; description "Unified KV Cache Compression Methods for Auto-Regressive Models". The arXiv abstract page links no repository.
License MIT both repos (GitHub API SPDX MIT; BartsLab LICENSE: "MIT License / Copyright (c) 2024 Zefan Cai").
Checkpoints None (training-free).

Supported backends / environment:

  • PyTorch + HF transformers. requirements.txt (both repos) pins transformers==4.44.2 (README text says ">= 4.41"); torch unpinned; flash-attn >= 2.4.0.post1 required for flash_attention_2, optional with --attn_implementation sdpa|eager (News 2024-06-10). Multi-GPU for Llama-3-70B (News 2024-06-25).
  • Models: Llama (Llama-3-8B/70B-Instruct) and Mistral-7B-Instruct-v0.2 patched attention; Mixtral, batch inference (eval_batch_size must be 1) and decoding-stage compression are TODO/not supported. KVCache-Factory additionally implements StreamingLLM, H2O, SnapKV, Quest, NACL, Scissorhands, L2Norm, CAM, AdaKV, HeadKV, ThinK, MiniCache, HeadInfer, MInference, KIVI, KVQuant, GEAR, FullKV.
  • Apple Silicon / MPS not mentioned. Selection code is plain PyTorch (see below) → portable in principle; the runner defaults to flash_attention_2.

Core algorithm (from pyramidkv_utils.py, class PyramidKVCluster, prefill only):

  1. Constructor defaults: num_hidden_layers=32, window_size=64, max_capacity_prompt=256+64, kernel_size=5, pooling='avgpool', beta=20, layer_idx=None. init_pyramidkv passes the layer's layer_idx and num_hidden_layers; β stays 20. The LongBench runner (run_longbench.py, both repos) overrides for snapkv|pyramidkv|h2o|cam: window_size = 8, kernel_size = 7, pooling = 'maxpool'; for streamingllm: window_size = max_capacity_prompt − 4. max_capacity_prompts CLI default 512 (paper: 64, 96, 128, 256, 512, 1024, 2048).
  2. Per-layer budget (arithmetic pyramid), with base = max_capacity_prompt − window_size: min_num = base // beta (top layer) ; max_num = 2·base − min_num (bottom layer) ; if max_num >= q_len − window_size: max_num = q_len − window_size, min_num = 2·base − max_num (clamp for short prompts) ; steps = (max_num − min_num) // (num_hidden_layers − 1) ; budget_l = max_num − layer_idx · steps (+ the window). Sum over layers ≈ num_layers · base, i.e. the same total as a uniform SnapKV budget. Paper form: k^{m−1} = k_total/(β·m), k^0 = 2·k_total/m − k^{m−1}, k^l = k^0 − ((k^0 − k^{m−1})/(m−1))·l. Guard: if q_len < max_capacity_prompt → no compression; if q_len < 2·base → flat budget base in every layer (pyramid only kicks in for long prompts).
  3. Within-layer selection = SnapKV: last window_size queries (paper: α = 8 "instruction tokens") attend to all keys (causal mask on the window block, fp32 softmax); scores = attn[:, :, -w:, :-w].sum(-2); 1-D pooling (kernel k, padding k//2, stride 1); per-head topk(budget_l); gather and concat with the window K/V. GQA handled with gqa_score_agg='mean' in KVCache-Factory.
  4. Paper hyperparameters: β = 20, α = 8 in main experiments (appendix: α = 8 or 16 best; β insensitive). Pooling kernel size is not stated in the paper text; code uses 7 (max-pool) in the runner.

Original evaluation setting: Llama-3-8B-Instruct, Llama-3-70B-Instruct, Mistral-7B-Instruct (Mixtral only in attention visualisations); LongBench (17 datasets; some sections say 16) at budgets 64/96/128/256/2048 (512/1024 in the memory table); Needle-in-a-Haystack (context 1 000–8 001 tokens, step 100; budgets 64–2048). Claims: ~12 % of KV cache matches full-cache LongBench; with 0.7 % retained, up to +20.5 points on TREC vs other methods; 128 KV entries give Llama-3-70B 100 % NIAH accuracy. Baselines run with the same code: SnapKV, H2O, StreamingLLM, FullKV.

Stated limitations (paper Appendix A, paraphrased): only three base models; English only (no cross-lingual study); weaker on summarisation than on few-shot in-context learning; no decoding-collapse analysis (future work). Repo: no decoding-stage compression, batch size 1, Mixtral pending, percentage-based budget allocation planned.

Question-access class: Question-aware (inherits SnapKV's observation window). The paper explicitly calls the last α tokens "instruction tokens … holding the most immediate task-related information" and keeps them in every layer. The budget allocation across layers itself is content-independent (depends only on β, total budget, layer index, prompt length), so a question-blind variant of PyramidKV = pyramid budget + a question-blind within-layer scorer — worth noting as a decomposition in WP30.


# 4. H2O (Heavy-Hitter Oracle) — h2o2023

Fetched: https://arxiv.org/abs/2306.14048 · https://arxiv.org/html/2306.14048v3 (two chunks of three) · https://github.com/FMInference/H2O · raw README.md, h2o_hf/README.md, h2o_flexgen/README.md, h2o_hf/utils_real_drop/modify_llama.py, h2o_hf/utils_hh/modify_llama.py · GitHub API (/contents/ root and h2o_hf listings).

Field Verified value
Exact title H₂O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models (arXiv renders "H$_2$O"; repo spells "H2O")
Authors (as listed on arXiv) Zhenyu Zhang, Ying Sheng, Tianyi Zhou, Tianlong Chen, Lianmin Zheng, Ruisi Cai, Zhao Song, Yuandong Tian, Christopher Ré, Clark Barrett, Zhangyang Wang, Beidi Chen
Venue / status NeurIPS 2023 — stated by the repo description "[NeurIPS'23] H2O: …". arXiv page has no Comments field; arXiv HTML text shows no venue footnote.
Year 2023
arXiv revisions v1 2023-06-24 ; v2 2023-07-19 ; v3 2023-12-18 (latest)
Subjects cs.LG
Repository https://github.com/FMInference/H2O — exists, public, not a fork, linked from the arXiv abstract. Default branch main, 537 stars, created 2023-06-12.
Latest commit ac75c2a8a9e76832b2a4139b9363373b56336bfb — 2024-06-18 (last push 2024-08-01)
License MIT badge in README only ("License: MIT" shield linking to opensource.org) — there is NO LICENSE file: GitHub API license: null; root listing = .gitignore, Figs, README.md, h2o_flexgen, h2o_hf. Record as "MIT (README badge only; no LICENSE file — legally ambiguous)".
Checkpoints None (training-free eviction policy).

Supported backends / environment:

  • Two code bases: h2o_flexgen (FlexGen fork, OPT, throughput; "PyTorch >= 1.12", pip install -e .) and h2o_hf (HF transformers; pip install git+https://github.com/huggingface/transformers unpinned dev branch, crfm-helm, lm-eval; a patched toxicity_metrics.py must be copied into HELM).
  • h2o_hf provides (a) simulation mode (utils_hh/: attention-mask masking, budgets in ratios of prompt length) and (b) real KV dropping (utils_real_drop/, class H2OKVCache_LayerWise). Both assert batch size 1 (assert attn_weights.shape[0] == 1, .squeeze()). Models in h2o_hf README: LLaMA (huggyllama/llama-7b/13b, --model_arch llama); paper also OPT and GPT-NeoX.
  • CUDA assumed (${GPU-ID} arguments); Apple Silicon / MPS not mentioned. The eviction logic is plain PyTorch (sum, topk, scatter, boolean indexing) → portable.

Core algorithm (from utils_real_drop/modify_llama.py + utils_hh/modify_llama.py + paper Algorithm 1/2):

  1. Score = accumulated attention received. After softmax, score = attn_weights.sum(0).sum(1) → (heads, kv_len): for each key, the sum of attention probabilities over all query rows processed so far (during prefill, over all prompt rows at once). On subsequent steps the previous scores are added to the old columns (scores[:, :-num_new] += previous_scores) — cumulative, per head, per layer. Paper: accumulated beats averaged scores; accumulated scores bias toward older tokens.
  2. Budget. Real-drop: H2OKVCache_LayerWise(hh_size=4, recent_size=512) → cache_size = hh_size + recent_size. Simulation: heavy_budget = int(heavy_ratio · prompt_len), recent_budget = int(recent_ratio · prompt_len), fixed at the first forward.
  3. Eviction (whenever seq_len > cache_size, i.e. every decoding step once full): always keep the last recent_size tokens; among the older tokens take topk(hh_size) by accumulated score, independently per head; keep = cat(topk_idx, recent_idx), build a boolean mask, gather K/V, and keep only the scores of surviving tokens (hh_score = hh_score[mask]). Simulation does the same with a 0/1 attention mask carried to the next step (attention_masks_next), evicting one token per step.
  4. Paper framing: greedy eviction of one token per step maximising a submodular set score; FlexGen note: "for n heavy hitters and n locals, we actually preserve n−1 heavy hitters and n+1 locals after the first iteration".
  5. Experimental budgets: KV budgets of 4 %, 10 %, 20 %, 60 % of prompt length; "H2O (20 %)" = budget evenly split between heavy hitters and recent tokens (README commands: --heavy_ratio 0.1 --recent_ratio 0.1; "local" baseline --heavy_ratio 0 --recent_ratio 0.2).

Original evaluation setting: OPT-6.7B/13B/30B/66B, LLaMA-7B/13B, GPT-NeoX-20B; lm-eval-harness tasks COPA, MathQA, OpenBookQA, PiQA, RTE, Winogrande; HELM XSUM and CNN/Daily Mail; also AlpacaEval/MT-bench mentioned; throughput in FlexGen on T4/A100: up to 29× vs DeepSpeed Zero-Inference, 29× vs HF Accelerate, 3× vs FlexGen (OPT-6.7B/30B, 20 % budget); latency up to 1.9× lower at equal batch.

Stated limitations (Appendix B.2, paraphrased): inference remains expensive because most parameters sit in MLP blocks; heavy hitters appear there too and could drive an offloading policy (future work). From text/code: accumulated scores bias toward older tokens; HF implementation batch-size-1 only; FlexGen implementation "abused a little bit" (n−1/n+1); transformers dependency unpinned.

Question-access class: Query-agnostic policy, but question-informed in effect when the question is in the prefill. The score is the total attention a token has received from every query so far; if the prompt ends with the question, the question tokens' rows contribute to the sum (a small fraction when the context is long — the sum is dominated by context-to-context attention). If compression is performed before the question is appended (our question-blind protocol), H2O is strictly question-blind. H2O therefore sits between StreamingLLM (position-only) and SnapKV (window = question) and should be reported with both protocols.


# 5. StreamingLLM — streamingllm2023

Fetched: https://arxiv.org/abs/2309.17453 · https://arxiv.org/html/2309.17453v4 · https://github.com/mit-han-lab/streaming-llm · raw README.md, streaming_llm/kv_cache.py, streaming_llm/pos_shift/modify_llama.py, streaming_llm/enable_streaming_llm.py, examples/run_streaming_llama.py, setup.py · GitHub API.

Field Verified value
Exact title Efficient Streaming Language Models with Attention Sinks
Authors (as listed on arXiv) Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, Mike Lewis
Venue / status ICLR 2024 — arXiv Comments field "ICLR 2024"; repo description "[ICLR 2024] Efficient Streaming Language Models with Attention Sinks".
Year 2023 (v1 Sep 2023; ICLR 2024)
arXiv revisions v1 2023-09-29 ; v2 2023-11-21 ; v3 2023-12-12 ; v4 2024-04-07 (latest)
Subjects cs.CL; cs.AI
Repository https://github.com/mit-han-lab/streaming-llm — exists, public, not a fork, linked from the arXiv abstract. Default branch main, 7 273 stars, created 2023-09-29.
Latest commit 2e5042606d69933d88fbf909bd77907456b9b4dd — 2024-07-11
License MIT (GitHub API SPDX MIT; LICENSE file in sidebar).
Checkpoints None required (training-free; demo default lmsys/vicuna-13b-v1.3). The sink-token pre-training experiment (160M models) has no released weights on the page.

Supported backends / environment:

  • PyTorch (unpinned pip install torch torchvision torchaudio), Python 3.8 conda env, transformers==4.33.0 pinned, python setup.py develop (package streaming_llm 0.0.1). Demo: CUDA_VISIBLE_DEVICES=0 python examples/run_streaming_llama.py --enable_streaming.
  • Model support (enable_streaming_llm.py): llama (pos-shift patch), gpt_neox (Pythia; pos-shift patch), falcon (pos-shift patch), mpt (ALiBi, no patch; k_seq_dim=3); anything else raises ValueError.
  • Apple Silicon / MPS not mentioned in README/code (the News section cites third-party integrations: HF transformers PR, NVIDIA TensorRT-LLM, HPC-AI SwiftInfer, Intel Extension for Transformers, and "CMU, UW, OctoAI … endless generation on iPhone" — third-party, not this repo). The cache logic is pure tensor slicing → trivially portable.

Core algorithm (from kv_cache.py + pos_shift/modify_llama.py + paper):

  1. StartRecentKVCache(start_size=4, recent_size=512, k_seq_dim=2, v_seq_dim=2); cache_size = start_size + recent_size. Demo script defaults --start_size 4 --recent_size 2000. Paper: 4 attention-sink tokens by default; cache 4 + 2044 = 2048 for Llama-2 PG19 perplexity, 1024 total for Falcon/Pythia/MPT.
  2. __call__: if seq_len <= cache_size return unchanged; else for every layer keep K[:, :, 0:start_size] ⧺ K[:, :, seq_len−recent_size : seq_len] (same for V) — middle tokens dropped. evict_for_space(num_coming) frees room before a new prompt: keeps start_size + recent_size − num_coming most recent. evict_range(start, end) removes an arbitrary span. Policy is purely positional: no attention scores, no content.
  3. Positions "within the cache rather than in the original text" (paper phrasing). Implementation (modify_llama.py): keys are stored un-rotated (past_key_value = (key_states, value_states) before RoPE); at every step the whole cached key tensor is rotated with key_position_ids = arange(kv_seq_len) ("### Shift Pos: key pos is the pos in cache"), and queries are rotated with the supplied position_ids ("query pos is min(cache_size, idx)"). Paper example: cache holding text positions [0,1,2,3,6,7,8] while decoding the 9th token is assigned positions [0,1,2,3,4,5,6,7]. For ALiBi (MPT) a contiguous bias is used instead of a jumping one.
  4. Ablation (paper, Llama-2-13B): window attention alone 0+1024 → PPL 5158.07; 4+1020 → 5.40. Cache sizes 4+508 … 4+4092 tested on Llama-2-7B; larger caches do not monotonically lower perplexity.
  5. Sink-token pre-training: 160M models with/without a learnable sink token prepended to every sample; zero-shot accuracy unchanged (ARC-C 18.6 vs 19.6), streaming stable with the single sink token.

Original evaluation setting: Llama-2-7B/13B/70B, MPT-7B/30B, Falcon-7B/40B, Pythia-2.8B/6.9B/12B; PG19 perplexity on concatenated text up to 4 million tokens; StreamEval; ARC-Easy/Challenge streaming QA; up to 22.2× per-token decoding speedup vs sliding-window recomputation at similar memory.

Stated limitations (paper + README FAQ): "The context window remains unchanged" — cache still bounded by pre-training length (e.g. 4096 for Llama-2); no long-term memory; not suited to long-document QA or summarisation (a book summary would cover only the ending); StreamEval accuracy falls to zero once the query–answer distance exceeds the cache; StreamEval dataset not released (TODO).

Question-access class: Question-blind and content-blind (keeps the first start_size and last recent_size positions regardless of attention or query). It is the canonical question-blind baseline; note that if the question is the most recent text it is trivially retained by the recent window, but nothing about which context tokens survive depends on the question.


# Cross-source notes for WP30

  • Question-access summary: KIVI — not a selection method (uniform lossy precision; question-irrelevant). StreamingLLM — question-blind (position only). H2O — cumulative attention from all queries; question-informed only insofar as the question is part of the prefill (weak); strictly blind if compression precedes the question. SnapKV, PyramidKV — question-aware by construction (last-window observation; the paper authors themselves call the window "instruction tokens").
  • Venues not stated on arXiv/repo: SnapKV (NeurIPS 2024, verified only via proceedings.neurips.cc) and PyramidKV (COLM 2025, verified only via microsoft.com/research). Both arXiv pages have no Comments field; both repos cite the arXiv preprint. KIVI (ICML 2024), H2O (NeurIPS'23, repo description only) and StreamingLLM (ICLR 2024) are stated on arXiv and/or repo.
  • Repository anomalies: (i) the arXiv pages of SnapKV and PyramidKV do not link a repository; (ii) BartsLab/PyramidKV is a dead 0-star fork snapshot (last commit 2024-11-05) — cite Zefan-Cai/KVCache-Factory (renamed 2024-11-28) as the official code; (iii) FMInference/H2O has no LICENSE file (MIT badge only).
  • Apple Silicon: none of the five repositories mentions Apple Silicon/MPS/MLX. KIVI is CUDA/Triton-bound (custom kernels); SnapKV, PyramidKV, H2O (real-drop and simulation) and StreamingLLM are plain PyTorch tensor ops and can be re-implemented on MLX/MPS from the descriptions above. Pinned HF versions diverge widely (4.33.0 / 4.36.2–4.43 / 4.37.0 / 4.44.2 / unpinned dev), so a single environment cannot run the five original code bases unchanged — a unified re-implementation (as KVCache-Factory does on 4.44.2) is justified.
  • Author-list discrepancy to flag: PyramidKV (arXiv v4 lists Yucheng Li; repo BibTeX/Microsoft page list Baobao Chang).
Files · main
Menu

Theme