Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time

Zichang LiuJue WangTri DaoTianyi ZhouBinhang YuanZhao SongAnshumali ShrivastavaCe ZhangYuandong TianChristopher Ré

article2023ICML311 citationsOutstanding Paper Award

Introduces DejaVu, a hardware-aware system that dynamically predicts input-dependent contextual sparsity to cut the inference latency of 175-billion-parameter language models by more than half without retraining or sacrificing accuracy.

Listen

Large language models deliver state-of-the-art performance across diverse tasks, but their massive parameter scale creates substantial computational and latency bottlenecks during inference. In latency-sensitive generation settings, loading billions of parameters from memory dominates runtime. Prior model compression techniques—such as static weight pruning, task-specific pruning, or zero-shot unstructured pruning—often necessitate expensive retraining, degrade in-context learning capabilities, or fail to produce actual wall-clock speedups on modern hardware.

The article evaluates whether pre-trained large language models exhibit dynamic, input-dependent contextual sparsity that can be accurately predicted and exploited to accelerate inference without modifying model weights or degrading accuracy. To leverage this, the authors develop DEJAVU, an inference acceleration framework featuring lightweight sparsity predictors, asynchronous cross-layer execution, and hardware-aware graphics processing unit implementations.

The investigation combines empirical evaluations across multiple open-source models—primarily OPT models ranging up to 175 billion parameters, as well as the BLOOM architecture—with theoretical analyses of residual connections and self-attention clustering dynamics. The researchers evaluated model accuracy on standard language modeling benchmarks (WikiText and C4) and seven zero-shot and few-shot downstream reasoning tasks using evaluation suites on eight NVIDIA A100 graphics processing units.

The article demonstrates that contextual sparsity naturally exists at high rates in dense models: on average, individual inputs activate only about 20% of attention heads and 5% of multilayer perceptron parameters, yielding an overall structured parameter reduction of approximately 85%. Because token representations evolve slowly across layers due to strong residual connections, small neural network predictors can asynchronously forecast which parameters are required for upcoming layers, eliminating sequential prediction overhead. In end-to-end evaluations on the 175-billion-parameter OPT model, DEJAVU achieved over a 2× latency speedup compared to NVIDIA FasterTransformer and up to a 6× speedup compared to Hugging Face implementations at batch size 1, maintaining full baseline accuracy up to 75% sparsity while demonstrating strong compatibility with 4-bit weight quantization.

These findings indicate that large models do not require full dense activation during inference, providing a viable path to substantially lower serving costs and improve response times for interactive artificial intelligence services. By achieving wall-clock acceleration without retraining or losing in-context reasoning abilities, this approach overcomes the primary practical hurdles that previously limited dynamic model pruning on modern accelerator hardware.

Organizations serving large language models should evaluate the integration of contextual sparsity systems into their inference pipelines to reduce operational costs and latency. Systems teams should adopt fused GPU memory kernels and asynchronous prediction architectures to capitalize on hardware memory hierarchies. Future efforts should focus on deploying contextual sparsity in high-throughput, large-batch environments and exploring model depth optimizations such as dynamic layer skipping.

The primary limitations include lower sparsity savings under large batch sizes—where the union of activated parameters across disparate queries increases—and the reliance on custom hardware kernels optimized for memory bandwidth. Nevertheless, the findings offer high empirical and theoretical confidence for small-batch, latency-critical inference workloads.

Adobe Carnegie Mellon University ETH Zurich Meta Rice University Stanford University University of California, San Diego Zhejiang University ai applications inference language model contextual sparsity Deja Vu LLM inference

arXiv: 2310.17157 FMInference/DejaVu

Paper: MoEfication: Transformer Feed-forward Layers are Mixtures of Experts, Zhengyan Zhang et al. (2022). It demonstrates that transformer feed-forward layers exhibit naturally sparse, input-dependent activation patterns that can be routed dynamically, providing the empirical foundation for DejaVu's contextual sparsity.
Paper: DeepSpeed Inference: Enabling Efficient Inference of Transformer Models at Unprecedented Scale, Reza Yazdani Aminabadi et al. (2022). It establishes key high-performance system and kernel optimization principles for large-scale transformer inference that DejaVu directly compares against and builds upon.
Paper: Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsity, William Fedus et al. (2022). It introduces foundational concepts of dynamic sparse routing per token to reduce active computation during transformer execution.
Paper: Are Sixteen Heads Really Better than One?, Paul Michel et al. (2019). It provides foundational empirical evidence that individual attention heads can be dynamically bypassed at inference time with minimal performance loss.
Paper: FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness, Tri Dao et al. (2022). It introduces IO-aware hardware execution principles that underpin modern low-latency transformer inference and block-level sparsity optimizations.
Paper: SparseGPT: Massive Language Models Can Be Accurately Pruned in One-Shot, Elias Frantar et al. (2023). It explores post-training sparsity at the scale of 175B parameter models, framing the challenge of achieving wall-clock speedup without retraining that DejaVu tackles.

Paper: Mixture-of-Depths: Dynamically allocating compute in transformer-based language models, David Raposo et al. (2024). It extends dynamic conditional computation from layer-internal MLP/attention subsets to dynamic layer skipping and depth routing per token.
Paper: Kascade: A Practical Sparse Attention Method for Long-Context LLM Inference, Dhruv Deshmukh et al. (2025). It builds on dynamic inference-time sparsity by predicting and reusing anchor sparse attention patterns across transformer layers without retraining.
Paper: Language Models Can Control Their Own Attention, Namgyu Ho et al. (2026). It advances dynamic inference sparsity by letting models natively control their attention masks and KV-cache loads during decoding.
Paper: LongCat Sparse Attention: Taming the Lightning via Streaming-aware Hierarchical Cross-Layer Indexing, Wen Zan et al. (2026). It extends hardware-aligned dynamic sparse attention to massive long-context models using hierarchical cross-layer indexing.
Paper: Native Sparse Attention: Hardware-Aligned and Natively Trainable Sparse Attention, Jingyang Yuan et al. (2025). It explores natively trainable, hardware-aligned sparse attention to achieve high inference efficiency across extended contexts.
Paper: Sparser, Faster, Lighter Transformer Language Models, Edoardo Cetin et al. (2026). It builds upon high activation sparsity in feed-forward layers with custom GPU CUDA kernels to maximize wall-clock inference speedups.

Cover for Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time

Abstract

Large language models (LLMs) with hundreds of billions of parameters have sparked a new wave of exciting AI applications. However, they are computationally expensive at inference time. Sparsity is a natural approach to reduce this cost, but existing methods either require costly retraining, have to forgo LLM's in-context learning ability, or do not yield wall-clock time speedup on modern hardware. We hypothesize that contextual sparsity, which are small, input-dependent sets of attention heads and MLP parameters that yield approximately the same output as the dense model for a given input, can address these issues. We show that contextual sparsity exists, that it can be accurately predicted, and that we can exploit it to speed up LLM inference in wall-clock time without compromising LLM's quality or in-context learning ability. Based on these insights, we propose DejaVu, a system that uses a low-cost algorithm to predict contextual sparsity on the fly given inputs to each layer, along with an asynchronous and hardware-aware implementation that speeds up LLM inference. We validate that DejaVu can reduce the inference latency of OPT-175B by over 2X compared to the state-of-the-art FasterTransformer, and over 6X compared to the widely used Hugging Face implementation, without compromising model quality. The code is available at this https URL.

