The Underlying Logic of Language Models: The Underlying Logic of Language Models: Transformers and Circuits

The Underlying Logic of Language Models: Transformers and Circuits

Speakers: Jiaoda Li, Ryan Cotterell, Franz Nowak, Anej Svete

Conference: ICML 2025

YouTube: https://slideslive.com/39043867

Overview

This talk, delivered by Anej Svete as part of a broader session with Jiaoda Li, Ryan Cotterell, and Franz Nowak at ICML 2025, delves into a foundational understanding of transformer-based language models through the lens of Boolean circuit complexity theory. Moving beyond a purely empirical perspective, the speakers propose a formal framework to analyze the computational capabilities and inherent limitations of transformers by mapping their operations to directed acyclic graphs (DAGs), which are then interpreted as Boolean circuits. The core objective is to precisely characterize what problems transformers can and cannot solve, connecting their architectural properties (like fixed layers and attention mechanisms) to well-established complexity classes such as AC0, TC0, and NC1.

The significance of this work lies in its ability to provide a theoretical underpinning for the empirical successes and failures of large language models (LLMs). By translating the continuous operations of transformers into a binary, logical framework, the talk illuminates why certain tasks are inherently difficult for vanilla transformers while others are readily solvable. Furthermore, it offers a formal explanation for the observed benefits of advanced prompting techniques like Chain-of-Thought (CoT) reasoning and the strategic use of padding tokens, demonstrating how these methods fundamentally alter the computational expressivity of the models. This analytical approach is crucial for guiding future research in LLM architecture design, training methodologies, and effective prompting strategies, moving towards a more principled understanding of AI capabilities.

Background

▶ Watch: Introduction: Transformers as Boolean circuits (0:00)

The foundational understanding of machine learning models often begins with their architectural design and empirical performance. Transformers, with their multi-head attention mechanisms and feed-forward networks, have revolutionized natural language processing. However, a deep theoretical understanding of their intrinsic computational power, independent of specific training data or tasks, remains an active area of research. This talk addresses this gap by drawing a parallel between transformers and Boolean circuits, a concept from theoretical computer science.

A Boolean circuit is a mathematical model of computation represented as a directed acyclic graph (DAG). In this graph, nodes represent logical operations (such as AND, OR, NOT) or input/output bits, and edges represent the flow of information. Key properties of a circuit include its size (number of gates/nodes) and depth (length of the longest path from input to output). A crucial aspect is the concept of a circuit family, which is a sequence of circuits, one for each input length, capable of recognizing a formal language. This allows for the analysis of problems with varying input sizes, analogous to how transformers process sequences of different lengths.

The talk introduces three fundamental circuit complexity classes to categorize the computational power of different circuit families:

• AC0: Characterized by constant depth and unbounded fan-in gates (meaning AND/OR gates can take any number of inputs). Circuits in AC0 can perform operations like binary addition and fixed-precision multiplication.
• TC0: An extension of AC0 that includes majority gates (or threshold gates). A majority gate outputs 1 if more than half of its inputs are 1. This addition significantly boosts computational power, allowing for tasks like parity and majority detection, which are not possible in AC0. TC0 circuits still have constant depth and unbounded fan-in.
• NC1: Allows for logarithmic depth, but restricts gates to fan-in two (binary operations). This class is more powerful than TC0 and includes all regular languages, which can be recognized by finite automata.

The problem that this work addresses is the need to precisely locate transformers within this hierarchy. By understanding which complexity class a transformer falls into, we can infer its inherent computational limits and better design models or strategies to overcome them. The existing intuition that transformers process information in a finite number of layers suggests a constant-depth computation, aligning them with AC0 or TC0, rather than deeper classes like NC1 which allow for more sequential computation.

Key Findings

▶ Watch: Formal definition of a Boolean circuit (2:00)

The talk presents several key findings that establish a formal connection between transformer architectures and Boolean circuit complexity classes, shedding light on their intrinsic computational capabilities:

