In modern deep learning, transformer networks have established themselves as a fundamental building block, showcasing their versatility across diverse tasks such as language modeling [40], computer vision [16], and reinforcement learning [27]. At the core of transformers is the selfattention layer [57], a critical component assigning varying attention weights to different segments of the input sequence by discerning relevance between tokens. The success of transformers is closely tied to their representational capabilities in extracting structural information encoded in token embeddings. Empirical observations reveal that transformers trained with GD-based algorithms exhibit biases towards certain algorithmic solutions in some arithmetic tasks [18, 33, 61, 35]. However, few works have presented rigorous mathematical evidence that substantiates their superiority over alternative architectures. In recent work, Sanford et al. [48] introduced a simple task known as the q-sparse averaging for an input context sequence, where the target output is an average of a q-subset of the input tokens, specified in the input.