  The transformer architecture has catalyzed revolutionary advances in language
modeling. However, recent architectural recipes, such as state-space models,
have bridged the performance gap. Motivated by this, we examine the benefits of
Convolution-Augmented Transformer (CAT) for recall, copying, and length
generalization tasks. CAT incorporates convolutional filters in the K/Q/V
embeddings of an attention layer. Through CAT, we show that the locality of the
convolution synergizes with the global view of the attention. Unlike comparable
architectures, such as Mamba or transformer, CAT can provably solve the
associative recall (AR) and copying tasks using a single layer while also
enjoying guaranteed length generalization. We also establish computational
tradeoffs between convolution and attention by characterizing how convolution
can mitigate the need for full attention by summarizing the context window and
creating salient summary tokens to attend. Evaluations on real datasets
corroborate our findings and demonstrate that CAT and its variations indeed
enhance the language modeling performance.
