The context window within a transformer provides a form of active memory for
the current task, which can be useful for few-shot learning and conditional
generation, both which depend heavily on previous context tokens. However, as
the context length grows, the computational cost increases quadratically.
Recent works have shown that saving a few initial tokens along with a
fixed-sized sliding window leads to stable streaming generation with linear
complexity in transformer-based Large Language Models (LLMs). However, they
make suboptimal use of the fixed window by naively evicting all tokens
unconditionally from the key-value (KV) cache once they reach the end of the
window, resulting in tokens being forgotten and no longer able to affect
subsequent predictions. To overcome this limitation, we propose a novel
mechanism for storing longer sliding window contexts with the same total cache
size by keeping separate cascading sub-cache buffers whereby each subsequent
buffer conditionally accepts a fraction of the relatively more important tokens
evicted from the previous buffer. Our method results in a dynamic KV cache that
can store tokens from the more distant past than a fixed, static sliding window
approach. Our experiments show improvements of 5.6% on long context generation
(LongBench), 1.2% in streaming perplexity (PG19), and 0.6% in language
understanding (MMLU STEM) using LLMs given the same fixed cache size.
Additionally, we provide an efficient implementation that improves the KV cache
latency from 1.33ms per caching operation to 0.54ms, a 59% speedup over
previous work.

在基于 transformer 的大型语言模型（LLMs）中，通过使用一个保存了初始 token 和固定大小的滑动窗口的键值（KV）缓存，以线性复杂度实现稳定的流式生成，并能够在总缓存大小不变的情况下存储更远过去的 token，取得了 5.6% 在长上下文生成（LongBench）、1.2% 在流式困惑度（PG19）和 0.6% 在语言理解（MMLU STEM）方面的改进。

基于级联 KV 缓存的无需训练的滑动窗口上下文的指数扩展

Training-Free Exponential Extension of Sliding Window Context with  Cascading KV Cache

Dynamic density estimation is ubiquitous in many applications, including
computer vision and signal processing. One popular method to tackle this
problem is the "sliding window" kernel density estimator. There exist various
implementations of this method that use heuristically defined weight sequences
for the observed data. The weight sequence, however, is a key aspect of the
estimator affecting the tracking performance significantly. In this work, we
study the exact mean integrated squared error (MISE) of "sliding window"
Gaussian Kernel Density Estimators for evolving Gaussian densities. We provide
a principled guide for choosing the optimal weight sequence by theoretically
characterizing the exact MISE, which can be formulated as constrained quadratic
programming. We present empirical evidence with synthetic datasets to show that
our weighting scheme indeed improves the tracking performance compared to
heuristic approaches.

通过理论上的特征分类，我们提供了一个原则性指南，以选择最优的权重序列，从而改善卡尔曼滤波器在动态密度估计中的追踪效果。

使用理论最优滑动窗口方法追踪动态高斯密度

Tracking Dynamic Gaussian Density with a Theoretically Optimal Sliding  Window Approach

\emph{Coresets} are important tools to generate concise summaries of massive
datasets for approximate analysis. A coreset is a small subset of points
extracted from the original point set such that certain geometric properties
are preserved with provable guarantees. This paper investigates the problem of
maintaining a coreset to preserve the minimum enclosing ball (MEB) for a
sliding window of points that are continuously updated in a data stream.
Although the problem has been extensively studied in batch and append-only
streaming settings, no efficient sliding-window solution is available yet. In
this work, we first introduce an algorithm, called AOMEB, to build a coreset
for MEB in an append-only stream. AOMEB improves the practical performance of
the state-of-the-art algorithm while having the same approximation ratio.
Furthermore, using AOMEB as a building block, we propose two novel algorithms,
namely SWMEB and SWMEB+, to maintain coresets for MEB over the sliding window
with constant approximation ratios. The proposed algorithms also support
coresets for MEB in a reproducing kernel Hilbert space (RKHS). Finally,
extensive experiments on real-world and synthetic datasets demonstrate that
SWMEB and SWMEB+ achieve speedups of up to four orders of magnitude over the
state-of-the-art batch algorithm while providing coresets for MEB with rather
small errors compared to the optimal ones.

通过引入算法 AOMEB 并以此为基础，提出了两个维护在滑动窗口上具有常数近似比的算法：SWMEB 和 SWMEB +，并支持再生核希尔伯特空间 (RKHS) 中 MEB 的 coreset，实验表明与最佳算法相比，这些算法可以实现快达 4 个数量级的加速，并提供具有较小误差的 MEB coreset。

滑动窗口上最小包围球的核心集

Coresets for Minimum Enclosing Balls over Sliding Windows

Deep Neural Networks now excel at image classification, detection and
segmentation. When used to scan images by means of a sliding window, however,
their high computational complexity can bring even the most powerful hardware
to its knees. We show how dynamic programming can speedup the process by orders
of magnitude, even when max-pooling layers are present.

利用动态规划算法，即使存在最大池化层，也能将深度神经网络在滑动窗口扫描图像时的计算复杂度提高数倍。