spb/wp30_uqo

1# Literature audit — Group 2 (KV-cache compression primary sources)23WP30 — "Cache Compression and Knowledge Transfer in Multi-Agent Systems"4Access 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").56Conventions:7- "arXiv Comments" = the Comments field on the abstract page (the only place arXiv itself states a venue).8- "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).9- 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`.1011---1213## 1. KIVI — `kivi2024`1415**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.1617| Field | Verified value |18|---|---|19| Exact title | KIVI: A Tuning-Free Asymmetric 2bit Quantization for KV Cache |20| Authors (as listed on arXiv) | Zirui Liu, Jiayi Yuan, Hongye Jin, Shaochen Zhong, Zhaozhuo Xu, Vladimir Braverman, Beidi Chen, Xia Hu |21| 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". |22| Year | 2024 (v1 Feb 2024) |23| arXiv revisions | v1 2024-02-05 ; **v2 2024-07-25 (latest)** |24| Subjects | cs.CL; cs.LG; cs.PF |25| 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. |26| Latest commit | `876b4d2d08e3b1d5f70d0969c299d8c7c42ddfb6` — 2025-11-20 |27| License | **MIT** (GitHub API SPDX `MIT`; README: "The code is released under the MIT License.") |28| 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). |2930**Supported backends / environment (verified in repo files):**31- 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`).32- `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).33- `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.34- **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.3536**Core algorithm (implementation-grade):**371. 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`).382. **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.393. **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.404. **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, :]`).415. 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`.426. 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.4344**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.4546**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.4748**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").4950---5152## 2. SnapKV — `snapkv2024`5354**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.5556| Field | Verified value |57|---|---|58| Exact title | SnapKV: LLM Knows What You are Looking for Before Generation |59| Authors (as listed on arXiv) | Yuhong Li, Yingbing Huang, Bowen Yang, Bharat Venkitesh, Acyr Locatelli, Hanchen Ye, Tianle Cai, Patrick Lewis, Deming Chen |60| 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)". |61| Year | 2024 |62| arXiv revisions | v1 2024-04-22 ; **v2 2024-06-17 (latest)** |63| Subjects | cs.CL; cs.AI |64| 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. |65| Latest commit | `e216ddc84c5bd210378cbdbbba12ba02102aa640` — 2025-07-10 |66| License | **Apache-2.0** (GitHub API SPDX `Apache-2.0`; `pyproject.toml` classifier "License :: OSI Approved :: Apache Software License"). |67| 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. |6869**Supported backends / environment:**70- 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.71- 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.7273**Core algorithm (from `snapkv_utils.py`, class `SnapKVCluster.update_kv`, prefill only):**741. 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'`.752. Asserts `key_len == query_len` (prefill). If `q_len < max_capacity_prompt`: return K/V unchanged.763. **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)`.774. **Voting:** `attn_weights_sum = attn[:, :, -w:, :-w].sum(dim=-2)` → `(b, h, L−w)` = attention mass each prefix token receives from the window queries.785. **Clustering/pooling:** `F.avg_pool1d` or `F.max_pool1d` with `kernel_size`, `padding = kernel_size // 2`, `stride = 1` (length-preserving).796. **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.807. 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.818. 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.8283**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.8485**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.8687**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.8889---9091## 3. PyramidKV — `pyramidkv2024`9293**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.9495| Field | Verified value |96|---|---|97| Exact title | PyramidKV: Dynamic KV Cache Compression based on Pyramidal Information Funneling |98| 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. |99| 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)". |100| Year | 2024 (v1 June 2024; v4 May 2025) |101| arXiv revisions | v1 2024-06-04 ; v2 2024-06-16 ; v3 2024-10-03 ; **v4 2025-05-15 (latest)** |102| Subjects | cs.CL; cs.AI |103| 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". |104| 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. |105| License | **MIT** both repos (GitHub API SPDX `MIT`; BartsLab `LICENSE`: "MIT License / Copyright (c) 2024 Zefan Cai"). |106| Checkpoints | None (training-free). |107108**Supported backends / environment:**109- 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).110- 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.111- **Apple Silicon / MPS not mentioned.** Selection code is plain PyTorch (see below) → portable in principle; the runner defaults to `flash_attention_2`.112113**Core algorithm (from `pyramidkv_utils.py`, class `PyramidKVCluster`, prefill only):**1141. 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).1152. **Per-layer budget (arithmetic pyramid), with `base = max_capacity_prompt − window_size`:**116   `min_num = base // beta` (top layer) ; `max_num = 2·base − min_num` (bottom layer) ;117   if `max_num >= q_len − window_size`: `max_num = q_len − window_size`, `min_num = 2·base − max_num` (clamp for short prompts) ;118   `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`.119   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).1203. **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.1214. 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.122123**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.124125**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.126127**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.128129---130131## 4. H2O (Heavy-Hitter Oracle) — `h2o2023`132133**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).134135| Field | Verified value |136|---|---|137| Exact title | H₂O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models (arXiv renders "H$_2$O"; repo spells "H2O") |138| 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 |139| 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. |140| Year | 2023 |141| arXiv revisions | v1 2023-06-24 ; v2 2023-07-19 ; **v3 2023-12-18 (latest)** |142| Subjects | cs.LG |143| 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. |144| Latest commit | `ac75c2a8a9e76832b2a4139b9363373b56336bfb` — 2024-06-18 (last push 2024-08-01) |145| 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)". |146| Checkpoints | None (training-free eviction policy). |147148**Supported backends / environment:**149- 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).150- `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.151- CUDA assumed (`${GPU-ID}` arguments); **Apple Silicon / MPS not mentioned.** The eviction logic is plain PyTorch (`sum`, `topk`, `scatter`, boolean indexing) → portable.152153**Core algorithm (from `utils_real_drop/modify_llama.py` + `utils_hh/modify_llama.py` + paper Algorithm 1/2):**1541. **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.1552. **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.1563. **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.1574. 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".1585. 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`).159160**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**.161162**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.163164**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.165166---167168## 5. StreamingLLM — `streamingllm2023`169170**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.171172| Field | Verified value |173|---|---|174| Exact title | Efficient Streaming Language Models with Attention Sinks |175| Authors (as listed on arXiv) | Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, Mike Lewis |176| Venue / status | **ICLR 2024** — arXiv Comments field "ICLR 2024"; repo description "[ICLR 2024] Efficient Streaming Language Models with Attention Sinks". |177| Year | 2023 (v1 Sep 2023; ICLR 2024) |178| arXiv revisions | v1 2023-09-29 ; v2 2023-11-21 ; v3 2023-12-12 ; **v4 2024-04-07 (latest)** |179| Subjects | cs.CL; cs.AI |180| 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. |181| Latest commit | `2e5042606d69933d88fbf909bd77907456b9b4dd` — 2024-07-11 |182| License | **MIT** (GitHub API SPDX `MIT`; LICENSE file in sidebar). |183| 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. |184185**Supported backends / environment:**186- 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`.187- 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`.188- **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.189190**Core algorithm (from `kv_cache.py` + `pos_shift/modify_llama.py` + paper):**1911. `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.1922. `__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.1933. **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.1944. 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.1955. 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.196197**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.198199**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).200201**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.202203---204205## Cross-source notes for WP30206207- **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").208- **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.209- **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).210- **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.211- **Author-list discrepancy to flag:** PyramidKV (arXiv v4 lists Yucheng Li; repo BibTeX/Microsoft page list Baobao Chang).212