Topics

ai applications inference language model large language models probabilistic inference clock signal reference clock facial images multilayer perceptrons

Keywords

contextual sparsity Deja Vu LLM inference sparsity prediction locality-sensitive hashing dynamic sparsity structured sparsity KV cache inference latency

1 Introduction
2 Related Work and Problem Formulation
2.1 Quantization, Pruning, Distillation for Inference
2.2 LLM Inference Latency Breakdown
2.3 Problem Formulation
3 Pre-trained LLMs are Contextually Sparse
3.1 Contextual Sparsity Hypothesis
3.2 Token Clustering in Attention Layers
3.3 Slowly Changing Embeddings across Layers
4 dejavu
4.1 Contextual Sparsity Prediction in MLP Blocks
4.2 Contextual Sparsity Prediction in Attention Blocks
4.3 Reducing Overhead with Asynchronous Execution
4.4 Hardware-efficient Implementation
5 Empirical Evaluation
5.1 End-to-End Result
5.2 Ablation Results
6 Conclusion
References
A Related Work
B Additional Observation on Slowly Changing Observation
C Additional Experiment Detail
C.1 Large Batch Size
C.2 Near Neighbor classifier
C.3 Future Possibility: Skipping Layer
D Implementation Details
E Benchmarking Sparse MLP and Sparse Attention
F Notations and Basic Definitions
G Subspace Embeddings and Norm Preserving
G.1 Soft-Max Functions
G.2 ReLU Functions
G.3 Folded Gaussian Distribution
G.4 ℓ2\ell_{2} subspace embedding
G.5 ℓ1\ell_{1} subspace embedding
G.6 Random Matrices
H Distances, Angles, and Inner Product
H.1 Angle is close
I Function Approximations
I.1 Function Approximations for Two Operators
I.2 Function Approximations for Four Operators
J Nearest Neighbor Search Data Structure
J.1 𝖫𝖲𝖧\mathsf{LSH} and 𝖬𝖺𝗑𝖨𝖯\mathsf{MaxIP}
J.2 Connections
J.3 Efficient Transformations
J.4 Data Structures
K Self-attention layer as a clustering algorithm
L The role of self-attention
L.1 The capacity of embedding layer
L.2 The role of self-attention
L.3 How the clustering happens through self-attention?
L.4 Multiple embeddings
M Link self-attention with generative models.

Knowls

Knowl 1 — Contextual Sparsity in Transformer Models
definition
Contextual sparsity refers to the existence of dynamic, input-dependent subsets of Multi-Head Attention (MHA) heads and Multi-Layer Perceptron (MLP) neurons that produce an output approximately equal to the full dense model computation for a specific input during autoregressive inference.

For an input hidden state $y \in \mathbb{R}^{1 \times d}$ at the current token generation step and an MLP block with weight matrices $W^1, W^2 \in \mathbb{R}^{d \times 4d}$ where column $i$ denotes $W^1_i, W^2_i \in \mathbb{R}^{d \times 1}$ , sparsified MLP computation with an active neuron index set $S_M \subseteq [4d]$ is defined as:

$\text{MLP}_{S_M}(y) = \sigma\left(y W^1_{S_M}\right) \left(W^2_{S_M}\right)^\top$

where $\sigma$ is an activation function (e.g., ReLU or GeLU), $W^1_{S_M} \in \mathbb{R}^{d \times |S_M|}$ , and $W^2_{S_M} \in \mathbb{R}^{d \times |S_M|}$ .

For Multi-Head Attention with $h$ heads, let $X \in \mathbb{R}^{n \times d}$ denote the embeddings of all $n$ prompt and previously generated tokens, and let $y \in \mathbb{R}^{1 \times d}$ denote the current query token. For each head $i \in [h]$ , let $W^Q_i, W^K_i, W^V_i \in \mathbb{R}^{d \times d_h}$ and $W^O_i \in \mathbb{R}^{d_h \times d}$ . Sparsified Multi-Head Attention with an active head index subset $S_A \subseteq [h]$ is defined as:

$\text{MHA}_{S_A}(y) = \sum_{i \in S_A} H_i(y) W^O_i$

where $H_i(y) \in \mathbb{R}^{1 \times d_h}$ and normalizer $D_i(y) \in \mathbb{R}$ are given by:

$H_i(y) := D_i(y)^{-1} \exp\left(y W^Q_i (W^K_i)^\top X^\top\right) X W^V_i$

$D_i(y) := \exp\left(y W^Q_i (W^K_i)^\top X^\top\right) \mathbf{1}_n$

Given a computational budget, contextual sparsification selects $S_M$ and $S_A$ to minimize the approximation error with respect to the dense computation.
Knowl 2 — Asynchronous Lookahead Sparsity Prediction
model/method
In standard sequential execution of a Transformer layer $l$ , computing sparsity predictors $\text{SP}^l_A$ (for attention heads) and $\text{SP}^l_M$ (for MLP neurons) on-the-fly introduces latency overheads that serialize with block computation:

$S^l_A \leftarrow \text{SP}^l_A(y_l), \quad \tilde{y}_l \leftarrow \text{MHA}^l_{S^l_A}(y_l), \quad S^l_M \leftarrow \text{SP}^l_M(\tilde{y}_l), \quad \hat{y}_l \leftarrow \text{MLP}^l_{S^l_M}( ilde{y}_l)$

where $y_l \in \mathbb{R}^{1 \times d}$ is the input to layer $l$ , $\tilde{y}_l$ is the output of the attention block, and $\hat{y}_l$ is the output of the MLP block.

To remove predictor latency from the critical path, an asynchronous lookahead predictor leverages the high cosine similarity between hidden representations across consecutive layers. The lookahead predictor computes the active sets for layer $l+1$ concurrently with the core computation of layer $l$ :

$\tilde{y}_l \leftarrow \text{MHA}^l_{S^l_A}(y_l), \quad \hat{y}_l \leftarrow \text{MLP}^l_{S^l_M}(\tilde{y}_l)$

$S^{l+1}_A \leftarrow \text{SP}^{l+1}_A(y_l), \quad S^{l+1}_M \leftarrow \text{SP}^{l+1}_M(y_l)$

Because $S^{l+1}_A$ and $S^{l+1}_M$ are evaluated asynchronously in parallel with $\text{MHA}^l$ and $\text{MLP}^l$ using the incoming activation $y_l$ , the prediction overhead is hidden behind memory I/O and compute operations of the current layer.
Knowl 3 — Hardware-Aware Sparse Kernel Fusion and Memory Coalescing
model/method
Small-batch autoregressive token generation is memory-bandwidth bound because of low arithmetic intensity. Standard sparse implementations that first gather or index active columns $W_{S_M}$ before computing matrix multiplication incur a $3\times$ I/O amplification (reading the sub-matrix, writing it contiguously, and re-reading it for the multiplication).

