Imagen de Portada

The I/O Complexity of Attention, or How Optimal is Flash Attention?

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Saha, Barna, Ye, Christopher
Formato:	Preprint
Publicado:	2024
Materias:	Machine Learning Computational Complexity Data Structures and Algorithms Information Theory
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Learning Partitions with Optimal Query and Round Complexities
por: Black, Hadley, et al.
Publicado: (2025)

Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs
por: Black, Hadley, et al.
Publicado: (2025)

Computation-Utility-Privacy Tradeoffs in Bayesian Estimation
por: Chen, Sitan, et al.
Publicado: (2026)

Optimal certification of constant-local Hamiltonians
por: Lee, Junseo, et al.
Publicado: (2025)

Optimality of Frequency Moment Estimation
por: Braverman, Mark, et al.
Publicado: (2024)

Simple algorithms to test and learn local Hamiltonians
por: Gutiérrez, Francisco Escudero
Publicado: (2024)

Hamiltonian Property Testing
por: Bluhm, Andreas, et al.
Publicado: (2024)

AdaBoost is not an Optimal Weak to Strong Learner
por: Høgsgaard, Mikael Møller, et al.
Publicado: (2023)

Linear Index for Logarithmic Search-Time for any String under any Internal Node in Suffix Trees
por: Al-okaily, Anas
Publicado: (2024)

List Decoding Expander-Based Codes up to Capacity in Near-Linear Time
por: Srivastava, Shashank, et al.
Publicado: (2025)

Tight Bounds for Noisy Computation of High-Influence Functions, Connectivity, and Threshold
por: Gu, Yuzhou, et al.
Publicado: (2025)

Improved Decoding of Tanner Codes
por: Zhou, Zhaienhe, et al.
Publicado: (2025)

An $Ω( (\log n / \log \log n)^2 )$ Cell-Probe Lower Bound for Dynamic Boolean Data Structures
por: Ko, Young Kun
Publicado: (2026)

The Sample Complexity of Replicable Realizable PAC Learning
por: Larsen, Kasper Green, et al.
Publicado: (2026)

The Computational Complexity of Almost Stable Clustering with Penalties
por: Khodamoradi, Kamyar, et al.
Publicado: (2025)

The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem
por: Blanc, Guy, et al.
Publicado: (2024)

Cascaded Learned Bloom Filter for Optimal Model-Filter Size Balance and Fast Rejection
por: Sato, Atsuki, et al.
Publicado: (2025)

Optimal Trace Distance and Fidelity Estimations for Pure Quantum States
por: Wang, Qisheng
Publicado: (2024)

Sample-Optimal Quantum Estimators for Pure-State Trace Distance and Fidelity via Samplizer
por: Wang, Qisheng, et al.
Publicado: (2024)

Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems
por: Blanchard, Moise
Publicado: (2024)

Fine-Grained Optimality of Partially Dynamic Shortest Paths and More
por: Saha, Barna, et al.
Publicado: (2024)

Derandomizing Multi-Distribution Learning
por: Larsen, Kasper Green, et al.
Publicado: (2024)

On Computationally Efficient Multi-Class Calibration
por: Gopalan, Parikshit, et al.
Publicado: (2024)

Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps
por: Kelner, Jonathan, et al.
Publicado: (2024)

Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials
por: Luo, Yuetian, et al.
Publicado: (2023)

Explicit Good Codes Approaching Distance 1 in Ulam Metric
por: Goldenberg, Elazar, et al.
Publicado: (2024)

The Fine-Grained Complexity of Gradient Computation for Training Large Language Models
por: Alman, Josh, et al.
Publicado: (2024)

Superconstant Inapproximability of Decision Tree Learning
por: Koch, Caleb, et al.
Publicado: (2024)

Fast decision tree learning solves hard coding-theoretic problems
por: Koch, Caleb, et al.
Publicado: (2024)

Adaptive and oblivious statistical adversaries are equivalent
por: Blanc, Guy, et al.
Publicado: (2024)

Private graphon estimation via sum-of-squares
por: Chen, Hongjie, et al.
Publicado: (2024)

Omnipredictors for Regression and the Approximate Rank of Convex Functions
por: Gopalan, Parikshit, et al.
Publicado: (2024)

On the Power of Interactive Proofs for Learning
por: Gur, Tom, et al.
Publicado: (2024)

Low-degree phase transitions for detecting a planted clique in sublinear time
por: Mardia, Jay, et al.
Publicado: (2024)

Hardness of Learning Boolean Functions from Label Proportions
por: Guruswami, Venkatesan, et al.
Publicado: (2024)

Exact and Approximate Algorithms for Polytree Learning
por: Harviainen, Juha, et al.
Publicado: (2026)

Differentially Private Verification of Distribution Properties
por: Du, Elbert, et al.
Publicado: (2026)

Efficient and Private Property Testing via Indistinguishability
por: Dwork, Cynthia, et al.
Publicado: (2025)

A Distributional-Lifting Theorem for PAC Learning
por: Blanc, Guy, et al.
Publicado: (2025)

Low-Degree Method Fails to Predict Robust Subspace Recovery
por: Jia, He, et al.
Publicado: (2026)