💬 NLP

Understanding LLM Failures: A Multi-Tape Turing Machine Analysis of Systematic Errors in Language Model Reasoning

This paper proposes a formal multi-tape Turing machine framework to rigorously analyze and localize systematic reasoning failures in large language models, offering a principled alternative to geometric metaphors for understanding how tokenization and internal representations contribute to errors and how techniques like chain-of-thought prompting function.

Original authors: Magnus Boman

Published 2026-02-20

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Magnus Boman

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a super-smart robot that can write stories, answer questions, and solve riddles. You might think it "thinks" like a human, but this paper argues that it actually works more like a very specific, rigid machine with a few distinct workstations.

The author, Magnus Boman, proposes a new way to look at Large Language Models (LLMs) by comparing them to a Multi-Tape Turing Machine. If that sounds like sci-fi gibberish, here's the simple translation:

The Analogy: The Factory Assembly Line

Think of the AI not as a magical brain, but as a factory assembly line with seven different conveyor belts (tapes) running side-by-side. Each belt has a specific job, and the "worker" (the machine's logic) moves from one belt to the next, passing information along.

Here is what each belt does:

Belt 1 (The Raw Input): The raw text you type in (like "Strawberry").
Belt 2 (The Tokenizer): This belt chops your text into chunks called "tokens." It's like a butcher cutting a whole chicken into pieces. Sometimes, the whole word "Strawberry" is one piece. Sometimes, it's cut into "Str," "aw," and "berry."
Belt 3 (The Dictionary): The rulebook for how to chop words and how to put them back together later.
Belt 4 (The Brain/Weights): The actual "knowledge" of the model—the math and parameters it learned during training.
Belt 5 (The Scratchpad): A temporary workspace where the machine does its math and calculations.
Belt 6 (The Probability Board): A scoreboard showing how likely the next word is to be "cat," "dog," or "fled."
Belt 7 (The Output): The final text written out for you to read.

Why Does the Robot Fail?

The paper uses this factory model to explain why the robot makes silly mistakes on simple tasks.

1. The "Strawberry" Problem (The Chopping Issue)

The Task: Count how many times the letter "r" appears in the word "Strawberry."
The Human Way: We see the letters S-t-r-a-w-b-e-r-r-y. We count: 1, 2, 3. Easy.
The Robot's Way:

If the robot sees "Strawberry" as one single chunk (token) on Belt 2, it never actually "sees" the individual letters inside. It's like being handed a sealed box labeled "Strawberry" and asked to count the red letters inside without opening it.
The robot has to guess based on what it saw in its training data, not by actually counting. It's a "pattern match," not a calculation.
The Fix: The paper suggests we need to add a specific "counting worker" to the factory line (Belt 5) that can open the box, look at the letters, and count them one by one. Without this specific tool, the robot is blind to the details.

2. The "Nested Sentence" Problem (The Memory Issue)

The Task: Finish this sentence: "The cat that the dog that the mouse feared chased..."
The Human Way: We understand the layers. The mouse feared the dog. The dog chased the cat. The cat needs a verb (like "fled").
The Robot's Way:

The robot looks at the sentence and sees a jumble of words. It struggles to keep track of which "that" belongs to which animal because it doesn't have a true "stack" (like a stack of plates) to hold onto the layers of meaning.
It tries to guess the next word based on what usually comes after "chased," often failing to realize the sentence structure is a deep nesting of dependencies.
The Limit: The robot is good at shallow patterns but gets lost in deep, recursive structures, like a person trying to remember a phone number while reciting a poem.

The Magic of "Chain-of-Thought" (CoT)

You've probably heard of "Chain-of-Thought" prompting, where you tell the AI, "Let's think step-by-step."

The Paper's Explanation: In our factory analogy, CoT is like giving the robot a second piece of paper (Belt 7) to write its thoughts on before giving the final answer.
Instead of trying to hold the whole complex problem in its tiny internal memory (Belt 5), it writes the steps down: "Step 1: The mouse feared the dog. Step 2: The dog chased the cat..."
By writing it down, it can "read" its own notes to solve the next step. This helps a lot, but it's not magic. If the task requires counting letters inside a word that was chopped up, writing "Let me think" won't help unless the robot actually has a tool to count.

The Big Takeaway

This paper is a wake-up call. It tells us that LLMs aren't "thinking" in the way we do. They are statistical pattern matchers running on a rigid assembly line.

They are great at guessing what word comes next based on billions of examples.
They are bad at tasks that require exact, step-by-step logic (like counting letters) or deep structural understanding, unless we force them to use specific tools (like writing out steps or using a counting subroutine).

The author argues that instead of just making bigger models (scaling up), we need to understand these "factory line" limitations to fix them. We need to build better tools into the machine so it can actually do the math, not just guess the answer.

1. Problem Statement

Large Language Models (LLMs) frequently exhibit failure modes on tasks that are trivial for humans, such as counting specific characters in a word (e.g., the number of "r"s in "Strawberry") or handling deeply nested recursive structures. While empirical research has focused on scaling laws to describe performance, there is a lack of rigorous, formal frameworks to explain why these specific failures occur. Existing descriptions often rely on geometric metaphors or high-level abstractions that obscure the specific pipeline stages where errors originate. The paper argues that to understand these limitations, LLM behavior must be decomposed into discrete computational stages and analyzed through the lens of classical computability theory.

2. Methodology: The Multi-Tape Turing Machine Formalization

The authors propose a formal model of LLM inference using a deterministic multi-tape Turing Machine (TM). This model decomposes the LLM pipeline into distinct, interacting components, each represented by a specific tape and a set of control states.

The Seven Tapes:

Tape 1 (Chars-in): Raw input characters (byte/character alphabet).
Tape 2 (Tokens): Token sequences (integer IDs), including input tokens and generated tokens.
Tape 3 (Tokeniser + Vocab): Read/Write access to BPE merge rules, vocabulary, frequency statistics, and inverse mappings.
Tape 4 (Model Spec): Architecture metadata and parameters (finite-precision rationals).
Tape 5 (Work): Intermediate activations, including Key/Value (KV) caches and temporary scratch values for attention/feed-forward computations.
Tape 6 (Logits/Probs): Buffer for probability distributions of the next token.
Tape 7 (Chars-out): Detokenized character output.

Operational Phases:
The machine operates in a cyclic sequence of phases governed by transition functions:

Tokenisation: Reads characters from Tape 1, consults rules on Tape 3, and writes token IDs to Tape 2.
Forward Computation: Reads tokens from Tape 2, uses parameters from Tape 4 and workspace from Tape 5 to compute attention and feed-forward operations, writing probability distributions to Tape 6.
Token Selection: Scans Tape 6 to select the next token (greedy argmax or sampling).
Emission & Detokenisation: Appends the selected token to Tape 2 and converts it back to characters on Tape 7 using the inverse vocabulary from Tape 3.

The model distinguishes between control states (governing the phase, e.g., $Q_{tok}, Q_{fwd}, Q_{select}$ ) and tape symbols. It explicitly models how attention mechanisms operate over bounded windows and how the absence of specific subroutines (like a stack or counter) limits the machine's capabilities.

3. Key Contributions

Formal Decomposition: Introduces a multi-tape deterministic TM formalization that assigns distinct roles to every stage of the LLM pipeline, moving beyond "black box" descriptions.
Error Localization: Demonstrates how to pinpoint failures to specific stages (e.g., distinguishing between tokenisation errors and forward computation limitations).
Computational Limits: Clarifies which tasks are computationally trivial but inaccessible to standard LLMs due to the lack of explicit subroutines (e.g., iterative counting).
Reinterpretation of Chain-of-Thought (CoT): Provides a theoretical explanation for CoT prompting as the externalization of intermediate computation onto the output tape (Tape 7), acting as an external scratchpad.
Attention Analysis: Formalizes attention mechanisms as tape operations, enabling precise analysis of failure modes like context window violations and attention dilution.

4. Key Results and Analysis

A. The "Strawberry" Counting Failure

The paper analyzes why LLMs fail to count the letter "r" in "Strawberry."

Mechanism: In standard tokenization regimes, "Strawberry" is often split into subwords (e.g., Str, aw, berry) or treated as a single token.
Failure Point: The forward computation states ( $Q_{fwd}$ ) operate on token IDs. Unless explicit character-counting subroutines are implemented, the model cannot iterate through the internal character structure of a token. The tokenization process obscures the character-level boundaries required for the task.
Solution in Model: To solve this, the model requires specific states ( $q_{locate}, q_{detok,internal}, q_{count}$ ) to map tokens back to characters and iterate, effectively changing the algorithm from pattern matching to symbolic computation.

B. Recursive Centre-Embedding

The paper examines the difficulty LLMs face with sentences like "The cat that the dog that the mouse feared chased..."

Mechanism: Transformers rely on attention mechanisms to track dependencies.
Failure Point: Standard attention computes weights based on token similarity without an explicit stack mechanism. As nesting depth increases, the model loses track of which subject corresponds to which verb.
Theoretical Limit: The paper links this to the Chomsky Hierarchy. Centre-embedded structures require Context-Sensitive Grammar (Type 1), but standard transformers with finite windows and no explicit memory implement at most Context-Free Grammar (Type 2). Without $q_{push}$ and $q_{pop}$ states to manage a stack, the model cannot resolve deep recursion.

C. Chain-of-Thought (CoT) Prompting

Formalization: CoT is modeled as writing intermediate reasoning steps to Tape 7 (the output tape) before generating the final answer.
Mechanism: This allows the model to "attend" to its own previous outputs (on Tape 7) during subsequent forward passes, effectively using the output tape as extended working memory.
Limitations: CoT does not change the underlying computational class. It helps only when intermediate steps can be externalized as natural language within the context window. It fails for tasks requiring unbounded recursion, exact counting without subroutines, or resolving paradoxes.

5. Significance and Implications

Rigorous Error Analysis: The paper moves LLM analysis from phenomenological scaling laws to principled error analysis based on computability theory. It provides a falsifiable framework to predict when and why models will fail.
Clarifying CoT: It demystifies Chain-of-Thought, showing it is not a magical reasoning upgrade but a specific computational pattern that offloads state management to the output tape. This explains why CoT has limits (e.g., it cannot fix the lack of a counting subroutine).
Architectural Insights: The model suggests that to solve complex reasoning tasks, LLMs may require architectural changes that explicitly implement stack-like memory or counting subroutines, rather than relying solely on larger parameter counts or better prompting.
Complement to Empirics: While empirical studies show that models scale, this formal model explains what is computationally possible and impossible for current architectures, bridging the gap between neural network behavior and classical computer science theory.

In conclusion, the paper argues that many LLM failures are not due to a lack of "intelligence" but are inherent consequences of the specific computational pipeline (tokenization + attention + finite state) and the absence of explicit algorithmic subroutines for tasks like counting and recursion.