  Large language models based on the transformer architectures can solve highly
complex tasks. But are there simple tasks that such models cannot solve? Here
we focus on very simple counting tasks, that involve counting how many times a
token in the vocabulary have appeared in a string. We show that if the
dimension of the transformer state is linear in the context length, this task
can be solved. However, the solution we propose does not scale beyond this
limit, and we provide theoretical arguments for why it is likely impossible for
a size limited transformer to implement this task. Our empirical results
demonstrate the same phase-transition in performance, as anticipated by the
theoretical argument. Our results demonstrate the importance of understanding
how transformers can solve simple tasks.