• Transformers as Computational Graphs: A fundamental insight is that a transformer can be viewed as a specific type of directed acyclic graph (DAG). Its operations (embeddings, attention, feed-forward networks, residual connections, layer normalization) can be abstracted into computational nodes, and the flow of information dictates the graph's structure.
• Precision Determines Complexity Class: The computational expressivity of a transformer is heavily dependent on the precision of its internal representations.
• Constant precision transformers (e.g., using fixed-point arithmetic or low-bit quantization) are shown to fall into the AC0 circuit complexity class. This implies they are limited to problems solvable with constant depth and unbounded fan-in logical operations, such as binary addition and fixed-precision multiplication. They cannot, for instance, compute parity or majority over the entire input sequence.
• Logarithmic precision transformers (where the number of bits used for internal representation grows logarithmically with the input string length) elevate their capabilities to the TC0 circuit complexity class. This is primarily due to the ability of majority gates (which are central to TC0) to simulate the aggregation operations (like sums in attention) that occur over an unbounded number of positions in the input sequence.
• Vanilla Transformers are Limited to TC0: The core conclusion for standard, fixed-layer transformers is that, even with logarithmic precision, they are constrained to solving problems within the TC0 class. This means they are inherently suited for highly parallelizable problems that can be solved in a constant number of computational steps.
• Problems Beyond Vanilla Transformer Capabilities: The talk highlights that several important problems fall outside the TC0 class and are thus generally intractable for vanilla transformers. These include:
• Computing the value of a general Boolean formula (which might require logarithmic depth).
• Solving the Boolean satisfiability problem (SAT), which is much harder.
• Recognizing and generating general context-free languages (e.g., parsing natural language grammar), which often require abilities beyond NC1. This implies a fundamental limitation for transformers in tasks requiring complex hierarchical or recursive processing without additional mechanisms.
• Chain-of-Thought (CoT) Adds Computational Depth: CoT prompting strategies, which involve generating intermediate reasoning steps, are formally shown to add sequentiality and computational depth to transformers. By allowing the model to rely on outputs from previous computational steps for a non-constant number of iterations, CoT effectively moves transformers beyond the constant-depth limitations of AC0/TC0. Under certain assumptions (e.g., sufficient precision), CoT can even enable transformers to achieve Turing completeness, allowing them to simulate arbitrary computations.
• Padding Tokens Add Computational Width/Space: The strategic use of padding tokens in the input sequence is shown to increase the computational width or "workspace" available to the transformer. While it doesn't add depth, a polynomially increasing number of padding tokens can provide the model with more space to store variables and perform intermediate computations. This mechanism is proven to enable transformers to provably reach the entire expressivity of TC0, resolving open questions about whether vanilla transformers could fully capture TC0 without such explicit computational space.

These findings collectively offer a robust theoretical framework for understanding the computational boundaries of transformers and for designing more capable AI systems and prompting strategies.

Technical Deep Dive

▶ Watch: Circuit execution, size, depth, and limitations (2:40)

The technical exposition meticulously maps the operations of a transformer to the components of a Boolean circuit, beginning with an abstract view of the transformer as a computational graph. This graph consists of nodes representing operations and edges representing information flow. The goal is to transform this into a binary circuit model.

First, the talk abstracts away common transformer components. Feed-forward networks (FFNs), residual connections, and layer normalization are initially absorbed into abstract aggregation operations. The focus then shifts to representing the core transformer operations (embeddings, attention, FFNs) as Boolean circuits.

The analysis distinguishes between two types of transformer operations:

1. Position-wise operations: These include input/output embeddings, positional encodings, multiplications by weight matrices (to derive queries, keys, values), and Multi-Layer Perceptrons (MLPs) within the FFNs. Crucially, these operations are performed independently and in parallel at each position in the sequence. With logarithmic precision (where the number of bits for internal representations scales logarithmically with string length), these position-wise operations can be simulated by AC0 circuits. This is because at any given position, the number of inputs to these functions is fixed, and AC0 is capable of handling such fixed-size computations.
2. Aggregation operations: The most significant of these is the attention mechanism. Attention involves summing over n different values across the entire sequence (e.g., in the softmax-weighted sum of value vectors). Unlike position-wise operations, the number of inputs to this aggregation is not fixed; it grows with the sequence length n. Standard AC0 circuits cannot handle such unbounded summations as they can only depend on a bounded subset of input positions.

This is where the distinction between AC0 and TC0 becomes critical. To perform operations that aggregate information over an unbounded number of positions (like the sum in attention), the circuit model requires the power of majority gates (or threshold gates). These gates, which define the TC0 complexity class, can compute whether a certain number of inputs are 1, effectively simulating summations. Therefore, the aggregation operations within a transformer, particularly attention, push its expressivity beyond AC0 and into TC0. The speaker explicitly mentions that special operations common in transformers, such as softmax, exponentiation, summation, and division, can all be performed within the TC0 complexity class.

The overall transformer architecture, with its finite number of layers, translates directly to a constant-depth circuit. Each layer of the transformer corresponds to a fixed-depth sub-circuit. The quadratic complexity of attention (in terms of sequence length) aligns with the polynomial number of computational nodes that AC0, TC0, and NC1 circuits can possess. By combining the AC0 sub-circuits for position-wise operations and the TC0 sub-circuits for aggregation, the entire transformer can be conceptualized as a large TC0 circuit.

