Express Language Modeling

Albert GongAnnabelle Michael CarrellRaaz DwivediLester Mackey

article2026arXiv0 citations

Develops Express, a method for converting non-causal attention approximations into causal ones with provable theoretical guarantees, delivering faster execution speeds than FlashAttention 2 across key long-context prefill and decoding bottlenecks.

Listen

Modern artificial intelligence relies heavily on large language models, but processing long text sequences is computationally expensive. Standard attention mechanisms suffer from quadratic scaling, meaning compute and memory requirements explode as context lengths increase. While various approximation methods speed up unmasked computations, language modeling requires causal masking, where each word can only attend to preceding text. This constraint causes severe memory and compute bottlenecks across long-context processing, key-value cache retention, and multi-step reasoning.

The article introduces Express, a general framework designed to convert high-quality unmasked attention approximations into causal approximations. By pairing this framework with the kernel halving algorithm, the article demonstrates Thinformer Express, an attention approximation technique providing strong mathematical error bounds, fixed memory scaling, and significant speedups.

The authors developed an input/output-aware GPU kernel implementation using Triton, incorporating memory tiling and parallelization to eliminate redundant data copies. They evaluated the framework across established long-context understanding benchmarks, such as LongBench-E, and complex mathematical reasoning tests using MATH-500. The testing suite benchmarked the approach against state-of-the-art exact and approximate baselines, including FlashAttention 2 and HyperAttention, across multiple open models like Llama 3.1 and DeepSeek-R1-Distill-Llama-8B.

The evaluation revealed several critical findings. First, in long-context processing, Thinformer Express achieved up to an 82-fold speedup over FlashAttention 2 at 512,000 tokens without running out of memory. Second, when integrated with leading key-value cache compression methods, it substantially reduced overall runtime while preserving baseline task accuracy. Third, in long-form step-by-step reasoning, Thinformer Express matched exact attention accuracy using only 61% of the typical cache size. Fourth, it delivered matching exact-attention accuracy in reasoning tasks while requiring only 56% of the computation time, maintaining very low compression overhead.

These results demonstrate that organizations can significantly reduce hardware costs and runtime latency for long-context language tasks without sacrificing model performance. Operating with a compact, dynamic cache lowers GPU memory requirements, allowing longer context windows on constrained hardware. This enables broader deployment of high-performing reasoning models and decreases energy consumption per inference query.

Engineering and deployment teams should consider piloting Thinformer Express to accelerate long-context pipelines and optimize key-value cache storage in generative workflows. Organizations deploying heavy reasoning models can adopt this approach to cut serving infrastructure costs. Future development should focus on extending the Triton implementation to support newer hardware features, such as 8-bit floating-point precision and advanced memory accelerators, as well as evaluating performance across non-English languages and specialized industrial domains.

The primary limitations include empirical validation limited to English, Chinese, and mathematical reasoning, alongside a software kernel that does not yet leverage newer architectural GPU features like specialized tensor memory accelerators. Nevertheless, because the theoretical guarantees are rigorous and backed by consistent benchmark results across diverse models, there is high confidence in the reported speed and memory improvements for standard transformer architectures.

Cornell University Microsoft University of Cambridge cache language model random access memory Thinformer Express Algorithm long-form memory-constrained decoding attention approximation

arXiv: 2606.10944

Paper: FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning, Tri Dao (2023). FlashAttention-2 establishes the causal and non-causal attention kernels and hardware-efficiency baseline that Express’s Triton implementation improves upon.
Paper: FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness, Tri Dao et al. (2022). FlashAttention introduces the I/O-aware attention approach underlying the efficiency context for Express’s implementation and speed comparisons.

No sufficiently relevant recommendations were found.

Abstract

We introduce a new tool, Express, for converting a non-causal attention approximation into a causal approximation with matching approximation guarantees. When combined with the state-of-the-art Thinformer approximation, Express improves upon the best known causal attention guarantees, delivering $\log^{3/2}(n)/s$ approximation error with only $O(s)$ memory and $O(s^2 \log^2(n))$ compression overhead for a sequence of length $n$ . We pair these developments with an efficient I/O-aware Triton implementation, demonstrate substantial speedups over FlashAttention 2, and use Express to overcome four resource bottlenecks in the language modeling pipeline: long-context prefill, KV cache compression, long-form memory-constrained decoding, and long-form compute-constrained decoding.

