PaperlayerView exact revision on arXiv

Source-linked AI summary

Saturated Transformers are Constant-Depth Threshold Circuits

William Merrill, Ashish Sabharwal, Noah A. Smith

arXiv:2106.16213v3cs.CLcs.CCcs.LG

TL;DR

The paper asks how much formal-language power transformers retain under attention mechanisms more realistic than hard attention. It analyzes saturated attention and proves that floating-point saturated transformers are bounded by the circuit class TC0.

  • Problem

    Hard-attention transformers have limited formal-language power, motivating analysis of saturated attention as a more realistic attention model.

  • Method

    The paper characterizes saturated transformers by proving circuit-complexity results for rational- and floating-point-valued models.

  • Results

    Saturated transformers recognize languages outside AC0, including majority, while floating-point saturated transformers are contained in TC0.

  • Takeaways & Limitations

    Moving from hard to saturated attention increases the model’s characterized power from AC0 to the more powerful class TC0.

  • Takeaways & Limitations

    Rational-valued models with unconstrained internal functions can simulate arbitrary computation, so the main bound relies on restricting transformer values to floats.

Abstract

from arXiv · show

Transformers have become a standard neural network architecture for many NLP problems, motivating theoretical analysis of their power in terms of formal languages. Recent work has shown that transformers with hard attention are quite limited in power (Hahn, 2020), as they can be simulated by constant-depth AND/OR circuits (Hao et al. 2021). However, hard attention is a strong assumption, which may complicate the relevance of these results in practice. In this work, we analyze the circuit complexity of transformers with saturated attention: a generalization of hard attention that more closely captures the attention patterns learnable in practical transformers. We first show that saturated transformers transcend the known limitations of hard-attention transformers. We then prove saturated transformers with floating-point values can be simulated by constant-depth threshold circuits, giving the class $\mathsf{TC}^0$ as an upper bound on the formal languages they recognize.

1 Introduction

The paper studies transformer language capacity through circuit complexity, focusing on saturated attention because hard attention may not reflect practical attention patterns. It shows saturated transformers exceed AC0 while floating-point saturated transformers remain bounded by TC0.

  • Motivation: Hard-attention circuit results may not transfer cleanly to practical transformers because hard attention is a strong assumption.Uniform attention can support synthetic counting tasks that hard attention does not allow.
  • Saturated attention: Saturated attention generalizes hard attention by allowing tied positions to be averaged, approximating attention patterns acquired through gradient descent.This mechanism qualitatively supports counting behavior observed in transformers.
  • Contributions: The paper shows that saturated transformers recognize languages outside AC0, unlike the known hard-attention characterization.The result establishes greater theoretical power for saturated attention.
  • Contributions: Floating-point saturated transformers are simulated by constant-depth threshold circuits, placing their recognized formal languages within TC0.The paper presents this as an upper bound for a more realistic transformer model.

2 Roadmap

The paper first contrasts rational- and floating-point saturated transformers, then establishes their power beyond hard attention and bounds floating-point models using representation size and threshold-circuit simulation.

  • Model progression: Rational-valued saturated transformers with unconstrained size-preserving internal functions can be universally powerful, while floating-point values provide a more realistic restriction.Floats cannot encode the full input sequence into one position as rationals can.
  • Beyond hard attention: Floating-point saturated transformers recognize the majority language, which lies outside AC0, and experiments validate that transformers can learn it.This demonstrates power beyond the theoretical limitations established for hard-attention transformers.
  • Representation bounds: Each floating-point transformer state vector uses O(log n) bits, while the full state at a layer uses O(n log n) bits.Hierarchical representations may therefore be distributed across state vectors rather than compacted into one vector.
  • Circuit simulation: Bounded representations allow floating-point saturated transformers to be simulated by constant-depth threshold circuits and placed in TC0.The paper interprets saturated attention as extending the network’s implicit gates to threshold gates.
  • Significance: The results aim to provide upper bounds for a more realistic transformer model, with pretrained transformers reported to be approximately saturated.The paper presents this as motivation for refining saturated-attention analyses and comparing soft and saturated attention.

