[NeurIPS 2022] Transformers meet Stochastic Block Models: Attention with Data-Adaptive Sparsity and Cost

Proposes SBM-Transformer, a Transformer model that uses a Stochastic Block Model to data-adaptively choose attention sparsity and computational cost, enabling linear complexity in the number of sampled edges while preserving universal approximability.