Topics

cache language model random access memory

Keywords

Thinformer Express Algorithm long-form memory-constrained decoding attention approximation language modeling dot-product attention attention kernel space complexity

1 Introduction
2 Background on Attention and Thinning
2.1 Unmasked attention
2.2 Attention with causal masking
3 Express Language Modeling
3.1 Express
3.2 Thinformer Express
4 Experiments
5 Conclusion
References
A Kernel Halving
B Proof of :
C Proof of :
D Proof of :
E Proof of :
F Proof of :
G Proof of :
H Offline-Express
H.1 Offline-Subsample
H.2 Offline-Compress2
H.3 Offline-Express
I Supplementary Experiment Details
I.1 Configurations for accelerating prefill
I.2 Configurations for accelerating KV cache compression
I.3 Configurations for long-form decoding

Knowls

Knowl 1 — EXPRESS converts offline thinning into an online weighted cache
algorithm
EXPRESS turns a halving algorithm into a streaming coreset procedure for a sequence of input points. It is initialized with a target cache size $n_{\mathrm{out}}$ , a fixed inflation cap $\bar m$ chosen so that $2^{\bar m}=\Theta(n_{\mathrm{out}})$ , and a halving routine HALVE that reduces a set to half its size. The thinning level $m$ begins at zero and increases by two after each major round.

The first $n_{\mathrm{out}}$ points are stored exactly in a summary $E$ . Thereafter, EXPRESS processes each block of $2^m n_{\mathrm{out}}$ incoming points in a thin phase and adds a summary of size $n_{\mathrm{out}}$ to $E$ . If $m\leq\bar m$ , the block is passed through unchanged; otherwise, it is stratified into groups of size $2^{m-\bar m}$ and one uniformly random point is selected from each group, leaving $2^{\bar m}n_{\mathrm{out}}$ points. COMPRESS2 then reduces the resulting block to $n_{\mathrm{out}}$ using a hierarchy of HALVE calls: points enter level $S_0$ , and whenever a level reaches its prescribed capacity it is halved and promoted to the next level. The weighted cache exposes each level $S_i$ with weight $2^{i-q}$ , where $q=m\wedge\bar m$ .

After three thin-phase summaries have been added, $E$ contains $4n_{\mathrm{out}}$ points. EXPRESS applies HALVE twice to reduce $E$ back to $n_{\mathrm{out}}$ , increases $m$ by two, and initializes the thinning objects for the next round. The cache returned by EXPRESS consists of $E$ with unit weights together with the weighted COMPRESS2 levels. This update rule supports both online processing and per-prefix coreset queries; the cap $\bar m$ controls the amount of subsampling at high thinning levels.
Knowl 2 — EXPRESS has sequence-length-independent cache size and bounded compression cost
theoretical result
Suppose HALVE, on an input of size $r$ , uses space $s_H(r)$ and runtime $r_H(r)$ . EXPRESS with target cache size $n_{\mathrm{out}}$ and inflation cap $\bar m$ has weighted cache size at most $6n_{\mathrm{out}}$ points and space at most $6n_{\mathrm{out}}d+s_H(4n_{\mathrm{out}})$ , where each input point has dimension $d$ . These bounds do not grow with the length $n$ of the processed sequence, apart from the temporary workspace required by HALVE.

Define the COMPRESS2 runtime at level $q$ as $r_C(q)=\sum_{j=0}^{q-1}4^j r_H(n_{\mathrm{out}}2^{1-j})$ . Then, for $n\geq4n_{\mathrm{out}}$ , EXPRESS's total update runtime is bounded by $\lceil\log_4(n/n_{\mathrm{out}})\rceil\big[r_H(4n_{\mathrm{out}})+r_H(2n_{\mathrm{out}})+3r_C(\bar m)+3\cdot2^{\bar m}n_{\mathrm{out}}\big]$ ; before that threshold no HALVE calls are needed. The logarithmic factor counts major rounds, while the last term accounts for stratified subsampling. If HALVE has quadratic runtime, this construction yields the paper's stated near-linear-in-sequence-length compression regime when the target cache grows with the sequence.
Knowl 3 — EXPRESS preserves sub-Gaussian thinning quality across every prefix
theoretical result
Let $X_{\mathrm{out}}(j)$ be the weighted cache produced by EXPRESS after processing $j$ points, and let $\kappa$ be a kernel with reproducing-kernel Hilbert space $\mathcal H_\kappa$ and norm $\|\cdot\|_\kappa$ . A coreset is $(\kappa,\nu)$ -sub-Gaussian when, for every $f\in\mathcal H_\kappa$ , the moment-generating function of the difference between the input average and its weighted coreset average is bounded by $\exp(\nu^2\|f\|_\kappa^2/2)$ .