To eliminate this overhead, two GPU-level optimizations are used:
1. Kernel Fusion: Custom Triton kernels fuse the sparse dynamic indexing and vector multiplication into a single pass. The kernel reads the required sliced rows/columns of the weight matrix directly from global memory into registers/SRAM, multiplies them with the input activation vector $y$ , and writes back the output vector.
2. Memory Coalescing: Modern GPUs load memory in 128-byte transactions. In standard dense MLP implementations, linear layers are stored as $(W^1)^\top$ and $W^2$ in row-major layout. Loading non-contiguous rows corresponding to active index set $S_M$ from $W^2$ leads to uncoalesced memory access. To ensure full 128-byte coalesced loads, the second linear matrix $W^2$ and the attention output projection $W^O$ are transposed and stored in column-major layout (i.e., $(W^2)^\top$ and $(W^O)^\top$ in row-major memory) at model loading time.
Knowl 4 — Sparse Predictor Training via MaxIP Classification
algorithm
Contextual sparsity prediction is formulated as an approximate Maximum Inner Product Search (MaxIP) problem. To avoid the CPU overhead and search latency of graph-based nearest neighbor methods (such as HNSW or FAISS), a small 2-layer fully connected neural network classifier is trained for each layer's MLP block and Attention block.
Input: Pre-trained LLM block parameters $M$ , activation dataset at block input $M = \{x_i\}_{i=1}^N$ , activation norm threshold $t$ , predictor model $\text{SP}$ , loss function $\mathcal{L}$
Output: Trained sparse predictor $\text{SP}$
$P_+ \leftarrow \emptyset$
$P_- \leftarrow \emptyset$
for $i = 1$ to $N$ do
    for each component $m_r \in M$ do
        if $m_r(x_i) \ge t$ then
             $P_+ \leftarrow P_+ \cup \{(x_i, m_r)\}$
        else
             $P_- \leftarrow P_- \cup \{(x_i, m_r)\}$
        end if
    end for
end for
$\text{SP} \leftarrow \text{Train}(\text{SP}, P_+, P_-, \mathcal{L})$
return $\text{SP}$
For MLP prediction, components $m_r$ correspond to individual neurons of the first linear layer $W^1$ . For attention prediction, components $m_r$ correspond to individual attention heads $H_i$ . Training data is generated from 500 token sequences from training data without requiring LLM parameter updates.
Knowl 5 — Deferred Key-Value Cache Computation for Sparsified Attention
model/method
When attention heads are sparsely selected at each decoding step, non-selected heads do not compute or populate Key and Value states in the KV cache for the current token. If a previously bypassed head $i$ is selected at a subsequent token generation step $t'$ , the standard KV cache for head $i$ lacks historical key and value entries.

To resolve missing KV entries without dense forward passes:
1. At step $t$ , for any non-selected head $i \notin S_A$ , the system retains a copy of the input token hidden state $y_t \in \mathbb{R}^{1 \times d}$ .
2. When head $i$ is subsequently selected at step $t'$ , the missing keys $K_i$ and values $V_i$ for past uncomputed tokens are materialized on the fly from the stored token embeddings $y$ using $W^K_i$ and $W^V_i$ .
Because token generation is bottlenecked by the memory I/O of loading giant model weight matrices rather than arithmetic compute, caching compact $d$ -dimensional hidden states and performing deferred matrix multiplications on demand introduces negligible runtime cost.
Knowl 6 — Slowly Changing Embeddings Across Transformer Layers
empirical result
Across OPT model sizes ranging from 125M to 175B parameters, the cosine similarity between hidden representations $X_l$ and $X_{l+1}$ at consecutive layers exceeds $0.95$ , reaching approximately $0.99$ for OPT-175B for all layers $l \ge 2$ . Across larger layer gaps $l$ to $l+n$ (for $n \in \{2, 4, 8\}$ ), median cosine similarity remains high throughout the network depth.

This behavior is driven by the residual architecture $X' = X + F(X)$ , where $F(X)$ represents the Multi-Head Attention or MLP sub-block. In empirical measurements across layers of OPT-175B, the $\ell_2$ norm of the residual stream $\|X\|_2$ is significantly larger than the sub-block perturbation $\|F(X)\|_2$ (e.g., $\|X\|_2 \approx 1000\text{--}2000$ whereas $\|F(X)\|_2 \approx 50\text{--}150$ after layer 1), confirming that layer representations evolve slowly.
Knowl 7 — Theoretical Guarantee for Cross-Layer MaxIP Sparsity Prediction
theoretical result
Let $y_l, y_{l-1} \in \mathbb{S}^{d-1}$ be unit-norm token embedding inputs at layers $l$ and $l-1$ , respectively, satisfying $\|y_l - y_{l-1}\|_2 \le \epsilon$ for $\epsilon \in (0, 0.1)$ . Let $Y \subset \mathbb{S}^{d-1}$ be a set of $n$ candidate weight parameter vectors.

For approximation parameters $c \in (0, 1)$ and threshold $\tau \in (0, 1)$ , if $\max_{y \in Y} \langle y_{l-1}, y \rangle \ge \tau$ and $\epsilon < 0.01 c \tau$ , then any vector $z \in Y$ that satisfies the $(c, \tau)$ -MaxIP condition at layer $l-1$ :

$\langle y_{l-1}, z \rangle \ge c \cdot \max_{y \in Y} \langle y_{l-1}, y \rangle$

also satisfies a $(0.99c, \tau)$ -MaxIP condition at layer $l$ :

$\langle y_l, z \rangle \ge 0.99c \cdot \max_{y \in Y} \langle y_l, y \rangle$

This guarantees that nearest-neighbor sparsity predictors evaluated on the prior layer's input $y_{l-1}$ maintain approximation bounds for layer $l$ .
Knowl 8 — End-to-End Latency and Downstream Quality of DejaVu on OPT-175B
empirical result
Evaluated on 8 $\times$ NVIDIA A100 80GB GPUs with NVLink in FP16 at batch size 1 across prompt lengths 128, 256, 512, and 1024, the DejaVu system reduces token generation latency of OPT-175B by $1.8\times$ to $2.0\times$ compared to FasterTransformer and by $4.8\times$ to $6.0\times$ compared to the Hugging Face implementation.

Under an overall model contextual sparsity of 75% (85% MLP neuron sparsity and 50% attention head sparsity), DejaVu incurs no accuracy loss across zero-shot and 5-shot benchmarks (including CB, COPA, Lambada, OpenBookQA, PIQA, RTE, and Winogrande) and maintains perplexity on WikiText and C4 relative to dense OPT-175B.

Knowl 9 — Ablation of Separated MLP and Attention Contextual Sparsity on OPT-175B

data/table

Applying contextual sparsity independently to the MLP blocks (at 85% sparsity) or the Attention blocks (at 50% sparsity) in OPT-175B preserves baseline accuracy across zero-shot downstream tasks and language modeling perplexity.