3 Definitions and Notation

The paper formalizes transformers over binary-string datatypes, defines rational and floating-point semantics, specifies transformer computation and recognition, and distinguishes hard from saturated attention.

  • Datatypes: The model represents integers, rationals, and floats as binary strings, with arithmetic operations determined by the datatype semantics.Rationals use sign, numerator, and denominator components; floats constrain denominators to powers of 2.
  • Datatypes: Size-preserving functions produce outputs whose bit length is at most a constant multiple of sufficiently large input lengths.This definition applies equivalently to binary strings, integers, rationals, and floats.
  • Transformer model: A transformer maps token-position pairs to vectors, repeatedly aggregates sequence information through attention heads, and applies internal functions across L layers.The model includes an alphabet, datatype, attention function, layers, heads, embeddings, scoring functions, and feedforward operations.
  • Attention: Hard attention assigns all probability mass to the earliest position attaining the maximum score, whereas saturated attention spreads mass uniformly across tied maxima.Saturated attention reduces to hard attention for one maximizer and becomes uniform when all positions tie.
  • Attention and recognition: The paper uses weak saturated attention for lower bounds and strong saturated attention for upper bounds, showing that even weak saturation exceeds hard attention.Language recognition is defined by linear separability using the first value in the final layer.

4 Circuit Complexity

Circuit complexity analyzes parallel computation through circuit families, measuring their size and depth and classifying languages by allowed gates and resource bounds.

  • Circuits: A circuit is a computation graph whose leaves contain input bits or negations and whose internal nodes are logic gates leading to one output.A circuit family supplies one circuit for each input size.
  • Complexity measures: Circuit size counts gates, depth measures the longest input-to-output path, and complexity classes group languages by gates, size, and depth.The paper uses these measures to define AC0 and TC0.
  • AC0: AC0 uses unbounded-arity AND and OR gates with polynomial size and O(1) depth.The accompanying example tests whether a length-5 binary string contains the bigram 11.
  • TC0: TC0 extends the gate set with threshold gates while retaining unbounded arity, polynomial size, and O(1) depth.A threshold gate returns 1 when at least a specified number of input bits are 1.
  • Class relationships: The classes satisfy AC0 ⊂ TC0 ⊆ NC1, although it is unknown whether the TC0-to-NC1 containment is strict.TC0 properly contains parity, while whether it contains all regular languages remains unknown.
  • Uniformity: The paper uses non-uniform circuit families, so circuits for different input sizes need not be related by a uniform construction.Non-uniform families can recognize some uncomputable languages.

5 Aren’t Transformers Universal?

With rational values and size-preserving internal functions, saturated transformers can recognize every formal language, but this universality relies on unrealistic prime encodings and unconstrained activation functions. Restricting computation through linear-time embeddings or floating-point values yields more bounded characterizations.

  • Rational-valued transformers: Saturated transformers with rational values and size-preserving internal functions can recognize every formal language.The paper denotes this class by ALL.
  • Rational-valued transformers: A one-layer rational-valued transformer encodes input positions with prime-dependent values and aggregates them into a single representation.The construction uses one attention head to sum position-specific values, allowing the input sequence to be recovered.
  • Rational-valued transformers: The construction is unrealistic because it requires prime encoding and uses the activation layer as a black box for recognizing arbitrary, even uncomputable, languages.Practical fixed-weight feedforward subnetworks cannot implement all computable functions when weights are independent of sequence length.
  • Resource-bounded transformers: If the embedding function runs in linear time and internal functions run in T(m) time, recognizable languages fall within TIME(T(m)).The theorem states that the transformer’s complexity matches the complexity of its scoring and activation functions under these assumptions.
  • Resource-bounded transformers: Allowing polynomial-time functions inside the transformer yields exactly P, but arbitrary linear-time embeddings are identified as a major unrealism.These results motivate analyzing a more constrained model with floating-point values.
  • Floating-point transformers: Floating-point constraints prevent universal simulation and support a tighter characterization, with saturated transformers bounded within TC0.The paper contrasts this with rational-valued models and presents TC0 as the relevant constant-depth threshold-circuit class.