Assume every HALVE call made during the first $j$ updates is sub-Gaussian with parameter $\nu_{H,j}(r)$ on an input of size $r$ , and that $r\nu_{H,j}(r)$ is nondecreasing in both $r$ and $j$ . Write $m_j=2\lceil\log_4(j/(4n_{\mathrm{out}}))\rceil$ for $j\geq4n_{\mathrm{out}}$ . On a common high-probability event determined by the failure probabilities of the invoked HALVE calls, every prefix coreset is sub-Gaussian with parameter $\nu_E(j)$ satisfying $\nu_E(j)=0$ for $j<4n_{\mathrm{out}}$ and, for $j\geq4n_{\mathrm{out}}$ , $\nu_E^2(j)\leq\frac{16(16+3(m_j\wedge\bar m))}{15}\big(\nu_{H,j}^2(4n_{\mathrm{out}})+\nu_{H,j}^2(2n_{\mathrm{out}})\big)+\frac{16\|\kappa\|_j}{5n_{\mathrm{out}}2^{\bar m}}\mathbf 1[m_j>\bar m]$ , where $\|\kappa\|_j=\max_{i\leq j}\kappa(x_i,x_i)$ . Thus, the quality guarantee applies to the evolving cache, not merely to a single final summary; the additional term is incurred when the sequence has progressed beyond the subsampling cap.
Knowl 4 — KH-EXPRESS provides practical runtime, space, and quality guarantees
theoretical result
KH-EXPRESS $(\delta)$ is EXPRESS instantiated with the quadratic-time kernel-halving routine KH $(\eta)$ , which uses linear space in its input size. The failure probability is allocated across thinning rounds and levels: at round $m$ , set $\delta_m=\frac{\delta}{2}\left(\frac{1}{\log_2(m/2+2)}-\frac{1}{\log_2(m/2+3)}\right)$ ; use KH $(\delta_m/2)$ for the two major-round halvings and KH $(\delta_{m,i})$ at compression level $i$ , where $\delta_{m,i}=\frac{4^{i+1-(m\wedge\bar m)}\delta_m}{3(m\wedge\bar m)}$ .

For target cache size $n_{\mathrm{out}}$ and sequence length $n$ , the update runtime is $O\big(dn_{\mathrm{out}}^2\log(n/n_{\mathrm{out}})\log(n_{\mathrm{out}})\big)$ and space is at most $10n_{\mathrm{out}}d$ . With probability at least $1-\delta/2$ , the weighted coreset after $n$ updates is $\kappa$ -sub-Gaussian with $\nu_E^2(n)=O\left(\frac{\|\kappa\|_n\log(n_{\mathrm{out}})\log\!\left(n_{\mathrm{out}}\log(n/n_{\mathrm{out}})/\delta\right)}{n_{\mathrm{out}}^2}+\frac{\|\kappa\|_n}{2^{\bar m}n_{\mathrm{out}}}\right)$ , where $\|\kappa\|_n=\max_{i\leq n}\kappa(x_i,x_i)$ . This instantiation turns quadratic-time halving into an update procedure whose explicit dependence on sequence length is logarithmic.
Knowl 5 — Thinformer Express approximates causal attention using the EXPRESS cache
model/method
For query, key, and value vectors $q_i,k_i,v_i\in\mathbb R^d$ , exact causal attention at position $n$ is $o_n=\frac{\sum_{i=1}^n\exp(\langle q_n,k_i\rangle/\sqrt d)v_i}{\sum_{i=1}^n\exp(\langle q_n,k_i\rangle/\sqrt d)}$ . Thinformer Express uses KH-EXPRESS with the key-value kernel $\kappa_{\mathrm{att}}((k,v),(k',v'))=\exp(\langle k,k'\rangle/\sqrt d)(\langle v,v'\rangle+v_{\max}^2)$ , where $v_{\max}$ is the largest absolute value coordinate among values processed so far.

