The Underlying Logic of Language Models: The Underlying Logic of Language Models: Introduction

The Underlying Logic of Language Models: Introduction

Speakers: Anej Svete, Jiaoda Li, Franz Nowak (PhD Students in Ryan Cotterell's lab); Ryan Cotterell (Professor)

Conference: ICML 2025

YouTube: https://slideslive.com/39043865

Overview

This talk, an introductory segment of a broader tutorial presented at ICML 2025, delves into the fundamental question of "what language models can compute." Presented by Anej Svete, Jiaoda Li, and Franz Nowak from Ryan Cotterell's lab at ETH Zurich, the session sets the stage for a rigorous scientific inquiry into the underlying computational logic of modern language models, particularly Transformers. While acknowledging the astonishing capabilities of models like ChatGPT—demonstrated by their ability to generate intricate sonnets on abstract topics—the speakers immediately pivot to their persistent, often baffling failures on seemingly simple tasks, such as basic arithmetic or complex reasoning problems like the knapsack problem. This dichotomy highlights a critical gap in our understanding: despite their emergent intelligence, the precise computational boundaries and internal mechanisms of these models remain largely opaque.

The core motivation behind this research is to move beyond mere empirical observation and "try-it-and-see" approaches in language model design. Instead, the presenters advocate for a "science for language models" that aims to uncover fundamental insights into what these models can represent, what problems they can exactly solve, and how they achieve these computations. This scientific endeavor is framed as essential for making informed design decisions, identifying the potentials and limitations of models, and ultimately building more reliable and robust AI systems. The tutorial specifically focuses on the expressivity of language models, investigating their theoretical capacity to represent algorithms and formal languages, as opposed to their learnability or approximation capabilities. It promises to explore this expressivity through three distinct theoretical lenses: formal logic, circuit complexity, and structural decomposition using algebra.

Background

▶ Watch: Welcome and introduction to the tutorial (0:00)

The rapid ascent of large language models (LLMs) has revolutionized numerous fields, showcasing unprecedented abilities in natural language understanding, generation, and complex pattern recognition. However, beneath this veneer of impressive performance lies a significant scientific challenge: understanding why and how these models achieve what they do, and more importantly, what their fundamental computational limits are. As the speakers compellingly illustrate, while an LLM might craft a beautiful sonnet, it can simultaneously fail at basic multiplication or struggle with combinatorial optimization problems like the knapsack problem, which require precise, step-by-step reasoning. This inconsistency underscores the "black box" nature of neural networks, a problem that has plagued the field since their inception.

Historically, the quest to understand neural network internals dates back decades. In the context of natural language processing, early motivations (pre-dating the current LLM era and models like ChatGPT) often revolved around questions concerning the linguistic structures models acquired. Researchers sought to determine if neural networks were learning human-like grammatical rules or simply superficial correlations. This involved efforts to "open the black box" and peer into the internal representations and decision-making processes of models. With the advent of large-scale Transformers and their ubiquitous deployment, the motivation for a deeper, more scientific understanding has only intensified. The stakes are higher: LLMs are no longer just research curiosities but critical components in real-world applications, making it imperative to understand their reliability, generalizability, and potential failure modes.

The current emphasis shifts from merely observing performance boosts to seeking fundamental insights that can guide the informed design of future language models. This includes understanding their reasoning and generalization abilities—predicting when a model will successfully solve a problem or generalize to harder instances. It also involves identifying and introducing useful inductive biases into model architectures or training regimes to improve performance and tractability for specific tasks. Furthermore, connecting what language models do to human language processing offers a dual benefit: it helps interpret the models themselves and potentially sheds light on the mechanisms of human cognition. Finally, by mapping language models to known computational models, there's a promise of leveraging classic algorithms from computer science for more efficient inference or problem-solving. This tutorial specifically zeroes in on the theoretical expressivity of language models—what computations they are capable of performing in principle—rather than their trainability (what they learn from finite data) or their approximation capabilities (how well they can approximate functions in the limit). The focus is on formal language theory, which deals with the exact representation and solving of problems, providing a precise framework for analyzing computational power.

Key Findings

▶ Watch: Motivating hard problems: the knapsack problem (2:15)

As an introductory segment of a broader tutorial, this talk primarily outlines the critical need for a scientific understanding of language models and introduces the theoretical frameworks that will be employed to achieve this. It does not present specific "findings" in the traditional sense of experimental results or novel discoveries, but rather establishes the foundational "findings" that motivate the entire research direction and the methodological approaches.

The core "findings" presented in this introduction are:

1. The Paradox of LLM Capabilities: Modern language models exhibit astonishing capabilities in complex, creative tasks (e.g., writing sonnets) but simultaneously demonstrate fundamental failures in seemingly simple, rule-based tasks (e.g., multiplication) and intricate reasoning problems (e.g., the knapsack problem). This paradox underscores a profound lack of understanding regarding their underlying computational logic.
2. The Imperative for a "Science for Language Models": Moving beyond empirical observation and trial-and-error is crucial. A scientific approach is necessary to understand what language models can compute, how they compute it, and their inherent potentials and limitations. This understanding is vital for informed design decisions, improving trustworthiness, and guiding future development.
3. Focus on Expressivity via Formal Language Theory: The most productive avenue for this scientific inquiry, as argued by the speakers, is to investigate the expressivity of language models—their theoretical capacity to represent and exactly solve problems—through the lens of formal language theory. This approach provides precise tools for characterizing the computational power of models, abstracting away from the complexities of learning dynamics or approximation.
4. Three Pillars of Analysis for Transformer Expressivity: The tutorial will dissect the expressivity of Transformers using three distinct, yet complementary, theoretical approaches:

• Formal Logic: Analyzing how logical reasoning and computations can be described within the architecture of a Transformer.
• Circuit Complexity: Examining Transformers as computational circuits to understand their parallel processing capabilities and inherent limitations in solving problems efficiently.
• Structural Decomposition and Algebra: Employing algebraic methods to analyze the compositional structure and computational transformations performed by Transformer components, revealing underlying symmetries or properties.

These "findings" collectively set the agenda for the subsequent, more detailed parts of the tutorial, promising to shed light on the fundamental computational nature of the Transformer architecture.

Technical Deep Dive

▶ Watch: Analyzing LMs: expressivity vs. trainability (6:00)

The introductory segment of this tutorial lays the groundwork for a comprehensive technical deep dive into the expressivity of Transformers, specifically through the lens of formal language theory. While the present transcript does not delve into the specifics of each methodology, it meticulously outlines the upcoming technical exploration, providing a roadmap for understanding the "underlying logic" of these powerful architectures. The core idea is to move from the empirical observation of what Transformers do to a theoretical understanding of what they can compute.

The speakers propose a conceptual hierarchy for analyzing neural language models: starting from the broad category of neural language models, one can investigate their expressivity (what they can represent) or their trainability (what they can learn). This tutorial specifically focuses on expressivity, further subdividing it into approximation (how well they can approximate functions in the limit) and formal language theory (their ability for exact representation or solving of problems). It is this latter, precise, and rigorous domain of formal language theory that forms the bedrock of the planned technical deep dive. The choice of Transformers as the primary architecture reflects their dominance in modern NLP.

The technical deep dive will be structured around three principal approaches:

1. Formal Logic and Transformers

Jiaoda Li is slated to present on how formal logic can be used to describe computations within a Transformer. This area of research aims to establish a direct link between the operations performed by a Transformer's components (such as attention mechanisms and feed-forward networks) and established logical systems. For instance, attention mechanisms, which allow a model to weigh the importance of different input tokens when processing another, can be conceptualized as performing operations akin to quantifiers (e.g., "for all," "there exists") or relational logic. A Transformer layer, with its multi-head attention and subsequent position-wise feed-forward networks, could be modeled as executing a sequence of logical predicates and transformations on its input representations.

The goal here is to determine if Transformers can implement specific logical reasoning patterns, such as those found in first-order logic (FOL) or even more expressive logics. This involves mapping the continuous operations of neural networks to discrete logical steps. Researchers in this domain often explore whether Transformers can parse or generate strings belonging to languages defined by formal grammars (e.g., context-free grammars) which have direct logical interpretations. For example, can a Transformer correctly identify well-formed parentheses sequences, which is a classic context-free language? This perspective provides a powerful tool for understanding the symbolic reasoning capabilities inherent (or lacking) in these models, moving beyond mere statistical correlations to ascertain if they grasp underlying logical structures.

2. Circuit Complexity and Parallel Computations

Anej Svete will delve into circuit complexity, a branch of computational complexity theory that analyzes the resources (like number of gates or depth) required to compute a function using Boolean circuits. When applied to Transformers, this involves viewing the model's layers as a sequence of computational circuits. The highly parallel nature of the Transformer architecture, particularly its attention mechanism, makes it a prime candidate for analysis through this lens.

The central question here is what kinds of problems Transformers can solve efficiently in parallel. Circuit complexity classes like AC0 (constant-depth, polynomial-size circuits) or NC1 (logarithmic-depth, polynomial-size circuits) are often invoked. For instance, problems solvable in AC0 are typically those that can be computed by very shallow networks with a large number of simple gates, reflecting operations that can be performed simultaneously across all input elements. Analyzing Transformers through this framework helps to identify their inherent limits regarding tasks that require deep, sequential reasoning versus those that are amenable to parallel processing. For example, tasks like parity checking (determining if the number of '1's in a binary string is odd or even) are known to be outside of AC0, suggesting that a constant-depth Transformer might struggle with such problems without specific architectural augmentations or an increase in depth. Understanding these limits provides insights into why Transformers might excel at certain highly parallelizable pattern recognition tasks but falter at others requiring iterative, sequential computation. This approach precisely quantifies the parallel computational power afforded by the Transformer's architecture and where its inherent limitations lie.

3. Structural Decomposition and Algebra

Franz Nowak is tasked with explaining how algebra can be utilized for the structural decomposition and analysis of Transformers. This approach involves leveraging abstract algebraic concepts, such as group theory, semigroup theory, or ring theory, to characterize the transformations performed by different components of a Transformer. For example, the operations within a Transformer layer—linear transformations, non-linear activations, and attention mechanisms—can be viewed as elements of an algebraic structure.

The goal is to understand the compositional properties of these transformations. Can we decompose complex Transformer computations into simpler, well-understood algebraic operations? This method can reveal symmetries, invariants, or specific properties that are preserved or transformed across layers. For instance, certain algebraic structures might naturally describe how information is propagated, combined, or filtered through the attention heads and feed-forward networks. By abstracting the continuous numerical operations into a more symbolic algebraic framework, researchers can gain insights into the model's ability to learn and process structured data, such as hierarchical or compositional patterns in language. This could lead to a deeper understanding of phenomena like compositionality in language models, where the meaning of a whole is derived from the meaning of its parts and their arrangement. Algebraic analysis can help categorize the types of functions or transformations that a Transformer can implement, providing a powerful tool for understanding its representational capacity in a highly abstract and generalizable manner.

It is crucial to note that this deep dive will operate under specific theoretical idealizations of Transformers. The analysis will focus on their exact representation capabilities, purposefully abstracting away from the complexities of learnability (how they acquire these capabilities through training data and algorithms like SGD) and approximation (how well they can approximate arbitrary functions). Furthermore, the discussion will not venture into hypothetical architectural extensions that might fundamentally alter how Transformers operate, maintaining a focus on the standard, prevalent architecture. This focused theoretical approach aims to provide fundamental insights into the inherent computational logic of these models.

Experimental Setup & Results

▶ Watch: Tutorial's focus: exact representation via formal language theory (7:30)

As an introductory segment of a broader tutorial, this specific part of the talk does not detail experimental setups, specific datasets, or empirical results. The primary objective of this introductory presentation is to establish the theoretical motivation for a scientific inquiry into the underlying logic of language models and to outline the methodological frameworks that will be explored in subsequent, more detailed sections of the tutorial.

The speakers reference common observations about language models, such as their ability to generate creative text (e.g., a sonnet about formal language theory) while simultaneously failing at basic arithmetic (e.g., multiplying two numbers) or complex reasoning tasks (e.g., the knapsack problem). These are presented as illustrative examples to highlight the current state of empirical understanding and the motivation for deeper theoretical work, rather than as outcomes of controlled experiments within the scope of this particular talk.

Therefore, this section serves as a theoretical foundation, promising future detailed analyses of Transformer capabilities through formal logic, circuit complexity, and algebraic decomposition, which would typically involve theoretical proofs and formal language demonstrations rather than traditional experimental benchmarks or headline numbers derived from large-scale datasets.

Practical Implications

▶ Watch: What the tutorial will not cover (8:50)

Understanding the underlying logic of language models, as advocated in this tutorial, carries profound practical implications for everyone involved in the lifecycle of AI systems—from researchers and model builders to infrastructure teams and deployers. Moving beyond a purely empirical "what works" approach to a scientific "why it works, and what its limits are" paradigm is critical for the sustainable and responsible development of AI.

1. Informed Model Design and Architecture: Currently, much of language model development relies on iterative empirical improvements and architectural intuition. A deep understanding of expressivity, grounded in formal language theory, can guide the design of future models. If researchers know, for instance, that a standard Transformer architecture inherently struggles with certain types of sequential or logical reasoning problems due to its circuit complexity, they can make informed decisions about introducing specific inductive biases—such as recurrent components, external memory, or specialized layers—to address these limitations. This moves model building from an art to a more principled engineering discipline, potentially reducing the need for extensive hyperparameter tuning and architectural search.

1. Predicting Capabilities and Limitations (Trustworthiness): The ability to theoretically characterize what problems a Transformer can and cannot solve provides a crucial framework for predicting model behavior. This is vital for establishing trustworthiness. If a model's computational limits are understood, practitioners can confidently deploy it for tasks within its theoretical capabilities and, critically, identify scenarios where it is likely to fail. For example, if formal logic analysis reveals that a Transformer cannot reliably perform complex logical deductions without explicit step-by-step prompting, deployers would know not to trust its unprompted responses for such tasks in high-stakes environments. This helps to set realistic expectations and prevent over-reliance on models for tasks they are fundamentally ill-equipped to handle.

1. Improving Generalization and Robustness: By understanding the formal properties of the computations models perform, we can design training regimes and architectures that foster better generalization. If a model learns an underlying algebraic structure, for example, it might generalize more effectively to novel instances of a problem that adhere to the same structure, rather than simply memorizing patterns from the training data. This also contributes to robustness, as models grounded in formal principles might be less susceptible to adversarial attacks or out-of-distribution shifts that exploit superficial data correlations.

1. Leveraging Classic Computer Science Algorithms: Once the computational model of a Transformer is mapped to known theoretical frameworks (e.g., specific complexity classes or algebraic structures), it opens the door to integrating or adapting classic algorithms developed over decades in computer science. For instance, if a Transformer can be shown to implement a certain type of finite automaton, then well-established algorithms for efficient inference or state management for that automaton could potentially be adapted or inspire novel inference strategies for the neural model. This could lead to significant improvements in computational efficiency, especially during inference, by replacing computationally expensive neural operations with optimized algorithmic counterparts where appropriate.

1. Benchmarking and Evaluation: Current benchmarks often focus on task-specific accuracy. A deeper theoretical understanding allows for the creation of more rigorous, theoretically informed benchmarks that probe specific computational capabilities (e.g., logical inference, compositional generalization, memory access patterns). This would enable more meaningful comparisons between models and provide clearer insights into their strengths and weaknesses beyond simple performance metrics.

1. Understanding Human Cognition: The connection between artificial language models and human language processing is a long-standing area of interest. By formalizing the computational abilities of Transformers, researchers can draw more precise parallels (or distinctions) with human cognitive processes. This can inform theories of human language acquisition, reasoning, and even the neural basis of intelligence, offering insights into both artificial and natural systems.

However, these practical implications also come with tradeoffs and limitations. The theoretical idealizations discussed in the tutorial abstract away from crucial real-world complexities like finite training data, specific optimization algorithms (e.g., SGD), and hardware constraints. A model might be theoretically capable of solving a problem, but practically unable to learn it from available data or within reasonable training times. The gap between expressivity (what it can do) and learnability (what it does learn) remains a significant challenge. Furthermore, the very abstraction that makes theoretical analysis tractable can sometimes miss subtle emergent behaviors that arise from the interaction of billions of parameters in real-world, messy data. Nonetheless, this scientific pursuit provides the foundational knowledge necessary to navigate these complexities more effectively and build the next generation of truly intelligent and reliable AI systems.

Key Takeaways

• Language models exhibit a paradox: impressive creative abilities alongside fundamental failures in basic arithmetic and complex reasoning tasks.
• A "science for language models" is critically needed to move beyond empirical observation and understand their underlying computational logic, potentials, and limitations.
• The tutorial focuses on the expressivity of Transformers—what they can theoretically represent and exactly solve—through the lens of formal language theory.
• Three primary theoretical approaches will be used to analyze Transformer expressivity: formal logic, circuit complexity, and structural decomposition using algebra.
• Understanding Transformer expressivity can lead to more informed model design, improved trustworthiness, better generalization, and the potential to leverage classic computer science algorithms.
• This theoretical work aims to provide fundamental insights into what Transformers can and cannot compute, distinct from questions of learnability or approximation.

About the Speaker(s)

The tutorial was presented by Anej Svete, Jiaoda Li, and Franz Nowak, all of whom are PhD students of varying seniorities in Ryan Cotterell's lab at ETH Zurich. Ryan Cotterell, their professor and lab head, was unfortunately unable to attend the conference. For Anej, Jiaoda, and Franz, the "underlying logic of language models" has been the main area of research during their PhD studies, reflecting a dedicated focus within Professor Cotterell's broader research interests. The speakers also gratefully acknowledged contributions from Will and Lena, whose previous collaborations helped in adapting some of the slides for this presentation.