Model	CB	COPA	Lambada	OpenBookQA	PIQA	RTE	Winogrande	Wikitext (ppl)	C4 (ppl)
OPT-175B (Dense)	0.3523	0.86	0.7584	0.4460	0.8096	0.6029	0.7261	10.8221	7.7224
DEJAVU-MLP-OPT-175B (85% MLP)	0.3544	0.85	0.7619	0.4460	0.8096	0.6065	0.7206	10.7988	7.7393
DEJAVU-Attention-OPT-175B (50% Attn)	0.3544	0.86	0.7586	0.4460	0.8063	0.5921	0.7245	10.8696	7.7393

The data demonstrates that individual MLP blocks tolerate up to 85% neuron pruning per token and attention blocks tolerate 50% head pruning per token during inference without degrading generation quality.

Knowl 10 — Compatibility of Contextual Sparsity with 4-Bit Weight Quantization

data/table

Contextual sparsity (75% overall sparsity via DejaVu) is orthogonal to and composable with post-training weight quantization (W4A16, 4-bit weight and 16-bit activation) on OPT-175B. Evaluating zero-shot accuracy across benchmarks reveals that combining both techniques does not compound approximation errors.

Model Setting	CB	COPA	OpenBookQA	PIQA	RTE	Winogrande	Lambada
OPT-175B	0.352	0.86	0.446	0.809	0.602	0.726	0.758
DejaVu-OPT-175B (75% Sparse)	0.402	0.85	0.450	0.802	0.592	0.726	0.753
OPT-175B + W4A16	0.356	0.85	0.440	0.806	0.574	0.714	0.757
DejaVu-OPT-175B + W4A16	0.365	0.86	0.452	0.805	0.592	0.726	0.754

The combination of 4-bit quantization and 75% contextual sparsity achieves performance matching or exceeding the baseline dense FP16 model on every downstream zero-shot benchmark.

Knowl 11 — Self-Attention as Mean-Shift Clustering of Token Embeddings
theoretical result
Single-head self-attention without output projection maps an input query $y$ with past token keys and values $X = [x_1, \dots, x_n]^\top \in \mathbb{R}^{n \times d}$ to an updated representation $\tilde{y} = m(y) W^V$ , where:

$m(y) = \frac{\sum_{j=1}^n K(x_j, y) x_j}{\sum_{j=1}^n K(x_j, y)}, \quad K(x_j, y) = \exp\left(y W^Q (W^K)^\top x_j\right)$

With residual connection and normalization, the next-layer representation $\hat{y} = \text{Normalize}(y + m(y))$ has a fixed point $y = \gamma m(y)$ for scalar $\gamma$ . This matches one iteration of kernel mean-shift clustering, which shifts token embeddings toward local density modes in the projection space defined by $W^Q (W^K)^\top$ .

Because attention heads cluster token representations in learned subspaces, individual heads specialize into:
1. Uniform mixing heads, which disperse attention evenly across all tokens and contribute negligibly to specific contextual interactions (and exhibit small output norms).
2. Heavy-hitter heads, which attend strongly to specific token clusters and produce high output norms.
Sparsification by discarding heads with low output norms selectively prunes uniform mixing heads without degrading task performance.
Knowl 12 — Sublinear Scaling of Union Contextual Sparsity with Batch Size
empirical result
When running batched inference with batch size $B > 1$ , GPU execution of sparse matrix operations requires executing the union of all active neurons and heads across the batch. Union contextual sparsity is defined as:

$\text{Union Contextual Sparsity} = 1.0 - \frac{|\bigcup_{b=1}^B S^{(b)}|}{\text{Total Neurons or Heads}}$

Empirical measurements on OPT-175B for batch sizes $B \in \{2, 4, 8, 16, 32\}$ show that the number of distinct activated MLP neurons and Attention heads grows sub-linearly with batch size. This demonstrates that parameter activation across different input sequences follows a power-law distribution rather than a uniform distribution, allowing union sparsity (and speedup potential) to persist at larger batch sizes.

Coverage note — Omitted the preliminary exploratory experiments on depth sparsification / layer skipping (Appendix C.3) and standard Locality-Sensitive Hashing (LSH) theoretical data structure constructions (Appendix J) as they represent preliminary investigations or established external algorithmic machinery rather than the core DejaVu contextual sparsity system.

References