The method sets the target cache size to $n_{\mathrm{out}}=2^h$ . For each incoming token $(q_n,k_n,v_n)$ , it first computes attention using the current weighted cache together with $(k_n,v_n)$ , then inserts $(k_n,v_n)$ into the cache for future queries. If cache entries are $((k_e,v_e),w_e)$ , the approximate output is $\hat o_n=\frac{\sum_e w_e\exp(\langle q_n,k_e\rangle/\sqrt d)v_e}{\sum_e w_e\exp(\langle q_n,k_e\rangle/\sqrt d)}$ ; including the incoming token before the cache update ensures that it can attend to itself. For a sequence of length $n$ , the total query-attention cost is $O(n_{\mathrm{out}}nd)$ , while cache compression costs $O(dn_{\mathrm{out}}^2\log(n_{\mathrm{out}})\log(n/n_{\mathrm{out}}))$ .
Knowl 6 — Thinformer Express has a per-token causal attention error guarantee
theoretical result
Let $n_{\mathrm{out}}=2^h$ , let $\bar m$ be the EXPRESS inflation cap, and run Thinformer Express with KH-EXPRESS failure parameter $\delta=1/2$ . For a sequence of query-key-value vectors in $\mathbb R^d$ , define $R_n=\max_{i\leq n}\max(\|q_i\|_2,\|k_i\|_2)$ and let $V_n$ be the matrix with rows $v_1,\ldots,v_n$ ; $\|V_n\|_{2,\infty}$ is its maximum Euclidean row norm. With probability at least $1/2$ , the attention outputs are exact for every $n\leq4n_{\mathrm{out}}$ . For every $n>4n_{\mathrm{out}}$ , they simultaneously satisfy the bound $\|\hat o_n-o_n\|_\infty=O\!\left(\exp\!\left(\frac{2R_n^2}{\sqrt d}\right)\frac{\sqrt{\log((d+1)n)\log(n_{\mathrm{out}})\log\!\left(n_{\mathrm{out}}\log(n/n_{\mathrm{out}})\right)}}{\sqrt{2^{\bar m}n_{\mathrm{out}}}}\|V_n\|_{2,\infty}\right)$ .

The guarantee is for each causal output and depends on the maximum query/key norm and the maximum value-vector norm, rather than a matrix-wide Frobenius norm. The probability statement and error bound apply to the streaming attention procedure, including the changing cache at successive sequence prefixes.
Knowl 7 — I/O-aware Triton kernels make Thinformer Express practical on GPUs
model/method
The implementation uses Triton kernels for kernel halving and weighted-cache attention, with PyTorch orchestrating the remaining Thinformer Express updates. It tiles computation to reduce high-bandwidth-memory reads and writes and avoids materializing the kernel matrices used by halving. Attention computation is parallelized across batch, head, and query-row blocks.

For prefill, where all query-key-value tuples are available at once, same-sized HALVE calls are parallelized, and double dereferencing is used to index key and value vectors without unnecessary data copies. These implementation choices are designed to realize the algorithm's cache and runtime savings while limiting data movement; the paper reports an unmasked 32K-token benchmark in which the Triton version is faster than both the original PyTorch Thinformer implementation and exact FlashAttention 2.
Knowl 8 — Thinformer Express accelerates long-context prefill
empirical result
On an NVIDIA A6000 GPU, masked-prefill benchmarks compared Thinformer Express with FlashAttention 2 and HyperAttention over sequence lengths up to 512K tokens. At 512K tokens, Thinformer Express achieved an 82× speedup over FlashAttention 2 with $h=9$ and a 31× speedup with $h=10$ ; HyperAttention ran out of memory at that length. In an unmasked 32K-token benchmark with cache size $n_{\mathrm{out}}=256$ , the Triton Thinformer implementation was 27× faster than FlashAttention 2, compared with 15× for the original PyTorch implementation.

