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.
Figures & tables
Figure 1: Comparison of input embedding methods
Figure 2: Temperatures required for models with dimensions 4, 8, 16, 32 to achieve 100% accuracy using the theoretical construction. The embeddings are based on 1, 2, 4, and 8 frequencies, respectively.
Initialization
d=4
d=8
d=16
d=32
random
1.25
0.37
61.73
1.05
99.77
0.04
99.94
0.03
custom
1.84
1.46
99.86
0.10
99.99
0.00
99.99
0.02
Table 1: Accuracy (mean and SD) for same position dictionaries with n=100,N=1000 , using one attention layer. There is no position embedding.
Figure 3: Discrete Fourier transform analysis of initialized (blue) and learned (red) embeddings. The top row corresponds to models with random initialization with different embedding dimension, while the bottom row represents models with custom initializations. Note the dramatic spike at frequency 1 in the learned embeddings with random initialization for d=8,16 .
n
N
d=4
d=8
d=16
d=32
10
20
13.64
0.30
18.07
0.55
21.25
0.17
21.71
0.09
20
200
3.97
0.30
3.43
0.25
3.62
0.12
4.92
0.16
100
1000
0.45
0.04
0.57
0.04
0.58
0.03
0.47
0.03
Table 2: Accuracy (mean and SD) for consecutive position dictionaries, across varying n and N , using one attention layer. The position embedding is learned.
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Figure 4: Each integer k∈[8] is mapped to a point on the unit circle using the transformation \cs8(k)=[cos(82πk),sin(82πk)] . E.g., k=0 maps to (1,0) , k=2 maps to (0,1) , and so on. Dashed radial lines show the angles between consecutive points.