6 Beyond Hard Attention, with Floats

Saturated attention lets transformers recognize majority, a language outside AC0, using a single uniform attention head. Experiments show that a one-layer transformer can learn and generalize majority, with performance depending on positional encoding.

  • Majority recognition: Saturated transformers recognize MAJ, which lies outside AC0, establishing greater power than hard-attention transformers.The construction uses a single uniform attention head.
  • Majority recognition: A one-layer transformer recognizes MAJ by uniformly aggregating token representations and comparing the proportions of 1 and 0 tokens.The classifier returns true when #1(w)/n exceeds #0(w)/n.
  • Empirical evidence: A one-layer transformer learns and generalizes MAJ across sequence lengths from n = 100 to n = 500.The no-positional-embedding model generalizes best, followed by learned embeddings.
  • Standard implementation: The construction is implementable with standard transformer parameterizations, including zero query and key parameters for uniform attention.Layer normalization preserves the comparison needed by the final linear classifier.
  • Empirical evidence: Sinusoidal positional embeddings provide the wrong inductive bias for learning MAJ, despite MAJ being within the transformer's capacity.The result reinforces that positional encoding affects generalization on formal-language tasks.

7 Size of Transformer Values

The analysis bounds the size of saturated-transformer values over floats by O(log n). This compact representation supports counting while constraining the information individual vectors can encode.

  • Float sums: 4cz + 2 log n + 1 bounds the size of a sum of n floats whose individual sizes are at most z.This lemma is used to control the representation size of aggregated attention values.
  • Float sums: When each of n values has size O(log n), their sum also has size O(log n).The result provides the key aggregation bound for saturated attention.
  • Transformer values: For transformers with elementwise-size-preserving attention and polynomial-time internal functions, every value vector has size O(log n).The theorem is proved by induction over transformer layers.
  • Transformer values: Saturated transformers with size-preserving internal functions preserve the O(log n) value-size bound at every layer and position.Saturated attention satisfies the elementwise-size-preserving condition.
  • Scope: Softmax attention is not guaranteed to be elementwise-size-preserving because it requires exponentiation, preventing this technique from generalizing directly to soft attention.The limitation concerns the proof technique and its assumptions.
  • Interpretation: O(log n) space lets individual vectors count, but does not let them encode arbitrarily large combinatorial objects such as trees.This bound parallels the hard-attention representation limit while permitting counting behavior.

8 Threshold Circuit Simulation

The paper uses logarithmic-size float representations to simulate saturated transformers with constant-depth threshold circuits. Attention aggregation and feedforward computation are composed into a TC0 circuit.

  • Component circuits: Size-preserving functions on at most c log n input bits are computable by depth-3 polynomial-size Boolean circuits in AC0.This handles bounded-width component functions inside the transformer simulation.
  • Float-sum circuits: A sum of n floats of size at most c log n is computable by a constant-depth, polynomial-size threshold circuit.The construction combines AC0 comparison and reduction with TC0 arithmetic for integer sums.
  • Main theorem: AHAT(F) ⊆ TC0: saturated transformers over floats are simulable by constant-depth threshold circuits.The proof composes TC0 subcircuits for attention with AC0 subcircuits for feedforward computation.
  • Attention simulation: The attention simulation computes scores, selects maximal scores, masks untied positions, sums selected values, counts selected positions, and divides by that count.These operations produce the averaged saturated-attention output.
  • Feedforward simulation: Feedforward subnetworks, embeddings, and the classification head are simulated with AC0 circuits because their inputs have total size O(log n).Their outputs retain O(log n) size under the assumed size-preserving functions.
  • Scope: The paper considers non-uniform AC0 and TC0 rather than uniform circuit families, leaving uniform upper bounds as an open direction.Uniform classes are more directly connected to familiar formal-language classes.

