Every Bit Counts: A Theoretical Study of Precision–Expressivity Tradeoffs in Quantized Transformers Sayak Chakrabarti, Toniann Pitassi, Josh Alman Abstract Quantization reduces the numerical precision of Transformer computations and is widely used to accelerate inference, yet its effect on expressivity remains poorly characterized. We demonstrate a fine-grained theoretical tradeoff between expressivity and precision: For every p p we exhibit a function Γ \Gamma , inspired by the equality function, and prove that a one-layer softmax Transformer can compute Γ \Gamma , with p p bits of precision, but not with p − 1 p\!-\!1 bits of precision. This result concretely explains the widely observed phenomenon of empirical loss of expressivity when quantization is used. Practically, it suggests that tasks requiring equality-like comparisons (exact match, membership, etc.) are especially sensitive to quantization. Dropping even one bit can cross a threshold where the model cannot represent the needed comparison reliably. Thus, it paves the way for developing heuristics that will help practitioners choose how much quantization is possible: the precision should be chosen as a function of the length of equality to be checked for the specific task. Our proofs combine explicit finite-precision Transformer constructions with communication-complexity lower bounds, yielding a tight “one-bit” threshold. 1 Introduction Multi-layer Transformers ( 79 ) are at the core of recent advances in large language models (LLMs). They have become the default backbone for sequence modeling across natural language processing and beyond, including image classification ( 22 ) , speech recognition ( 25 ) , protein sequencing ( 66 ) , and robotics ( 12 ) . Their success is often attributed to their ability to capture pair-wise correlations between tokens. However, this comes with a price: the time and space complexity of this model scale quadratically in the sequence length, which requires heavy memory and compute resources for training and inference. In order to improve efficiency of these models, there is a large body of work that studies approximation algorithms to reduce the cost of attention and long-context processing (e.g., Longformer ( 5 ) , BigBird ( 92 ) , Reformer ( 39 ) , Performer ( 15 ) ), Hyperattention ( 27 ) , KDEformer ( 93 ) . Quantization. A popular line of work in this area targets the memory footprint of Transformers by focusing on systems-level efficiency via compression (low precision approximation). Prior work has explored parameter sharing and factorized embeddings to reduce redundant storage ( 43 ) , structured pruning of attention heads to enable efficient mapping to hardware ( 52 ; 80 ) , systems-aware attention implementations and scheduling to reduce activation and IO overhead ( 17 ; 18 ) , KV-cache reductions such as multi-query attention and grouped-query attention that substantially shrink per-token state ( 73 ; 2 ) . Among compression techniques, quantization , the process of limiting the numerical precision of a deep learning model, has emerged especially powerful and practical. It reduces the arithmetic and memory costs of Transformer inference via low-bit kernels (hardware-optimized implementations of core operations such that matrix multiplications that operate directly on low precision numbers), and quantized formats that define how tensors are stored using low-bit integers, plus scaling metadata. Intuitively, quantization should reduce the expressive power of the model, and the goal of this paper is to formally study the tradeoff between quantization and expressivity. Prior Empirical Work on Quantization. A large body of work studies reduced-precision deployment, including weight-only or parameter quantization ( 23 ; 45 ; 21 ) , activation quantization ( 85 ; 89 ; 14 ) , or dynamic or on-the-fly quantization schemes ( 38 ) , where the values are quantized but arithmetic is often performed in regular precision. In this paper, we are interested in quantization that also uses low-precision arithmetic, i.e., we treat limited numerical precision on core operations, and ask what functions remain computable when each primitive operation is carried out with restricted bit complexity. Low-precision arithmetic makes computations much faster, and has been widely used in deep-learning and Transformer literature. There are two commonly used formats to represent numbers: the fixed-point precision format and the floating-point precision format. We will formally define these in Appendix A , but we present an overview here. The fixed-point precision format for p bits works as: first, the values of the numbers are scaled to bring them within the range -(2^{p-1}-1) to (2^{p-1}-1) , and then rounded off to the closest integer (p-1) -bit integer. This (p-1) -bit integer along with one sign bit gives the representation of the number in p -bit fixed-point precision format. Another commonly used precision format in computing is the floating-point precision format. A number in this format is represented by a mantissa \mu and an exponent \varepsilon , and represents the number \pm 1.\mu\times 2^{\pm\varepsilon} . Each of the mantissa and the exponent has one sign bit each, giving the total number of bits of precision as 1+|\mu|+1+|\varepsilon| . Note that floating-point precision format can simultaneously represent much larger and much smaller non-zero values than fixed-point precision as it stores numbers with a variable exponent. However, this often introduces rounding quirks (many decimals like 0.1 aren’t exact), and equality comparisons can be tricky. On the other hand, with fixed-point precision format, every represented value is equally scaled by a constant factor, so the spacing between representable numbers is uniform across the entire range, thereby giving better predictability, but often leading to either large numbers being difficult to represent or small numbers being rounded to zero. Due to the advantages and disadvantages of both precision formats, they have been widely studied. Quantized computations with fixed point precision often employ 8 bits or 4 bits, which are represented as INT8 or INT4, respectively. For example, ( 19 ; 67 ) perform arithmetic for Transformers using INT8 by giving specific algorithms for operations like matrix multiplication and softmax computation. Other examples of fixed-point precision arithmetic in INT8 include ( 85 ; 89 ; 38 ; 91 ) and in INT4 include ( 23 ; 45 ; 21 ; 72 ; 20 ; 24 ) . Quantization to low-bit floating-point format is also commonly performed on Transformers and other neural networks. Usually, quantized floating-point numbers use 16 bit of precision (FP16), or 8 bits of precision (FP8). Some of the works of quantization on FP16 include ( 53 ; 74 ; 63 ; 4 ) and on FP8 include ( 54 ; 60 ; 44 ) . Some more works study even lower precision, even as low as one-bit quantizations ( 16 ; 29 ; 30 ; 96 ; 82 ; 46 ) . Other works that deploy low-precision arithmetic to speed up deep-learning models include ( 16 ; 65 ; 31 ; 58 ; 89 ; 33 ; 91 ; 6 ; 10 ) . With the growing popularity of quantization, modern hardware now enables dedicated low-precision matrix multiplication primitives, e.g., NVIDIA Tensor Cores support FP8 as well as INT8/INT4 MMA variants, while CPUs increasingly provide INT8 dot-product and matrix-multiply extensions (e.g., Intel AMX and Arm’s I8MM). To facilitate quantization on modern hardware, Graphcore, AMD, and Qualcomm published their FP8 specification in ( 57 ) and NVIDIA, Arm, and Intel followed ( 54 ) . Both works considered FP8 as E4M3 (4 exponent bits, 3 mantissa bits) and E5M2 (5 exponent bits, 2 mantissa bits). Despite being a standard engineering tool, the theoretical implications of quantization are less clear: what capabilities are preserved by lowering precision, and what capabilities are fundamentally lost? As observed in previous works, quantization comes with a price in terms of a loss in expressivity. ( 89 ) reports that for BERT-base on GLUE 1 1 1 GLUE ( 81 ) is a collection of NLP tasks that requires “understanding” by the language model. , quantizing from full precision to INT8 activations drops the average accuracy from 84.06\% to 79.61\% , and quantizing to even lower precision like INT4/INT8 and activations to FP16 drops the accuracy to as low as 33.11\% . Similarly, outliers (activation values that occasionally spike to very large numbers) and their adverse impact on quantization was observed by ( 84 ) , where they quantized BERT-large to INT8 for GLUE benchmark tasks and recorded an accuracy drop of around 13\% . Our main result, Theorem 1.1 below, can help explain this phenomenon: we prove that equality checks require high-precision Transformers, which means that achieving high accuracy on datasets like GLUE, which consist of tasks similar to equality testing like checking semantic equivalence and paraphrasing, also needs high precision. Usually parameters are quantized after training in usual precision format, which is called post-training quantization (PTQ) ( 85 ; 55 ) . In practice, if PTQ suffers high accuracy loss, the accuracy can sometimes be recovered by fine tuning, e.g., quantization aware training (QAT) where, at every epoch, the model is updated in usual precision and then quantized ( 31 ; 96 ; 14 ) , and other fine tuning methods like ( 20 ; 86 ; 32 ) . The success of fine-tuning approaches for improving the accuracy raises a fundamental question: Does quantization necessarily reduce the expressive power of the model, or can such techniques always recover the full expressive power? This paper addresses that gap. More specifically, we show that the loss in expressivity is provably unavoidable: we show that even losing a single bit of precision must dramatically reduce a model’s expressive power for important tasks, regardless of what training, fine-tuning, or other techniques are used to find the weights. Theoretical Understanding of Precision. Prior work has studied the theory of numerical precision in Transformers, but only at a much coarser level than we consider here. These results have primarily studied which classes from circuit complexity theory can capture Transformers with different amounts of precision, but these prior results are insensitive to polynomial blowups in the amount of precision. (By contrast, our results here will even demonstrate a loss in expressivity from losing a single bit of precision.) For example, ( 48 ; 49 ; 77 ) showed that Transformers using precision logarithmic in the number of tokens can be computed using TC0 circuits 2 2 2 A TC0 circuit is a Boolean circuit of polynomial size and constant depth consisting of AND, OR, NOT and threshold gates. . Later work of ( 13 ) improved this result to more expressive Transformers that use polynomial precision. When the precision is restricted to rational numbers, ( 28 ) showed that even AC0 circuits 3 3 3 AC0 circuits are like TC0 circuits but without threshold gates. can simulate hard-attention Transformers, a variant on the usual Transformer. Finally, with unbounded precision, Transformers can simulate Turing machines ( 62 ; 61 ; 50 ) . Equality. Our new fine-grained precision results concern the famous equality function, \mathsf{EQ} which takes as input two strings and should output 1 if and only if the strings are exactly equal (syntactically). Equality is a basic task that is ubiquitous across a wide variety of applications, and therefore important for Transformers to be able to quickly solve. For example, it is a basic primitive in databases, e.g., to test whether a particular tracking ID matches the ID of a product, or whether it appears in a list of IDs. It also the primitive underlying many other tasks such as file synchronization (testing whether two files are identical or whether they need to be synchronized), user authentication (testing if a proposed password exactly matches a secret string), and automated theorem proving and testing (which requires reasoning about symbolic objects). This equality function has a history of importance in computer science and has been widely studied, including communication complexity ( 88 ; 56 ) , quantum computing ( 8 ) , hashing ( 47 ) , machine learning ( 75 ; 35 ) , etc. It has also been used to study separations between the expressive power of two-layer Transformers and RNNs by ( 7 ) . One-Layer Transformer Limitations In this paper, we focus on the expressive power of single-layer Transformers, which serve as building blocks of multi-layer Transformer architectures. A single layer is a natural unit for understanding token-to-token interactions and serves as one round of attention-based information routing; stacking layers amounts to composing these rounds. Intuitively, if a single layer can compute a key function f , then an L -layer Transformer could perform more complex tasks which require computing f in sequence L times. Representational strengths and limitations of one-layer Transformers are widely studied, and lower bounds have been established for many problems including Parity and Dyck languages ( 26 ) , Match3 and averaging problems ( 69 ) , induction heads task ( 70 ) , function composition ( 59 ) , counting related tasks ( 90 ) , and function evaluation ( 76 ) . In contrast, very little is proven about multi-layer Transformers; even proving that two-layer Transformers cannot compute key functions appears far beyond current techniques (which are based on communication and circuit complexity approaches, as we discuss more in Section 2 below). The only unconditional lower bound to date was recently established by ( 11 ) , but it is only for decoder-only Transformers, and their proof critically relies on the intricacies of decoder units and do not generalize to Transformers with any encoder units. 1.1 Main Results We first describe what we mean by a Transformer solving a task. The Transformer can be viewed as a function, which takes n tokens as inputs from the alphabet an \Sigma (input tokens), each token embedded to a vector in \mathbb{R}^{d} , where d is the embedding dimension, and outputs n tokens (output tokens). For the inner workings of a Transformer, see Section A.1 . In this paper, we study the ability of Transformers to compute functions of interest. Let us assume that we want to compute a Boolean function f:\Sigma^{n}\rightarrow\{0,1\} . We consider the Transformer to have n+1 input tokens (instead of n ), where the first n input tokens correspond to the n inputs of the function, and the Transformer is expected to output the value of the function in the (n+1) -th (last) output-token. We prove our tradeoff on a function similar to the equality function. For integers m>0 and n>2m , define \mathcal{T}_{\mathsf{EQ}_{m}}^{n}:\{0,1\}^{n}\rightarrow\{0,1\} , where, given n bits as inputs, \mathcal{T}_{\mathsf{EQ}_{m}}^{n}(x_{1},\ldots,x_{n}) will output 1 if x_{i}=x_{m+i} for all i\in[m] . This checks whether the first m input bits are all equal to the next m input bits (and does not care about the remaining input bits). As we described before, computing an equality check is a natural and important component of many natural language processing tasks. Our main result shows exactly how many bits of precision are needed to compute it. Theorem 1.1 (Informal) . For every integer p>0 and n>4p , there exists an input representation such that 1. no one-layer Transformer that uses \leq p-1 bits of fixed-point precision can solve \mathcal{T}_{\mathsf{EQ}_{2p-1}}^{n} , 2. there exists a one-layer Transformer that can solve \mathcal{T}_{\mathsf{EQ}_{2p-1}}^{n} using p bits of fixed-point precision. This is the tightest tradeoff possible: reducing the precision by just one bit degrades the capability of the Transformer to solve equality. Note that contrary to prior works where precision has been considered as a coarse function of n (either constant, logarithmic in n , or polynomial in n ), we do not place any such restrictions on p . The tradeoff works for any value of p . We also prove similar tradeoff results for the floating-point precision format, where we obtain a tight tradeoff for linear Transformers, and an almost tight tradeoff for soft-max Transformers. The function on which this tradeoff is performed is again very similar to the equality function. However, owing to the mantissa and exponent structure of this precision format, constructing an upper bound (a Transformer that solves this variant of equality task) is more difficult. We discuss the challenges here in more detail in Section 2.3 below and, due to space constraints, the formal results have been moved to Appendix C . These results are primarily theoretical and intended to provide a rigorous framework to study the disadvantages of quantization. This is important as an understanding of expressivity loss can guide the design of quantization schemes that incur as much expressivity loss as the task of interest can tolerate. Indeed, it suggests that tasks requiring equality-like comparisons (exact match, membership, etc.) are especially sensitive to quantization. Dropping even one bit can cross a threshold where the model cannot represent the needed comparison reliably. Thus, it paves the way for developing heuristics that will help practitioners choose how much quantization is possible: the precision should be chosen as a function of the length of equality to be checked for the specific task. Moreover, this result concretely explains the widely observed phenomenon of empirical loss of expressivity when quantization is used. As described above, the qualitative difficulty of equality-style tasks under limited precision has been observed in prior works ( 89 ; 84 ) ; our results give a rigorous theoretical explanation for this phenomenon. In Section 3 , we support the theory with simple experiments on controlled datasets for equality checks, showing that single-layer Transformers with enough precision can learn to compute the equality function, and that decreasing the precision also decreases the accuracy. 2 Technique Overview In this section, we give an overview of the main results of precision-expressivity tradeoffs for fixed-point arithmetic. Input Representations. As described before, the function for which we are proving the tradeoff is the Equality function. However, we now discuss how the inputs to the function are represented as input tokens of the Transformer. For an integer n>0 , a Transformer is a function \mathsf{Tf}:\Sigma^{n+1}\rightarrow\Sigma^{n+1}_{out} , that takes as inputs (n+1) input-tokens from the set of alphabets \Sigma , and outputs (n+1) output-tokens from the alphabet set \Sigma_{out} . Given a function, f:\Lambda^{N}\rightarrow\Sigma_{out} , a Transformer \mathsf{Tf}:\Sigma^{n}\rightarrow\Sigma_{out}^{n} is said to compute f for an input representation \mathcal{T}:\Lambda^{N}\rightarrow\Sigma^{n} , for integers N,n>0 , if, when the Transformer is given as input n+1 tokens, where the i -th token is \mathcal{T}(x_{1},\ldots,x_{N})_{i} for i\in[n] , and the (n+1) -th token is r (a placeholder which is a predefined constant and can be considered as zero), outputs the value of f(x_{1},\ldots,x_{N}) in the (n+1) -th token of the output. More specifically, \begin{split}\mathsf{Tf}(\mathcal{T}(x_{1},\ldots,x_{N})_{1},\ldots,\mathcal{T}(x_{1},\ldots,&x_{N})_{n},r)_{n+1}\\ &=f(x_{1},\ldots,x_{n}).\end{split} For example, a simple input representation for n=N and \Lambda=\Sigma can be given by \mathcal{T}(x_{1},\ldots,x_{n})_{i}=x_{i} for all i\in[n] , i.e., each of the i -th input token of the Transformer contains the i -th input to the function x_{i} , and the transformer is expected to compute the value of f(x_{1},\ldots,x_{N}) . Using this definition, we will prove our main results. Here, a Transformer is expected to compute the Equality function, \mathsf{EQ}_{m}(\mathbf{y},\mathbf{z}) , i.e., for given strings \mathbf{y},\mathbf{z}\in\{0,1\}^{m} , the Transformer will output 1 if \mathbf{y}=\mathbf{z} , otherwise 0 . The input representation will be similar to the simple one described above, where the first m tokens will contain one of each bit of \mathbf{y} , followed by the next m tokens which will contain one of each bit of \mathbf{z} , followed by placeholder zeros to fill up the number of input tokens of the Transformer to n+1 . In all the results, the underlying function that the Transformer computes is always Equality \mathsf{EQ}_{m} . However, we modify the input representation somewhat so that testing Equality of two strings can be checked in the required precision format, and to prove lower and upper bounds. Lower Bounds. We prove the lower bounds, i.e., Transformers cannot compute the Equality function, using tools from communication complexity. Similar techniques of proving lower bounds for Transformers have been studied before (including works of ( 59 ; 69 ; 70 ; 90 ; 11 ; 9 ) ), but all of them treat precision as a technical artifact rather than something important. They give lower bounds on the size of the Transformer and present their results as: Hdp should be lower-bounded by some function of n . Recently, ( 41 ) removed this dependence on precision, p , using a concept called Split VC-dimension. However, we demonstrate how this dependence on precision should not be ignored, and it is fundamental in understanding the expressivity of Transformers. Upper Bounds. For the upper bounds, we give an explicit construction of a Transformer to show that Transformers can compute the Equality function (check if \mathbf{y}=\mathbf{z} ) using query dimension d_{q}=3 and value dimension d_{v}=1 . This construction has the basic idea: the numerator of the softmax self-attention is used to check if the first halves of the two strings are equal, and the denominator is used to check if the second halves are equal. This is performed by choosing the embedding function such that the value matrices of the tokens from the first halves of \mathbf{y},\mathbf{z} contribute to the numerator, while the remaining are zeros. For the denominator, the embedding function makes query and key matrices are such that the values of e^{\langle Q_{i},K_{j}\rangle} are small, and ignored for the first half of the strings, while the only contribution to the value of the denominator is from the tokens corresponding to the second halves of \mathbf{y},\mathbf{z} . We use careful low-precision arithmetic to prevent information getting lost due to rounding. An overview of the proofs have been given in the following subsections, and the complete proofs can be found in Appendix B . 2.1 Tradeoff with Fixed-Point Precision: Simple Equality Function First, we show that using a simple input representation, \mathsf{EQ}_{m} can be computed by a Transformer using p bits, but cannot be computed using p-2 bits, where m:=2p-3 . Formally, we start with two strings \mathbf{y},\mathbf{z}\in\{0,1\}^{m} , and are interested in computing the function \mathsf{EQ}_{m}(\mathbf{y},\mathbf{z}) with the promise conditions: • m is odd. • The binary values satisfy \mathbf{y}\leq\mathbf{z} . The input representation \mathcal{T}_{m}^{0}:\{0,1\}^{2m}\rightarrow\{0,1\}^{n} is as follows: 1. \mathcal{T}_{m}^{0}(\mathbf{y},\mathbf{z})_{i}=y_{i} for i\in[m] . 2. \mathcal{T}_{m}^{0}(\mathbf{y},\mathbf{z})_{i+m}=z_{i} for i\in[m] . 3. \mathcal{T}_{m}^{0}(\mathbf{y},\mathbf{z})_{i}=0 for all i\in[2m+1:n] . This input representation essentially implies that the first m tokens contain each bit of \mathbf{y} , the next m tokens contain each bit of \mathbf{z} , and the rest are zeros. The output of the Transformer (the value at the last output token) will be: • 1 if \mathbf{y}=\mathbf{z} and m is odd, • 0 if \mathbf{y}\neq\mathbf{z} and the promise conditions are met, and • don’t care otherwise. With this representation, we prove the following result: Theorem 2.1 (Tradeoff with Fixed-Point Precision for Equality) . For every integer p>0 and every integer n>4p , choosing m=2p-3 , 1. no one-layer Transformer with n tokens having value dimension d_{v}=1 and one head, can compute \mathsf{EQ}_{m} with the input representation \mathcal{T}_{m}^{0} , using p\!-\!2 bits of precision, 2. there exists a one-layer Transformer with n tokens having value dimension d_{v}=1 and one head, that can compute {\mathsf{EQ}_{m}} with the input representation \mathcal{T}_{m}^{0} using p bits of precision in the fixed-point precision format. Even though this is not a tight tradeoff, this is enough to show a separation in real life quantization regimes for fixed-point precision, where computations are usually often on 4,8,16 bits. However, this gap can be bridged to make the tradeoff tight, as will be shown in the next section. The proof of Theorem 2.1 will follow from the following two lemmas. Lemma 2.2 states the lower bound, showing that for our choice of parameter settings ( m=2p-3 ), no single layer Transformer with p-2 bits of precision can compute \mathsf{EQ}_{m} . Lemma 2.3 states the near matching upper bound, showing that \mathsf{EQ}_{m} can be computed using p+1 bits of precision. (Note that since we have set m=2p-3 and m is odd, \lceil m/2\rceil-1=p-2 and \lceil m/2\rceil+1=p .) Lemma 2.2 (Fixed-Point Lower Bound) . Given the input representation \mathcal{T}_{m}^{0} , any one-layer Transformer with d_{v}=1 and H=1 , cannot compute \mathsf{EQ}_{m} with \leq{\lceil m/2\rceil}-1 bits of precision. Lemma 2.3 (Fixed-Point Upper bound) . There exists a one-layer Transformer with d_{v}=1 and H=1 , that uses {\lceil m/2\rceil}+1 bits of fixed-point precision to compute \mathsf{EQ}_{m} in the input representation \mathcal{T}_{m}^{0} . Lemma 2.2 is proven via a reduction to a communication complexity lower bound, similar at a high level to other communication complexity based lower bound proofs for Transformers ( 59 ; 69 ) . Next we give a proof overview for Lemma 2.3 . The full proofs of both Lemmas can be found in Section B.1 . Proof overview. The main idea of this construction is inspired by the proof of the lower bound, where both the numerator and denominator of self-attention are used to transfer information. The construction uses the numerator to check equality in the first half (whether \mathbf{y}_{1:{\lceil m/2\rceil}}=\mathbf{z}_{1:{\lceil m/2\rceil}} ), and then use the denominator to check the rest. For the numerator part, we will choose the embedding such that the final numerator value is equal to the maximum possible value in this representation, 2^{{\lceil m/2\rceil}}-1 , if they are equal. We ensure that by making the summation value is \sum_{i=1}^{n+1}e^{\langle Q_{n+1},K_{i}\rangle}V_{i}=-\mathbf{y}_{1:{\lceil m/2\rceil}}+\mathbf{z}_{1:{\lceil m/2\rceil}}+\underbrace{1\ldots 1}_{{\lceil m/2\rceil}}. In order to obtain this value, we design the embedding and the W^{Q},W^{K},W^{V} matrices in a way such that \sum_{i=1}^{{\lceil m/2\rceil}}e^{\langle Q_{n+1},K_{i}\rangle}V_{i} gives the value -\mathbf{y}_{1:{\lceil m/2\rceil}} , and \sum_{i=m+1}^{m+{\lceil m/2\rceil}}e^{\langle Q_{n+1},K_{i}\rangle}V_{i} gives the value \mathbf{z}_{1:{\lceil m/2\rceil}} . Along with this, there will be a dummy token in the (2m+1) -th index such that e^{\langle Q_{n+1},K_{2m+1}\rangle}V_{2m+1}=2^{{\lceil m/2\rceil}}-1 , and the rest will be zeros. The value of the numerator will be exactly (2^{{\lceil m/2\rceil}}-1) if \mathbf{y}_{1:{\lceil m/2\rceil}}=\mathbf{z}_{1:{\lceil m/2\rceil}} , otherwise infinity (commonly used as float(‘inf’) in PyTorch), which follows from the promise on \mathbf{y},\mathbf{z} . For the denominator, we enforce \sum_{i=1}^{{\lceil m/2\rceil}}e^{\langle Q_{n+1},K_{j}\rangle} and \sum_{i=m+1}^{m+{\lceil m/2\rceil}}e^{\langle Q_{n+1},K_{j}\rangle} are small constants irrespective of \mathbf{y},\mathbf{z} , and summation \sum_{i={\lceil m/2\rceil}+1}^{m}e^{\langle Q_{n+1},K_{j}\rangle}+\sum_{i=m+{\lceil m/2\rceil}+1}^{2m}e^{\langle Q_{n+1},K_{j}\rangle} will be \bar{\mathbf{y}}_{{\lceil m/2\rceil}+1:m}+\mathbf{z}_{{\lceil m/2\rceil}+1:m}+2^{-1} . This is a fixed value if \mathbf{y}_{{\lceil m/2\rceil}+1:m}=\mathbf{z}_{{\lceil m/2\rceil}+1:m} , otherwise a larger value. Summing up, if \mathbf{y}_{1:m}=\mathbf{z}_{1:m} , then the numerator will be (2^{{\lceil m/2\rceil}}-1) and the denominator will be a fixed value 2^{({\lceil m/2\rceil}-1)}-1+2^{-1} , otherwise either the numerator make the output infinity ( float(‘inf’) ), or the denominator will a larger value (therefore the output different from \frac{2^{{\lceil m/2\rceil}}-1}{2^{{\lceil m/2\rceil}-1}-2^{-1}}=2 ), either of which can be detected with a simple MLP layer after the self-attention computation. ∎ 2.2 Tradeoff with Fixed-Point Precision: Theorem 1.1 In this section, we prove a tight one-bit tradeoff. We use the same function \mathsf{EQ}_{m} as before, along with the same promise that m is odd and \mathbf{y}\leq\mathbf{z} . For ease of notation, we consider indexing from -1 up n-2 . The input representation \mathcal{T}_{m}^{1}:\{0,1\}^{2m}\rightarrow\{0,1\}^{n} is defined as follows: 1. \mathcal{T}_{m}^{1}(\mathbf{y},\mathbf{z})_{-1}=0 . 2. \mathcal{T}_{m}^{1}(\mathbf{y},\mathbf{z})_{0}=y_{1} . 3. \mathcal{T}_{m}^{1}(\mathbf{y},\mathbf{z})_{i}=y_{i} for i\in[m] . 4. \mathcal{T}_{m}^{1}(\mathbf{y},\mathbf{z})_{i}=z_{1} for i\in\{m+1,m+2\} . 5. \mathcal{T}_{m}^{1}(\mathbf{y},\mathbf{z})_{m+3}=0 . 6. \mathcal{T}_{m}^{1}(\mathbf{y},\mathbf{z})_{i}=z_{i-m-2} for i\in[m+4:2m+2] . 7. \mathcal{T}_{m}^{1}(\mathbf{y},\mathbf{z})_{i}=0 for all i\in[2m+3:n-2] . Formally, Theorem 1.1 can be stated as follows. Theorem 2.4 (Tight Tradeoff with Fixed-Point Precision) . For every integer p>0 and every integer n>4p , choosing m=2p-1 , 1. no one-layer Transformer with n tokens having value dimension d_{v}=1 and one head, can compute \mathsf{EQ}_{m} with the input representation \mathcal{T}_{m}^{1} , using p-1 bits of precision, 2. there exists a one-layer Transformer with n tokens having value dimension d_{v}=1 and one head, that can compute {\mathsf{EQ}_{m}} with the input representation \mathcal{T}_{m}^{1} using p bits of precision in the fixed-point precision format. As we will see in the proof, padding tokens do increase the expressivity of the Transformer and helps us achieve this exact trade off for this function. On a theoretical standpoint, using padding tokens do indeed improve the expressivity of Transformers was also proved by ( 51 ) . In our case, we use this representation to prevent overflow as we are dealing with the exact number of bits that can be used to compute the function. We first state the lower bound present in Section B.2 . Lemma 2.5 (Lower Bound) . Given the input representation \mathcal{T}_{m}^{1} , any one-layer Transformer with d_{v}=1 and H=1 that computes \mathsf{EQ}_{m} requires precision \geq{\lceil m/2\rceil} bits. Now, we prove the existence of a Transformer with precision {\lceil m/2\rceil} bits which actually computes T_{m} . Lemma 2.6 (Upper Bound) . There exists a one-layer Transformer with d_{v}=1 and H=1 , that uses {\lceil m/2\rceil} bits of fixed-point precision to compute \mathsf{EQ}_{m} in the input representation \mathcal{T}_{m}^{1} . Proof overview. The construction is similar to the proof of Lemma 2.3 , where the numerator of the self-attention checks equality in the first half (whether \mathbf{y}_{1:{\lceil m/2\rceil}}=\mathbf{z}_{1:{\lceil m/2\rceil}} ), and then the denominator checks the rest. For the numerator part, we will choose the embedding such that the final numerator value is equal to one if they are equal. We make the summation value \sum_{i=-1}^{n+1}e^{\langle Q_{n+1},K_{i}\rangle}V_{i}=\mathbf{y}_{1:{\lceil m/2\rceil}}-\mathbf{z}_{1:{\lceil m/2\rceil}}+1 , by ensuring \sum_{i=-1}^{{\lceil m/2\rceil}-1}e^{\langle Q_{n+1},K_{i}\rangle}V_{i} gives \mathbf{y}_{1:{\lceil m/2\rceil}} , and \sum_{i=m}^{m+{\lceil m/2\rceil}}e^{\langle Q_{n+1},K_{i}\rangle}V_{i} gives \mathbf{z}_{1:{\lceil m/2\rceil}} . However, this is not directly possible as before, since \mathbf{y}_{1:{\lceil m/2\rceil}},\mathbf{z}_{1:{\lceil m/2\rceil}} use {\lceil m/2\rceil} bits, but in {\lceil m/2\rceil} bits of fixed-point precision, one bit is allocated to the sign bit, giving us {\lceil m/2\rceil}-1 positions. To circumvent this difficulty, we use a dummy token in the (-1) -th position, such that e^{\langle Q_{n+1},K_{-1}\rangle}V_{-1}=-(2^{{\lceil m/2\rceil}-1}-1) , and is used to add a negative shift to the value of \mathbf{y}_{1:{\lceil m/2\rceil}} in order to bring it to the permissible range of {\lceil m/2\rceil} precision bits. There is one more difficulty, the value \mathbf{y}_{1}2^{{\lceil m/2\rceil}-1} might be infinity while computing \mathbf{y}_{1:{\lceil m/2\rceil}} . In order to prevent this, we split this value amongst two tokens corresponding to 0 and 1 positions, where each of them has the value e^{\langle Q_{n+1},K_{i}\rangle}V_{i}=\mathbf{y}_{1}2^{{\lceil m/2\rceil}-2} . This will give the first part of the summation of the numerator as \sum_{i\in[-1:m]}e^{\langle Q_{n+1},K_{i}\rangle}V_{i}=\mathbf{y}_{1,{\lceil m/2\rceil}}-\underbrace{1\ldots 1}_{{\lceil m/2\rceil}-1}. A similar shift is added to -\mathbf{z}_{1:{\lceil m/2\rceil}} , to obtain: \sum_{i\in[m+1:2m+2]}e^{\langle Q_{n+1},K_{i}\rangle}V_{i}=-\mathbf{z}_{1,{\lceil m/2\rceil}}+\underbrace{1\ldots 1}_{{\lceil m/2\rceil}-1}. Finally, we choose the embedding such that e^{\langle Q_{n+1},K_{2m+3}\rangle}V_{2m+3}=1 , such that the value of the numerator will be exactly 1 if \mathbf{y}_{1:{\lceil m/2\rceil}}=\mathbf{z}_{1:{\lceil m/2\rceil}} , otherwise \leq 0 from the promise on \mathbf{y} and \mathbf{z} . For the denominator, again we ensure that \sum_{i=1}^{{\lceil m/2\rceil}}e^{\langle Q_{n+1},K_{j}\rangle} and \sum_{i=m+1}^{m+{\lceil m/2\rceil}}e^{\langle Q_{n+1},K_{j}\rangle} are small constants irrespective of \mathbf{y},\mathbf{z} , and ignored with respect to the summation \sum_{i={\lceil m/2\rceil}+1}^{m}e^{\langle Q_{n+1},K_{j}\rangle}+\sum_{i=m+{\lceil m/2\rceil}+3}^{2m+2}e^{\langle Q_{n+1},K_{j}\rangle} . This gives the value \bar{\mathbf{y}}_{{\lceil m/2\rceil}+1:m}+\mathbf{z}_{{\lceil m/2\rceil}+1:m} , which is a fixed value for \phi_{{\lceil m/2\rceil}+1:m}=\phi_{m+{\lceil m/2\rceil}+1:2m} , otherwise a larger than that due to the promise. Summing up, if \mathbf{y}=\mathbf{z} , then the numerator will be 1 and the denominator will be a fixed value 2^{({\lceil m/2\rceil}-1)}-1 , otherwise either the numerator will be non-positive or the denominator a larger value (i.e., float(‘inf’) ), either of which can be detected by the final MLP layer. ∎ Proof of Theorem 1.1 . We choose m:=2p-1 . From Lemma 2.5 , \mathsf{EQ}_{m} cannot be computed by a Transformer using \leq{\lceil m/2\rceil}-1=p-1 bits for input representation \mathcal{T}_{m}^{1} , but can be computed by a Transformer using {\lceil m/2\rceil}=p bits (Lemma 2.6 ). ∎ 2.3 Overview of Floating-Point Results We prove similar bounds for floating-point precision format with the same function \mathsf{EQ}_{m} . However, the input representation will be different– instead of each token containing a bit of \mathbf{y} or \mathbf{z} , we will allow each token to contain a tuples, where one-element is a tuple of e-1 bits from either \mathbf{y} or \mathbf{z} (which will be used to directly create the exponent in the floating-point precision format for the Transformer construction in the upper bound), and one more bit (which will contribute to the mantissa). This difficulty arises because, in the floating-point representation, the exponent will be exponentiated twice for computing e^{\langle Q_{i},K_{j}\rangle} , and summation over this to yield another floating-point number is difficult as it might lead to overflow in bounded precision format. This choice of input tokens containing tuples is a fairly known technique, and have been used in other Transformer based problems, including function evaluation where the indices and values are given as tuples ( 76 ) , graph problems where the edges are given as tuples ( 68 ) , higher-order graph Transformers where k -tuples of vertices are used ( 94 ) etc. Indeed, reformatting of inputs is an important technique that can completely alter what a Transformer can learn or represent ( 95 ) . More details and the complete proofs can be found in Appendix C . 3 Experiments In this section, we experimentally verify the theoretical results of this paper. We conduct experiments on the ability of a quantized one-layer transformer to check Equality. This has two main goals: to show that weights allowing such a transformer to compute equality can be learned, and to demonstrate the empirical degradation of accuracy when our results show that the precision is too low to test for equality. Experimental Setup. A simple input representation is used, where the first m tokens contain each of the corresponding m bits of the first string, the next m tokens contain each of the corresponding m bits of the second string, and the last token contains zero and is the placeholder token where the output is expected. A one-layer transformer is trained with number of heads H=2 and embedding dimension d=4 . Other details of the input generation, transformer architecture, training dynamics, quantization procedures, etc., can be found in Appendix D . The experiments were repeated over 10 random seeds. Experimental Results. The communication based lower bounds, presented in this paper and the ones introduced by ( 59 ) , state that if H(d+1)p