mlsanityData to 14 Oct 2026

Towards Sampling Data Structures for Tensor Products in Turnstile Streams

arXiv 2510.03678 ↗First posted 4 Oct 2025cs.LG stat.MLcited by 1

Not on the map. Why?

Abstract (arXiv)

This paper studies the computational challenges of large-scale attention-based models in artificial intelligence by utilizing importance sampling methods in the streaming setting. Inspired by the classical definition of the ℓ2 sampler and the recent progress of the attention scheme in Large Language Models (LLMs), we propose the definition of the attention sampler. Our approach significantly reduces the computational burden of traditional attention mechanisms. We analyze the effectiveness of the attention sampler from a theoretical perspective, including space and update time. Additionally, our framework exhibits scalability and broad applicability across various model architectures and domains.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 86 of its 135 references that are in the map. First posted on arXiv 4 Oct 2025.

Builds on

86 of 135 references.

References · 86

  1. 2017Attention Is All You Needcited by 60,361
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,399
  3. 2020Language Models are Few-Shot Learnerscited by 32,419
  4. 2023LLaMA: Open and Efficient Foundation Language Modelscited by 14,132
  5. 2019RoBERTa: A Robustly Optimized BERT Pretraining Approachcited by 13,372
  6. 2023Llama 2: Open Foundation and Fine-Tuned Chat Modelscited by 13,028
  7. 2022PaLM: Scaling Language Modeling with Pathwayscited by 5,326
  8. 2022OPT: Open Pre-trained Transformer Language Modelscited by 3,512
  9. 2024Gemini 1.5: Unlocking multimodal understanding across millions of tokens of contextcited by 3,224
  10. 2019XLNet: Generalized Autoregressive Pretraining for Language Understandingcited by 2,811
  11. 2023Efficient Streaming Language Models with Attention Sinkscited by 2,186
  12. 2020Transformers are RNNs: Fast Autoregressive Transformers with Linear Attentioncited by 2,022
38 more
  1. 2024Phi-3 Technical Report: A Highly Capable Language Model Locally on Your Phonecited by 1,917
  2. 2020Reformer: The Efficient Transformercited by 1,668
  3. 2019Generating Long Sequences with Sparse Transformerscited by 1,546
  4. 2020Linformer: Self-Attention with Linear Complexitycited by 1,474
  5. 2024ChatGLM: A Family of Large Language Models from GLM-130B to GLM-4 All Toolscited by 1,121
  6. 2024∞Bench: Extending Long Context Evaluation Beyond 100K Tokenscited by 367
  7. 2024DuoAttention: Efficient Long-Context LLM Inference with Retrieval and Streaming Headscited by 288
  8. 2021Inductive Biases and Variable Creation in Self-Attention Mechanismscited by 144
  9. 2021Scatterbrain: Unifying Sparse and Low-rank Attention Approximationcited by 130
  10. 2025FlexPrefill: A Context-Aware Sparse Attention Mechanism for Efficient Long-Sequence Inferencecited by 123
  11. 2021Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformerscited by 102
  12. 2023Fast Attention Requires Bounded Entriescited by 102
  13. 2018Solving Linear Programs in the Current Matrix Multiplication Timecited by 100
  14. 2023HyperAttention: Long-context Attention in Near-Linear Timecited by 85
  15. 2022A very preliminary analysis of DALL-E 2cited by 82
  16. 2021Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Modelscited by 76
  17. 2021Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Timecited by 62
  18. 2023KDEformer: Accelerating Transformers via Kernel Density Estimationcited by 58
  19. 2019Solving Empirical Risk Minimization in the Current Matrix Multiplication Timecited by 53
  20. 2023Attention Scheme Inspired Softmax Regressioncited by 49
  21. 2023Do Transformers Parse while Predicting the Masked Word?cited by 48
  22. 2024D'ej`aVu: KV-cache Streaming for Fast, Fault-tolerant Generative LLM Servingcited by 48
  23. 2020A Mathematical Theory of Attentioncited by 46
  24. 2017Relative Error Tensor Low Rank Approximationcited by 45
  25. 2023An Over-parameterized Exponential Regressioncited by 45
  26. 2020Faster Dynamic Matrix Inverse for Faster LPscited by 44
  27. 2023Solving Regularized Exp, Cosh and Sinh Regression Problemscited by 44
  28. 2023How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computationcited by 44
  29. 2024Challenges in Deploying Long-Context Transformers: A Theoretical Peak Performance Analysiscited by 44
  30. 2020SMYRF: Efficient Attention using Asymmetric Clusteringcited by 43
  31. 2021Approximating How Single Head Attention Learnscited by 38
  32. 2023Algorithm and Hardness for Dynamic Attention Maintenance in Large Language Modelscited by 37
  33. 2023Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimensioncited by 37
  34. 2022A Faster Small Treewidth SDP Solvercited by 36
  35. 2023An Iterative Algorithm for Rescaled Hyperbolic Functions Regressioncited by 35
  36. 2021Fast Sketching of Polynomial Kernels of Polynomial Degreecited by 33
  37. 2022SimA: Simple Softmax-free Attention for Vision Transformerscited by 32
  38. 2023Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Timecited by 31

50 most cited of 86 All 86 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Beyond Averaging in John Ellipsoid Approximation: High-Accuracy Algorithms in the Leverage-Score Modelcited by 0