% GraphKV research presentation; compile with pdflatex.
\documentclass[aspectratio=169,11pt]{beamer}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb,graphicx,booktabs}

\definecolor{AcademicBlue}{RGB}{26,57,86}
\definecolor{AcademicTeal}{RGB}{0,105,112}
\setbeamercolor{structure}{fg=AcademicBlue}
\setbeamercolor{frametitle}{fg=AcademicBlue,bg=white}
\setbeamercolor{title}{fg=AcademicBlue}
\setbeamercolor{alerted text}{fg=AcademicTeal}
\setbeamercolor{block title}{fg=white,bg=AcademicBlue}
\setbeamercolor{block body}{fg=black,bg=AcademicBlue!5}
\setbeamertemplate{navigation symbols}{}
\setbeamertemplate{itemize items}[circle]
\setbeamertemplate{footline}{%
  \hfill\usebeamerfont{page number in head/foot}%
  \insertframenumber\,/\,\inserttotalframenumber\hspace{4mm}\vspace{3mm}}
\setbeamersize{text margin left=8mm,text margin right=8mm}
\setbeamerfont{frametitle}{size=\Large,series=\bfseries}
\setbeamerfont{title}{size=\LARGE,series=\bfseries}
\newcommand{\papersource}[1]{\par\smallskip{\scriptsize\color{gray}#1\par}}

\usepackage{lmodern}
\hypersetup{pdftitle={GraphKV: research paper discussion},pdfauthor={Paper reading notes}}
\begin{document}
\begin{frame}{GraphKV: selection should account for redundancy}
\vspace{2mm}
{\Large\bfseries Breaking the Static Selection Paradigm with\\Graph-Based KV Cache Eviction}\par\medskip
Xuelin Li, Xiangqi Jin, Linfeng Zhang\\
EPIC Lab, Shanghai Jiao Tong University\par\bigskip
\begin{block}{Paper takeaway}
Keep the original importance scores, then discount tokens similar to high-score representatives before choosing the cache.
\end{block}
\medskip
\href{https://arxiv.org/abs/2509.00388v1}{arXiv:2509.00388v1} (30 August 2025)\\
Research group discussion $\cdot$ 25 minutes $\cdot$ 12 November 2026
\end{frame}
\begin{frame}{Paper identity and current artifact status}
\begin{itemize}
\item \textbf{Read version:} arXiv v1; 11 PDF pages, including appendix.
\item \textbf{Published at} \href{https://aclanthology.org/2025.emnlp-main.1112/}{EMNLP 2025, main conference}, pp. 21899--21909.
\item \href{https://github.com/lxlcooper/GraphKV}{\textbf{Official repository: partial code release.}} Evaluation script is public; core propagation implementation is not visible in the inspected tree.
\item All reported experiments below refer to arXiv v1.\\Status checked on 12 November 2026.
\end{itemize}
\begin{block}{Three questions for the discussion}
Why can top-score selection waste cache capacity?\\
What exactly does the graph update?\\
Where is the empirical benefit largest?
\end{block}
\papersource{arXiv v1; official ACL proceedings; repository README and file tree.}
\end{frame}
\begin{frame}{A high-scoring set may repeat the same information}
\begin{itemize}
\item KV eviction keeps a small subset of historical key/value entries.
\item Existing scores estimate token relevance; top-budget selection treats entries independently.
\item Several high-score tokens can have very similar keys, leaving less room for different information.
\end{itemize}

\begin{block}{GraphKV intervention}
Initial scores $\longrightarrow$ similarity-aware discounts $\longrightarrow$ final selection.
\end{block}
No additional model training; the KV vectors themselves are unchanged.
\papersource{Secs. 1--3, PDF pp. 1--4.}
\end{frame}
\begin{frame}{The motivating example shows clustered high-score keys}
\centering\includegraphics[width=.97\linewidth,height=.64\textheight,keepaspectratio]{figures/fig-02-observation.png}
\par\medskip
Rows: layers 1 and 25. Columns: all tokens, original top-10,\\
GraphKV top-10, similarity distribution. Less yellow means less similarity.
\papersource{Fig. 2, PDF p. 3. Llama3-8B, one HotpotQA sample, 128 tokens.}
\end{frame}
\begin{frame}{The graph sits between scoring and final retention}
\centering\includegraphics[width=.97\linewidth,height=.53\textheight,keepaspectratio]{figures/fig-03-main.png}
\begin{itemize}
\item Use an existing method for initial scores and cache budgets.
\item Select source nodes; discount similar neighbors; select final entries.
\end{itemize}
{\small Flow illustration only: the negative score shown in Fig. 3 is inconsistent with multiplicative Eq. (5); see backup.}
\papersource{Fig. 3, PDF p. 4; Eq. (5), PDF p. 5.}
\end{frame}
\begin{frame}{Source count and cache budget are different quantities}
\[
\mathbf K^l,\mathbf V^l\in\mathbb R^{n\times d}
\quad\longrightarrow\quad
\mathbf K_s^l,\mathbf V_s^l\in\mathbb R^{k_l\times d}
\]
\begin{center}
\begin{tabular}{ll}
\toprule
$n$ & Candidate token count\\
$k_l$ (or $B$) & Final cache budget for the layer\\
$k$ & Number of source nodes\\
$m$ & Neighbors per source node\\
$T$ & Number of score-update rounds\\
\bottomrule
\end{tabular}
\end{center}
\medskip
The paper uses a simplified matrix notation here; head axes are omitted.
\papersource{Sec. 4.1, PDF p. 4; Secs. 4.2--4.3, PDF pp. 4--5.}
\end{frame}
\begin{frame}{Only high-score sources compare against all candidates}
\[
O_{\mathrm{source}}=\{o_i\mid s_i\text{ ranks in top-}k\}
\]
\[
e_{ij}=\frac{\langle k_i,k_j\rangle}{\|k_i\|\|k_j\|},\qquad i\in O_{\mathrm{source}},\quad j\ne i
\]
\[
N(o_i)=\{o_j\mid e_{ij}\ge e_{i(m)},\ j\ne i\}
\]
\begin{itemize}
\item $s_i$: an existing importance score; $k_i$: token $i$'s key vector.
\item Compare $k$ sources to $n$ candidates, then keep top-$m$ neighbors.
\item Cosine is symmetric, but only sources send score updates.
\end{itemize}
\papersource{Eqs. (1)--(3), PDF pp. 4--5; Algorithm 1, PDF p. 11.}
\end{frame}
\begin{frame}{Multiple similar sources impose multiplicative discounts}
\[
\boxed{\quad s_j^{(t)}=s_j^{(t-1)}
\prod_{\substack{o_i\in O_{\mathrm{source}}\\o_j\in N(o_i)}}(1-e_{ij})\quad}
\]
\begin{itemize}
\item Start from $s_j^{(0)}=s_j$; choose the top-$k_l$ final scores.
\item Similarity $0.8$ gives a factor of $0.2$ on that edge.
\item Multiple incoming edges compound their discounts.
\item For nonnegative scores, positive similarities suppress scores. Negative similarities would increase them; no clipping rule is specified.
\end{itemize}
\papersource{Sec. 4.3, Eq. (5), PDF p. 5. Explanation follows the explicit product formula.}
\end{frame}
\begin{frame}{A small example makes the selection change visible}
Budget $k_l=2$; source $A$; neighbors $B,C$ with similarities $0.9,0.1$.
\medskip
\begin{center}
\begin{tabular}{lrrl}
\toprule
Token & Initial score & Updated score & Calculation\\
\midrule
$A$ & 1.0 & 1.00 & No incoming discount\\
$B$ & 0.9 & 0.09 & $0.9(1-0.9)$\\
$C$ & 0.7 & 0.63 & $0.7(1-0.1)$\\
$D$ & 0.6 & 0.60 & Outside the neighborhood\\
\bottomrule
\end{tabular}
\end{center}
\begin{block}{Selection changes from $\{A,B\}$ to $\{A,C\}$}
$B$ is highly relevant but mostly overlaps with representative $A$.
\end{block}
\papersource{Teaching example constructed from Eq. (5); not paper experiment data.}
\end{frame}
\begin{frame}{With a fixed graph, rounds strengthen the same discount}
\[
c_j=\prod_{i:\,o_j\in N(o_i)}(1-e_{ij})
\qquad\Longrightarrow\qquad
s_j^{(T)}=s_jc_j^T
\]
\begin{itemize}
\item This is a direct derivation from Eq. (5), for fixed sources and edges.
\item The formal description does not reselect sources each round.
\item $T$ changes score suppression; it does not update key vectors or imply $T$-hop message passing.
\item Sources are not formally forced into the final retained set.
\end{itemize}
\papersource{Reading analysis of Sec. 4.3, Eq. (5), PDF p. 5.}
\end{frame}
\begin{frame}{Near-linear cost assumes a fixed, small source count}
\begin{center}
\begin{tabular}{ll}
\toprule
Operation & Cost with explicit key dimension $d$\\
\midrule
Source-to-candidate similarities & $O(nkd)$\\
$T$ rounds over selected edges & $O(Tkm)$\\
Stored candidate similarities & $O(nk)$\\
Stored pruned edges & $O(km)$\\
\bottomrule
\end{tabular}
\end{center}
\medskip
\begin{itemize}
\item Additional top-$k$/top-$m$ selection work also applies.
\item Paper: $O(nk)\approx O(n)$ for $k\ll n$ and fixed budget.
\item If budget and $k$ grow proportionally with $n$, similarity work grows quadratically in $n$.
\end{itemize}
\papersource{Paper complexity claim: Sec. 1, PDF p. 2. Explicit dimensions and storage: reading analysis.}
\end{frame}
\begin{frame}{Evaluation compares the same scorer before and after}
\begin{itemize}
\item \textbf{Models:} Llama2-7B-Chat, Llama3-8B-Instruct, Mistral-7B-Instruct-v0.2.
\item \textbf{Main table:} 512-token cache setting; KNorm, SnapKV, PyramidKV, each with/without GraphKV; Full KV reference.
\item \textbf{LongBench:} 16 tasks; F1, ROUGE-L, accuracy, edit similarity; all higher is better.
\item \textbf{Needle:} Llama3-8B, input up to about 8K tokens, cache 128.
\item Single NVIDIA H20; beam search reported in Appendix A.1. CAKE and H2O appear in the round ablation.
\end{itemize}
\papersource{Secs. 5--6, PDF pp. 5--7; Appendix A.1 and Table 4, PDF p. 10.}
\end{frame}
\begin{frame}{LongBench gains are consistent in task averages}
\begin{center}
\begin{tabular}{llrrr}
\toprule
Model & Scorer & Base & +GraphKV & $\Delta$\\
\midrule
Llama2-7B & KNorm & 13.03 & 25.20 & +12.17\\
 & SnapKV & 31.95 & 32.35 & +0.40\\
 & PyramidKV & 32.04 & 32.25 & +0.21\\
\midrule
Llama3-8B & KNorm & 20.64 & 29.76 & +9.12\\
 & SnapKV & 39.97 & 40.35 & +0.38\\
 & PyramidKV & 39.58 & 40.09 & +0.51\\
\midrule
Mistral-7B & SnapKV & 40.24 & 40.60 & +0.36\\
 & PyramidKV & 40.16 & 40.50 & +0.34\\
\bottomrule
\end{tabular}
\end{center}
All entries: reported 16-task average, budget 512; $\Delta$ is an absolute score difference. Full averages remain higher.
\papersource{Table 1, PDF p. 6; selected rows. Mistral KNorm: 14.91 to 16.50.}
\end{frame}
\begin{frame}{QA gains and all-task gains use different denominators}
\begin{center}
\begin{tabular}{lrr}
\toprule
Llama3-8B, budget 512 & SnapKV & PyramidKV\\
\midrule
All 16 tasks: relative gain & +0.95\% & +1.29\%\\
Six QA tasks: relative gain & +2.89\% & +2.76\%\\
\bottomrule
\end{tabular}
\end{center}
\medskip
\begin{itemize}
\item The introduction's ``about 3\%'' aligns with the six-QA-task calculation, rather than the all-task average.
\item RepoBench-P: SnapKV 53.87 to 56.10; Full 52.38.
\item LCC: the same scorer falls from 59.50 to 58.42.
\item Individual tasks can exceed Full while the overall average stays below Full.
\end{itemize}
\papersource{Table 1, PDF p. 6. Subset means and relative gains calculated from reported values.}
\end{frame}
\begin{frame}{At cache 128, Needle retrieval gains are larger}
\centering\includegraphics[width=.97\linewidth,height=.57\textheight,keepaspectratio]{figures/fig-04-needle.png}
\par\smallskip
PyramidKV: 90.3\% $\to$ 96.9\% \quad (\textbf{+6.6 percentage points})\\
SnapKV: 87.7\% $\to$ 95.9\% \quad (\textbf{+8.2 percentage points})
\papersource{Fig. 4 and Sec. 5.3, PDF p. 6. Llama3-8B; context up to about 8K.}
\end{frame}
\begin{frame}{A moderate source set works best in the aggregate}
\begin{columns}[c]
\begin{column}{.53\textwidth}\centering\includegraphics[width=1.0\linewidth,height=.70\textheight,keepaspectratio]{figures/fig-05-sources.png}
\end{column}
\begin{column}{.45\textwidth}
\begin{itemize}
\item $k\approx0.3B$ is best in the plotted QA aggregates.
\item Larger source sets affect more tokens and may over-suppress useful scores.
\item Task-specific optima differ: Qasper favors 70\%, HotpotQA favors 10\% in Table 6.
\end{itemize}
\end{column}
\end{columns}
\papersource{Fig. 5(a), PDF p. 7; Table 6, PDF p. 11. Pink and teal use different y-axes.}
\end{frame}
\begin{frame}{Neighbor count also controls the suppression range}
\begin{columns}[c]
\begin{column}{.53\textwidth}\centering\includegraphics[width=1.0\linewidth,height=.70\textheight,keepaspectratio]{figures/fig-05-neighbors.png}
\end{column}
\begin{column}{.45\textwidth}
\begin{itemize}
\item Adaptive $\min(c,L)$ choices generally outperform fixed large neighborhoods.
\item More neighbors do not ensure better coverage after score decay.
\item Figure: $L=\text{input tokens}\times10^{-3}$. Prose calls it query length; units need clarification for reproduction.
\end{itemize}
\end{column}
\end{columns}
\papersource{Fig. 5(b) and Sec. 6.2, PDF p. 7. Preserve the original figure labels.}
\end{frame}
\begin{frame}{The first round helps; more rounds are not monotonic}
\begin{center}
\begin{tabular}{lrrrr}
\toprule
Scorer & $T=0$ & $T=1$ & $T=2$ & $T=3$\\
\midrule
CAKE & 46.49 & 46.86 & 46.47 & 46.76\\
H2O & 40.91 & 41.75 & 42.14 & 42.15\\
PyramidKV & 42.51 & 44.48 & 43.97 & 44.67\\
SnapKV & 42.60 & 43.03 & 43.04 & 43.38\\
\bottomrule
\end{tabular}
\end{center}
\medskip
\begin{itemize}
\item Largest first-round jump: PyramidKV, +1.97 F1.
\item CAKE at $T=2$ is slightly below its no-propagation value, contrary to the prose's blanket claim.
\item These are the plotted task F1 scores, not 16-task averages.
\end{itemize}
\papersource{Fig. 6 and Sec. 6.3, PDF p. 7. Configuration is not fully specified in that paragraph.}
\end{frame}
\begin{frame}{PCA shows which keys receive high scores}
\centering\includegraphics[width=.97\linewidth,height=.58\textheight,keepaspectratio]{figures/fig-07-pca.png}
\begin{itemize}
\item Panels show $T=0,1,2,3$; color and larger markers highlight important/retained entries.
\item The selection spreads across the key distribution. Key coordinates are not updated by GraphKV.
\end{itemize}

\papersource{Fig. 7, PDF p. 8; mechanism from Eq. (5), PDF p. 5.}
\end{frame}
\begin{frame}{Several similarity definitions work; the best varies}
\centering\includegraphics[width=.97\linewidth,height=.51\textheight,keepaspectratio]{figures/fig-08-similarity_edge.png}
\begin{itemize}
\item Five panels: three multi-document QA tasks and two code tasks.
\item Bars: Q--Q, Q--K, K--K, K--V, V--V; dashed line: baseline.
\item K--K is not uniformly best. Avoiding redundancy is the shared design idea.
\end{itemize}

\papersource{Fig. 8 and Sec. 7.1, PDF pp. 7--8. Y-scales and task metrics differ between panels.}
\end{frame}
\begin{frame}{Soft decay preserves a useful importance--diversity balance}
\begin{center}
\begin{tabular}{lrr}
\toprule
Signal & Reported average & $\Delta$ vs. baseline\\
\midrule
No propagation & 38.61 & ---\\
Decay ($-$) & \textbf{39.84} & +1.23\\
Enhancement ($+$) & 38.67 & +0.06\\
Evict neighbors ($-\infty$) & 18.80 & $-19.81$\\
\bottomrule
\end{tabular}
\end{center}
\medskip
\begin{itemize}
\item Cache 128; mean over the ten tasks listed in Table 2.
\item Similar neighbors can still carry useful information: hard eviction fails badly.
\item Decay is best on average, with task-level exceptions.
\end{itemize}
\papersource{Table 2, PDF p. 7; Sec. 7.2, PDF p. 8. Mixed task metrics; higher is better.}
\end{frame}
\begin{frame}{Measured decoding latency can increase or decrease}
\begin{center}
\begin{tabular}{lrrr}
\toprule
Scorer & Base (s) & +GraphKV (s) & Change\\
\midrule
PyramidKV & 5.133 & 5.265 & +2.5\%\\
SnapKV & 5.474 & 4.912 & $-10.2\%$\\
KNorm & 6.031 & 5.095 & $-15.5\%$\\
\bottomrule
\end{tabular}
\end{center}
\medskip
\begin{itemize}
\item QMSum, cache 512; lower is better.
\item A universal ``no latency increase'' claim conflicts with the PyramidKV row.
\item Authors suggest shorter generations may explain speedups. No fixed-output-length timing isolates graph overhead.
\end{itemize}
\papersource{Table 3 and Sec. 7.3, PDF p. 8.}
\end{frame}
\begin{frame}{The main open issues are precise update semantics and tuning}
\begin{itemize}
\item \textbf{Empirical tuning:} source count, neighborhood size and rounds trade relevance against suppression.
\item \textbf{Update semantics:} Eq. (5), Fig. 3 and Algorithm 2 do not fully agree; follow the product equation for this discussion.
\item \textbf{Scale:} reported model evaluation is limited to 7B--8B.
\item \textbf{Efficiency:} graph cost and variable generation length need separate timing.
\end{itemize}
\begin{block}{Research question}
Can a clear set-level objective explain when redundant-looking tokens should still be kept?
\end{block}
\papersource{Sec. 9, PDF p. 9; Eq. (5), Fig. 3, Algorithm 2, Table 3. Last question: reading analysis.}
\end{frame}
\begin{frame}{Take home: discount overlap before spending cache capacity}
\begin{enumerate}
\item \textbf{Mechanism:} keep a useful initial scorer, add similarity-aware score discounts, then select the cache.
\medskip
\item \textbf{Evidence:} modest all-task gains on strong scorers; larger retrieval gains at a very small cache budget.
\medskip
\item \textbf{Practical tradeoff:} soft suppression helps; excessive range, repeated discounts or hard deletion can remove useful information.
\end{enumerate}
\bigskip
\alert{Token importance and contribution to an already represented set are different quantities.}
\papersource{Synthesis of Secs. 4--7, PDF pp. 4--8.}
\end{frame}
\begin{frame}{References and artifact links}
\begin{itemize}
\item Xuelin Li, Xiangqi Jin, Linfeng Zhang.\\
\emph{GraphKV: Breaking the Static Selection Paradigm with Graph-Based KV Cache Eviction}.\\
\href{https://arxiv.org/abs/2509.00388v1}{arXiv:2509.00388v1}, 2025. This is the analyzed version.
\medskip
\item \href{https://aclanthology.org/2025.emnlp-main.1112/}{EMNLP 2025 official proceedings}, pp. 21899--21909.\\
\href{https://doi.org/10.18653/v1/2025.emnlp-main.1112}{DOI: 10.18653/v1/2025.emnlp-main.1112}.
\medskip
\item \href{https://github.com/lxlcooper/GraphKV}{Official repository: lxlcooper/GraphKV}. Partial release as of 12 November 2026: evaluation script visible; core propagation code not found in the inspected tree.
\end{itemize}
\end{frame}
\appendix
\begin{frame}{Backup: the paper has conflicting numerical update examples}
\begin{itemize}
\item Eq. (5): multiply all source discounts, $s_j^{(t)}=s_j^{(t-1)}\prod_i(1-e_{ij})$.
\item Fig. 3: score $0.7$ becomes $-0.07$. With nonnegative initial scores and cosine edges in $[-1,1]$, the product rule cannot produce this negative value.
\item Algorithm 2: inner-loop assignments repeatedly use $s_j^{(t-1)}$; a literal implementation overwrites earlier source updates in the same round.
\item Eq. (4) and Algorithm 2 also contain stray multiplication dots. No extra decay coefficient is defined there.
\end{itemize}
\medskip
\textbf{Interpretation used here:} the explicit multi-source product in Eq. (5).
\papersource{Fig. 3, PDF p. 4; Eqs. (4)--(5), PDF p. 5; Algorithm 2, PDF p. 11.}
\end{frame}
\begin{frame}{Backup: LongBench metrics must retain their task meanings}
\begin{center}
\begin{tabular}{lll}
\toprule
Task group & Datasets & Metric\\
\midrule
Single-doc QA & NarrativeQA, Qasper, MF-en & F1\\
Multi-doc QA & HotpotQA, 2Wiki, MuSiQue & F1\\
Summary & GovReport, QMSum, MultiNews & ROUGE-L\\
Few-shot & TREC / TriviaQA / SAMSum & Acc. / F1 / R-L\\
Synthetic & PCount, PRetrieval & Exact match\\
Code & LCC, RepoBench-P & Edit similarity\\
\bottomrule
\end{tabular}
\end{center}
\medskip
Most datasets: 200 examples; MF-en: 150; each code task: 500.\\
Appendix average lengths are \emph{words} for English/code, not tokenized model input lengths. The mixed-task mean is not pooled accuracy.
\papersource{Table 4, PDF p. 10; metric headings in Table 1, PDF p. 6.}
\end{frame}
\begin{frame}{Backup: the best source fraction differs by dataset}
\begin{center}
\begin{tabular}{lrrrrr}
\toprule
Task & 10\% & 30\% & 50\% & 70\% & 100\%\\
\midrule
Qasper & 24.86 & 24.47 & 24.45 & \textbf{25.20} & 24.53\\
NarrativeQA & \textbf{23.06} & 23.03 & 23.01 & 22.65 & 22.18\\
MFQA-en & 35.45 & 36.34 & 36.31 & 35.27 & \textbf{36.82}\\
HotpotQA & \textbf{43.91} & 43.75 & 43.70 & 43.10 & 42.66\\
2WikiQA & 33.09 & \textbf{34.05} & 34.00 & 33.70 & 33.51\\
MuSiQue & \textbf{20.65} & 20.33 & 20.29 & 20.28 & 20.57\\
\bottomrule
\end{tabular}
\end{center}
\medskip
Budget 512; percentages refer to source count as a fraction of budget.\\
The aggregate preference for 30\% does not imply a per-task optimum.
\papersource{Table 6, PDF p. 11.}
\end{frame}
\begin{frame}{Backup: memory estimates require KV heads and layer count}
\[
\text{KV bytes}=2\,N_{\mathrm{batch}}\,M\,n\,H_{\mathrm{KV}}\,d_{\mathrm{head}}\,b
\]
\begin{itemize}
\item $2$: keys and values; $M$: layer count; $b$: bytes per scalar.
\item Use KV heads, not query heads; they differ with grouped-query attention.
\item Table 5 reports 0.063 GB at cache 512 and 15.625 GB at 128K, but does not clearly specify layer/KV-head accounting behind these values.
\item A fixed cache of 512 is not a universal 10\% retention ratio: input lengths differ by sample and model.
\end{itemize}
\papersource{Table 5, PDF p. 11; 10\% statement in Sec. 5.2, PDF p. 5. Formula: reading analysis.}
\end{frame}
\end{document}