The quality/runtime comparison replaced attention in the last $k$ layers of ChatGLM2-6B-32K at a context length of 32,768, preserving the first and last 32 tokens. Both Thinformer Express settings had a better speedup-perplexity trade-off than HyperAttention, and the $h=10$ setting improved both speed and perplexity relative to HyperAttention. With every layer replaced, the evaluated approximate-attention methods kept perplexity within a factor of 1.06 of exact attention.
Knowl 9 — Express-assisted KV compression reduces runtime while preserving task quality
empirical result
KV-cache compression was evaluated by pairing Thinformer Express ( $h=9$ ) with SnapKV, StreamingLLM, and PyramidKV in all layers of Llama 3.1 8B Instruct. The LongBench-E tasks were TREC-E, TriviaQA-E, and HotpotQA-E. Each paired method used approximate attention to produce context keys and values during prefill and then applied the corresponding cache compressor; the comparison methods produced those keys and values with exact attention. The measured runtime summed key-value computation during prefill, cache compression, and query attention during decoding across all 32 layers.

Across the three task-and-compressor comparisons, the Express-paired variants reduced total attention runtime while preserving the accuracy of the underlying KV-cache compression methods. The experiment therefore demonstrates that approximate attention can accelerate the production of inputs to cache compression without an observed loss in the evaluated task accuracy.
Knowl 10 — Thinformer Express improves memory and runtime trade-offs in long-form decoding
empirical result
Long-form decoding was evaluated on all 500 MATH-500 problems using DeepSeek-R1-Distill-Llama-8B. The prompts averaged about 75 tokens, while generations averaged more than 4K tokens. Thinformer Express was compared with StreamingLLM, SnapKV, ExpectedAttention, KeyDiff, and Knorm. Its cache-size-versus-accuracy curve achieved the highest accuracy at nearly every cache size and matched exact-attention accuracy using 61% of the cache elements. Its runtime-versus-accuracy curve dominated those of the five alternatives and matched exact-attention accuracy using 56% of the computation time.

For the $h=10$ setting, across benchmark questions, weighted-cache attention took an average of 35,000 ms, while KH-EXPRESS cache updates took 470 ms. This measurement indicates that, in this evaluated decoding workload, the cost of maintaining the cache was small relative to the cost of querying it.

Coverage note — The paper's stated limitations—evaluation limited to English, Chinese, and mathematical reasoning; missing newer Triton/GPU optimizations; and limited testing of alternative halving routines—and its broader-impact discussion are omitted because they do not add a technical result or experimental finding comparable to the ten knowls above.

References