1.Winogrande: An adversarial winograd schema challenge at scale. 2019.
2.Allen-Zhu, Z. and Li, Y. What can resnet learn efficiently, going beyond kernels? Advances in Neural Information Processing Systems, 32, 2019.
3.Alman, J. and Song, Z. Fast attention requires bounded entries. arXiv preprint arXiv:2302.13214, 2023.
4.Alman, J., Liang, J., Song, Z., Zhang, R., and Zhuo, D. Bypass exponential time preprocessing: Fast neural network training via weight-data correlation preprocessing. arXiv preprint arXiv:2211.14227, 2022.
5.Alon, N., Matias, Y., and Szegedy, M. The space complexity of approximating the frequency moments. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pp. 20–29, 1996.
6.Aminabadi, R. Y., Rajbhandari, S., Awan, A. A., Li, C., Li, D., Zheng, E., Ruwase, O., Smith, S., Zhang, M., Rasley, J., et al. Deepspeed-inference: Enabling efficient inference of transformer models at unprecedented scale. In 2022 SC22: International Conference for High Performance Computing, Networking, Storage and Analysis (SC), pp. 646–660. IEEE Computer Society, 2022.
7.Andoni, A. and Razenshteyn, I. Optimal data-dependent hashing for approximate near neighbors. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing (STOC), pp. 793–801, 2015.
8.Andoni, A., Indyk, P., Nguyen, H. L., and Razenshteyn, I. Beyond locality-sensitive hashing. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pp. 1018–1028. SIAM, 2014.
9.Andoni, A., Indyk, P., Laarhoven, T., Razenshteyn, I., and Schmidt, L. Practical and optimal lsh for angular distance. In Advances in Neural Information Processing Systems (NIPS), pp. 1225–1233. Curran Associates, 2015.
10.Andoni, A., Laarhoven, T., Razenshteyn, I., and Waingarten, E. Optimal hashing-based time-space trade-offs for approximate near neighbors. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 47–66. SIAM, 2017.
11.Andoni, A., Indyk, P., and Razenshteyn, I. Approximate nearest neighbor search in high dimensions. arXiv preprint arXiv:1806.09823, 7, 2018.
12.Arya, S. and Mount, D. M. Approximate nearest neighbor queries in fixed dimensions. In SODA, volume 93, pp. 271–280. Citeseer, 1993.
13.Balduzzi, D., Frean, M., Leary, L., Lewis, J., Ma, K. W.-D., and McWilliams, B. The shattered gradients problem: If resnets are the answer, then what is the question? In International Conference on Machine Learning, pp. 342–350. PMLR, 2017.
14.Bansal, H., Gopalakrishnan, K., Dingliwal, S., Bodapati, S., Kirchhoff, K., and Roth, D. Rethinking the role of scale for in-context learning: An interpretability-based case study at 66 billion scale. arXiv preprint arXiv:2212.09095, 2022.
15.Baum, L. E. and Petrie, T. Statistical inference for probabilistic functions of finite state markov chains. The annals of mathematical statistics, 37(6):1554–1563, 1966.
16.Bello, I., Fedus, W., Du, X., Cubuk, E. D., Srinivas, A., Lin, T.-Y., Shlens, J., and Zoph, B. Revisiting resnets: Improved training and scaling strategies. Advances in Neural Information Processing Systems, 34:22614–22627, 2021.
17.Bengio, Y., Ducharme, R., Vincent, P., and Jauvin, C. A neural probabilistic language model. Journal of machine learning research (JMLR), 3(Feb):1137–1155, 2003.
18.Bisk, Y., Zellers, R., Bras, R. L., Gao, J., and Choi, Y. Piqa: Reasoning about physical commonsense in natural language. In Thirty-Fourth AAAI Conference on Artificial Intelligence, 2020.
19.Black, S., Biderman, S., Hallahan, E., Anthony, Q., Gao, L., Golding, L., He, H., Leahy, C., McDonell, K., Phang, J., Pieler, M., Prashanth, U. S., Purohit, S., Reynolds, L., Tow, J., Wang, B., and Weinbach, S. GPT-NeoX-20B: An open-source autoregressive language model. In Proceedings of the ACL Workshop on Challenges & Perspectives in Creating Large Language Models, 2022. URL https://arxiv.org/abs/2204.06745.
20.Bommasani, R., Hudson, D. A., Adeli, E., Altman, R., Arora, S., von Arx, S., Bernstein, M. S., Bohg, J., Bosselut, A., Brunskill, E., et al. On the opportunities and risks of foundation models. arXiv preprint arXiv:2108.07258, 2021.
21.Boutsidis, C., Woodruff, D. P., and Zhong, P. Optimal principal component analysis in distributed and streaming models. In STOC’16—Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016.
22.Boytsov, L., Novak, D., Malkov, Y., and Nyberg, E. Off the beaten path: Let’s replace term-based retrieval with k-nn search. In Proceedings of the 25th ACM international on conference on information and knowledge management (CIKM), pp. 1099–1108, 2016.
23.Brand, J. v. d., Peng, B., Song, Z., and Weinstein, O. Training (overparametrized) neural networks in near-linear time. In ITCS, 2021.
24.Brand, J. v. d., Song, Z., and Zhou, T. Algorithm and hardness for dynamic attention maintenance in large language models. arXiv preprint arXiv:2304.02207, 2023.
25.Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al. Language models are few-shot learners. Advances in neural information processing systems, 33: 1877–1901, 2020.
26.Chan, S. C., Santoro, A., Lampinen, A. K., Wang, J. X., Singh, A. K., Richemond, P. H., McClelland, J., and Hill, F. Data distributional properties drive emergent in-context learning in transformers. In Advances in Neural Information Processing Systems, 2022.
27.Chang, W.-C., Yu, F. X., Chang, Y.-W., Yang, Y., and Kumar, S. Pre-training tasks for embedding-based large-scale retrieval. arXiv preprint arXiv:2002.03932, 2020.
28.Charikar, M., Chen, K., and Farach-Colton, M. Finding frequent items in data streams. In International Colloquium on Automata, Languages, and Programming, pp. 693–703. Springer, 2002.
29.Chen, B., Xu, Y., and Shrivastava, A. Fast and accurate stochastic gradient estimation. Advances in Neural Information Processing Systems, 32, 2019.
30.Chen, B., Medini, T., Farwell, J., Tai, C., Shrivastava, A., et al. Slide: In defense of smart algorithms over hardware acceleration for large-scale deep learning systems. Proceedings of Machine Learning and Systems, 2:291–306, 2020a.
31.Chen, B., Dao, T., Winsor, E., Song, Z., Rudra, A., and Ré, C. Scatterbrain: Unifying sparse and low-rank attention. Advances in Neural Information Processing Systems, 34: 17413–17426, 2021a.
32.Chen, B., Liu, Z., Peng, B., Xu, Z., Li, J. L., Dao, T., Song, Z., Shrivastava, A., and Re, C. Mongoose: A learnable lsh framework for efficient neural network training. In International Conference on Learning Representations, 2021b.
33.Chen, H., Chillotti, I., Dong, Y., Poburinnaya, O., Razenshteyn, I., and Riazi, M. S. {SANNS}: Scaling up secure approximate k-nearest neighbors search. In 29th {USENIX} Security Symposium ({USENIX} Security 20), pp. 2111–2128, 2020b.
34.Chen, L. On the hardness of approximate and exact (bichromatic) maximum inner product. In 33rd Computational Complexity Conference (CCC), 2018.
35.Cho, J. H. and Hariharan, B. On the efficacy of knowledge distillation. In Proceedings of the IEEE/CVF international conference on computer vision, pp. 4794–4802, 2019.
36.Chowdhery, A., Narang, S., Devlin, J., Bosma, M., Mishra, G., Roberts, A., Barham, P., Chung, H. W., Sutton, C., Gehrmann, S., et al. PaLM: Scaling language modeling with pathways. arXiv preprint arXiv:2204.02311, 2022.
37.Clarkson, K. L. and Woodruff, D. P. Low-rank approximation and regression in input sparsity time. In STOC, 2013.
38.Cohen, M. B. Nearly tight oblivious subspace embeddings by trace inequalities. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pp. 278–287. SIAM, 2016.
39.Cook, S. CUDA Programming: A Developer’s Guide to Parallel Computing with GPUs. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1st edition, 2012. ISBN 9780124159334.
40.Cox, M. and Cox, T. Multidimensional scaling, 315–347. Handbook of data visualization. Springer, Berlin, Germany, 2008.
41.Dao, T., Fu, D. Y., Ermon, S., Rudra, A., and Ré, C. Flashattention: Fast and memory-efficient exact attention with io-awareness. In Advances in Neural Information Processing Systems, 2022.
42.Datar, M., Immorlica, N., Indyk, P., and Mirrokni, V. S. Locality-sensitive hashing scheme based on p-stable distributions. InProceedings of the twentieth annual symposium on Computational geometry (SoCG), pp. 253–262, 2004.
43.de Marneffe, M.-C., Simons, M., and Tonhauser, J. The commitmentbank: Investigating projection in naturally occurring discourse. 2019.
44.Deng, Y., Li, Z., and Song, Z. Attention scheme inspired softmax regression. arXiv preprint arXiv:2304.10411, 2023a.
45.Deng, Y., Mahadevan, S., and Song, Z. Randomized and deterministic attention sparsification algorithms for over-parameterized feature dimension. arxiv preprint: arxiv 2304.03426, 2023b.
46.Derpanis, K. G. Mean shift clustering. Lecture Notes, 32: 1–4, 2005.
47.Dettmers, T., Lewis, M., Belkada, Y., and Zettlemoyer, L. Llm. int8 (): 8-bit matrix multiplication for transformers at scale. arXiv preprint arXiv:2208.07339, 2022.
48.Dong, S., Lee, Y. T., and Ye, G. A nearly-linear time algorithm for linear programs with small treewidth: A multiscale representation of robust central path. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 1784–1797, 2021.
49.Dong, Y., Indyk, P., Razenshteyn, I., and Wagner, T. Learning space partitions for nearest neighbor search. In International Conference on Learning Representations, 2019.
50.Fang, J., Yu, Y., Zhao, C., and Zhou, J. Turbotransformers: an efficient gpu serving system for transformer models. In Proceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp. 389–402, 2021.
51.Frankle, J. and Carbin, M. The lottery ticket hypothesis: Finding sparse, trainable neural networks. arXiv preprint arXiv:1803.03635, 2018.
52.Frantar, E. and Alistarh, D. Massive language models can be accurately pruned in one-shot. arXiv preprint arXiv:2301.00774, 2023.
53.Frantar, E., Ashkboos, S., Hoefler, T., and Alistarh, D. Gptq: Accurate post-training quantization for generative pretrained transformers. arXiv preprint arXiv:2210.17323, 2022.
54.Frei, S., Cao, Y., and Gu, Q. Algorithm-dependent generalization bounds for overparameterized deep residual networks. Advances in neural information processing systems, 32, 2019.
55.Gao, L., Tow, J., Biderman, S., Black, S., DiPofi, A., Foster, C., Golding, L., Hsu, J., McDonell, K., Muennighoff, N., Phang, J., Reynolds, L., Tang, E., Thite, A., Wang, B., Wang, K., and Zou, A. A framework for few-shot language model evaluation, September 2021. URL https://doi.org/10.5281/zenodo.5371628.
56.Gao, Y., Mahadevan, S., and Song, Z. An over-parameterized exponential regression. arXiv preprint arXiv:2303.16504, 2023a.
57.Gao, Y., Song, Z., and Yang, X. Differentially private attention computation. arXiv preprint arXiv:2305.04701, 2023b.
58.Giampiccolo, D., Magnini, B., Dagan, I., and Dolan, B. The third PASCAL recognizing textual entailment challenge. In Proceedings of the ACL-PASCAL Workshop on Textual Entailment and Paraphrasing, pp. 1–9, Prague, June 2007. Association for Computational Linguistics. URL https://aclanthology.org/W07-1401.
59.Gionis, A., Indyk, P., Motwani, R., et al. Similarity search in high dimensions via hashing. In Vldb, volume 99, pp. 518–529, 1999.
60.Gordon, A., Kozareva, Z., and Roemmele, M. SemEval-2012 task 7: Choice of plausible alternatives: An evaluation of commonsense causal reasoning. In *SEM 2012: The First Joint Conference on Lexical and Computational Semantics – Volume 1: Proceedings of the main conference and the shared task, and Volume 2: Proceedings of the Sixth International Workshop on Semantic Evaluation (SemEval 2012), pp. 394–398, Montréal, Canada, 7-8 June 2012. Association for Computational Linguistics. URL https://aclanthology.org/S12-1052.
61.Gu, Y. and Song, Z. A faster small treewidth sdp solver. arXiv preprint arXiv:2211.06033, 2022.
62.Gu, Y., Song, Z., Yin, J., and Zhang, L. Low rank matrix completion via robust alternating minimization in nearly linear time. arXiv preprint arXiv:2302.11068, 2023.
63.Hall, R. and Attenberg, J. Fast and accurate maximum inner product recommendations on map-reduce. In Proceedings of the 24th International Conference on World Wide Web (WWW), pp. 1263–1268, 2015.
64.Han, S., Mao, H., and Dally, W. J. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. arXiv preprint arXiv:1510.00149, 2015.
65.Harris, M. How to access global memory efficiently in CUDA C/C++ kernels. NVIDIA, Jan, 2013.
66.He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770–778, 2016.
67.He, Y., Liu, P., Wang, Z., Hu, Z., and Yang, Y. Filter pruning via geometric median for deep convolutional neural networks acceleration. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 4340–4349, 2019.
68.Hinton, G., Vinyals, O., Dean, J., et al. Distilling the knowledge in a neural network. arXiv preprint arXiv:1503.02531, 2(7), 2015.
69.Hoefler, T., Alistarh, D., Ben-Nun, T., Dryden, N., and Peste, A. Sparsity in deep learning: Pruning and growth for efficient inference and training in neural networks. J. Mach. Learn. Res., 22(241):1–124, 2021.
70.Hooker, S. The hardware lottery. Communications of the ACM, 64(12):58–65, 2021.
71.Hu, H., Song, Z., Weinstein, O., and Zhuo, D. Training overparametrized neural networks in sublinear time. arXiv preprint arXiv:2208.04508, 2022.
72.Indyk, P. and Motwani, R. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the thirtieth annual ACM symposium on Theory of computing (STOC), pp. 604–613, 1998a.
73.Indyk, P. and Motwani, R. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pp. 604–613, 1998b.
74.Indyk, P. and Wagner, T. Approximate nearest neighbors in limited space. In Conference On Learning Theory, pp. 2012–2036. PMLR, 2018.
75.Ivanov, A., Dryden, N., Ben-Nun, T., Li, S., and Hoefler, T. Data movement is all you need: A case study on optimizing transformers. Proceedings of Machine Learning and Systems, 3:711–732, 2021.
76.Jacob, B., Kligys, S., Chen, B., Zhu, M., Tang, M., Howard, A., Adam, H., and Kalenichenko, D. Quantization and training of neural networks for efficient integer-arithmetic-only inference. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 2704–2713, 2018.
77.Jiang, S., Song, Z., Weinstein, O., and Zhang, H. A faster algorithm for solving general lps. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 823–832, 2021.
78.Johnson, J., Douze, M., and Jégou, H. Billion-scale similarity search with GPUs. IEEE Transactions on Big Data, 7(3):535–547, 2019.
79.Johnson, W. B. and Lindenstrauss, J. Extensions of lipschitz mappings into a hilbert space. Contemporary mathematics, 26(189-206):1, 1984.
80.Kitaev, N., Kaiser, Ł., and Levskaya, A. Reformer: The efficient transformer. In ICLR, 2020.
81.Kurtz, M., Kopinsky, J., Gelashvili, R., Matveev, A., Carr, J., Goin, M., Leiserson, W., Moore, S., Shavit, N., and Alistarh, D. Inducing and exploiting activation sparsity for fast inference on deep neural networks. In III, H. D. and Singh, A. (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 5533–5543. PMLR, 13–18 Jul 2020. URL https://proceedings.mlr.press/v119/kurtz20a.html.
82.Laurent, B. and Massart, P. Adaptive estimation of a quadratic functional by model selection. Annals of Statistics, pp. 1302–1338, 2000.
83.LeCun, Y., Denker, J., and Solla, S. Optimal brain damage. Advances in neural information processing systems, 2, 1989.
84.Lee, M., He, X., Yih, W.-t., Gao, J., Deng, L., and Smolensky, P. Reasoning in vector space: An exploratory study of question answering. In ICLR, 2016.
85.Lee, N., Ajanthan, T., and Torr, P. H. Snip: Single-shot network pruning based on connection sensitivity. arXiv preprint arXiv:1810.02340, 2018.
86.Lee, Y. T., Song, Z., and Zhang, Q. Solving empirical risk minimization in the current matrix multiplication time. In Conference on Learning Theory, pp. 2140–2157. PMLR, 2019.
87.Li, P., Li, X., and Zhang, C.-H. Re-randomized densification for one permutation hashing and bin-wise consistent weighted sampling. Advances in Neural Information Processing Systems, 32, 2019.
88.Li, S., Song, Z., Xia, Y., Yu, T., and Zhou, T. The closeness of in-context learning and weight shifting for softmax regression. arXiv preprint, 2023a.
89.Li, X. and Li, P. C-MinHash: Improving minwise hashing with circulant permutation. In Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., and Sabato, S. (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 12857–12887. PMLR, 17–23 Jul 2022. URL https://proceedings.mlr.press/v162/li22m.html.
90.Li, Z., You, C., Bhojanapalli, S., Li, D., Rawat, A. S., Reddi, S. J., Ye, K., Chern, F., Yu, F., Guo, R., and Kumar, S. Large models are parsimonious learners: Activation sparsity in trained transformers, 2022. URL https://arxiv.org/abs/2210.06313.
91.Li, Z., Song, Z., and Zhou, T. Solving regularized exp, cosh and sinh regression problems. arXiv preprint, 2303.15725, 2023b.
92.Liang, P., Bommasani, R., Lee, T., Tsipras, D., Soylu, D., Yasunaga, M., Zhang, Y., Narayanan, D., Wu, Y., Kumar, A., et al. Holistic evaluation of language models. arXiv preprint arXiv:2211.09110, 2022.
93.Liu, Z., Sun, M., Zhou, T., Huang, G., and Darrell, T. Rethinking the value of network pruning. arXiv preprint arXiv:1810.05270, 2018.
94.Liu, Z., Xu, Z., Ji, A., Zhang, J., Li, J., Chen, B., and Shrivastava, A. Halos: Hashing large output space for cheap inference. Proceedings of Machine Learning and Systems, 4:110–125, 2022.
95.Lu, Y., Dhillon, P., Foster, D. P., and Ungar, L. Faster ridge regression via the subsampled randomized hadamard transform. In Advances in neural information processing systems (NIPS), pp. 369–377, 2013.
96.Malkov, Y., Ponomarenko, A., Logvinov, A., and Krylov, V. Approximate nearest neighbor algorithm based on navigable small world graphs. Information Systems, 45: 61–68, 2014.
97.Malkov, Y. A. and Yashunin, D. A. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE transactions on pattern analysis and machine intelligence, 42(4):824–836, 2018.
98.Meng, X. and Mahoney, M. W. Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pp. 91–100, 2013.
99.Merity, S., Xiong, C., Bradbury, J., and Socher, R. Pointer sentinel mixture models, 2016.
100.Michel, P., Levy, O., and Neubig, G. Are sixteen heads really better than one? Advances in neural information processing systems, 32, 2019.
101.Mihaylov, T., Clark, P., Khot, T., and Sabharwal, A. Can a suit of armor conduct electricity? a new dataset for open book question answering. In EMNLP, 2018.
102.Min, S., Lyu, X., Holtzman, A., Artetxe, M., Lewis, M., Hajishirzi, H., and Zettlemoyer, L. Rethinking the role of demonstrations: What makes in-context learning work? arXiv preprint arXiv:2202.12837, 2022.
103.Molchanov, P., Tyree, S., Karras, T., Aila, T., and Kautz, J. Pruning convolutional neural networks for resource efficient inference. arXiv preprint arXiv:1611.06440, 2016.
104.Nagel, M., Baalen, M. v., Blankevoort, T., and Welling, M. Data-free quantization through weight equalization and bias correction. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 1325–1334, 2019.
105.Nelson, J. and Nguyên, H. L. Osnap: Faster numerical linear algebra algorithms via sparser subspace embeddings. In 2013 ieee 54th annual symposium on foundations of computer science, pp. 117–126. IEEE, 2013.
106.Neyshabur, B. and Srebro, N. On symmetric and asymmetric lshs for inner product search. In International Conference on Machine Learning (ICML), pp. 1926–1934. PMLR, 2015.
107.NVIDIA. Fastertransformer. https://github.com/NVIDIA/FasterTransformer.
108.NVIDIA. Gpu performance background user’s guide, 2022. URL https://docs.nvidia.com/deeplearning/performance/dl-performance-gpu-background/index.html.
109.Park, G., Park, B., Kwon, S. J., Kim, B., Lee, Y., and Lee, D. nuqmm: Quantized matmul for efficient inference of large-scale generative language models. arXiv preprint arXiv:2206.09557, 2022.
110.Pope, R., Douglas, S., Chowdhery, A., Devlin, J., Bradbury, J., Levskaya, A., Heek, J., Xiao, K., Agrawal, S., and Dean, J. Efficiently scaling transformer inference. arXiv preprint arXiv:2211.05102, 2022.
111.Qin, L., Song, Z., and Wang, Y. Fast submodular function maximization. CoRR, abs/2305.08367, 2023a.
112.Qin, L., Song, Z., Zhang, L., and Zhuo, D. An online and unified algorithm for projection matrix vector multiplication with application to empirical risk minimization. In AISTATS, 2023b.
113.Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., and Sutskever, I. Language models are unsupervised multitask learners. 2019.
114.Raffel, C., Shazeer, N., Roberts, A., Lee, K., Narang, S., Matena, M., Zhou, Y., Li, W., and Liu, P. J. Exploring the limits of transfer learning with a unified text-to-text transformer. arXiv e-prints, 2019.
115.Razenshteyn, I., Song, Z., and Woodruff, D. P. Weighted low rank approximations with provable guarantees. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pp. 250–263, 2016.
116.Sarlos, T. Improved approximation algorithms for large matrices via random projections. In 2006 47th annual IEEE symposium on foundations of computer science (FOCS), pp. 143–152. IEEE, 2006.
117.Seo, M., Lee, J., Kwiatkowski, T., Parikh, A. P., Farhadi, A., and Hajishirzi, H. Real-time open-domain question answering with dense-sparse phrase index. In ACL, pp. 4430–4441, 2019.
118.Shrivastava, A., Song, Z., and Xu, Z. Sublinear least-squares value iteration via locality sensitive hashing. arXiv preprint arXiv:2105.08285, 2021.
119.Smith, J. E. A study of branch prediction strategies. In 25 years of the international symposia on Computer architecture (selected papers), pp. 202–215, 1998.
120.Sohler, C. and Woodruff, D. P. Subspace embeddings for the l1-norm with applications. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pp. 755–764, 2011.
121.Song, Z. and Ye, M. Efficient asynchronize stochastic gradient algorithm with structured data. CoRR, abs/2305.08001, 2023.
122.Song, Z. and Yu, Z. Oblivious sketching-based central path method for linear programming. In International Conference on Machine Learning, pp. 9835–9847. PMLR, 2021.
123.Song, Z., Woodruff, D. P., and Zhong, P. Low rank approximation with entrywise l1-norm error. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 688–701, 2017.
124.Song, Z., Woodruff, D. P., and Zhong, P. Relative error tensor low rank approximation. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2772–2789. SIAM, 2019.
125.Song, Z., Zhang, L., and Zhang, R. Training multi-layer over-parametrized neural network in subquadratic time. arXiv preprint arXiv:2112.07628, 2021.
126.Song, Z., Wang, W., and Yin, C. Fast and efficient matching algorithm with deadline instances. CoRR, abs/2305.08353, 2023a.
127.Song, Z., Yang, X., Yang, Y., and Zhang, L. Sketching meets differential privacy: fast algorithm for dynamic kronecker projection maintenance. In International Conference on Machine Learning (ICML), 2023b.
128.Tang, R., Lu, Y., Liu, L., Mou, L., Vechtomova, O., and Lin, J. Distilling task-specific knowledge from bert into simple neural networks. arXiv preprint arXiv:1903.12136, 2019.
129.Tillet, P., Kung, H.-T., and Cox, D. Triton: an intermediate language and compiler for tiled neural network computations. In Proceedings of the 3rd ACM SIGPLAN International Workshop on Machine Learning and Programming Languages, pp. 10–19, 2019.
130.Touvron, H., Cord, M., Douze, M., Massa, F., Sablayrolles, A., and Jégou, H. Training data-efficient image transformers & distillation through attention. In International Conference on Machine Learning, pp. 10347–10357. PMLR, 2021.
131.Veit, A., Wilber, M. J., and Belongie, S. Residual networks behave like ensembles of relatively shallow networks. Advances in neural information processing systems, 29, 2016.
132.Viterbi, A. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE transactions on Information Theory, 13(2):260–269, 1967.
133.Wang, B. and Komatsuzaki, A. GPT-J-6B: A 6 billion parameter autoregressive language model. https://github.com/kingoflolz/mesh-transformer-jax, May 2021.
134.Wang, R. and Woodruff, D. P. Tight bounds for lp oblivious subspace embeddings. 2018.
135.Wang, X., Xiong, Y., Wei, Y., Wang, M., and Li, L. Lightseq: A high performance inference library for transformers. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies: Industry Papers, pp. 113–120, 2021.
136.Woodruff, D. P. Sketching as a tool for numerical linear algebra. Foundations and Trends® in Theoretical Computer Science, 10(1–2):1–157, 2014.
137.Xiao, G., Lin, J., Seznec, M., Demouth, J., and Han, S. Smoothquant: Accurate and efficient post-training quantization for large language models. arXiv preprint arXiv:2211.10438, 2022.
138.Xie, S. M., Raghunathan, A., Liang, P., and Ma, T. An explanation of in-context learning as implicit bayesian inference. In International Conference on Learning Representations, 2022. URL https://openreview.net/forum?id=RdJVFCHjUMI.
139.Xue, H.-J., Dai, X., Zhang, J., Huang, S., and Chen, J. Deep matrix factorization models for recommender systems. In IJCAI, pp. 3203–3209, 2017.
140.Yao, Z., Aminabadi, R. Y., Zhang, M., Wu, X., Li, C., and He, Y. Zeroquant: Efficient and affordable post-training quantization for large-scale transformers. arXiv preprint arXiv:2206.01861, 2022.
141.Yu, G.-I., Jeong, J. S., Kim, G.-W., Kim, S., and Chun, B.-G. Orca: A distributed serving system for {Transformer-Based} generative models. In 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22), pp. 521–538, 2022.
142.Zandieh, A., Han, I., Daliri, M., and Karbasi, A. Kdeformer: Accelerating transformers via kernel density estimation. arXiv preprint arXiv:2302.02451, 2023.
143.Zhang, L. Speeding up optimizations via data structures: Faster search, sample and maintenance. Master’s thesis, Carnegie Mellon University, 2022.
144.Zhang, M., Wang, W., Liu, X., Gao, J., and He, Y. Navigating with graph representations for fast and scalable decoding of neural language models. Advances in neural information processing systems, 31, 2018.
145.Zhao, R., Hu, Y., Dotzel, J., De Sa, C., and Zhang, Z. Improving neural network quantization without retraining using outlier channel splitting. In International conference on machine learning, pp. 7543–7552. PMLR, 2019.

Citation

MLA

Liu, Z., et al. “Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time”. Proceedings of the 40th International Conference on Machine Learning, 2023, 919, 2023, http://arxiv.org/abs/2310.17157v1.

APA

Liu, Z., Wang, J., Dao, T., Zhou, T., Yuan, B., Song, Z., Shrivastava, A., Zhang, C., Tian, Y., Re, C., & Chen, B. (2023). Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time. Proceedings of the 40th International Conference on Machine Learning, 2023, 919. http://arxiv.org/abs/2310.17157v1

Chicago

Liu, Z., J. Wang, T. Dao, et al. 2023. “Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time”. Proceedings of the 40th International Conference on Machine Learning, 2023, 919. http://arxiv.org/abs/2310.17157v1.

Harvard

Liu, Z. et al. (2023) “Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time”, Proceedings of the 40th International Conference on Machine Learning, 2023, 919 [Preprint]. Available at: http://arxiv.org/abs/2310.17157v1.

Vancouver

1. Liu Z, Wang J, Dao T, et al (2023) Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time. Proceedings of the 40th International Conference on Machine Learning, 2023, 919

BibTeX

@article{liu2023deja,
  title = {Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time},
  author = {Liu, Zichang and Wang, Jue and Dao, Tri and Zhou, Tianyi and Yuan, Binhang and Song, Zhao and Shrivastava, Anshumali and Zhang, Ce and Tian, Yuandong and Re, Christopher and Chen, Beidi},
  year = {2023},
  journal = {Proceedings of the 40th International Conference on Machine Learning, 2023, 919},
  url = {http://arxiv.org/abs/2310.17157v1},
  eprint = {2310.17157}
}

Metadata:arXiv

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

Deja Vu: Contextual Sparsity for Efficient LLMs at Inference Time

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Contextual Sparsity in Transformer Models

Knowl 2 — Asynchronous Lookahead Sparsity Prediction

Knowl 3 — Hardware-Aware Sparse Kernel Fusion and Memory Coalescing

Knowl 4 — Sparse Predictor Training via MaxIP Classification

Knowl 5 — Deferred Key-Value Cache Computation for Sparsified Attention

Knowl 6 — Slowly Changing Embeddings Across Transformer Layers

Knowl 7 — Theoretical Guarantee for Cross-Layer MaxIP Sparsity Prediction

Knowl 8 — End-to-End Latency and Downstream Quality of DejaVu on OPT-175B