Towards Sampling Data Structures for Tensor Products in Turnstile Streams
This work addresses computational efficiency problems for AI researchers and practitioners using attention mechanisms, though it appears incremental as it builds on existing sampling and attention methods.
This paper tackles the computational challenges of large-scale attention-based models by proposing an attention sampler based on importance sampling in streaming settings, which significantly reduces computational burden with theoretical analysis of space and update time.
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 $\ell_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.