1.Ryan Alweiss, Yang P Liu, and Mehtaab Sawhney. Discrepancy minimization via a self-balancing walk. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 14–20, 2021. (Cited on page 6.)
2.Yushi Bai, Xin Lv, Jiajie Zhang, Hongchang Lyu, Jiankai Tang, Zhidian Huang, Zhengxiao Du, Xiao Liu, Aohan Zeng, Lei Hou, Yuxiao Dong, Jie Tang, and Juanzi Li. Longbench: A bilingual, multitask benchmark for long context understanding. In Proceedings of the 62nd annual meeting of the association for computational linguistics (volume 1: Long papers), pages 3119–3137, 2024. (Cited on pages 1, 2, and 8.)
3.Zefan Cai, Yichi Zhang, Bofei Gao, Yuliang Liu, Yucheng Li, Tianyu Liu, Keming Lu, Wayne Xiong, Yue Dong, Junjie Hu, et al. Pyramidkv: Dynamic kv cache compression based on pyramidal information funneling. In Second Conference on Language Modeling, 2025. (Cited on pages 2 and 8.)
4.Annabelle Michael Carrell, Albert Gong, Abhishek Shetty, Raaz Dwivedi, and Lester Mackey. Low-rank thinning. In International Conference on Machine Learning, pages 6811–6848. PMLR, 2025. (Cited on pages 1, 2, 5, 6, 7, 13, 16, and 17.)
5.Bernard Chazelle and Jiri Matousek. On linear-time deterministic algorithms for optimization problems in fixed dimension. Journal of Algorithms, 21(3):579–597, 1996. (Cited on page 6.)
6.Tri Dao. Flashattention-2: Faster attention with better parallelism and work partitioning. In The Twelfth International Conference on Learning Representations, 2024. URL https://openreview.net/forum?id=mZn2Xyh9Ec. (Cited on pages 1, 7, and 10.)
7.Tri Dao, Dan Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. Flashattention: Fast and memory-efficient exact attention with io-awareness. Advances in Neural Information Processing Systems, 35:16344–16359, 2022. (Cited on pages 1 and 7.)
8.Alessio Devoto, Yu Zhao, Simone Scardapane, and Pasquale Minervini. A simple and effective l_2 norm-based strategy for kv cache compression. In Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing, pages 18476–18499, 2024. (Cited on page 9.)
9.Alessio Devoto, Maximilian Jeblick, and Simon Jégou. Expected attention: Kv cache compression by estimating attention from future queries distribution. arXiv preprint arXiv:2510.00636, 2025. (Cited on pages 9 and 21.)
10.Raaz Dwivedi and Lester Mackey. Generalized kernel thinning. In International Conference on Learning Representations, 2022. (Cited on pages 2 and 5.)
11.Raaz Dwivedi and Lester Mackey. Kernel thinning. Journal of Machine Learning Research, 25 (152):1–77, 2024. (Cited on pages 2, 5, and 15.)
12.Team Glm, Aohan Zeng, Bin Xu, Bowen Wang, Chenhui Zhang, Da Yin, Dan Zhang, Diego Rojas, Guanyu Feng, Hanlin Zhao, et al. Chatglm: A family of large language models from glm-130b to glm-4 all tools. arXiv preprint arXiv:2406.12793, 2024. (Cited on page 8.)
13.Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Alex Vaughan, et al. The llama 3 herd of models. arXiv preprint arXiv:2407.21783, 2024. (Cited on page 8.)
14.Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Peiyi Wang, Qihao Zhu, Runxin Xu, Ruoyu Zhang, Shirong Ma, Xiao Bi, et al. Deepseek-r1 incentivizes reasoning in llms through reinforcement learning. Nature, 645(8081):633–638, 2025. (Cited on pages 1 and 9.)
15.Insu Han, Rajesh Jayaram, Amin Karbasi, Vahab Mirrokni, David Woodruff, and Amir Zandieh. Hyperattention: Long-context attention in near-linear time. In The Twelfth International Conference on Learning Representations, 2024. URL https://openreview.net/forum?id=Eh0Od2BJIM. (Cited on pages 1, 6, and 8.)
16.Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the MATH dataset. In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021. URL https://openreview.net/forum?id=7Bywt2mQsCe. (Cited on pages 9 and 21.)
17.Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13–30, 1963. ISSN 01621459, 1537274X. URL http://www.jstor.org/stable/2282952. (Cited on page 15.)
18.Mandar Joshi, Eunsol Choi, Daniel S Weld, and Luke Zettlemoyer. Triviaqa: A large scale distantly supervised challenge dataset for reading comprehension. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1601–1611, 2017. (Cited on page 8.)
19.Ekaterina Kochetkova, Kshiteej Sheth, Insu Han, Amir Zandieh, and Michael Kapralov. Streaming attention approximation via discrepancy theory. In Advances in Neural Information Processing Systems, 2025. (Cited on pages 1 and 6.)
20.Xin Li and Dan Roth. Learning question classifiers. In COLING 2002: The 19th International Conference on Computational Linguistics, 2002. (Cited on page 8.)
21.Yuhong Li, Yingbing Huang, Bowen Yang, Bharat Venkitesh, Acyr Locatelli, Hanchen Ye, Tianle Cai, Patrick Lewis, and Deming Chen. Snapkv: Llm knows what you are looking for before generation. In Advances in Neural Information Processing Systems, volume 37, 2024. (Cited on pages 2, 8, and 9.)
22.Hunter Lightman, Vineet Kosaraju, Yuri Burda, Harrison Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let’s verify step by step. In The twelfth international conference on learning representations, 2023. (Cited on pages 2, 9, and 21.)
23.Jiri Matousek. Approximations and optimal geometric divide-and-conquer. Journal of Computer and System Sciences, 50(2):203–208, 1995. (Cited on page 6.)
24.Junyoung Park, Dalton Jones, Matthew J Morse, Raghavv Goel, Mingu Lee, and Christopher Lott. Keydiff: Key similarity-based kv cache eviction for long-context llm inference in resource-constrained environments. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025. (Cited on page 9.)
25.Jeff M Phillips. Algorithms for ε-approximations of terrains. In International Colloquium on Automata, Languages, and Programming, pages 447–458. Springer, 2008. (Cited on page 6.)
26.Tobias Schröder and Lester Mackey. Wildcat: Near-linear attention in theory and practice. arXiv preprint arXiv:2602.10056, 2026. (Cited on pages 1 and 6.)
27.Jay Shah, Ganesh Bikshandi, Ying Zhang, Vijay Thakkar, Pradeep Ramani, and Tri Dao. Flashattention-3: Fast and accurate attention with asynchrony and low-precision. Advances in Neural Information Processing Systems, 37:68658–68685, 2024. (Cited on page 10.)
28.Abhishek Shetty, Raaz Dwivedi, and Lester Mackey. Distribution compression in near-linear time. In International Conference on Learning Representations, 2022. (Cited on pages 3 and 14.)
29.Ingo Steinwart and Andreas Christmann. Support vector machines. Wiley Interdisciplinary Reviews: Computational Statistics, 1, 2008. URL https://api.semanticscholar.org/CorpusID:661123. (Cited on pages 2 and 15.)
30.Philippe Tillet, Hsiang-Tsung Kung, and David Cox. 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, pages 10–19, 2019. (Cited on pages 1 and 7.)
31.Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS’17, page 6000–6010, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 9781510860964. (Cited on pages 1, 2, and 3.)
32.Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis. Efficient streaming language models with attention sinks. In International Conference on Learning Representations, 2024. URL https://openreview.net/forum?id=NG7sS51zVF. (Cited on pages 2, 8, and 9.)
33.Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William Cohen, Ruslan Salakhutdinov, and Christopher D Manning. Hotpotqa: A dataset for diverse, explainable multi-hop question answering. In Proceedings of the 2018 conference on empirical methods in natural language processing, pages 2369–2380, 2018. (Cited on page 8.)
34.Amir Zandieh, Insu Han, Majid Daliri, and Amin Karbasi. Kdeformer: Accelerating transformers via kernel density estimation. In International Conference on Machine Learning, pages 40605–40623. PMLR, 2023. (Cited on page 1.)