A crucial nuance is the role of precision. If transformers were restricted to constant precision (e.g., all values are represented by a fixed small number of bits, regardless of sequence length), even the aggregation operations would effectively be limited in their ability to distinguish subtle differences across many inputs. In such a scenario, constant precision transformers would fall back into AC0, making them less powerful than their logarithmic precision counterparts.

The talk then explores how to transcend the TC0 barrier:

• Chain-of-Thought (CoT): This technique fundamentally alters the computational model by introducing sequentiality. Instead of computing the output in a single, constant-depth pass, CoT allows the transformer to generate intermediate steps, where the output of one step informs the next. This sequential dependency effectively adds computational depth to the model. By allowing a non-constant number of such steps, CoT can simulate an automaton's state transitions or even the operations of a Turing machine, potentially elevating the transformer's capabilities to Turing completeness (under assumptions about fine-grained precision). This explains why CoT allows transformers to tackle problems that require more than constant-depth computation, such as evaluating complex logical formulas or recognizing non-regular languages.
• Padding Tokens: While CoT adds depth, padding tokens add computational width or "space." By appending a polynomially large number of padding tokens to the input, the transformer is given a larger canvas (a longer input sequence) on which to perform its computations. This provides more "variables" or "memory" for intermediate results. Although the number of layers (depth) remains constant, this increased width allows the transformer to utilize the full polynomial size capabilities inherent in TC0 circuits. This mechanism is shown to enable transformers to provably reach the entire expressivity of TC0, addressing the question of whether standard transformers could harness all TC0 capabilities without this explicit computational space.

The theoretical framework underscores that the core limitations of vanilla transformers stem from their fixed number of layers (constant depth) and the way they handle information aggregation. The proposed extensions (CoT and padding) directly address these limitations by introducing mechanisms for increased depth and width, respectively.

Experimental Setup & Results

▶ Watch: Introducing circuit families for formal languages (3:30)

This talk primarily focuses on theoretical analysis and does not present new empirical experimental results from the speakers. Instead, it provides a formal framework for understanding the computational capabilities of transformers and interpreting existing empirical observations.

However, the discussion does touch upon connections between the theoretical expressivity and observed empirical performance of transformers, particularly during the Q&A session:

• Parity vs. Majority: The speaker notes that transformers "famously struggle" with tasks like parity (determining if the number of ones in a binary string is odd or even), even though parity is a TC0 function. In contrast, they find majority (determining if more than half the bits are one), also a TC0 function, "way easier" to learn. This discrepancy highlights that while a model might theoretically be expressive enough to compute a function (i.e., it falls into the correct complexity class), its ability to learn that function (learnability) is a separate, complex issue.
• Sensitivity: One hypothesis for the difficulty in learning parity is its high sensitivity. Flipping a single input bit in a parity problem changes the output, requiring the model to be highly sensitive to all inputs. AC0 functions, in contrast, typically have "tame sensitivity" because their output cannot depend on all inputs simultaneously. This suggests that transformers might struggle with functions requiring high sensitivity across the entire input.
• AC0 Functions are Easier to Learn: Empirically, AC0 functions are generally observed to be easier for transformers to learn than TC0 functions. This aligns with the theoretical finding that constant precision transformers are in AC0, while logarithmic precision is needed for TC0.
• k-SAT Problem: During the Q&A, a question about encoding k-SAT (a Boolean satisfiability problem) in a transformer was raised. The speaker noted that while any formula can be written in conjunctive or disjunctive normal form, doing so for k-SAT would require exponentially many terms or nodes in a fixed-depth circuit. This would imply an exponentially deep or wide transformer (e.g., with exponentially many padding tokens), which is generally impractical and well beyond the scope of TC0.

In essence, while the talk doesn't introduce new benchmarks, it provides the theoretical lens through which existing and future empirical results on transformer capabilities and limitations can be rigorously analyzed and understood. The distinction between expressivity (what a model can compute) and learnability (what a model can be trained to compute) is a crucial implication for practitioners.

Practical Implications

▶ Watch: Relating individual transformers to circuit families (4:30)

This theoretical framework for understanding transformers through Boolean circuits offers profound practical implications for anyone involved in building, deploying, or utilizing large language models:

