Copertina

$k$NN Attention Demystified: A Theoretical Exploration for Scalable Transformers

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autore principale:	Haris, Themistoklis
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Machine Learning Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Fast-MWEM: Private Data Release in Sublinear Time
di: Haris, Themistoklis, et al.
Pubblicazione: (2026)

Compression Barriers for Autoregressive Transformers
di: Haris, Themistoklis, et al.
Pubblicazione: (2025)

Fast Computation of Leave-One-Out Cross-Validation for $k$-NN Regression
di: Kanagawa, Motonobu
Pubblicazione: (2024)

Estimating Hitting Times Locally At Scale
di: Haris, Themistoklis, et al.
Pubblicazione: (2025)

Efficient Algorithms for Adversarially Robust Approximate Nearest Neighbor Search
di: Andoni, Alexandr, et al.
Pubblicazione: (2026)

Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform
di: Alman, Josh, et al.
Pubblicazione: (2025)

A Faster $k$-means++ Algorithm
di: Liang, Jiehao, et al.
Pubblicazione: (2022)

Relax and Merge: A Simple Yet Effective Framework for Solving Fair $k$-Means and $k$-sparse Wasserstein Barycenter Problems
di: Song, Shihong, et al.
Pubblicazione: (2024)

Learning Augmented Graph $k$-Clustering
di: Fan, Chenglin, et al.
Pubblicazione: (2025)

Incremental (k, z)-Clustering on Graphs
di: Cruciani, Emilio, et al.
Pubblicazione: (2026)

Dynamic algorithms for k-center on graphs
di: Cruciani, Emilio, et al.
Pubblicazione: (2023)

Average Sensitivity of Hierarchical $k$-Median Clustering
di: Li, Shijie, et al.
Pubblicazione: (2025)

LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions
di: Kannan, Ravindran, et al.
Pubblicazione: (2024)

Dynamic Consistent $k$-Center Clustering with Optimal Recourse
di: Forster, Sebastian, et al.
Pubblicazione: (2024)

Stochastic $k$-Submodular Bandits with Full Bandit Feedback
di: Nie, Guanyu, et al.
Pubblicazione: (2024)

Fairness in Monotone $k$-submodular Maximization: Algorithms and Applications
di: Zhu, Yanhui, et al.
Pubblicazione: (2024)

Generalized Top-k Mallows Model for Ranked Choices
di: Haddadan, Shahrzad, et al.
Pubblicazione: (2025)

Decision-Theoretic Approaches for Improved Learning-Augmented Algorithms
di: Angelopoulos, Spyros, et al.
Pubblicazione: (2025)

A New Rejection Sampling Approach to $k$-$\mathtt{means}$++ With Improved Trade-Offs
di: Shah, Poojan, et al.
Pubblicazione: (2025)

Scalable Learning of Item Response Theory Models
di: Frick, Susanne, et al.
Pubblicazione: (2024)

Approximating Fair $k$-Min-Sum-Radii in Euclidean Space
di: Drexler, Lukas, et al.
Pubblicazione: (2023)

Metric $k$-clustering using only Weak Comparison Oracles
di: Raychaudhury, Rahul, et al.
Pubblicazione: (2026)

Learning-Augmented Algorithms for $k$-median via Online Learning
di: Hebbar, Anish, et al.
Pubblicazione: (2026)

Differentially Private and Scalable Estimation of the Network Principal Component
di: Khayatian, Alireza, et al.
Pubblicazione: (2025)

Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation
di: Pham, Ninh, et al.
Pubblicazione: (2025)

Linear Programming based Approximation to Individually Fair k-Clustering with Outliers
di: Maity, Binita, et al.
Pubblicazione: (2024)

Efficient Banzhaf-Based Data Valuation for $k$-Nearest Neighbors Classification
di: Zhang, Guangyi, et al.
Pubblicazione: (2026)

Top-k on a Budget: Adaptive Ranking with Weak and Strong Oracles
di: Oettershagen, Lutz
Pubblicazione: (2026)

Dynamic Algorithm for Explainable k-medians Clustering under lp Norm
di: Makarychev, Konstantin, et al.
Pubblicazione: (2025)

Theoretically Grounded Pruning of Large Ground Sets for Constrained, Discrete Optimization
di: Nath, Ankur, et al.
Pubblicazione: (2024)

Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel
di: Chen, Yixin, et al.
Pubblicazione: (2021)

Polynomial-time derivation of optimal k-tree topology from Markov networks
di: Dastjerdi, Fereshteh R., et al.
Pubblicazione: (2024)

Nearly Tight Bounds for Exploration in Streaming Multi-armed Bandits with Known Optimality Gap
di: Karpov, Nikolai, et al.
Pubblicazione: (2025)

Sample-and-Search: An Effective Algorithm for Learning-Augmented k-Median Clustering in High dimensions
di: Cheng, Kangke, et al.
Pubblicazione: (2026)

Misalignment, Learning, and Ranking: Harnessing Users Limited Attention
di: Agarwal, Arpit, et al.
Pubblicazione: (2024)

Positional LSH: Binary Block Matrix Approximation for Attention with Linear Biases
di: Wolfson, Daniel, et al.
Pubblicazione: (2026)

The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Bandits
di: Assadi, Sepehr, et al.
Pubblicazione: (2023)

Provable Quantization with Randomized Hadamard Transform
di: Feng, Ying, et al.
Pubblicazione: (2026)

Constant-Factor Approximations for Doubly Constrained Fair k-Center, k-Median and k-Means
di: Funk, Nicole, et al.
Pubblicazione: (2026)

Learning Mixture Models via Efficient High-dimensional Sparse Fourier Transforms
di: Kalavasis, Alkis, et al.
Pubblicazione: (2026)