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…
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…
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…
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…
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…