Near-Optimal Real-Time Personalization with Simple Transformers

Real-time personalization by and large relies on embedding-based models, which enable fast optimization via nearest-neighbors, but fail to capture complex user behavior. Transformer-based models successfully capture such behavior, but are provably hard to optimize. We study simple transformers, i.e. those with a single self-attention layer, and show they still capture rich user behavior despite their simplicity. We then develop a sub-linear time algorithm with near-optimal performance. On large-scale Spotify and Trivago datasets, simple transformers match the accuracy of deeper models while enabling real-time recommendations, improving objective values by over 20% against natural benchmarks.