Concise One-Layer Transformers Can Perform Dictionary Lookup

arXiv:2503.22076v2 Announce Type: replace Abstract: While transformers have proven enormously successful in a range of tasks, their fundamental properties as models of computation are not well understood. This paper contributes to the study of the expressive capacity of transformers, focusing on their ability to perform the fundamental computational task of looking up a key in a dictionary. We prove that concise 1-layer transformers (i.e., with a polylog bound on the product of the number of heads, the embedding dimension, and precision) can perform this task when the key and value are represented in the same input position, but, under the p-bit rational precision assumption, cannot perform it when the keys and values are represented in different input positions. Concise 2-layer transformers can perform the task in the second case. Experimentally, we find an alignment between what we have proven can be computed by concise transformers and what can be practically learned.

Source: arXiv cs.LG | 2026-10-28