Abstract: Maximum Inner Product Search (MIPS) is a ubiquitous task in machine learning applications such as recommendation systems. Given a query vector and $n$ atom vectors in $d$-dimensional space, the goal of MIPS is to find the atom that has the highest inner product with the query vector. Existing MIPS algorithms scale at least as $O(\sqrt{d})$, which becomes computationally prohibitive in high-dimensional settings.In this work, we present BanditMIPS, a novel randomized MIPS algorithm that improves the complexity from $O(\sqrt{d})$ to $O(1)$. We also perform experiments on four real-world and synthetic datasets to demonstrate that BanditMIPS outperforms prior state-of-the-art algorithms. Finally, we propose a variant of our algorithm, named BanditMIPS-$\alpha$, which achieves further speedups by employing non-uniform sampling across coordinates.Our algorithm is a standalone subroutine that doesn't require preprocessing, meaning it's easily applicable for downstream tasks such as Matching Pursuit and Fourier analysis which we also show.