Citation

MLA

Gong, A., et al. “Express Language Modeling”. arXiv, 2026, http://arxiv.org/abs/2606.10944v1.

APA

Gong, A., Carrell, A. M., Dwivedi, R., & Mackey, L. (2026). Express Language Modeling. arXiv. http://arxiv.org/abs/2606.10944v1

Chicago

Gong, A., A. M. Carrell, R. Dwivedi, and L. Mackey. 2026. “Express Language Modeling”. arXiv. http://arxiv.org/abs/2606.10944v1.

Harvard

Gong, A. et al. (2026) “Express Language Modeling”, arXiv [Preprint]. Available at: http://arxiv.org/abs/2606.10944v1.

Vancouver

1. Gong A, Carrell AM, Dwivedi R, Mackey L (2026) Express Language Modeling. arXiv

BibTeX

@article{gong2026express,
  title = {Express Language Modeling},
  author = {Gong, Albert and Carrell, Annabelle Michael and Dwivedi, Raaz and Mackey, Lester},
  year = {2026},
  journal = {arXiv},
  url = {http://arxiv.org/abs/2606.10944v1},
  eprint = {2606.10944}
}

Metadata:arXiv

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/

Express Language Modeling

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — EXPRESS converts offline thinning into an online weighted cache

Knowl 2 — EXPRESS has sequence-length-independent cache size and bounded compression cost

Knowl 3 — EXPRESS preserves sub-Gaussian thinning quality across every prefix

Knowl 4 — KH-EXPRESS provides practical runtime, space, and quality guarantees

Knowl 5 — Thinformer Express approximates causal attention using the EXPRESS cache

Knowl 6 — Thinformer Express has a per-token causal attention error guarantee

Knowl 7 — I/O-aware Triton kernels make Thinformer Express practical on GPUs

Knowl 8 — Thinformer Express accelerates long-context prefill

Knowl 9 — Express-assisted KV compression reduces runtime while preserving task quality

Knowl 10 — Thinformer Express improves memory and runtime trade-offs in long-form decoding

References

Citation

BibTeX

Access the Paper