Efficient Clustering of Transformer-Induced Slate Spaces

Online platforms repeatedly evaluate large collections of ordered slates for recommendation, simulation, indexing, and downstream optimization. Clustering can replace similar decisions with a small set of prototypes, reducing the cost of these repeated tasks. However, clustering the original item embeddings is insufficient: after self-attention, an item's representation depends on the other items displayed with it. Consequently, a catalog of $n$ items induces $n^m$ contextualized representations of $m$-item slates, making direct clustering infeasible. We study this implicit clustering problem for a trained single-layer, single-head self-attention model and introduce *Lifted Centers*. Under bounded-norm assumptions and using a constant-factor weighted $k$-means routine, the returned centers satisfy $\operatorname{ALG}_k \leq O(m)\operatorname{OPT}_k+O(m\delta^2)$, where $\operatorname{OPT}_k$ is the optimal $k$-means cost over the complete slate space and $\delta$ measures the maximum within-group variation in the model parameters that determine attention. Given the catalog partition, the runtime is $O(n)$ when the other parameters are fixed. Experiments on embeddings learned from real Trivago hotel-search activity and Spotify playlist data show that the practical variant consistently outperforms two computational-budget-matched sampling baselines.