• Informed Model Design: Understanding that vanilla transformers are inherently limited to TC0 problems (highly parallelizable, constant-depth computations) can guide architectural innovations. If a task requires capabilities beyond TC0 (e.g., complex sequential reasoning, deep hierarchical parsing), simply scaling up existing transformer layers might not be sufficient. This could motivate the integration of explicit recurrent mechanisms, memory networks, or specialized modules designed to add computational depth or width beyond what standard attention and FFNs provide.
• Strategic Prompt Engineering: The formalization of Chain-of-Thought (CoT) reasoning and padding tokens provides a principled basis for these empirically successful prompting strategies. CoT is not just a "trick" but a mechanism that fundamentally extends the model's computational depth, potentially towards Turing completeness. This means for tasks requiring multi-step logical deduction or state tracking, CoT is theoretically necessary to unlock the model's full potential. Similarly, padding tokens are not merely for batching but add crucial "computational workspace," enabling transformers to fully exploit their TC0 expressivity for tasks requiring more intermediate storage or complex parallel computations. Practitioners can use this insight to strategically design prompts that either elicit sequential reasoning or provide ample "scratchpad" space.
• Realistic Expectations for LLM Capabilities: This analysis helps set realistic expectations for what current LLMs can achieve. Tasks like general Boolean formula evaluation, or parsing highly complex context-free languages, are shown to be inherently difficult or impossible for vanilla transformers. This prevents overestimation of model capabilities and guides the selection of appropriate tools for specific problems. For instance, if a task explicitly requires deep recursion or unbounded state tracking, a vanilla transformer might require substantial scaffolding or an alternative approach.
• Trade-offs in Resource Allocation: The discussion on precision (constant vs. logarithmic) highlights a fundamental trade-off. While higher precision (logarithmic) is required to reach the full TC0 class, it comes with increased computational cost and memory footprint. For simpler AC0-level tasks, constant precision might be sufficient, offering efficiency gains. Similarly, CoT reasoning increases inference time due to sequential steps, and padding tokens increase sequence length, both impacting computational resources. Infra teams and model deployers can use this understanding to optimize hardware utilization and cost by matching model complexity and operational strategies to the problem's inherent computational demands.
• Guiding Research into Learnability: The observed gap between theoretical expressivity and empirical learnability (e.g., transformers struggling with parity despite being in TC0) opens new research avenues. Future work could focus on why certain theoretically computable functions are hard to learn, exploring factors like input sensitivity, architectural inductive biases, or training dynamics. This could lead to more robust training algorithms or architectural modifications that improve learnability for complex tasks.
• Formal Verification and Explainability: By framing transformer computations as circuits, this work lays groundwork for more formal verification and explainability. If a transformer's computation can be mapped to a circuit, it becomes potentially verifiable against logical specifications, offering a path towards more reliable and transparent AI systems.

In summary, this theoretical deep dive moves beyond black-box empiricism, providing a robust framework for understanding the "why" behind transformer performance. It empowers practitioners to make more informed decisions about model architecture, prompting strategies, and resource management, ultimately leading to more effective and efficient AI deployments.

Key Takeaways

• Transformers as Boolean Circuits: Transformers can be formally modeled as directed acyclic graphs (DAGs), analogous to Boolean circuits, allowing for rigorous analysis of their computational power using complexity theory.
• Precision Dictates Expressivity: The computational class of a transformer depends on its internal precision: constant precision models fall into AC0, while logarithmic precision models achieve TC0 expressivity, primarily due to the need for majority gates to handle attention's aggregation operations.
• Vanilla Transformers are TC0-Limited: Standard, fixed-layer transformers are fundamentally limited to solving problems within the TC0 complexity class, meaning they excel at highly parallelizable tasks computable in a constant number of steps.
• Chain-of-Thought Adds Depth: Chain-of-Thought (CoT) reasoning enhances transformers' capabilities by adding sequential computational depth, allowing them to tackle problems that require non-constant steps, potentially achieving Turing completeness.
• Padding Adds Width: Padding tokens provide transformers with additional computational width or "workspace," enabling them to fully leverage the expressivity of TC0 by allowing more intermediate storage and parallel computations.
• Theoretical Limits Guide Practice: Understanding these theoretical limits and the mechanisms to extend them (CoT, padding) is crucial for designing effective transformer architectures, developing advanced prompting strategies, and setting realistic expectations for LLM capabilities.

About the Speaker(s)

The talk presented here was primarily delivered by Anej Svete, with contributions and context from a broader research group including Jiaoda Li, Ryan Cotterell, and Franz Nowak. While specific titles and affiliations for Anej Svete are not detailed in the transcript, the content of the presentation clearly positions him as a researcher deeply involved in the theoretical underpinnings of machine learning, particularly concerning the computational complexity and formal expressivity of neural networks. His work, as evidenced by this talk, focuses on bridging the gap between empirical observations of transformer behavior and the rigorous mathematical frameworks of theoretical computer science and complexity theory. The comprehensive nature of the analysis, from abstracting transformer operations to mapping them onto Boolean circuits and exploring advanced prompting techniques, highlights a strong expertise in both deep learning and computational theory.