2024/06/11 by Zixuan Wang, Stanley Wei, Wang, Zixuan +5 · 2 citations
Engineering · #Advanced Memory and Neural Computing #FOS: Computer and information sciences #Ferroelectric and Negative Capacitance Devices #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Radiation Effects in Electronics
paper · pdf · doi:10.48550/arxiv.2406.06893
openalex publication_date 2024/06/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The transformer architecture has prevailed in various deep learning settings due to its exceptional capabilities to select and compose structural information. Motivated by these capabilities, Sanford et al. proposed the sparse token selection task, in which transformers excel while fully-connected networks (FCNs) fail in the worst case. Building upon that, we strengthen the FCN lower bound to an average-case setting and establish an algorithmic separation of transformers over FCNs. Specifically, a one-layer transformer trained with gradient descent provably learns the sparse token selection task and, surprisingly, exhibits strong out-of-distribution length generalization. We provide empirical simulations to justify our theoretical findings.