@inproceedings{duong-etal-2026-forget,
title = "Forget Without Compromise: Nexus Sampling for Streaming {KV}-Cache Eviction Under Fixed Budgets",
author = "Duong, Duc and
Le, Hoang Anh Duy and
Xie, Jianwen and
Shrivastava, Anshumali and
Xu, Zhaozhuo",
editor = "Lee, Hung-Yi and
Dev, Sunipa and
Li, Jessy and
Elliott, Desmond",
booktitle = "Proceedings of the 2026 Conference on Empirical Methods in Natural Language Processing",
month = oct,
year = "2026",
address = "Budapest, Hungary",
publisher = "Association for Computational Linguistics",
url = "https://aclanthology.org/2026.emnlp-main.1642/",
pages = "37313--37334",
ISBN = "979-8-89176-459-0",
abstract = "Long-context and agentic LLM workloads push the KV cache past any fixed memory budget, forcing the inference stack to permanently *evict* tokens at every step of a continuous-inference stream. Existing methods all share the same template: a per-step direct-attention score followed by *deterministic top-$K$* selection, which converts a single below-cutoff step into an irreversible verdict and permanently erases any subtly important token that direct attention cannot single out from noise. To address this challenge, we propose **Nexus Sampling**, a training-free eviction method that pairs *Nexus scoring*, an iterative walk over direct attention that surfaces bridge tokens, with *weighted reservoir sampling*, which retains tokens with inclusion probability in place of deterministic top-$K$. Theoretically, we show that Nexus Sampling dominates deterministic top-$K$ in long-run survival of subtly important tokens. Empirically, at 80{\%} KV cache eviction, Nexus Sampling matches dense attention within $\sim$1 point on LongBench while outperforming top-$K$ baselines on retrieval-heavy tasks, with up to $10\times$ smaller per-sequence cache memory. Our code is available at {\ensuremath{<}}https://github.com/duongduc388222/NexusSampling{\ensuremath{>}}."
}<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="duong-etal-2026-forget">
<titleInfo>
<title>Forget Without Compromise: Nexus Sampling for Streaming KV-Cache Eviction Under Fixed Budgets</title>
</titleInfo>
<name type="personal">
<namePart type="given">Duc</namePart>
<namePart type="family">Duong</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Hoang</namePart>
<namePart type="given">Anh</namePart>
<namePart type="given">Duy</namePart>
<namePart type="family">Le</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Jianwen</namePart>
<namePart type="family">Xie</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Anshumali</namePart>
<namePart type="family">Shrivastava</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Zhaozhuo</namePart>
<namePart type="family">Xu</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<originInfo>
<dateIssued>2026-10</dateIssued>
</originInfo>
<typeOfResource>text</typeOfResource>
<relatedItem type="host">
<titleInfo>
<title>Proceedings of the 2026 Conference on Empirical Methods in Natural Language Processing</title>
</titleInfo>
<name type="personal">
<namePart type="given">Hung-Yi</namePart>
<namePart type="family">Lee</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Sunipa</namePart>
<namePart type="family">Dev</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Jessy</namePart>
<namePart type="family">Li</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Desmond</namePart>
<namePart type="family">Elliott</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<originInfo>
<publisher>Association for Computational Linguistics</publisher>
<place>
<placeTerm type="text">Budapest, Hungary</placeTerm>
</place>
</originInfo>
<genre authority="marcgt">conference publication</genre>
<identifier type="isbn">979-8-89176-459-0</identifier>
</relatedItem>
<abstract>Long-context and agentic LLM workloads push the KV cache past any fixed memory budget, forcing the inference stack to permanently *evict* tokens at every step of a continuous-inference stream. Existing methods all share the same template: a per-step direct-attention score followed by *deterministic top-K* selection, which converts a single below-cutoff step into an irreversible verdict and permanently erases any subtly important token that direct attention cannot single out from noise. To address this challenge, we propose **Nexus Sampling**, a training-free eviction method that pairs *Nexus scoring*, an iterative walk over direct attention that surfaces bridge tokens, with *weighted reservoir sampling*, which retains tokens with inclusion probability in place of deterministic top-K. Theoretically, we show that Nexus Sampling dominates deterministic top-K in long-run survival of subtly important tokens. Empirically, at 80% KV cache eviction, Nexus Sampling matches dense attention within \sim1 point on LongBench while outperforming top-K baselines on retrieval-heavy tasks, with up to 10\times smaller per-sequence cache memory. Our code is available at \ensuremath<https://github.com/duongduc388222/NexusSampling\ensuremath>.</abstract>
<identifier type="citekey">duong-etal-2026-forget</identifier>
<location>
<url>https://aclanthology.org/2026.emnlp-main.1642/</url>
</location>
<part>
<date>2026-10</date>
<extent unit="page">
<start>37313</start>
<end>37334</end>
</extent>
</part>
</mods>
</modsCollection>
%0 Conference Proceedings
%T Forget Without Compromise: Nexus Sampling for Streaming KV-Cache Eviction Under Fixed Budgets
%A Duong, Duc
%A Le, Hoang Anh Duy
%A Xie, Jianwen
%A Shrivastava, Anshumali
%A Xu, Zhaozhuo
%Y Lee, Hung-Yi
%Y Dev, Sunipa
%Y Li, Jessy
%Y Elliott, Desmond
%S Proceedings of the 2026 Conference on Empirical Methods in Natural Language Processing
%D 2026
%8 October
%I Association for Computational Linguistics
%C Budapest, Hungary
%@ 979-8-89176-459-0
%F duong-etal-2026-forget
%X Long-context and agentic LLM workloads push the KV cache past any fixed memory budget, forcing the inference stack to permanently *evict* tokens at every step of a continuous-inference stream. Existing methods all share the same template: a per-step direct-attention score followed by *deterministic top-K* selection, which converts a single below-cutoff step into an irreversible verdict and permanently erases any subtly important token that direct attention cannot single out from noise. To address this challenge, we propose **Nexus Sampling**, a training-free eviction method that pairs *Nexus scoring*, an iterative walk over direct attention that surfaces bridge tokens, with *weighted reservoir sampling*, which retains tokens with inclusion probability in place of deterministic top-K. Theoretically, we show that Nexus Sampling dominates deterministic top-K in long-run survival of subtly important tokens. Empirically, at 80% KV cache eviction, Nexus Sampling matches dense attention within \sim1 point on LongBench while outperforming top-K baselines on retrieval-heavy tasks, with up to 10\times smaller per-sequence cache memory. Our code is available at \ensuremath<https://github.com/duongduc388222/NexusSampling\ensuremath>.
%U https://aclanthology.org/2026.emnlp-main.1642/
%P 37313-37334
Markdown (Informal)
[Forget Without Compromise: Nexus Sampling for Streaming KV-Cache Eviction Under Fixed Budgets](https://aclanthology.org/2026.emnlp-main.1642/) (Duong et al., EMNLP 2026)
ACL