Transformers as Transducers (2025)

Abstract: We study the sequence-to-sequence mapping capacity of transformers by relating them to finite transducers, and find that they can express surprisingly large classes of (total functional) transductions. We do so using variants of RASP, a programming language designed to help people “think like transformers,” as an intermediate representation. We extend the existing Boolean variant B-RASP to sequence-to-sequence transductions and show that it computes exactly the first-order rational transductions (such as string rotation). Then, we introduce two new extensions. B-RASP[pos] enables calculations on positions (such as copying the first half of a string) and contains all first-order regular transductions. S-RASP adds prefix sum, which enables additional arithmetic operations (such as squaring a string) and contains all first-order polyregular transductions. Finally, we show that masked average-hard attention transformers can simulate S-RASP.

## introduction transformers @xcite have become a standard tool in natural language processing and vision tasks. they are primarily studied in terms of their expressivity (which functions they can or cannot compute) or learnability (which functions they can or cannot learn from examples). much recent expressivity work views transformers as recognizers of formal languages, by comparing them to automata, circuits, or logic @xcite . here we take the more general view that they compute (total functional) transductions, or functions from strings to strings. transductions are a fundamental object in computer science, with a long history in linguistics and natural language processing @xcite . many empirical tests of transformer reasoning ability use transductions to define algorithmic sequence generation tasks (e.g., @xcite such as tracking shuffled objects, sorting strings, concatenating all k-th letters, or removing duplicates from a list. this paper is the first theoretical analysis, to our knowledge, of transformers as transducers of formal languages (figure 1 ). previous work on transformers as recognizers showed that unique-hard attention transformers correspond to star-free regular languages @xcite ; here, we prove the analogous result for transformers as transducers, that unique-hard attention transformers correspond to aperiodic rational transductions. we then study two superclasses of aperiodic rational transductions that are (also) analogous to star-free regular languages: aperiodic regular transductions (e.g., @xmath0.g., @xmath1. we prove unique-hard attention transformers cannot compute all of these, but average-hard attention transformers can. to do this, we introduce two new variants of rasp @xcite , a programming language designed to make it easier to write down the kinds of computations that transformers can perform. this makes our analysis more simple, concise, and interpretable compared to describing transformers directly using linear algebra. these variants, called b-rasp @xcite and s-rasp, compute more than just the aperiodic regular and aperiodic polyregular transductions, and are interesting in their own right. ## preliminaries we write [n] for the set {0, . . . , n -1}. fix finite input and output alphabets σ and γ. we sometimes use special symbols # and , which we assume do not belong to σ or γ. let σ * and γ * be the sets of strings over σ and γ, respectively. the empty string is denoted ε. for any string w, we number its positions starting from 0, so @xmath2. we write uv or u • v for the concatenation of strings u and v, and w r for the reverse of string w. ## b-rasp and unique hard attention transformers in this section, in order to facilitate our study of transformers and how they relate to classes of transductions, we modify the definition of b-rasp to compute transductions and use it to show that unique-hard attention transformers are equivalent to aperiodic rational transductions. in sections 4 and 5, we consider two extensions: b-rasp[pos] adds position information, and s-rasp also includes an operator for prefix sum. these have various correspondences both with more realistic transformers and with larger classes of transductions. ## conclusions this is, to our knowledge, the first formal study of transformers for sequence-to-sequence transductions, using variants of rasp to connect classes of transformers to classes of transductions. we showed that unique-hard attention transformers and b-rasp compute precisely the class of aperiodic rational transductions; b-rasp[pos] strictly contains all aperiodic regular transductions; and average-hard attention transformers and s-rasp strictly contain all aperiodic polyregular transductions. our finding that b-rasp[pos] and s-rasp can compute transductions outside the corresponding aperiodic class in the transduction hierarchy raises the question of fully characterizing their expressivity, a promising future research direction. five more coordinates are designated to hold the position encoding (pe) and quantities computed from it. descriptive names for these coordinates of the activation vector at position i are as follows. we turn to how s-rasp programs may be simulated. vectors of boolean, symbol, and integer values in an s-rasp program are represented in one or more coordinates of an activation sequence in the transformer. each operation of an s-rasp program computes a new vector of values, and is simulated by one or more transformer encoder layers which compute new values in one or more coordinates of the activation sequence. assume that p f is an s-rasp program computing a transduction f : σ * → γ * with minimum vector length q(ℓ), and that @xmath3. maximization. if s(i, j) is a boolean combination of boolean vectors, to ensure that attention from any position to the default position is 0, we let s base (i, j) = ¬default(j) ∧ s(i, j). this may be computed by dot product attention, as described by @xcite . for the special case where s(i, j) is an equality comparison of integer vectors, say v 1 (i) = v 2 (j): we first use a lookup operation (lem. b.2) with the posq entry of the pe to get the squares of the values in v 2 in coordinate t. let u -1 , u 0 , . . . , u n-1 be the resulting activation sequence. we then use an average hard attention operation with the attention score function breaking ties. if s base (i, j) were used with average hard attention, then the activation values would be averaged for all the satisfying j. to ensure that the maximum satisfying position j has a unique maximum score, we break ties by adding or subtracting s tie (i, j). we must ensure that the values added or subtracted are smaller than the minimum difference between the values for satisfying and non-satisfying positions. for a boolean combination of boolean vectors, let s tie (i, j) = max(0, j/(2n)). then under rightmost attention, the rightmost satisfying j has the highest attention score, which is at least 1, while every non-satisfying j has an attention score less than 1/2. similarly for leftmost attention. for an equality comparison v 1 (i) = v 2 (j), the difference between the maximum score attained and any other score is at least (1/n) 2 by lem. b.1. so if we add or subtract values less than (1/n) 2 , no non-equality score can exceed an equality score. this can be achieved by letting s tie (i, j) = j/(2n 3 ). this is computable using dot product attention because j/n is in the pe for j and (1/n) 2 is in the pe for 1 and can be initially broadcast to all positions. default values. the term s def needs to give the default position an attention score strictly between the possible scores for satisfying and non-satisfying j. for a boolean combination of boolean vectors, the maximum non-satisfying score is less than 1/2 and the minimum satisfying score is at least 1, so if we let s def (i) = 3/4, then the default position has an attention score of 3/4, so it will be the unique maximum in case there are no satisfying positions. for an equality comparison of integer vectors, the maximum non-satisfying score is less than (v 1 (i)/n) 2 -(1/2)(1/n 2 ), and the minimum satisfying score is at least (v 1 (i)/n) 2 , so s def (i) = (v 1 (i)/n) 2 -(1/4)(1/n 2 ) is strictly between these values. the value of (v 1 (i)/n) 2 may be obtained at position i using lem. b.2 with index v 1 (i)/n and the posq coordinate of the pe. thus, the default position is selected when there is no @xmath4; it remains to supply the default value. we use an attention layer with the attention score s given above and value v (j) = default(j) v (j) . let j i be the position that i attends to. then we use a position-wise if/else operation that returns (the simulation of) d(i) if default(j i ) = 1 and v (j i ) otherwise. this concludes the proof of theorem 5.11.