9 Conclusion

Saturated attention is more powerful than hard attention: it reaches beyond AC0, while floating-point saturated transformers remain within TC0. The paper interprets this shift as adding threshold-gate power.

  • Conclusion: Saturated attention recognizes languages outside AC0, whereas hard attention has AC0 as an upper bound.This establishes a theoretical power increase from hard to saturated attention.
  • Conclusion: Floating-point saturated transformers fall within TC0, a more powerful circuit class than AC0.The result characterizes their formal-language recognition limit under floating-point representations.
  • Conclusion: The paper interprets replacing hard attention with saturated attention as augmenting transformers with threshold gates.It identifies comparisons with soft attention and uniform circuit families as open questions.

A Float Division

Float operations are defined in a truncated representation that preserves size, supporting simulation in TC^0. The section checks size preservation for the arithmetic and activation operations used by feedforward networks and layer normalization.

  • A Float Division: Float division uses an approximate multiplicative inverse for integer divisors, then multiplies by the second operand for float divisors.The resulting numerator and denominator are explicitly constructed from the divisor representation.
  • A Float Division: Float division is size-preserving because it is defined using integer multiplication and division, enabling TC^0 simulation.
  • A Float Division: Feedforward networks preserve float size because they use a fixed number of addition, multiplication, division, ReLU, and square-root operations.The argument reduces network size preservation to showing that each operation belongs to S(F).
  • A Float Division: Addition and multiplication preserve size through bounded numerator and denominator growth under the stated representation.The bounds are expressed in terms of the maximum numerator and denominator sizes.
  • A Float Division: Division preserves size because its numerator and denominator grow at most linearly in the operand sizes.
  • A Float Division: ReLU cannot expand its input, while square root is analyzed in truncated form to support layer normalization.The square-root argument bounds the resulting rational components.

C Resource-Bounded Transformers

The resource-bounded transformer class allows linear-time embeddings while assigning the remaining internal functions a time bound T(m). For T(m) ≥ m, its language complexity matches the complexity of those activation functions.

  • C Resource-Bounded Transformers: AHAT(D, T(m)) permits linear-time embeddings and internal functions sℓ,h and fℓ computable in FTIME(T(m)).
  • C Resource-Bounded Transformers: For T(m) ≥ m, transformers in AHAT(D, T(m)) have the complexity of their activation functions.
  • C Resource-Bounded Transformers: The upper inclusion AHAT(D, T(m)) ⊆ TIME(T(m)) follows because embeddings and saturated attention are linear-time, while other internal functions run in FTIME(T(m)).
  • C Resource-Bounded Transformers: The converse construction uses a one-layer transformer with three embedding components to simulate computation in the language class.
  • C Resource-Bounded Transformers: The output function extracts a float numerator in O(m) time and then handles rational and float representations separately.
  • C Resource-Bounded Transformers: For floats, the construction computes the encoded input and feeds w through the indicator function, yielding TIME(T(m)) ⊆ AHAT(D, T(m)).

D Proof from Hao et al. (2022)

The proof constructs constant-depth Boolean circuits for a multi-output function by evaluating each output bit through its disjunctive normal form. The resulting circuit has depth 3 and size at most d(2c + c + 1).

  • D Proof from Hao et al. (2022): The resulting Boolean circuit has depth 3 and size at most d(2c + c + 1).
  • D Proof from Hao et al. (2022): The proof defines d parallel subcircuits, one for each output bit of the function.
  • D Proof from Hao et al. (2022): Each output bit is computed from its disjunctive normal form using negation, conjunction, and disjunction layers.
Loading 2106.16213v3…