9 papers
Approaching I/O-optimality for Approximate Attention
Pál András Papp, Aleksandros Sobczyk, Anastasios Zouzias
We revisit the I/O complexity of attention in large language models. Given query-key-value matrices , and a machine with fast memory size , the g…
Fast and Stable Triangular Inversion for Delta-Rule Linear Transformers
Aleksandros Sobczyk, Gioele Gottardo, Christos K. Matzoros +4
Linear attention has emerged as a cornerstone for efficient long-context architectures, as evidenced by its integration into state-of-the-art open-source models including Qwen3.5/3…
Prefix Sums via Kronecker Products
Aleksandros Sobczyk, Anastasios Zouzias
In this work, we revisit prefix sums through the lens of linear algebra. We describe an identity that decomposes triangular all-ones matrices as a sum of two Kronecker products, an…
Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation
Almudena Carrera Vazquez, Aleksandros Sobczyk
Approximating the -th spectral gap and the corresponding midpoint of an Hermitian matrix with eigenvalues $λ_1\geqλ_2…
Segmented Operations using Matrix Multiplications
Aleksandros Sobczyk, Giuseppe Sorrentino, Anastasios Zouzias
Specialized computational units that perform small matrix multiplications as primitive operations are typically present in modern AI accelerators. However, these Matrix Multiplicat…
The Impact of Partial Computations on the Red-Blue Pebble Game
Pál András Papp, Aleksandros Sobczyk, A. N. Yzelman
We study an extension of the well-known red-blue pebble game (RBP) with partial computation steps, inspired by the recent work of Sobczyk. While the original RBP assumes that we ne…
Quantum Doubly Stochastic Transformers
Jannis Born, Filip Skogh, Kahn Rhrissorrakrai +3
At the core of the Transformer, the softmax normalizes the attention matrix to be right stochastic. Previous research has shown that this often de-stabilizes training and that enfo…
I/O complexity and pebble games with partial computations
Aleksandros Sobczyk
Optimizing data movements during program executions is essential for achieving high performance in modern computing systems. This has been classically modeled with the Red-Blue Peb…
Deterministic complexity analysis of Hermitian eigenproblems
Aleksandros Sobczyk
In this work we revisit the arithmetic and bit complexity of Hermitian eigenproblems. Recently, [BGVKS, FOCS 2020] proved that a (non-Hermitian) matrix can be diagonalized with a r…