Vahab S. Mirrokni

Vahab S. Mirrokni

Vahab Mirrokni is a Google Fellow and VP at Google Research, where he co-leads Gemini Data and multiple Agentic and RSI efforts within Gemini and AntiGravity. More broadly, his team drives impact in Algorithms and Optimization areas including GenAI algorithms, large-scale machine learning, data mining, market algorithms, and graph learning.

He received his PhD from MIT in 2005 and his B.Sc. from Sharif University of Technology in 2001. He joined Google Research in 2008, after holding research positions at Microsoft Research, MIT and Amazon.com.

He is the co-winner of a range of paper awards at KDD, ACM EC, PODS, SoCG, Informs OM, and SODA. He also co-led Gemini efforts in achieving Gold medals in IMO’25 and ICPC’25.

Previously, his research areas included algorithms, distributed and stochastic optimization, and computational economics. More recently, he has been working on GenAI algorithms including quantization, sparsity, data and model efficiency, and new architecture design for continual and adaptive learning.

His full publication list by year can be found here.

Authored Publications
Sort By
  • Title
  • Title, descending
  • Year
  • Year, descending
Preview abstract We give a conditional hardness result for the sparse least square regression problem (conjecture 27 in https://jmlr.csail.mit.edu/papers/volume22/20-661/20-661.pdf) View details
Theoretical Perspectives on Data Quality and Synergistic Effects in Pre- and Post-Training Reasoning Models
Adel Javanmard
Baharan Mirzasoleiman
arXiv preprint arXiv:2603.01293 (to appear in ICML 2026) (2026)
Preview abstract We will study a theoretical model (one layer linear self attention with in-context linear task) to rigorously explain several observations (already reported in previous empirical work in the literature) about the characteristics of pretraining and post-training data that are relevant for good performance. Our analysis explain the importance of having a balanced diverse data in pretraining, and hard small set of examples for SFT, and large volume data fro RL. The experiments are on synthetic toy settings and on GPT-2 with synthetic linear regression data. View details
Preview abstract Multi-vector embeddings represent items by point clouds and compare query and document point clouds using Chamfer similarity, whereas single-vector embeddings use ordinary inner products. For singleton queries, Chamfer becomes maximum inner product similarity (MAX-IP). In our setting, MUVERA gives dimension $m^{O(1/\epsilon^2)}$~\cite{dhulipala2024muvera}, whereas the previous lower bound $(\epsilon^2m)^{\Omega(1/\epsilon)}$~\cite{jayaram2026expressive} left a gap between $1/\epsilon$ and $1/\epsilon^2$ in the exponent of $m$. We nearly close this gap. For every fixed $\delta\in(0,1)$, there are constants $A_\delta,c_\delta>0$ such that, for all sufficiently small $\epsilon>0$ and every $m\ge(1/\epsilon)^{A_\delta}$, there exist unit query vectors and document point clouds of at most $m$ unit vectors for which every single-vector approximation of all pairwise MAX-IP values to additive error $\epsilon$ has dimension \[ D \ge m^{c_\delta/\epsilon^{2-2\delta}}. \] This holds even for fully data-dependent representations chosen after seeing the dataset. It also applies to Chamfer because all queries are singletons. Since $\delta$ can be arbitrarily small, the exponent approaches the $O(1/\epsilon^2)$ dependence of the upper bound. The proof combines Sherstov's pattern matrix method with polynomial-size, constant-width DNF formulas computing functions of approximate degree $\Omega(k^{1-\delta})$. Uniform-width padding and a block encoding create an $\Omega(\epsilon)$ gap. A dummy coordinate then equalizes all false inputs, yielding a unit-sphere MAX-IP matrix that is an exact two-valued affine image of the DNF pattern matrix with gap at least $8\epsilon$. This allows the approximate-rank bound to apply. The proof was first obtained using a fully automated Gemini-based agentic system developed internally at Google. The authors have verified the proof and edited it for clarity of presentation. View details
Preview abstract Quantizing high-dimensional vectors is fundamental to similarity search, distributed learning, and model compression. Feng, Indyk, Kapralov, Krachun, and Prokhorov established sharp guarantees for an unbiased dithered quantizer based on a randomized Hadamard transform~\cite{feng2026provable}. Their $1/d$-scale inner-product estimator, however, uses a second randomized transform and residual quantization, increasing both communication and the leading constant in the proved bound. We show that this extra stage is unnecessary: pairwise-independent dithers across Hadamard coordinates suffice. The resulting unbiased single-stage estimator uses $b$ bits per coordinate and achieves \[ \mathbb{E} |\langle y,\widehat{x}-x\rangle|^{2} \leq \left(\frac{3\pi\sqrt{3}}{2}+o(1)\right) \frac{\|y\|_2^2}{d\,4^b} \] as $b\to\infty$, with a dimension-free $o(1)$ term uniform over unit inputs and fixed queries. Compared with the two-stage construction, it saves approximately $3.72d$ bits per encoded vector and reduces the leading upper-bound constant by a factor of approximately $5.93$. View details
Preview abstract We study strong coresets for $\ell_p$ subspace approximation in the regime $p>2$. The best previous dimension-independent construction, due to Woodruff and Yasuda~\cite{WY25}, has size $\widetilde{O}_p(k^{p/2}\epsilon^{-p})$ and runs in nearly input-sparsity time. We give a refined analysis of root ridge leverage score sampling that improves the coreset size to $\widetilde{O}_p(k^{p/2}\epsilon^{-2})$. The analysis uses a threshold-aware aggregation of the truncated sampling probabilities to obtain a sharper recursive row-count bound. The resulting construction retains the running time $\widetilde{O}(\mathrm{nnz}(A)+d^\omega)$ of the underlying sampling framework. View details
Preview abstract Quantization methods have significantly improved the compute and memory efficiency of Large Language Model (LLM) training. However, existing approaches still rely on accumulating their updates into high precision: concretely, gradient updates must be applied to a high-precision weight buffer, known as \textit{master weights}. This buffer introduces substantial memory overhead, particularly for Sparse Mixture of Experts (SMoE) models, where model parameters and optimizer states dominate memory usage. In this work, we introduce the Error-Compensating Optimizer (ECO), which \textit{for the first time} enables the complete elimination of master weights by directly accumulating updates into quantized parameters, by leveraging existing optimizer states. ECO quantizes the weights after every gradient step and injects the resulting quantization error into the optimizer's momentum buffer, creating an error-feedback loop with zero additional memory overhead for quantization. Beyond its practical efficiency, ECO comes with theoretical guarantees. Specifically, under standard assumptions, naive master weight removal can lead to unbounded drift from the ideal parameter trajectory, whereas ECO provably bounds this drift, ensuring stable convergence. We validate ECO across a range of models, including small transformers (30M--800M), Gemma-3 1B, and an SMoE 2.1B model, using FP8 quantization. In all cases, ECO achieves near-lossless accuracy compared to high-precision baselines. For large SMoE models, ECO reduces memory usage by up to 25\%, establishing a new Pareto frontier for the trade-off between static memory and training loss. View details
Titans: Learning to Memorize at Test Time
Ali Behrouz
Peilin Zhong
The Thirty-ninth Annual Conference on Neural Information Processing Systems (NeurIPS) (2025)
Preview abstract Over more than a decade there has been an extensive research effort of how effectively utilize recurrent models and attentions. While recurrent models aim to compress the data into a fixed-size memory (called hidden state), attention allows attending to the entire context window, capturing the direct dependencies of all tokens. This more accurate modeling of dependencies, however, comes with a quadratic cost, limiting the model to a fixed-length context. We present a new neural long-term memory module that learns to memorize historical context and helps an attention to attend to the current context while utilizing long past information. We show that this neural memory has the advantage of a fast parallelizable training while maintaining a fast inference. From a memory perspective, we argue that attention due to its limited context but accurate dependency modeling performs as a short-term memory, while neural memory due to its ability to memorize the data, acts as a long-term, more persistent, memory. Based on these two modules, we introduce a new family of architectures, called Titans, and present three variants to address how one can effectively incorporate memory into this architecture. Our experimental results on language modeling tasks show that Titans are more effective than Transformers and recent modern linear recurrent models. They further can \emph{effectively} scale to larger than 2M context window size with higher accuracy in needle-in-haystack tasks compared to baselines. View details
Preview abstract Transformers, while powerful, suffer from quadratic computational complexity and the ever-growing Key-Value (KV) cache of the attention mechanism. This paper introduces Trellis, a novel Transformer architecture with bounded memory that learns how to compress its key-value memory dynamically at test time. Trellis replaces the standard KV cache with a fixed-size memory and train a two-pass recurrent compression mechanism to store new keys and values into memory. To achieve this, it leverages an online gradient descent procedure with a forget gate, enabling the compressed memory to be updated recursively while learning to retain important contextual information from incoming tokens at test time. Extensive experiments on language modeling, common-sense reasoning, recall-intensive tasks, and time series show that the proposed architecture outperforms strong baselines. Notably, its performance gains increase as the sequence length grows, highlighting its potential for long-context applications. View details
Preview abstract Over more than a decade there has been an extensive research effort of how effectively utilize recurrent models and attentions. While recurrent models aim to compress the data into a fixed-size memory (called hidden state), attention allows attending to the entire context window, capturing the direct dependencies of all tokens. This more accurate modeling of dependencies, however, comes with a quadratic cost, limiting the model to a fixed-length context. We present a new neural long-term memory module that learns to memorize historical context and helps an attention to attend to the current context while utilizing long past information. We show that this neural memory has the advantage of a fast parallelizable training while maintaining a fast inference. From a memory perspective, we argue that attention due to its limited context but accurate dependency modeling performs as a short-term memory, while neural memory due to its ability to memorize the data, acts as a long-term, more persistent, memory. Based on these two modules, we introduce a new family of architectures, called Titans, and present three variants to address how one can effectively incorporate memory into this architecture. Our experimental results on language modeling tasks show that Titans are more effective than Transformers and recent modern linear recurrent models. They further can \emph{effectively} scale to larger than 2M context window size with higher accuracy in needle-in-haystack tasks compared to baselines. View details
Preview abstract Modern foundation models are trained on diverse datasets to enhance generalization across tasks and domains. A central challenge in this process is determining how to effectively mix and sample data from multiple sources. This naturally leads to a multi-task learning (MTL) perspective. While prior work in MTL has emphasized mitigating gradient conflicts, we observe that large-scale pre-training scenarios-such as multilingual or multi-domain training-often exhibit little to no gradient conflict. Motivated by this observation, we propose PiKE (Positive gradient interaction-based K task weights Estimator), an adaptive data mixing algorithm that dynamically adjusts sampling weights during training. PiKE exploits non-conflicting gradient interactions to minimize a near-tight upper bound on the average loss decrease at each step, while incurring negligible computational overhead. We provide theoretical convergence guarantees and show that PiKE outperforms static and nonadaptive mixing baselines. Furthermore, we extend PiKE to promote balanced learning across tasks. Extensive experiments on large-scale language model pre-training confirm that PiKE achieves faster convergence and improved downstream performance compared to existing approaches. View details
×