Michael Kapralov

Michael Kapralov

Associate Professor, EPFL

School of Computer and Communication Sciences
Theory Group · EPFL

Contact

michael dot kapralov at epfl dot ch
+41 21 69 38143

EPFL IC · Building INJ (INJ113)
Station 14
CH-1015 Lausanne
Switzerland

Research

I am broadly interested in the design of efficient algorithms. Most of my current work is on designing models that consume little space and/or can be applied in a scalable manner.

Interested in working with me? Apply to the EPFL EDIC PhD program and mention my name on your application. For undergraduate summer internships, see Summer@EPFL.

Postdoctoral opportunities: see the Theory Group’s current call.

Selected recent work

  1. Towards Tight Bounds for Streaming Attention

    SODA 2027 (to appear)

    J. Chen, Y. Feng, P. Indyk, M. Kapralov, E. Kochetkova, B. Prokhorov

    Algorithms and lower bounds for memory-efficient attention and KV-cache compression.

    [Abstract]

    The attention mechanism is a cornerstone of modern transformer architectures. However, its expressive power comes at the cost of quadratic runtime and linear space usage. In particular, the classical transformer architecture explicitly stores all previously seen input elements (tokens) in order to generate the next one. The problem of implementing a transformer in limited space, known as KV cache compression, has received much interest over the past few years, spurring the development of powerful heuristics. Recent works of Haris et al, COLT'25 and Kochetkova et al, NeurIPS'25, formalized KV cache compression as the streaming attention approximation problem, providing both upper bounds (based on discrepancy theory) and information theoretic lower bounds. However, those papers left open a significant gap between the upper and lower bounds. For example, the space usage of their algorithms increases with the precision parameter, but the lower bound does not get stronger.

    In this work, we revisit the streaming attention approximation problem and provide nearly tight bounds on its space complexity. On the algorithmic side, we achieve the result through a surprisingly tight interplay between three distinct methods for kernel density estimation: discrepancy-based coreset constructions (e.g., Charikar-Kapralov-Waingarten'24), the polynomial method (e.g., Greengard-Rokhlin'87, Alman-Song'23), and space partitioning (e.g., Andoni-Laarhoven-Razenshteyn-Waingarten'17, Charikar-Kapralov-Nouri-Siminelakis'20). On the lower bound side, our main technical contribution is a new technique for using the INDEX problem with a large amount of side information that we hope will prove useful in other high dimensional geometric estimation problems.

  2. DASHQuant: Provable Quantization with a Single Randomized Hadamard Transform

    NeurIPS 2026 (to appear)

    Y. Feng, P. Indyk, M. Kapralov, D. Krachun, B. Prokhorov

    Fast vector quantization with provable error guarantees using a single randomized Hadamard transform.

    [Abstract]

    Vector quantization via random projection followed by scalar quantization is a fundamental primitive in machine learning, with applications ranging from similarity search to federated learning and KV cache compression. While dense random rotations yield clean theoretical guarantees, they require $\Theta(d^2)$ time. The randomized Hadamard transform $HD$ reduces this cost to $O(d \log d)$, but its discrete structure complicates analysis and leads to weaker or purely empirical compression guarantees. In this work, we introduce DASHQuant (Dithered Accelerated Single-Hadamard Quantization), a provable variant of this approach. Specifically, the quantizer applies $HD$ to the input vector and adds a random dithering before quantizing, injecting additional randomness at negligible cost. We prove that this approach is unbiased and provides mean squared error bounds that asymptotically match those achievable with truly random rotation matrices. In particular, we prove that a dithered version of TurboQuant, and a special case of EDEN, achieves mean squared error $\bigl(\pi\sqrt{3}/2 + o(1)\bigr) \cdot 4^{-b}$ at $b$ bits per coordinate, where the $o(1)$ term vanishes uniformly over all unit vectors and all dimensions as the number of quantization levels grows.

  3. Streaming Attention Approximation via Discrepancy Theory

    NeurIPS 2025 · Spotlight

    E. Kochetkova, K. Sheth, I. Han, A. Zandieh, M. Kapralov

    BalanceKV: a streaming approach to attention approximation with theoretical guarantees and empirical evaluation.

    [Abstract]

    Large language models (LLMs) have achieved impressive success, but their high memory requirements present challenges for long-context token generation. In this paper we study the streaming complexity of attention approximation, a key computational primitive underlying token generation.

    Our main contribution is BalanceKV, a streaming algorithm for $\epsilon$-approximating attention computations based on geometric process for selecting a balanced collection of Key and Value tokens as per Banaszczyk's vector balancing theory. We complement our algorithm with space lower bounds for streaming attention computation. Besides strong theoretical guarantees, BalanceKV exhibits empirically validated performance improvements over existing methods, both for attention approximation and end-to-end performance on various long context benchmarks.

  4. Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions

    ICLR 2025

    P. Indyk, M. Kapralov, K. Sheth, T. Wagner

    Subquadratic kernel matrix–vector multiplication under sparsity assumptions, motivated by fast attention.

    [Abstract]

    Motivated by the problem of fast processing of attention matrices, we study fast algorithms for computing matrix-vector products for asymmetric Gaussian Kernel matrices $K\in \mathbb{R}^{n\times n}$. $K$'s columns are indexed by a set of $n$ keys $k_1,k_2\ldots, k_n\in \mathbb{R}^d$, rows by a set of $n$ queries $q_1,q_2,\ldots,q_n\in \mathbb{R}^d $, and its $i,j$ entry is $K_{ij} = e^{-\|q_i-k_j\|_2^2/2\sigma^2}$ for some bandwidth parameter $\sigma>0$. Given a vector $x\in \mathbb{R}^n$ and error parameter $\epsilon>0$, our task is to output a $y\in \mathbb{R}^n$ such that $\|Kx-y\|_2\leq \epsilon \|x\|_2$ in time subquadratic in $n$ and linear in $d$. Our algorithms rely on the following modelling assumption about the matrices $K$: the sum of the entries of $K$ scales linearly in $n$, as opposed to worst case quadratic growth. We validate this assumption experimentally, for Gaussian kernel matrices encountered in various settings such as fast attention computation in LLMs. We obtain the first subquadratic-time algorithm that works under this assumption, for unrestricted vectors.

Full publication list

Courses, seminars, schools

People

I have been fortunate to advise or co-advise the following PhD students and postdocs. For former members, parentheses give the first position after EPFL.

Current PhD students

Former students and postdocs

Teaching

Algorithms II (CS-450) · Fall 2026

Previous courses and lecture notes

Program committees

SODA 2026, ITCS 2026, FOCS 2025, RANDOM 2025, SODA 2025, ITCS 2025, ICALP 2024, SOSA 2023, STOC 2022, RANDOM 2021, ICALP 2021, CSR 2021, SOSA 2021, ESA 2020, HALG 2020, SODA 2020, PODS 2019, FSTTCS 2018, ICALP 2017, FOCS 2015.

About

I completed my PhD at Stanford iCME, where I was advised by Ashish Goel. After graduating from Stanford I spent two years as a postdoc at the Theory of Computation Group at MIT CSAIL, working with Piotr Indyk, and then a year at the IBM T. J. Watson Research Center as a Herman Goldstine Postdoctoral Fellow.

I am grateful to the European Research Council for their generous support (ERC Starting Grant SUBLINEAR, 2018-2023).

Publications

Earlier work on imaging