The Imitation Game: Turing Machine Imitator is Length Generalizable Reasoner

ArXiv: 2507.13332

🎯 Pitch

Stripping all human-like narration from chain-of-thought and forcing a language model to mimic a Turing machine’s flat sequence of atomic read–write steps is what unlocks genuine length generalization—not the reasoning style itself. Remarkably, this TAIL approach trained on synthetic algorithmic data lets a 7B model beat DeepSeek-R1 on tasks like large-number addition, where it hits 86.5% at unseen lengths versus just 24% for prior baselines.

1. Executive Summary

This paper introduces Turing mAchine Imitation Learning (TAIL), a data-driven framework for constructing chain-of-thought (CoT) training data that enables length generalization in large language models by having them imitate the execution of a Turing machine. Using 18 synthetic tasks across 8 algorithmic paradigms, the authors fine-tune Qwen2.5-7B on TAIL-structured CoT that instantiates three core modules — Linear Transition (unrolling complex control flow into a flat sequence of steps), Atomic State (decomposing each step into minimal read-write-logic operations), and Memory Fetcher (explicitly retrieving distant operands before operating on them to localize attention) — and achieve strong out-of-distribution length generalization across all tasks, surpassing both prior data-driven methods like Index Hint and Reversed Format (e.g., 86.5% vs. 24.0% on large-number addition at long lengths) and the 671B DeepSeek-R1 reasoning model on most tasks. A critical finding emerges from the thinking-style ablation: removing all human-like linguistic narrative from the CoT and retaining only the three core TAIL modules preserves full performance, establishing that the structured Turing-machine imitation — not surface-level reasoning style — is the primary enabler of length generalization, while the approach is bounded to computable problems with deterministic algorithms.

2. Context and Motivation

The Core Problem: Length Generalization Is a Fundamental Weakness of LLMs

The question this paper tackles is simple to state but has resisted systematic solutions: if you train a language model on short input sequences, can it reliably solve problems with much longer inputs at test time? This is the problem of length generalization, and it represents one of the most persistent failures of Transformer-based large language models (LLMs). A model trained to add 10-digit numbers may achieve near-perfect accuracy on 10-digit addition, yet collapse to random guessing on 30-digit or 50-digit addition — even though the underlying algorithm (digit-by-digit addition with carry propagation) is identical regardless of input length.

The authors frame this failure concretely in Section 1:

"recent studies... indicate that LLMs still struggle with length generalization, which sometimes explores and falls into shortcuts that eventually cause errors"

The word "shortcuts" here is precise: models don't fail because they lack the capacity to perform the computation. They fail because they learn spurious patterns that correlate with correctness on short inputs but don't generalize. For example, a model trained on addition with 5-digit operands might learn to attend to the first few high-order digits (which dominate the answer's magnitude) and ignore lower-order position-specific processing that becomes essential when carry propagation crosses many digit boundaries in longer sequences. The shortcut works on short inputs, so gradient descent reinforces it, and the model never acquires the true step-by-step algorithm.

This is a learning problem, not a capacity problem. The Transformer architecture is in principle Turing-complete given enough CoT steps (as theoretically established by Li et al., 2024 and cited by the authors in Section 2.2), meaning it can simulate any algorithmic computation. The challenge is getting the model to actually learn the algorithm from finite data, rather than converging to a shortcut that memorizes statistical patterns in the training distribution.

Why This Matters: Beyond Academic Curiosity

Length generalization is not a niche concern. It matters for at least three interconnected reasons that the paper surfaces:

First, it's a criterion for genuine reasoning. If a model truly understands addition, it should be able to add numbers of any length — just as a human who understands the addition algorithm can add 2-digit numbers and 100-digit numbers with the same conceptual framework. When performance degrades with length, it reveals that the model is doing something qualitatively different from algorithmic reasoning: it's pattern-matching against its training distribution. This connects to deeper questions about whether LLMs can learn procedures versus merely statistical regularities (the distinction the authors implicitly draw by invoking the Turing machine as a model of procedural computation in Section 2.2).

Second, it limits practical deployment. Real-world use cases rarely guarantee that test inputs match training lengths. A code generation model must handle programs of arbitrary size; a mathematical reasoning system must solve equations with varying numbers of terms; a symbolic manipulation tool must process expressions of unbounded nesting depth. Models that break down on longer sequences are brittle — they work until they suddenly don't, with no warning and no graceful degradation.

Third, it exposes a gap between how models learn and how algorithms work. Algorithms operate through compositional rules that apply uniformly regardless of input size. The digit-by-digit addition procedure at position 1 is exactly the same as at position 100. If models truly internalize this compositional structure, length generalization should emerge naturally. That it doesn't — even in modern LLMs — reveals that standard training paradigms (next-token prediction on natural data, or even on algorithmically generated data with conventional CoT) fail to induce the right kind of structural understanding.

The Landscape of Prior Approaches and Their Limitations

The paper situates itself relative to two broad categories of prior work — architectural modifications and data-driven CoT engineering — and identifies specific shortcomings in each.

Architectural Modifications: Powerful but Impractical

Prior work explored modifying Transformer internals to bake in length-generalizable inductive biases. These include:

• Specialized position encodings (Ruoss et al., 2023; Li et al., 2023; Kazemnejad et al., 2023): randomized or functional interpolation schemes that allow models to extrapolate to unseen positions by making position representations continuous and extrapolatable rather than discrete and memorized.
• Looped or recurrent forward mechanisms (Fan et al., 2024; Giannou et al., 2023): architectures where the same computation is applied iteratively, mimicking the loop structure of algorithmic execution and enabling arbitrary-length processing by repeating the loop body.
• Modified attention patterns (Duan et al., 2023): attention mechanisms that enforce locality or structured sparsity patterns aligned with known algorithmic structures (e.g., attending only to adjacent digits in arithmetic).

The authors acknowledge these contributions but identify a critical limitation in Section 5:

"architectural enhancements modify the components... of Transformers for specific tasks and further adaptation to be applicable to prevailing LLMs"

The problem is practical: each architectural modification is typically designed for a specific class of tasks (e.g., addition-specific attention patterns), and retrofitting these modifications into production-scale LLMs (Qwen, LLaMA, DeepSeek) requires retraining from scratch or significant engineering overhead. The modifications don't transfer across model families, and they often solve only the specific problems they were designed for. Furthermore, the authors note that this line of work tends to test on simplified environments (small transformers, synthetic tasks with clean structure) rather than on modern 7B+ parameter models trained with conventional pretraining objectives — leaving a gap between theoretical demonstration and practical adoption.

Data-Driven CoT Engineering: Task-Specific Band-Aids

The more directly relevant prior work focuses on how the training data is structured — specifically, the format of the chain-of-thought — to promote length generalization without modifying model architecture. The paper identifies several prominent approaches:

• Index Hint (Zhou et al., 2023; 2024): annotating each digit or symbol with its positional index (e.g., 3a 6b 1c + 5a 7b 6c = 9a 3b 7c) to help the model track position identity during computation. This has proven effective for arithmetic and parity tasks but, as the authors point out, is inherently tied to tasks where positional matching is the core computational primitive. It doesn't naturally extend to tasks like binary search (where midpoints shift dynamically), dynamic programming (where subproblem indices aren't simple positional tags), or graph algorithms (where structure isn't linear).

• Reversed Format (Zhou et al., 2024; Lee et al., 2023; Shen et al., 2023; McLeish et al., 2024): reversing the digit order of operands so that the least-significant digit (where addition begins) appears first in the left-to-right generation order, aligning the natural addition flow with the model's autoregressive direction. This helps arithmetic specifically because it resolves the misalignment between the algorithm's right-to-left carry flow and the model's left-to-right generation — but it's completely irrelevant for tasks like string reversal or sorting, where the algorithmic flow doesn't have an inherent directionality mismatch.

• Sequence padding (Jelassi et al., 2023): padding sequences to a fixed length to create uniform input formats, which reduces distribution shift between short and long inputs. This addresses surface-level formatting but doesn't change the underlying CoT structure or how the model reasons about intermediate steps.

The authors' core criticism (Section 1) is damning but precise:

"these methods remain inherently task-specific, e.g., Index Hint for symbolic reasoning tasks and Reversed Format for arithmetic problems, and yield only moderate performance gains"

The word "task-specific" is the key charge. Each prior method encodes a structural insight about a particular class of computations — positional matching for Index Hint, digit ordering for Reversed Format — and that insight doesn't generalize across algorithmic paradigms. You can't use Index Hint to teach binary search, and you can't use Reversed Format to teach sorting. This means that for each new task, researchers must manually design a new CoT format that encodes the right inductive bias — an unscalable, artisanal process that doesn't illuminate any universal principle.

Moreover, the performance gains are described as "moderate" — Table 1 shows Index Hint achieving only 24.0% at long lengths on large-number addition, and Reversed Format at 35.0%, both substantially below TAIL's 86.5%. These methods help but don't solve the problem. They mitigate shortcut learning rather than eliminating it, because they don't provide the model with a complete, principled framework for step-by-step algorithmic execution.

Reasoning Models: A Different Mechanism Entirely

A final category of comparison is worth noting, even though it's not a "prior approach" in the same sense. The paper explicitly contrasts TAIL with reasoning models like DeepSeek-R1, which also produce long CoT through reinforcement learning. The authors argue that these models improve performance through a fundamentally different mechanism:

"Reasoning models aim to expand the search space by prolonging the reasoning trajectory, encouraging broad method exploration instead of delving into the problem step by step"

The Appendix K.1 example vividly illustrates this: DeepSeek-R1's response to a string reversal task shows the model trying multiple approaches (manual reversal, Python-style slicing, splitting by words), retracing steps, and ultimately producing an incorrect answer with visible uncertainty. The CoT is long, but it's long because the model is searching, not because it's systematically executing a known algorithm. This exploration-based approach can improve average-case performance by trying many heuristics, but it doesn't guarantee correctness — and as Figure 3 shows, DeepSeek-R1's length generalization on structured algorithmic tasks is substantially worse than TAIL's, with sharp degradation on longer sequences.

This contrast is crucial for understanding the paper's positioning: TAIL is not about making models think longer (the reasoning model paradigm) or tweaking architecture or CoT format for specific tasks (the prior data-driven paradigm). It's about giving models a universal procedural framework — the Turing machine execution trace — that applies across all computable problems and guarantees, in principle, that if the model faithfully follows the trace, it will arrive at the correct answer regardless of input length.

How This Paper Positions Itself

The paper's conceptual innovation is to observe that all the tasks where length generalization matters — arithmetic, sorting, search, dynamic programming — share a common property: they are computable by deterministic algorithms. The execution trace of any such algorithm can be modeled as a Turing machine transitioning through states, reading from and writing to a tape. Therefore, rather than designing task-specific CoT formats, the natural universal approach is to structure CoT to imitate the Turing machine's execution trace.

The authors make this connection explicit in Section 2.1:

"many tasks can essentially be solved through discrete symbolic transformations governed by bounded algorithmic computational rules... We refer to such tasks as Computable Problems, whose commonality lies in being solvable by a well-defined, deterministic algorithmic procedure. Such algorithms inherently handle inputs of arbitrary length, which aligns with the goal of length generalization."

The key insight is that algorithms already solve the length generalization problem — a sorting algorithm sorts arrays of any size, a search algorithm searches lists of any length, an addition algorithm adds numbers of any digit count. If the model can learn to faithfully execute the algorithm step by step, length generalization comes for free because the algorithm's structure is inherently length-invariant. The challenge is getting the model to learn the algorithm rather than shortcuts.

This framing unifies the problem space under a single theoretical umbrella (Church-Turing thesis: all computable problems are solvable by Turing machines) and provides a principled design methodology for CoT construction: identify the algorithm, implement it as a Python program, add string-append statements to dump the execution trace, and use that trace as training data. The three TAIL modules — Linear Transition, Atomic State, Memory Fetcher — are not arbitrary design choices but are derived from the structural properties of Turing machine execution:

• Linear Transition corresponds to unrolling the state transition sequence $q_0 \to q_1 \to ... \to q_n$, flattening even complex control structures (loops, recursion) into a linear trace that the autoregressive model can process.
• Atomic State corresponds to enforcing that each reasoning step is a single Turing machine state transition (read-write-update), preventing the model from learning composite shortcuts that skip intermediate reasoning.
• Memory Fetcher directly addresses the mismatch between the Turing machine's in-place tape modification and the autoregressive model's append-only context: by explicitly re-outputting operands at each step, it simulates the tape head reading before writing, localizing the attention patterns needed for accurate computation.

The paper's claim to universality rests on this derivation: because the Turing machine is a universal model of computation, TAIL's approach should work for any computable problem, not just the specific tasks tested. The authors validate this on 18 diverse tasks across 8 algorithmic paradigms — far broader than prior work, which typically tested 1-3 tasks within the same algorithmic family.

The thinking-style ablation (Figure 4) provides the most compelling evidence for the paper's central thesis: the three modules, not the linguistic surface form, are what matter. When all human-like narrative ("Let's perform the binary search step by step...") is stripped away, leaving only the bare atomic states, memory fetchers, and linear transitions, performance is indistinguishable from the stylized version. This is the paper's answer to the question it poses in the introduction: "Is there a universal and effective CoT structure for length generalization?" The answer is yes — and it's not a CoT "style" at all, but a structured imitation of the algorithmic execution process itself.

3. Technical Approach

3.1 Reader Orientation

TAIL is a data synthesis framework — it is not a model architecture, a training algorithm, or a prompting technique. It is a method for constructing chain-of-thought training data such that when a standard language model is fine-tuned on this data, it learns to execute algorithms step by step and thereby generalizes to input lengths never seen during training. The problem it solves is that standard CoT training causes models to learn spurious shortcuts that correlate with correctness on short inputs but fail on long ones; TAIL replaces those shortcuts with a universal structural template derived from the Turing machine execution model, which is inherently length-invariant because algorithms process inputs of any size through the same sequence of primitive operations.

3.2 Big-Picture Architecture (Diagram in Words)

The TAIL system has three conceptual stages, each feeding into the next:

1. Program Authoring (one per task, done once). For each task (e.g., binary search, 0-1 knapsack, large-number addition), a human writes a Python program that implements the correct algorithm. Crucially, the program is instrumented with string-append statements that dump its execution trace into a text buffer. This trace is the TAIL-structured chain-of-thought. The program takes a random input (of specified length) and produces both the correct answer and the complete step-by-step reasoning trace.

2. Data Synthesis (automated, at scale). The instrumented program is run many times with varied inputs to generate a large corpus of (input, TAIL-CoT, answer) triples. The input is rendered into natural-language query templates (the authors create "more than 20 query templates" per task for diversity). The output contains only the reasoning trace and final answer. Key properties: the trace conforms to the three TAIL modules (described below), uses no external tool calls or search — it is a single linear text that the model will learn to autoregressively generate.

3. Fine-Tuning (standard SFT). A pretrained LLM (Qwen2.5-7B) is fine-tuned via supervised next-token prediction on the synthetic (query, TAIL-CoT) pairs. The model learns to generate the TAIL-structured reasoning trace when given a new query. At inference, greedy decoding produces a trace that follows the algorithmic pattern; the answer is extracted from the final step.

Information flows: Task specification → Python program with trace instrumentation → batch generation of (query, TAIL-CoT) pairs → deduplication and length-range stratification → SFT on Qwen2.5-7B → inference with greedy decoding on out-of-distribution lengths.

3.3 Roadmap for the Deep Dive

• First, the core claim about what TAIL is and what type of paper this is, to ground everything that follows.
• Second, the formal connection to the Turing machine (Section 2.2 of the paper), because all three TAIL modules are derived from Turing machine properties and the derivation would be unmotivated without this foundation.
• Third, each of the three core modules in detail: Linear Transition (the macro-level CoT structure), Atomic State (the micro-level step decomposition), and Memory Fetcher (the attention-localization mechanism). These are the heart of the method and must be understood individually before their interaction can be appreciated.
• Fourth, the data synthesis pipeline — how Python programs are instrumented to produce TAIL-structured traces, the distinction between TAIL-CoT and TAIL-CoT-styled, and the practical construction choices (query templates, length ranges, dataset sizes).
• Fifth, the training and evaluation configuration, including hyperparameters, the dual-model evaluation framework, and the specific length ranges that define "short," "medium," and "long" for each task.

3.4 Detailed, Sentence-Based Technical Breakdown

This is a data synthesis method paper whose core idea is that structuring chain-of-thought training data to imitate a Turing machine's execution trace — through three specific structural modules — causes models to learn the underlying algorithm rather than statistical shortcuts, enabling length generalization across diverse computable problems.

The Formal Connection to Turing Machines

Before defining the modules, the paper establishes a formal relationship between LLM chain-of-thought reasoning and Turing machine execution (Section 2.2). This mapping is the theoretical justification for why the three modules take the specific form they do.

The Turing machine as a model of computation. A Turing machine is formally defined as a 7-tuple:

$M = (Q, \Sigma, \Gamma, \delta, q_0, B, F)$

where $Q$ is a finite set of internal states, $\Sigma$ is the finite input alphabet (symbols the machine can read), $\Gamma$ is the finite tape alphabet (superset of $\Sigma$ including the blank symbol $B$), $\delta$ is the state transition function, $q_0 \in Q$ is the designated initial state, $B \in \Gamma \setminus \Sigma$ is the blank symbol representing uninitialized tape cells, and $F \subseteq Q$ is the set of accepting (halting) states.

What this defines: a machine with an infinite tape (memory), a read/write head positioned over one tape cell at a time, and a finite control unit that, at each step, reads the symbol under the head, consults $\delta$ to determine what symbol to write, what direction to move the head (left or right), and what state to enter next. Computation proceeds as a discrete sequence of these read-write-move-state transitions until an accepting state is reached.

Why this matters: the Church-Turing thesis states that any effectively computable function can be computed by a Turing machine. By structuring CoT to mimic Turing machine execution, TAIL inherits this universality — any problem solvable by a deterministic algorithm can, in principle, have its CoT constructed through this template. This is what distinguishes TAIL from task-specific methods like Index Hint or Reversed Format, which encode structural insights about particular computational patterns rather than about computation itself.

The state transition formalized. The paper defines a single Turing machine step as:

$\delta(q_s, a) = (q_{s+1}, b, D)$

where $q_s$ is the current state, $a$ is the symbol read from the tape at the current head position, $q_{s+1}$ is the next state, $b$ is the symbol written to the tape (overwriting $a$), and $D \in \{\text{Left}, \text{Right}\}$ is the direction the head moves after writing.

What this computes: given the current internal state and the observed tape symbol, the transition function deterministically specifies the next internal state, the symbol to write, and the head movement direction. The complete computation from start to halt is the linear sequence of these transitions: $q_0 \to q_1 \to q_2 \to ... \to q_n$ where $q_n \in F$.

Why this form is central to TAIL: the transition function conflates two logically independent operations into a single $\delta$ application — reading a symbol and then writing/updating — and the overall computation is a linear chain of these conflated operations. TAIL's modules are designed to deconfound these operations and make the linear structure explicit. Specifically, Memory Fetcher decouples the reading from the writing by making operand retrieval a separate, explicit step before each computational operation, while Linear Transition enforces that the CoT is a flat sequential chain even when the underlying algorithm has nested control structures. The paper states this mapping explicitly:

"each reasoning step $x$ corresponds to a Turing Machine state $q$"

so the CoT sequence $x_0 \to x_1 \to ... \to x_n$ is the analog of $q_0 \to q_1 \to ... \to q_n$.

The critical gap TAIL fills. The paper notes that prior work (Li et al., 2024) proved Transformers can achieve Turing completeness given sufficiently long CoT — meaning the architecture can simulate any Turing machine. However, that work "has not provided concrete guidelines for constructing such CoT sequences in a wide range of tasks." TAIL provides those guidelines: the three modules are the structural template that instantiates Turing machine execution in autoregressive text generation.

Module 1: Linear Transition

Linear Transition operates at the macro-structural level of the CoT: it governs how individual reasoning steps are arranged into a complete solution. The rule is simple but has deep implications for what kinds of reasoning patterns the model is exposed to during training.

Definition. Linear Transition requires that the entire CoT be organized as a single, flat, sequential chain of reasoning steps with no branching, no nested substructures, and no non-sequential control flow. The paper states this as:

"complex reasoning structures (like trees and graphs) can be linearly unrolled and traversed to enable complete and non-redundant execution of all reasoning steps, thereby preventing shortcuts in the reasoning process"

What this means operationally. Consider binary search. The natural conceptual structure is a tree: at each node, you compare the target to the middle element, then recursively search either the left or right subarray. A human might describe binary search hierarchically — "we searched the left half, and within that, the left quarter" — but the actual execution trace is linear: step 1 examines the full array, step 2 examines one half, step 3 examines one quarter, and so on. TAIL unrolls this tree into a flat sequence by having each step specify exactly which subarray is being processed (e.g., "The currently processed interval is {0,10}" at step 1, then "The currently processed interval is {0,4}" at step 2, then "{0,1}" at step 3). The transitions between steps are marked explicitly: the paper uses notation like {0,10} → {0,4} to denote "after this step, the search space narrows from indices 0-10 to indices 0-4."

For an algorithm with a while-loop (like Dijkstra's algorithm or bubble sort), the loop is unrolled into a linear trace where each iteration becomes a sequence of atomic states corresponding to one pass through the loop body. For recursion (like computing Levenshtein distance or derangements), the call stack is flattened: each recursive subproblem invocation appears as a contiguous block of steps in the trace, with explicit markers indicating which subproblem is currently being solved.

The RASP-Generalization Conjecture connection. The paper anchors this design choice in a theoretical insight from Zhou et al. (2023). The RASP-Generalization Conjecture states that Transformers "struggle with problems that involve intricate control structures, such as loops." The conjecture is based on the RASP (Restricted Access Sequence Processing) computational model, which characterizes what kinds of functions Transformers can learn to compute in a length-generalizable way. Loops — where the same operation must be applied a variable number of times depending on the input — are particularly challenging because the model must learn to count iterations implicitly through its positional encodings and attention patterns, rather than having an explicit loop counter.

Linear Transition addresses this by eliminating loops from the CoT structure. Instead of "repeat the following operation until condition X is met," the CoT explicitly lists every iteration as a separate reasoning step. The model no longer needs to learn loop control flow — it learns to generate the next iteration in the unrolled sequence based on the previous iteration's output. The paper's version of the RASP-L hypothesis is invoked here:

"we do not strictly follow RASP-L to constrain each reasoning step, but use it to indicate problems directly solvable by Transformers"

This is a pragmatic relaxation: they use the intuition (flat sequences are easier for Transformers) without formally verifying RASP-L compliance for every task.

Why this prevents shortcut learning. When a model is trained on standard CoT that says "repeat for each digit" without explicitly unrolling, it can learn a shortcut: always produce approximately K reasoning steps for an input of length L because that's what the training distribution exhibits. When L changes, the shortcut breaks — the model doesn't know how many iterations to produce. Linear Transition forces the training data to explicitly show exactly the right number of steps for each input length, so the model learns that step count is caused by the input content rather than correlated with input length in the training set.

The cost. Unrolling control structures makes CoT sequences longer for problems where the underlying algorithm's iteration count scales with input size. For example, bubble sort on an array of size $n$ requires $O(n^2)$ comparisons in the worst case; the unrolled TAIL trace will have $O(n^2)$ reasoning steps, making the CoT quadratically longer than the input. The paper acknowledges this implicit cost but doesn't quantify it as a limitation — it's an accepted tradeoff: longer CoT is the price of length generalization.

Module 2: Atomic State

Atomic State operates at the micro-structural level of each individual reasoning step. While Linear Transition specifies how steps are arranged (flat sequence), Atomic State specifies what a single step contains — and, critically, what it does not contain.

Definition. An Atomic State is the smallest meaningful unit of algorithmic progress, consisting of three components in a fixed structure:

1. Operand retrieval — identifying and surfacing the specific data values that this step will operate on (implemented via Memory Fetcher, detailed in the next subsection).
2. Elementary computation — performing a single operation on those operands to produce a local result (e.g., comparing two values, adding two digits, updating one cell of a DP table).
3. Logical control — determining the next state based on the result (e.g., "since the target is less than the median, continue on the left subinterval").

The paper states:

"overly large reasoning steps not only increase the difficulty of learning for the model but also risk introducing shortcuts within a single step. Therefore, we attempt to constrain the size of a reasoning step by enforcing a standardized internal structure"

The granularity constraint. The paper provides a concrete operational criterion for what counts as "atomic":

"we define an Atomic State as a single algorithmic step in the program without internal loops"

This means each Atomic State corresponds to exactly one Python statement or small block at the innermost level of the program — no for-loops, no while-loops, no recursion within a single Atomic State. For example, in binary search, one Atomic State computes the midpoint from left and right boundaries, compares the target to the middle element, and decides whether to go left or right. It does not do multiple iterations of narrowing the search range — that would be multiple Atomic States chained by Linear Transition.

Why this granularity matters. When a reasoning step is too large — say, "sort the list using bubble sort" as a single step — the model can learn a mapping from (input list, "sort the list") to (output list) by memorizing input-output pairs for the training lengths. This works on training-length inputs but fails on longer inputs because the model hasn't learned how to sort; it has learned pattern completion. By forcing each step to be an atomic operation that is identical regardless of input size (comparing two adjacent elements and conditionally swapping them is the same operation whether the list has 3 elements or 100), Atomic State ensures the model must learn the operation itself, which naturally transfers across lengths.

Connection to the Turing machine state. In a Turing machine, each state transition $\delta(q_s, a) = (q_{s+1}, b, D)$ is atomic: it reads one symbol, writes one symbol, moves one step, and transitions to exactly one next state. An Atomic State in TAIL mirrors this: it reads specific operands (analogous to reading from the tape), produces a local result (analogous to writing to the tape), and specifies the next state (analogous to the next state in $Q$). The paper explicitly draws this parallel:

"each Atomic State should adhere to the principles of realizability and simplicity"

where "realizability" means the state corresponds to a single, unambiguous operation that the model can learn to execute accurately, and "simplicity" means it avoids compositional complexity that would reintroduce shortcuts.

Examples from the paper. Figure C3 shows TAIL-CoT for binary search. Each Atomic State is marked by an interval specifier (e.g., {0,10}, then {0,4}, then {0,1}, then {1,1}). Within each state, the structure is: (1) Memory Fetcher outputs the relevant subarray elements with their indices, (2) the midpoint is computed and compared to the target, (3) a control decision narrows the interval. Crucially, step 1 (examining the full array of 11 elements) and step 2 (examining the left half of 5 elements) are separate Atomic States even though they're part of the same "binary search" — the iteration is unrolled into a sequence of atomic steps by Linear Transition, and each step is individually atomic.

In Figure C4 (the styled version), the Atomic State structure is preserved beneath the natural-language veneer: "1. The currently processed interval is..." is one Atomic State, then "2. The currently processed interval is..." is the next. The natural language adds transition phrases ("Let's perform the binary search step by step") but the underlying structure — interval specification, operand listing, midpoint calculation, comparison, control decision — remains atomic per iteration.

What Atomic State prevents. Without Atomic State, a CoT might contain a reasoning step like "sort the remaining elements" or "process all digits from right to left." The model could learn to produce plausible-looking intermediate results for such macro-steps without actually performing the underlying computation, because the macro-step spans multiple primitive operations and the model can interpolate between them. Atomic State eliminates this ambiguity by forcing every individual primitive operation to be surfaced in the training data, so there is no "hidden" computation for the model to gloss over.

Module 3: Memory Fetcher

Memory Fetcher addresses a fundamental architectural mismatch between the Turing machine model of computation and the autoregressive Transformer model of generation. This mismatch is subtle but, the paper argues, is one of the primary reasons standard CoT fails at length generalization.

The mismatch. In a Turing machine, when the head reads a symbol from the tape, it does so by moving to that tape cell's position. The read operation is position-addressed and the data is directly accessible regardless of how far the head moved to get there — the tape is random-access from the perspective of any single step (the head can move arbitrarily far in one step). After reading, the head overwrites the symbol in-place, modifying the tape at that position.

In contrast, an autoregressive Transformer can only append tokens to its context. It cannot modify previously generated tokens. Its attention mechanism can attend to any previous position — so in theory it can "read" any operand from anywhere in the context — but in practice, attention becomes diluted as the context grows, and attending precisely to a specific token among thousands requires the model to learn increasingly precise attention patterns. The paper describes this as:

"simultaneously performing data retrieval and generating the elementary solution at the same time increases the learning difficulty for the model"

Definition. Memory Fetcher decouples data retrieval from computation by mandating that, at the beginning of each Atomic State, the model explicitly outputs all operands needed for that state's computation as literal text before performing any operations on them. The paper states:

"to address this, we propose Memory Fetcher to decouple these two operations by: (1) first explicitly outputting all relevant operands at the beginning of every Atomic State, (2) then performing reasoning and outputting local results"

Operational mechanics. In the binary search example (Figure C3, C4), the Memory Fetcher step takes the form:

Memory Fetcher: [(s0=-5957), (s1=-5259), (s2=-4195), (s3=-2263), (s4=1289)]
Memory Fetcher: Find=-5259

The first line retrieves the current subarray with element-to-index mapping. The second line retrieves the target value being searched for. Only after both are explicitly written out does the reasoning step proceed: "Mid=2, s2=-4195 > Find" — the comparison is now between two values that are adjacent in the context (the most recently generated tokens), not between a value generated 200 tokens ago and the current computation.

Why this helps — the attention localization argument. The paper provides a theoretical grounding by citing Wang et al. (2025), which "theoretically proved" that localizing operands at the end of the context improves reasoning accuracy. The intuition (elaborated in Appendix G and Figure G2) is:

• Without Memory Fetcher: when the model computes "is the middle element greater than the target?", the middle element was generated many steps ago (when the subarray was first listed) and the target was generated even earlier (in the problem statement). The attention mechanism must simultaneously (a) attend to the local reasoning pattern for "compare X to Y," (b) attend to the distant position where the middle element was defined, and (c) attend to the even more distant position where the target was defined. These competing attention demands cause "significant sparsification of long-range attention" — the attention weights get distributed across many positions, and the precise values needed for the comparison get insufficient focus.

• With Memory Fetcher: the operands are re-output at the current position, immediately before the computation. The attention for the comparison can be purely local — the target value was generated 5 tokens ago, the middle element was generated 10 tokens ago, and the comparison logic attends to a narrow recent window. The long-range retrieval (finding the correct operands in the first place) is isolated to the Memory Fetcher step itself, which is a simpler operation (copy a value) than computation (compare values and decide next state).

Figure G2 visualizes this: the attention maps of a TAIL-fine-tuned model show "strong and focused attention on the corresponding tokens" in layers where computation occurs, while the model without Memory Fetcher shows "attention patterns become sparse and disorganized, showing insufficient focus on the operands."

The decoupling principle more formally. The paper frames this as separating two distinct attention subroutines:

1. Long-range operand retrieval: "where in the context is the value I need for this computation?" — this is what Memory Fetcher does, and it produces the value as literal output.
2. Local computation: "given these nearby values, what operation should I apply?" — this is what the subsequent atomic computation does, using the values that Memory Fetcher just produced.

Traditional CoT conflates these: the model must retrieve and compute in the same generation step. Memory Fetcher separates them into two sequential steps, each with a simpler attention profile.

What counts as an operand? The paper's examples show that Memory Fetcher retrieves:

• Current state parameters: the search interval boundaries, the DP table row/column being processed, the current list element indices.
• Data values: the actual elements in the current subarray, the current DP cell value, the digit being added.
• Control values: the target being searched for, the pivot element, the carry bit from the previous digit addition.

Essentially, any value from the past context that is needed for the current computation gets explicitly re-output. Values produced within the current Atomic State (like the newly computed midpoint) don't need Memory Fetcher because they're already local.

Memory Fetcher is not retrieval-augmented generation (RAG). This is an important distinction: Memory Fetcher doesn't query an external database or vector store. The retrieved operands come from the model's own previously generated tokens — it's copying from its own context. The "fetching" is achieved through the model's attention mechanism attending to the correct earlier positions and generating them again. The module enforces when and where this copying happens in the CoT structure, not how it happens mechanically.

The ablation evidence. Table 2 shows that removing Memory Fetcher causes the largest performance drop on iteration-heavy tasks: Population Growth drops from 90.0% to 73.8% (Medium) and from 84.4% to 67.6% (Long). This makes sense: iterative tasks involve repeatedly applying the same operation to a state variable that gets updated and carried forward — precisely the scenario where long-range attention to the previous state is critical. In contrast, Compare Numbers — a simulation task where each comparison is local to adjacent digits — shows a smaller drop without Memory Fetcher (from 94.2% to 90.2% Medium, 90.0% to 88.0% Long), because the operands are already naturally close in the context.

The Data Synthesis Pipeline

The three modules are structural constraints on the CoT format. The practical instantiation of these constraints into large-scale training data follows a systematic pipeline (described in Section 4.1 and Appendix C).

Step 1: Implement the algorithm as an instrumented Python program. For each of the 18 tasks, a human writes a correct Python program that solves the task for arbitrary inputs within the task's length range. This is feasible because all 18 tasks are deterministic computable problems — the algorithms are well-known (binary search, Dijkstra's algorithm, dynamic programming for 0-1 knapsack, bubble sort, etc.). The authors argue this is a key advantage:

"since each task belongs to a specific algorithm, it's feasible to construct a Python program and add string append statements to assemble CoT"

The programs are not "solving" the tasks through learned heuristics — they are exact implementations that produce the correct answer. The CoT is generated by inserting string-concatenation statements at specific points in the program that output the execution state. When the program runs on an input, it executes the algorithm and simultaneously produces the TAIL-structured CoT as a side effect of the print statements.

Step 2: Inject the three modules through program instrumentation. The paper specifies how each module is realized in the program:

• Atomic State: "Treating each algorithmic step as an Atomic State, especially each time entering a loop." This means the program's loop structure defines the state boundaries — each loop iteration is one Atomic State, and within that iteration, the string-append statements output the operand retrieval, elementary computation, and control decision for that iteration. For non-loop algorithms (like recursion), each recursive call is an Atomic State.

• Linear Transition: "Unfolding the algorithmic process sequentially as Linear Transition, achieved by using programs to synthesize CoT itself." Since the Python program executes sequentially (even recursive calls have a sequential execution order), the natural output of the string-append statements is already a flat sequence. The program doesn't need to explicitly "unroll" anything — sequential execution does it automatically. For recursion, the program outputs state markers showing the current subproblem, creating the appearance of a linear traversal of the call tree.

• Memory Fetcher: "Explicitly outputting all relevant operands of current algorithm step as Memory Fetcher in CoT." Before performing each atomic operation, the program prints the values it will operate on. In binary search, this means printing the current subarray bounds and elements, and the target value. In DP, this means printing the current cell indices and the previously computed values needed to compute the current cell.

Step 3: Generate training and evaluation data at scale. The instrumented program is run with many different inputs to produce the dataset. The key configuration choices:

• Length ranges. Each task has three length ranges — Short (S), Medium (M), and Long (L) — defined specifically for that task based on what constitutes a meaningful difficulty gradient. For example, Bubble Sort has S: [2,4] elements, M: [5,6], L: [7,8]; Large Number Addition has S: [10,30] digits, M: [31,40], L: [41,50]; Binary Search has S: [5,20] elements, M: [21,40], L: [41,70]. The full table is in Appendix E (Table E1). These ranges are designed so that Long represents a substantial extrapolation from Short — typically 2-5× the training length — while remaining computationally feasible to evaluate.

• Dataset sizes. 100,000 training samples are generated for each length range (some harder-to-construct tasks retain 20,000). For evaluation, 500 samples per length range per task (or 200 for harder tasks), producing 1,500 evaluation samples per task total. The evaluation samples are verified to not overlap with training samples — "strict deduplication" is performed.

• Query diversity. The paper generates "more than 20 query templates" per task to vary the surface form of the problem statement. Figure C2 shows three example queries for the Binary Search task, varying in phrasing while asking the same underlying question. This prevents the model from overfitting to a single query format while keeping the reasoning structure identical.

Step 4: Produce two CoT variants. The paper distinguishes between two versions of the synthetic data:

• TAIL-CoT: contains only the three core modules with no additional natural language. The format is symbolic and minimal — a sequence of Atomic States delimited by markers like {0,10}, containing Memory Fetcher outputs like [(s0=-5957), ...], elementary computations like Mid=5, s5=3514>Find, and Linear Transition markers like {0,10} → {0,4}. Figure C3 is the canonical example. This version is used to isolate the effect of the core modules (the "thinking style" ablation in Figure 4).

• TAIL-CoT-styled: wraps the TAIL-CoT structure in natural language for readability while preserving the underlying modular structure. Atomic States become numbered paragraphs ("1. The currently processed interval is..."), Memory Fetcher becomes "First we map each number to its index...", and control decisions become "The target number is less than the median number, continue these operations on the left subinterval." Figure C4 shows this version. This is the version used for the main experiments in Figure 3, because it's more human-readable and the thinking-style ablation (Figure 4) shows it performs equivalently to TAIL-CoT.

The critical design choice: program execution trace as ground truth. The CoT is not generated by an LLM, not annotated by humans, and not produced through search or reinforcement learning. It is the literal execution trace of a correct Python program. This has two crucial implications:

1. Correctness is guaranteed: every TAIL-CoT training example has a correct reasoning trace leading to the correct answer, because the program is a correct implementation of the algorithm. There are no reasoning errors, hallucinations, or near-misses in the training data.

2. Structural consistency is enforced by construction: the program's instrumented output naturally conforms to the three modules because the program was written to output in that format. There's no need to verify or post-process the CoT for module compliance — it's built into the generation process. This is what the paper means by "TAIL is task universal" — any task solvable by a Python program can have its CoT constructed this way.

Training and Evaluation Configuration

Model and fine-tuning. The paper fine-tunes Qwen2.5-7B (a 7-billion-parameter pretrained Transformer) using standard supervised fine-tuning (SFT) — next-token prediction on the (query, TAIL-CoT) pairs. Hyperparameters: training for "2 epochs for most tasks and more epochs for a few more challenging ones," global batch size of 1024, initial learning rate of $1 \times 10^{-5}$ decaying to $7 \times 10^{-7}$, and weight decay of 0.1. The optimizer is not explicitly named but the learning rate schedule (linear decay from 1e-5 to 7e-7) is standard for SFT. The model is fine-tuned separately for each of the 18 tasks — there is no multi-task training in the main experiments. This means the model is a specialist for each task, not a generalist that can solve all 18 tasks from a single checkpoint. (The paper explores compositional generalization in Appendix H, finding it "not significant" — training on tasks A and B doesn't transfer well to task C even within the same algorithmic paradigm.)

The dual-model evaluation framework. To evaluate pass@1 label accuracy, the paper uses an unusual dual-model setup (Section 4.2):

1. Answer extraction: a "small 1.5B specialized model" extracts the final answer from the generated CoT. This handles the variability in how the answer might be formatted (boxed, stated in text, etc.).
2. Correctness judgment: Qwen2.5-72B-Instruct compares the extracted answer to the ground truth, outputting \boxed{YES} or \boxed{NO}.

This two-step process is used to avoid brittle string matching since answers might be formatted differently across tasks. The extraction model is a smaller specialized model fine-tuned for this purpose; the evaluation model is a much larger instruction-tuned model to ensure reliable comparison. Both are separate from the 7B model being evaluated.

What is being measured. The primary metric is pass@1 label accuracy under greedy decoding (temperature = 0). For each test query, the model generates exactly one CoT via greedy decoding, and the extracted answer is compared to the ground truth. The accuracy is reported separately for each length range (S, M, L). Length generalization is operationalized as: can a model trained only on S-range data maintain high accuracy on M-range and L-range data? A "sharp performance degradation" on out-of-domain lengths indicates failure to generalize.

The length generalization activation experiment (Appendix D). To investigate how much long-sequence data is needed to recover length generalization, the paper keeps the total training sample count constant but varies the proportion from S, M, and L ranges: <1:0:0> (S-only, the pure generalization setting), <8:1:1>, <7:2:1>, <5:3:2>, and <4:3:3>. The finding (Figure D1) is that for most tasks, adding even a small fraction of longer sequences (<8:1:1>) causes performance to rapidly approach saturation — a phenomenon the paper calls "length generalization activation." This contrasts with prior work (Lee et al., 2023) which concluded that "balanced length" training data is necessary, and suggests that TAIL's structured CoT makes the model much more data-efficient at learning the underlying algorithm: once the structure is learned from short sequences, only a few longer examples are needed to demonstrate that the same structure scales.

Baseline data construction for comparison methods (Appendix F). For the comparison with Index Hint and Reversed Format on the Large Number Addition task, the paper constructs equivalent training data following the principles of those methods but adapted for the authors' more challenging setting (random-length operands with optional decimal points). For Index Hint, digits are annotated with a letter (a, b, c) indicating their position in a zero-padded alignment, with negative indices for decimal places. For Reversed Format, the digits of both operands are reversed before being presented. The key difference from prior work's experiments is that the operands have random lengths rather than fixed lengths, and decimal points can appear at any position — making the task substantially harder and the prior methods' limitations more apparent (Table 1: Index Hint achieves only 24.0% Long vs. TAIL's 86.5%).

Summary of Why These Three Modules Together

The three modules are not independent optimizations that happen to work well together. They form a complete specification of how a Turing machine execution trace maps to autoregressive text generation:

• Linear Transition (macro-level): ensures the CoT is a flat sequence, matching the Turing machine's sequential state transition model, and eliminating control-structure complexity that causes shortcut learning.
• Atomic State (micro-level): ensures each step in the sequence is a single primitive operation, matching the granularity of a Turing machine transition $\delta(q_s, a) = (q_{s+1}, b, D)$, and preventing the model from learning composite shortcuts within a step.
• Memory Fetcher (attention-level): resolves the architectural mismatch between the Turing machine's in-place tape modification (random access at any distance) and the autoregressive Transformer's append-only context (where relevant data gets buried in increasingly long history), by making operand retrieval an explicit, attention-localizing step.

Removing any one module (Table 2) breaks the correspondence to the Turing machine model in a different way, and the ablation results show that each removal degrades length generalization, with the exact severity depending on which algorithmic property the task most depends on. The thinking-style ablation (Figure 4) then shows that these three structural modules — not the natural language wrapper — are sufficient for length generalization, completing the paper's central empirical argument.

4. Key Insights and Innovations

Innovation 1: The Meta-Problem Unification — Length Generalization as Turing Machine Imitation

The paper's most fundamental contribution is not any single module but rather the reframing of length generalization from a disparate collection of task-specific failures into a single problem with a single solution principle. This is a conceptual advance, not an architectural one.

Before this work, the field treated length generalization as something that had to be addressed case by case. Index Hint (Zhou et al., 2023; 2024) worked for symbolic matching tasks where positional identity was the core operation. Reversed Format (Lee et al., 2023; Shen et al., 2023; McLeish et al., 2024) worked for arithmetic tasks where right-to-left carry propagation clashed with left-to-right generation. Each method encoded a structural insight about a specific computational pattern, and the tacit assumption was that length generalization required discovering the right inductive bias for each pattern. There was no unifying principle — just a growing toolkit of bespoke CoT format tweaks.

The authors' key move is to step back and ask: what do all these problems have in common? The answer they propose is deceptively simple: they are computable — solvable by deterministic algorithms. And by the Church-Turing thesis, any algorithm's execution can be modeled as a Turing machine trace. Therefore, structuring CoT to imitate Turing machine execution should be a universal solution for length generalization on computable problems, not just a task-specific one.

What makes this reframing genuinely novel — rather than an obvious invocation of Turing completeness (which the field has known about since the Transformer's theoretical properties were established) — is that it bridges theory and practice with a concrete instantiation. Prior work (Li et al., 2024) proved Transformers are Turing-complete with sufficient CoT, but that result said nothing about how to construct the CoT to actually induce Turing machine behavior during training. It's one thing to know an architecture can simulate a Turing machine; it's quite another to design training data that causes the model to learn that simulation rather than converging to statistical shortcuts. The authors identify three structural properties of Turing machine execution — sequential state transition, atomic read-write operations, and localized operand access — and translate each into a CoT design constraint. The mapping from Turing machine abstraction to CoT formatting rules is the intellectual contribution that makes the theory actionable.

The thinking-style ablation (Figure 4 and Appendix C) provides the cleanest evidence for this reframing's validity. When all natural language narrative is stripped away, leaving only the three structural modules, performance is indistinguishable from the stylized version across eight algorithmic paradigms. This result has a clear implication: the structural imitation of algorithmic execution, not the surface-level "reasoning style," is what drives length generalization. It is a diagnostic finding that isolates what matters in CoT construction, and in doing so, it reframes the design space: future work on length generalization should focus on fidelity to algorithmic execution structure, not on crafting more human-like or more elaborate reasoning narratives.

This reframing is fundamental rather than incremental because it changes the unit of analysis for length generalization research. Before TAIL, the unit was the individual task (how do we make addition length-generalize? how do we make parity length-generalize?). After TAIL, the unit is the algorithmic paradigm (how do we make the CoT faithfully reflect the execution trace of the algorithm that solves this class of problems?). The shift from task-level to paradigm-level thinking is what enables the paper to claim universality — validated across 18 tasks spanning 8 algorithmic paradigms — and it represents a genuinely new way of approaching the problem.

Innovation 2: Deconfounding Computation into Three Orthogonal Structural Axes

The paper's second conceptual contribution is the decomposition of algorithmic execution into three structurally independent dimensions — sequential ordering (Linear Transition), computational granularity (Atomic State), and memory access (Memory Fetcher) — and the demonstration that each dimension matters independently for length generalization, with importance varying by the algorithmic properties of the task.

This is more than a taxonomy. It is a diagnostic framework for understanding why standard CoT fails at length generalization and what kind of structural intervention is needed. Standard CoT conflates these three dimensions: a single reasoning step might contain multiple primitive operations (violating atomicity), might skip showing intermediate state transitions (violating linear unrolling), and might require the model to attend to distant operands without explicit retrieval (conflating memory access with computation). The result is that the model can learn shortcuts in any of these dimensions — and different tasks are vulnerable to different shortcuts.

The ablation study (Table 2) is the key evidence for this decomposition's validity. Removing any single module causes performance degradation, but the pattern of degradation is task-dependent in ways that align with algorithmic structure:

• Removing Memory Fetcher hurts most on iteration-heavy tasks (Population Growth drops 16.2 percentage points on Medium, 16.8 on Long) and least on simulation tasks with naturally local operations (Compare Numbers drops only 4.0 on Medium, 2.0 on Long). This makes sense: iterative tasks repeatedly update a state variable that drifts further from the current generation position with each iteration, making long-range attention critical. Simulation tasks operate on adjacent elements where the operands are already nearby in the context.
• Removing Linear Transition disproportionately harms recursion-based tasks (Derangement drops 56.6 points on Long, compared to 55.0 with full TAIL). Recursion involves nested subproblem invocations that, when unrolled, produce a long chain of dependent states — without explicit linear unrolling, the model must implicitly track the call stack through its attention patterns, which becomes harder as depth increases.
• Removing Atomic State causes the most uniform degradation across paradigms (drops of 7–30+ percentage points depending on the task), consistent with its role as the fundamental granularity constraint — overly large steps create shortcut opportunities in any algorithm.

This is an advance over prior work because it moves from "this CoT format helps on task X" to "these are the three structural properties that a CoT format must have to support length generalization, and their relative importance depends on the task's algorithmic characteristics." It provides a design vocabulary for reasoning about length generalization interventions: rather than asking "what's the right CoT format for binary search?", one asks "what are the memory access patterns, control structures, and operational granularities in binary search, and are all three adequately surfaced in the CoT?"

The finding is fundamental rather than incremental because it identifies the independent causal factors in length generalization, rather than treating CoT design as a monolithic whole. This decomposition makes the problem tractable — it reduces the infinite space of possible CoT formats to three design axes that can be assessed and optimized independently.

Innovation 3: Proof by Construction — Program Execution Traces as Training Data

The third innovation is methodological rather than theoretical: the paper demonstrates that program execution traces, when instrumented to surface algorithmic state, serve as an automatic and correct-by-construction source of length-generalizable CoT training data. This eliminates the two hardest problems in CoT data generation — ensuring correctness and ensuring structural consistency — by construction.

The traditional approach to CoT data generation — whether through human annotation, LLM distillation, or heuristic template filling — suffers from a fundamental tension: the more complex the reasoning, the harder it is to generate correct, consistent CoT at scale. Human annotation is expensive and error-prone for multi-step reasoning. LLM distillation (as the paper shows with DeepSeek-R1 in Appendix J and K) produces CoT that is often long but structurally inconsistent — models explore multiple approaches, backtrack, and sometimes converge to incorrect answers despite elaborate reasoning. Heuristic templates (Index Hint, Reversed Format) are correct but narrowly applicable.

TAIL sidesteps this entirely by leveraging a property that is obvious in retrospect but unexploited in prior work: for computable problems, the correct algorithm is known and can be implemented as a program. That program's execution trace is a correct, complete, and structurally consistent reasoning path by definition. The CoT is not generated — it is recorded from a program that already solves the problem. The authors don't need to verify the reasoning; they need only verify that the program implements the correct algorithm, which is a standard software engineering task.

This has two implications that go beyond the paper's specific experiments:

1. Scalability. Once the program is written (a one-time cost per algorithmic paradigm), generating 100,000 training examples is a matter of running the program with different inputs. The cost scales with compute, not human effort. This makes TAIL practically scalable in a way that human-annotated or LLM-distilled CoT is not.

2. Correctness guarantees. The training data contains no reasoning errors. Every intermediate state, every operand retrieval, every control decision is correct. This eliminates a major source of noise in CoT training — the model never sees incorrect reasoning steps labeled as correct, so it never learns to reproduce reasoning errors. The contrast with DeepSeek-R1 distillation (Table J1) is instructive: fine-tuning on DeepSeek-R1's correct outputs (which likely contain some reasoning inconsistencies even when the final answer is correct) produces substantially worse length generalization than fine-tuning on program-generated traces (R1-Distill-Qwen2.5-7B achieves 61.8% Long vs. TAIL's 90.0% on Large Number Addition).

The methodological innovation is fundamental because it changes where the intelligence comes from in the training pipeline. In traditional CoT approaches, the intelligence is in the model's ability to learn reasoning patterns from data and generalize them. In TAIL, the intelligence is in the human-written program that implements the algorithm — the model's job is to faithfully imitate the program's execution, not to discover the algorithm from examples. This is a different learning problem (imitation of a known process vs. induction of an unknown process) and it turns out to be substantially easier for current LLMs, as the results demonstrate.

Innovation 4: The Negative Result — Reasoning Models and Thinking Styles Are Not the Path

The paper contains an implicit fourth contribution that is as important as the positive ones: a clear negative result demonstrating that longer CoT through broad heuristic exploration (the reasoning model paradigm) does not produce length generalization, and that the surface-level "thinking style" of the CoT is irrelevant compared to its structural fidelity to algorithmic execution.

The DeepSeek-R1 comparison (Figure 3, Appendix K) is not just a benchmark win. It isolates a mechanistic difference. DeepSeek-R1 produces long CoT — comparable in average token count to TAIL-CoT (Table I1: 1,461 vs. 1,455 tokens for the Compare Numbers task) — but achieves substantially lower accuracy (51.2% vs. 90.0%) with sharp degradation on longer sequences. The qualitative example in Appendix K.1 shows why: DeepSeek-R1's CoT for string reversal tries multiple methods (manual character-by-character reversal, Python slicing, word-level splitting), repeats verification attempts, and never settles into a systematic step-by-step execution. The model is searching — exploring a space of heuristics — rather than executing a known algorithm. Search can improve average-case performance by trying enough approaches that one works, but it doesn't guarantee correctness, and it doesn't scale systematically with input length because the search space grows combinatorially.

The thinking-style ablation (Figure 4) complements this by showing that human-like narrative ("Let's perform the binary search step by step...") adds nothing to performance. This is a striking finding given the prevailing emphasis in the reasoning model literature on natural language reasoning, self-reflection, and elaborate thinking processes. It suggests that the field's focus on how models express their reasoning — the linguistic surface form — may be misdirected for length generalization. What matters is the underlying computational structure, not the eloquence of its description.

Together, these findings establish a boundary condition for length generalization: it requires structured, algorithmic execution traces, not open-ended exploration. Reasoning models that expand CoT length through RL-driven search are optimizing for a different objective (finding correct answers through trial and error) than the one TAIL optimizes for (faithfully executing a known correct procedure). The paper doesn't argue that reasoning models are "wrong" — they clearly improve performance on many benchmarks — but it demonstrates that their mechanism of improvement does not transfer to length generalization, which requires a fundamentally different kind of reasoning: procedural, algorithmic, and systematic rather than exploratory and heuristic.

This negative result is significant because it provides a diagnostic criterion for future work: if a method improves length generalization, is it because it makes the CoT more faithfully algorithmic, or because it expands the search space? The answer determines whether the improvement will scale to arbitrary lengths (the former) or plateau as the search problem becomes intractable (the latter).

5. Experimental Analysis

Evaluation Methodology

• Dataset. The evaluation is conducted on 18 synthetic tasks spanning 8 algorithmic paradigms: Simulation, Recursion, Iteration, Greedy, Enumeration, Dynamic Programming, Divide & Conquer, and Backtracking (Table B1). Each task has three evaluation sets corresponding to Short (S), Medium (M), and Long (L) length ranges, with 500 evaluation samples per length range (or 200 for harder-to-construct tasks), yielding 1,500 total evaluation samples per task. The evaluation sets are strictly deduplicated against training data. The length ranges are task-specific: for example, Bubble Sort uses S: [2,4], M: [5,6], L: [7,8]; Large Number Addition uses S: [10,30], M: [31,40], L: [41,50] digits (full range specifications in Table E1).

• Base model(s). All main experiments fine-tune Qwen2.5-7B (Yang et al., 2024), a 7-billion-parameter open-source pretrained Transformer. The authors chose this model because it represents a modern, capable base model at a scale where fine-tuning is computationally feasible, and because open-source models in this family (along with DeepSeek-R1) "did not perform well on our tasks" out of the box (Appendix L), providing a meaningful baseline from which TAIL's improvements can be measured. For the answer extraction step in evaluation, a separate "small 1.5B specialized model" is used. For correctness judgment, Qwen2.5-72B-Instruct is employed.

• Metrics. The primary metric is pass@1 label accuracy under greedy decoding (temperature = 0). For each query, the model generates exactly one chain-of-thought via greedy decoding; the final answer is extracted from this generation and compared to the ground-truth answer. Accuracy is reported separately for each length range (S, M, L). Length generalization is operationalized as: can a model trained exclusively on S-range data maintain high accuracy when evaluated on M-range and L-range data? A sharp accuracy decline on out-of-domain lengths indicates failure to generalize.

• Baselines. The paper compares against several categories of baselines: (1) Base model without fine-tuning: Qwen2.5-7B and Qwen2.5-7B Instruct (representing a model fine-tuned on large amounts of traditional non-TAIL CoT data). (2) Reasoning model: DeepSeek-R1 671B (Guo et al., 2025), evaluated zero-shot as a representative open-source reasoning model that produces long CoT through reinforcement learning. (3) Prior data-driven CoT methods: Index Hint (Zhou et al., 2023; 2024) and Reversed Format (Zhou et al., 2024; Lee et al., 2023; Shen et al., 2023; McLeish et al., 2024), compared specifically on the Large Number Addition task. (4) R1-Distill fine-tuning: Qwen2.5-7B fine-tuned on an equal amount of correct CoT data distilled from DeepSeek-R1 (Appendix J). For the prior methods (Index Hint and Reversed Format), the paper constructs training data following the methods' principles but adapted for the more challenging setting of random-length operands with optional decimal points (Appendix F).

• Generation budget / compute accounting. The paper does not use a FLOPs-based or token-based compute budget for fair comparison in the main experiments. The primary axis of comparison is accuracy at each length range given fixed training data quantity (100,000 S-range samples for all methods compared on Large Number Addition; 100,000 samples per length range for TAIL's main experiments). The CoT length comparison (Table I1) partially addresses cost: TAIL-CoT averages 1,455 tokens vs. DeepSeek-R1's 1,461 tokens on the Compare Numbers task, indicating comparable inference cost despite TAIL's 7B scale vs. DeepSeek-R1's 671B. However, the paper does not systematically account for the cost of generating the synthetic training data (writing and running the instrumented Python programs), the cost of SFT, or the cost difference between training on S-only vs. mixed-length data. This is a notable gap: the "cost" of TAIL includes the one-time human effort of implementing each task's algorithm as an instrumented Python program, but this cost is not quantified or compared to alternatives.

• Cross-validation / statistical protocol. No cross-validation or statistical significance testing is reported. For each task, the model is trained once on the S-range training set and evaluated on the fixed S, M, L evaluation sets. The length generalization activation experiments (Appendix D) sweep five data proportion configurations (<1:0:0>, <8:1:1>, <7:2:1>, <5:3:2>, <4:3:3>), but each configuration is trained once. The evaluation sets contain 500 samples per length range per task (or 200 for harder tasks), providing reasonable per-task sample sizes, but there is no quantification of variance across training runs or evaluation subsets.

Main Quantitative Results

Overall Length Generalization Across 18 Tasks

The headline result (Figure 3) is that Qwen2.5-7B fine-tuned on TAIL-CoT-styled data achieves strong length generalization across all 18 tested tasks, with no sharp performance degradation on out-of-domain length sequences. The figure displays pass@1 accuracy for S, M, and L ranges as connected line plots for each task. Key observations from this figure:

• Near-saturation on several tasks. Compare Numbers, Bubble Sort, and Any Substring reach near-ceiling accuracy even on L-range data, indicating that the model has fully internalized the underlying algorithm and is no longer sensitive to input length within the tested ranges.
• Consistent improvement over base model and instruct model. Qwen2.5-7B and Qwen2.5-7B Instruct show substantially lower accuracy across all tasks and length ranges, with many tasks exhibiting sharp drops from S to L. The authors state that TAIL "outperformed Qwen2.5-7B (representing the base model), Qwen2.5-7B Instruct (representing fine-tuning on a large amount of traditional non-TAIL-CoT data), and DeepSeek-R1 671B (a representative open-source reasoning model) in both label accuracy and length generalization abilities."
• DeepSeek-R1 underperforms despite its scale. The 671B reasoning model shows lower accuracy than the 7B TAIL-fine-tuned model on most tasks, with visible degradation on longer sequences. The paper attributes this to mechanistic differences: DeepSeek-R1 explores heuristics rather than executing a structured algorithm (see Appendix K for the qualitative comparison).

The authors summarize this finding in Section 4.3:

"We observe length generalization on most difficult tasks, where there was no sharp performance degradation on out-of-domain length sequences."

However, the paper also notes limitations: "we also find some limitations of TAIL, details can be seen in Appendix L." These limitations include the gap with closed-source models (e.g., O4-mini, which the authors acknowledge "were able to solve these problems well") and the failure of compositional generalization (Appendix H).

Comparison with Prior Data-Driven Methods on Large Number Addition

Table 1 provides the direct comparison on the Large Number Addition task (Simulation algorithm). This is the only task where prior methods are compared because, as the authors note, "previous methods (Index Hint and Reversed Format) have proven effective on limited problems such as large number operations." The results:

Table 1: Pass@1 accuracy on Large Number Addition task.

TAIL outperforms Index Hint by 40.0 percentage points on S-range data, 58.0 points on M-range, and 62.5 points on L-range. Against Reversed Format, the margins are even larger: 57.5 points on S-range, 57.0 on M-range, and 51.5 on L-range. Crucially, both prior methods show substantial degradation from S to L (Index Hint drops 33.0 points; Reversed Format drops 4.5 points but from a much lower baseline), while TAIL's degradation is only 10.5 points from S to L.

The authors contextualize this:

"Unlike prior work using fixed-length integers, our setup samples two operands with random lengths and optional decimal points, greatly expanding the state space."

This makes the comparison somewhat asymmetrical: the prior methods were designed for simpler settings and are being tested in a harder regime than their original evaluations. However, this is precisely the point — TAIL is designed to handle this complexity, while the prior methods' task-specific inductive biases break down when the state space expands.

DeepSeek-R1 Comparison and R1-Distill Training

Figure 3 shows DeepSeek-R1's accuracy across all 18 tasks, consistently below TAIL's performance. The paper provides a qualitative comparison in Appendix K, contrasting DeepSeek-R1's and TAIL's CoT for the Word Flip task. DeepSeek-R1's response shows multiple attempted approaches (manual reversal, Python-style slicing, word splitting), repeated verification, backtracking, and an ultimately incorrect output. TAIL's response shows systematic index-by-index reversal from position 89 down to position 1, with each step explicitly showing the running intermediate result.

The CoT length comparison (Table I1) on the Compare Numbers task:

The near-identical token counts but dramatically different accuracies (38.8 percentage point gap) support the paper's claim that CoT length alone is not the mechanism — structural fidelity to algorithmic execution is what matters.

For a fairer comparison at equal model scale, Appendix J (Table J1) reports results from fine-tuning Qwen2.5-7B on an equal amount of correct data distilled from DeepSeek-R1 on the Large Number Addition task:

The R1-distilled model not only underperforms TAIL on in-domain data (72.2 vs. 98.0) but shows steeper degradation on longer sequences (72.2 → 61.8, a drop of 10.4 points from S to L, compared to TAIL's 98.0 → 90.0, a drop of 8.0 points). This is despite the R1-distilled data being "correct" (final answers match ground truth). The paper's interpretation is that DeepSeek-R1's CoT, even when correct, encodes reasoning patterns that are less structurally consistent than program-execution traces, and that this inconsistency limits the fine-tuned model's ability to generalize.

Length Generalization Activation

The data proportion experiment (Appendix D, Figure D1) investigates how much long-sequence data is needed to achieve strong length generalization. Training configurations keep total sample count constant but vary the S:M:L ratio: <1:0:0> (pure generalization), <8:1:1>, <7:2:1>, <5:3:2>, and <4:3:3>. The key finding:

"for almost all tasks, even a small addition of longer sequence data (i.e., at <8:1:1>) led to a rapid saturation in long-sequence reasoning, a phenomenon we refer to as length generalization activation"

This finding has practical significance: it suggests that TAIL-structured CoT makes models data-efficient at learning algorithmic structure. Once the algorithm is internalized from short sequences (which are cheaper to generate and train on), only a small fraction of longer examples is needed to demonstrate that the same structure scales. The paper explicitly contrasts this with prior conclusions:

"This observation is quite different from the 'balanced length' conclusion of training data in previous works (Lee et al., 2023), indicating that TAIL has the potential to expand to much longer sequences at a lower cost in the future."

The figure (Figure D1) shows per-task accuracy curves across the five data proportions for all 18 tasks. For tasks that haven't reached saturation under <1:0:0>, the curves rise sharply at <8:1:1> and mostly plateau thereafter. Tasks already at ceiling under <1:0:0> (e.g., Compare Numbers) show flat lines near 100%. The paper does not report which specific tasks are "unsaturated" under <1:0:0>, but the figure visually suggests most tasks benefit from the small long-data addition.

Cross-Task Compositional Generalization (Negative Result)

Appendix H (Figure H1) tests whether training on some tasks within an algorithmic paradigm transfers to other tasks within the same paradigm. The setup: for a given algorithm (e.g., DP, which includes 0-1 Knapsack, LCS, and Levenshtein Distance), the model is fine-tuned on (a) only the target task (SFT(Task)), (b) all other tasks within the algorithm excluding the target (SFT(Rest)), or (c) all tasks including the target (SFT(All)). The finding:

"the combinatorial generalization property is not significant, which is the target of our future works"

Figure H1 shows that SFT(Rest) — training on related tasks but not the target task — produces near-zero accuracy (below 5% for many entries) on the held-out task. This is a meaningful negative result: despite sharing an algorithmic paradigm (e.g., all three DP tasks involve filling a table through recurrence relations), the specific TAIL-CoT structure learned for one task does not transfer to another. The model is learning task-specific execution traces rather than a transferable "dynamic programming" reasoning skill. The authors flag this as a limitation and future work direction in Appendix L.

Ablation Studies and Robustness Checks

Key module ablation (Table 2): Removing any one of the three core TAIL modules — Atomic State, Linear Transition, or Memory Fetcher — causes a notable decline in length generalization performance across all eight algorithmic paradigms evaluated. For each algorithm, one representative task is selected and evaluated on M and L ranges (sequences exceeding training length). The full TAIL model achieves: Simulation (Compare Numbers): 94.2 (M), 90.0 (L); Enumeration (Count Letters): 96.0 (M), 92.6 (L); Iteration (Population Growth): 90.0 (M), 84.4 (L); Divide & Conquer (Binary Search): 98.6 (M), 89.2 (L); Recursion (Derangement): 99.6 (M), 87.0 (L); DP (0-1 Knapsack): 90.2 (M), 71.8 (L); Greedy (Dijkstra): 91.8 (M), 62.0 (L); Backtracking (Permutation Combination): 83.6 (M), 76.0 (L).

Removing Atomic State causes the most uniformly severe degradation. For Recursion (Derangement), accuracy drops from 99.6 to 52.2 on M (a 47.4-point drop) and from 87.0 to 32.0 on L (55.0 points). For DP (0-1 Knapsack), it drops from 90.2 to 77.4 on M (12.8 points) and from 71.8 to 61.0 on L (10.8 points). This consistency suggests Atomic State's role as the fundamental granularity constraint is critical across algorithmic paradigms — without it, models can learn composite shortcuts that break on longer sequences.

Removing Linear Transition disproportionately harms recursion and greedy tasks. For Recursion (Derangement): 43.0 (M) and 30.8 (L), representing drops of 56.6 and 56.2 points respectively. For Greedy (Dijkstra): 20.6 (M) and 11.2 (L), drops of 71.2 and 50.8 points. These tasks involve non-trivial control flow (recursive call stacks, priority queue updates) that Linear Transition unrolls into flat sequences. Without explicit unrolling, the model must implicitly track control state through attention patterns — a capability that degrades as sequence depth increases.

Removing Memory Fetcher shows task-dependent impact: it is most critical for Iteration (Population Growth drops from 90.0 to 73.8 on M, a 16.2-point drop, and from 84.4 to 67.6 on L, a 16.8-point drop) and least critical for Simulation (Compare Numbers drops only from 94.2 to 90.2 on M, 4.0 points, and from 90.0 to 88.0 on L, 2.0 points). The paper attributes this variation to task structure: "Tasks like Compare Numbers involve only local transitions and weak long-range dependencies, making Memory Fetcher less essential." The DP task (0-1 Knapsack) shows an interesting pattern: without Memory Fetcher, L-range accuracy (74.8) is actually higher than with full TAIL (71.8), though M-range is lower (80.8 vs. 90.2). The paper does not comment on this specific inversion, but it may reflect overfitting to the Memory Fetcher format at the expense of learning the underlying recurrence in the DP case.

The Qwen2.5-7B base model (no TAIL fine-tuning) is included in Table 2 for reference and shows dramatically lower accuracy across all tasks, confirming that the base model has not acquired these algorithmic reasoning capabilities through pretraining alone. For Recursion (Derangement), the base model achieves only 19.4 (M) and 3.0 (L) — effectively random on longer sequences.

Thinking style ablation (Figure 4): Fine-tuning with TAIL-CoT (minimalist, symbolic format containing only the three core modules) versus TAIL-CoT-styled (natural language wrapper around the same modules) produces "minimal impact on the final performance." Figure 4 shows side-by-side bar charts for eight representative tasks (one per algorithm), with accuracy at S, M, and L ranges. The TAIL-CoT and TAIL-CoT-styled bars are nearly identical across all tasks and length ranges. This result establishes that "the specific style of CoT is not a critical factor" and that "key modules of TAIL appears to play a more significant role in determining the overall performance." This is the critical evidence for the paper's central claim that structural fidelity to algorithmic execution — not surface-level reasoning style — drives length generalization.

Attention visualization of Memory Fetcher (Figure G2, Appendix G): Attention maps from selected Transformer layers are visualized for models with and without Memory Fetcher on the Binary Search task. The paper reports that with Memory Fetcher, "we observe strong and focused attention on the corresponding tokens." Without Memory Fetcher, "the attention patterns become sparse and disorganized, showing insufficient focus on the operands." This is a qualitative corroboration of the mechanism, not a quantitative ablation. No metrics (e.g., attention entropy, retrieval accuracy) are reported. The visualization supports the mechanistic story but does not independently quantify Memory Fetcher's contribution beyond the accuracy ablation in Table 2.

Data proportion sweep (Appendix D, Figure D1): For tasks not at saturation under <1:0:0>, the paper sweeps five S:M:L training data ratios: <1:0:0>, <8:1:1>, <7:2:1>, <5:3:2>, and <4:3:3>. The finding is that even <8:1:1> (a small fraction of longer data) produces rapid performance gains approaching saturation, a phenomenon the authors label "length generalization activation." This is a robustness check demonstrating that TAIL's benefits are not dependent on precisely balanced length distributions in training data — once the algorithmic structure is learned from predominantly short sequences, only a small amount of longer-sequence exposure is needed to activate generalization to those lengths. The paper contrasts this with prior work (Lee et al., 2023) that advocated for balanced-length training, suggesting TAIL's structured CoT changes the data efficiency properties of length generalization.

DeepSeek-R1 Distillation (Appendix J, Table J1): Fine-tuning Qwen2.5-7B on correct CoT data distilled from DeepSeek-R1 (same quantity as TAIL training data) yields substantially lower performance than TAIL fine-tuning on the Large Number Addition task: 72.2 vs. 98.0 (S), 67.2 vs. 94.2 (M), 61.8 vs. 90.0 (L). The R1-distilled model also shows a steeper degradation slope. This serves as a robustness check establishing that the source and structure of CoT data matter independently of its correctness — even "correct" reasoning traces from a powerful model do not induce the same length generalization as program-execution traces structured by TAIL's three modules. The paper notes that "since DeepSeek-R1 has a low accuracy rate on some tasks, distilling the same amount of training data requires a large number of tokens, so this experiment was not conducted on a large scale" — meaning the comparison is limited to one task (Large Number Addition) and may not generalize to all 18 tasks.

Combinatorial generalization (Appendix H, Figure H1): Training on related tasks within the same algorithmic paradigm does not transfer to held-out tasks. For DP tasks, SFT(Rest) — training on 0-1 Knapsack and LCS but testing on Levenshtein Distance — produces near-zero accuracy (below 5% for many configurations). Even SFT(All) — training on all DP tasks — sometimes underperforms SFT(Task) — training only on the target task. This negative result is a robustness check on the scope of TAIL's effectiveness: it improves length generalization within individual tasks but does not produce transferable "algorithmic reasoning skills" that generalize across task boundaries within the same paradigm.

Critical Assessment

Does TAIL Genuinely Enable Length Generalization, or Does It Enable Better Memorization of the Training Distribution?

The paper's central claim is that TAIL "significantly improves the length generalization ability" of LLMs on computable problems. The experimental design for testing this is: train on Short-range data only (<1:0:0> configuration) and evaluate on Medium and Long ranges. A method that achieves high accuracy on M and L ranges under this protocol has demonstrated length generalization — the model is solving problems with inputs substantially longer than any it saw during training.

The evidence for this claim is strong but comes with important caveats:

What the experiments demonstrate: On 18 diverse tasks spanning 8 algorithmic paradigms, Qwen2.5-7B fine-tuned on TAIL-structured CoT achieves high accuracy on out-of-distribution lengths, with no sharp degradation on most tasks (Figure 3). The ablation study (Table 2) further shows that the three core modules are individually necessary — removing any one degrades length generalization. The comparison with prior methods (Table 1) shows that TAIL's advantage is substantial, not marginal (86.5% vs. 24.0% at Long for Index Hint on Large Number Addition).

Caveat 1: The length ranges are modest, not extreme. The "Long" ranges represent, at most, a 5-10× extension over the training lengths (e.g., Binary Search: S = [5,20] elements, L = [41,70] — roughly 2-3.5×; Bubble Sort: S = [2,4], L = [7,8] — roughly 2×; Large Number Addition: S = [10,30] digits, L = [41,50] — roughly 1.4-5×). These are meaningful extrapolations but not the kind of unbounded generalization that a true algorithmic understanding would imply. A model that has truly internalized addition should be able to add 100-digit or 1,000-digit numbers, not just 50-digit ones. The paper does not test whether TAIL's generalization continues to hold at even longer lengths (e.g., L+ = [100, 200] for addition). The length generalization activation experiment (Appendix D) hints that adding a small fraction of longer data may extend the generalization frontier, but this is not directly tested. Figure 3 shows that some tasks (e.g., Dijkstra, 0-1 Knapsack, Permutation Combination) show visible downward slopes from M to L even with TAIL, suggesting that the generalization is not perfect and may degrade further at lengths beyond the tested L range.

Caveat 2: The distinction between length generalization and length interpolation is blurred in the data proportion experiments. The main claim is about generalization — training on S only, testing on M and L. But the length generalization activation finding shows that adding even a small fraction of M and L data (<8:1:1>) substantially improves performance. This is presented as a feature (data efficiency) but also reveals that pure S-only training does not achieve ceiling performance on all tasks. For the tasks where <1:0:0> leaves room for improvement, the model is not fully generalizing from short sequences alone — it benefits from seeing examples of the algorithm applied to longer inputs, even in small quantities. This is still a form of generalization (the model extrapolates from a few long examples to many), but it is weaker than the claim "trained only on short sequences, generalizes to arbitrary lengths."

Caveat 3: No comparison with training on uniformly sampled lengths. The paper compares TAIL at <1:0:0> against prior methods at <1:0:0>, but it does not compare TAIL at <1:0:0> against TAIL trained on uniformly sampled lengths from S through L. This would establish how much generalization gap remains — i.e., how much performance is left on the table by restricting training to short sequences. Figure D1 partially addresses this by showing that adding long data helps, but the <4:3:3> configuration (approximately uniform across lengths) is not directly compared to the <1:0:0> baseline in a side-by-side accuracy table. The visual evidence suggests that for many tasks, <8:1:1> reaches near-saturation, implying the gap between <1:0:0> and uniformly-sampled training is small but nonzero.

Does TAIL Outperform DeepSeek-R1 Through a Fundamentally Different Mechanism?

The paper's second major claim is that TAIL's mechanism (structured, algorithmic execution) is fundamentally different from and superior to DeepSeek-R1's mechanism (broad heuristic exploration) for length generalization.

What the experiments demonstrate: DeepSeek-R1 671B achieves lower accuracy than TAIL-fine-tuned Qwen2.5-7B on most of the 18 tasks (Figure 3), with particularly poor length generalization (sharp S-to-L degradation). The qualitative CoT comparison (Appendix K) shows DeepSeek-R1 trying multiple approaches and failing to execute a systematic algorithm. The R1-distilled fine-tuning experiment (Table J1) shows that even when Qwen2.5-7B is trained on DeepSeek-R1's correct outputs, it underperforms TAIL training and degrades on longer sequences.

Caveat 1: The comparison is not at equal model scale or training paradigm. DeepSeek-R1 is evaluated zero-shot, while TAIL is evaluated after supervised fine-tuning on task-specific synthetic data. This is not a controlled comparison of "reasoning mechanism A vs. reasoning mechanism B." It is a comparison of "large reasoning model prompted zero-shot vs. small base model fine-tuned on structured CoT." The fact that the 7B fine-tuned model outperforms the 671B zero-shot model is impressive but does not isolate the mechanism — it could be that fine-tuning on any high-quality task-specific data would outperform a general-purpose reasoning model, regardless of TAIL's specific structural properties. The R1-distill experiment partially addresses this by controlling for fine-tuning, but it is limited to a single task (Large Number Addition).

Caveat 2: DeepSeek-R1 was not designed for algorithmic length generalization. DeepSeek-R1 was trained through reinforcement learning to solve reasoning problems by exploring multiple approaches and self-verifying. Its training objective does not specifically incentivize learning algorithms that generalize across input lengths. So the finding that it underperforms on length generalization is not surprising — it is being evaluated on a capability it was not optimized for. This doesn't invalidate the finding but contextualizes it: the paper demonstrates that TAIL is better for this specific capability, not that the reasoning model paradigm is inherently flawed.

Caveat 3: The CoT length comparison (Table I1) is on a single task. The paper shows that TAIL-CoT and DeepSeek-R1 have comparable token counts on Compare Numbers (1,455 vs. 1,461) but vastly different accuracies (90.0 vs. 51.2). This is presented as evidence that CoT length isn't the mechanism — structure is. But this comparison is for one task only, and CoT length varies substantially across tasks. Without similar comparisons for the other 17 tasks, we cannot assess whether the token-efficiency advantage generalizes. It is possible that for some tasks, DeepSeek-R1's CoT is substantially longer (representing more computation) and that this partially closes the accuracy gap.

Does the Thinking-Style Ablation Prove That Structure, Not Style, Matters?

The thinking-style ablation (Figure 4) shows that minimalist TAIL-CoT (bare symbolic format) and natural-language TAIL-CoT-styled achieve indistinguishable performance. This is the paper's cleanest result and supports the claim that the three structural modules — not the linguistic wrapper — are what enable length generalization.

What the experiments demonstrate: Across 8 representative tasks (one per algorithm), TAIL-CoT and TAIL-CoT-styled produce nearly identical accuracy at S, M, and L lengths. Both substantially outperform the base model.

Caveat 1: "Style" is narrowly defined. The thinking-style ablation compares two variants of TAIL-structured CoT — one minimalist, one with added natural language. Both preserve the three core modules. This shows that the natural language is unnecessary, but it does not show that any CoT format with the three modules works, or that the modules are sufficient conditions for length generalization in general. It shows that within the TAIL framework, style is irrelevant — not that structure is all that matters across all possible CoT formats.

Caveat 2: The ablation doesn't test whether the modules alone are sufficient. The paper claims in the executive summary that "even minimalist CoT data containing only core modules without any thinking styles maintains full effectiveness." This is true, but the minimalist CoT is still generated from the program execution trace — it's not a random permutation of atomic states or a different structural decomposition. The ablation shows that natural language is dispensable, not that the three modules are the only structural elements that matter. It's possible that other structural decompositions (e.g., with different granularity, different memory mechanisms) would also work, and the ablation doesn't distinguish between "these three modules are sufficient" and "these three modules are necessary."

Do the Ablations Genuinely Isolate Each Module's Contribution?

The key module ablation (Table 2) removes each module individually and measures the performance impact. The finding is that all three modules matter, with task-dependent severity.

What the experiments demonstrate: Removing Atomic State, Linear Transition, or Memory Fetcher each causes significant accuracy drops on out-of-domain lengths across most tasks. The pattern of degradation aligns with algorithmic properties: Memory Fetcher is most important for iteration-heavy tasks, Linear Transition for recursion-heavy tasks, Atomic State broadly important.

Caveat 1: The ablations are not independently implemented. When Atomic State is removed, what replaces it? The paper describes "w/o Atomic State" as producing CoT without the atomic decomposition of steps into read-write-logic units — but what does the resulting CoT actually look like? Is it the original Python program's output without the fine-grained string-append statements? Is it a coarser trace? Without this specification, it's unclear whether the ablation removes only Atomic State or also inadvertently changes other properties (e.g., making steps larger might implicitly reduce the effectiveness of Memory Fetcher because operands are listed less frequently). The ablation is conceptually clean but operationally underspecified.

Caveat 2: The ablation is single-dimensional (remove one module at a time). The paper does not explore interactions between modules — e.g., does removing both Memory Fetcher and Linear Transition cause super-additive degradation? Are there tasks where removing one module is compensated by another? The modular decomposition implies independence, but the ablation design doesn't test for interactions.

Caveat 3: Table 2 reports only one representative task per algorithm. The ablation covers 8 tasks (one per algorithm), not all 18. This is a practical constraint, but it means we don't know whether the module-importance patterns generalize within algorithmic paradigms. For example, within DP (which includes 0-1 Knapsack, LCS, and Levenshtein Distance), only 0-1 Knapsack is ablated. Do LCS and Levenshtein Distance show the same sensitivity to removing Linear Transition? Without this data, we cannot assess whether the module importance is task-specific or paradigm-specific.

Missing Experiments That Would Strengthen the Claims

Several experiments are conspicuously absent and would address key open questions:

1. Extreme-length testing. The paper tests generalization to L ranges that are 2-5× the training lengths. Testing on even longer sequences (e.g., L+ = [100, 200] for addition) would reveal whether TAIL's generalization is robust or eventually breaks down. The length generalization activation experiment hints that a small amount of longer data extends the frontier, but this is post-hoc — the model is then trained on some L-range data, so it's no longer pure generalization.

2. Multi-task training. All experiments fine-tune separately for each task. Can a single model be fine-tuned on TAIL-CoT from all 18 tasks and achieve length generalization on all of them simultaneously? The compositional generalization results (Appendix H) are pessimistic about cross-task transfer, but they test transfer from related tasks to a held-out task, not joint training on all tasks. Multi-task training would test whether TAIL's structure enables the model to learn 18 algorithms in one set of weights without catastrophic interference.

3. Scaling with model size. All experiments use Qwen2.5-7B. Does TAIL's effectiveness scale with model size (e.g., would a 1.5B model also benefit, or does TAIL require 7B parameters to internalize the algorithmic structure)? Does a 72B model fine-tuned on TAIL achieve near-perfect length generalization on all tasks? Model size ablations are standard in the literature and their absence limits claims about TAIL's universality.

4. Comparison with chain-of-thought prompting (not fine-tuning). TAIL is a fine-tuning method. How does it compare to few-shot prompting with TAIL-structured examples (without fine-tuning)? If TAIL's structural principles can be conveyed through in-context learning, the approach would be more practical. If fine-tuning is necessary, it restricts TAIL to settings where task-specific fine-tuning is feasible.

5. Non-synthetic tasks. All 18 tasks are synthetic, with clean algorithmic solutions. Can TAIL's principles be applied to more naturalistic tasks that have algorithmic components embedded in noisy contexts (e.g., math word problems, code generation, data manipulation queries)? This is the bridge from synthetic demonstration to practical utility, and the paper does not attempt it.

Summary of Experimental Support

The experiments provide strong support for the core existence claim: there exists a CoT structure (TAIL) that, when used for fine-tuning, enables length generalization on diverse computable tasks where prior CoT methods fail. The ablation evidence convincingly shows that the three modules each contribute to this capability, and the thinking-style ablation cleanly demonstrates that natural language narrative is not the active ingredient.

The experiments provide qualified support for the mechanism claim: TAIL works by inducing Turing-machine-like algorithmic execution rather than heuristic exploration. The DeepSeek-R1 comparison and attention visualizations are suggestive but not definitive — a rigorous mechanism test would require interventions that selectively disrupt Turing-machine-like behavior and measure the impact on length generalization.

The experiments leave open the universality claim: TAIL's principles are argued to apply to all computable problems, but only 18 synthetic tasks are tested. The absence of extreme-length testing, multi-task training, model size scaling, and non-synthetic tasks means the claim of universality is supported within the tested scope but not validated beyond it. The compositional generalization failure (Appendix H) actually provides evidence against one form of universality — algorithmic paradigm transfer — and the authors appropriately acknowledge this as a limitation.

6. Limitations and Trade-offs

Assumption: All Tasks Must Be Deterministic and Algorithmically Solvable

The paper explicitly bounds TAIL's applicability to Computable Problems — tasks that admit a well-defined, deterministic procedural solution (Section 2.1). The authors state the scope clearly in Section 6:

"This work further centers on computable problems with deterministic algorithms, leaving nondeterministic cases as open directions."

This is not a minor scope restriction; it excludes entire categories of reasoning where length generalization also matters but where no single correct algorithm exists. Open-ended generation (dialogue, creative writing, summarization), tasks with multiple valid solution paths (mathematical proof, code generation with multiple correct implementations), and problems requiring probabilistic or approximate reasoning cannot be addressed by TAIL because there is no single deterministic program whose execution trace constitutes a "correct" CoT. In such cases, the answer space is not uniquely determined by the input, and the concept of "faithfully imitating the algorithm" doesn't apply — there is no canonical algorithm to imitate.

The consequence is that TAIL cannot be applied to the majority of real-world LLM deployment scenarios. Most production use cases (customer support, document analysis, code generation, data extraction from unstructured text) involve tasks where the correct output is either non-deterministic or not expressible as a clean algorithmic trace. Even within the reasoning domain, many important benchmarks (GSM8K, MATH, HumanEval) contain problems where the solution path involves heuristic search, analogical reasoning, or "insight" that resists reduction to a deterministic program trace. TAIL's framework provides no guidance for these settings, and the authors do not claim otherwise — but practitioners should understand that TAIL is a solution for a specific, narrow class of problems (synthetic, algorithmic, deterministically solvable) rather than a general-purpose length generalization method.

Evidence in the paper: The entire evaluation uses only 18 synthetic tasks (Table B1), all of which are standard algorithmic problems with well-known deterministic solutions. No real-world benchmark is tested. Appendix L acknowledges the boundary explicitly: "for non-deterministic problems or open-ended reasoning, we cannot directly model an algorithm to solve it, which is a problem that TAIL cannot currently solve." The compositional generalization failure (Appendix H, Figure H1) provides further evidence of narrowness: even within the same algorithmic paradigm (e.g., DP), training on one task does not transfer to another, suggesting TAIL learns task-specific execution patterns rather than general algorithmic reasoning principles.

Mitigation status: The authors present the computability scope as a defined boundary, not a bug — TAIL is for computable problems, and it works well on them. However, the limitation is significant because the paper's framing (particularly the title and abstract's emphasis on "universal" and "generalizable") could be read as claiming broader applicability than the method delivers. The authors do not propose concrete steps to extend TAIL to nondeterministic settings beyond a general commitment: "We will actively explore ways to break through the boundaries of computable and fuzzy problems with structured CoT in future work" (Appendix L). Given that this limitation is fundamental to the method's design (it relies on program execution traces as ground truth), extending TAIL beyond deterministic problems likely requires a different underlying mechanism, not an incremental improvement.

The Cost of Human Program Authoring Is Unquantified and Non-Trivial

TAIL requires a human to manually write a correct, instrumented Python program for each new task. The paper presents this as straightforward (Section 4.1):

"for each task belonging to a specific algorithm, it's feasible to construct a Python program and add string append statements to assemble CoT"

But this understates the engineering burden. Writing a correct program to solve 0-1 knapsack or Dijkstra's algorithm is standard undergraduate-level computer science. Writing a program whose instrumented output serves as effective training data for an LLM — producing CoT that instantiates Linear Transition, Atomic State, and Memory Fetcher correctly across all possible inputs, handling edge cases, generating varied query templates, and doing so at scale — is a substantially more involved software engineering task. For the 18 tasks in the paper, the authors presumably invested significant effort per task, but this investment is not quantified (person-hours, lines of code, debugging time).

The consequence is that TAIL does not eliminate the bottleneck that prior data-driven CoT methods also struggled with: the effort cost of designing the CoT format for each new task. Prior methods like Index Hint and Reversed Format required task-specific design (the authors criticize this as not "universal"), but TAIL also requires task-specific design — it's the same design step (determining how to structure the CoT for this particular algorithm), just executed through program instrumentation rather than CoT format heuristics. The universality in TAIL is that any computable problem can in principle be handled, not that the approach is effortless to apply to a new problem. A practitioner facing a novel algorithmic reasoning task would need to: (1) identify the correct algorithm, (2) implement it in Python with careful instrumentation, (3) verify that the instrumented output faithfully instantiates the three TAIL modules, (4) generate diverse query templates, and (5) tune the instrumentation to produce CoT that is neither too verbose nor information-sparse. Steps 2-4 require programming skill and understanding of TAIL's structural requirements; they are not automatable from the method as described.

Evidence in the paper: The paper provides no metrics on the human effort involved — no ablation on "how bad would the CoT be if the program were written sloppily?", no sensitivity analysis on instrumentation choices, no comparison of different program implementations for the same task. Appendix C shows the overall pipeline (Figure C1) with the step "Manually define the Python program" as a black box. The method is presented as scalable because data generation is automated — but program authoring is not, and the cost of program authoring dominates for small-to-medium numbers of tasks (for a single new task, 100% of the human effort is in writing the program; data generation is computationally cheap by comparison).

Mitigation status: The authors do not acknowledge program authoring cost as a limitation. They present the pipeline as efficient because "writing this program is very convenient and well-reasoned" (Appendix C), which assumes the algorithm is known and straightforward to implement — true for the tested tasks, but not true for arbitrary computable problems where algorithm design itself is non-trivial. No automation of the program-writing step is proposed. This is a practical limitation for anyone wanting to apply TAIL to a new domain: the cost is front-loaded in software engineering effort, and the paper provides no guidance on how to reduce it.

Length Generalization Is Tested Only at Modest Extrapolation Ratios

The paper operationalizes length generalization as: train on Short-range data, test on Medium and Long ranges. The Long ranges represent extrapolations of roughly 2-5× beyond the training lengths for most tasks (Table E1): Large Number Addition goes from S: [10,30] to L: [41,50] (1.4-5×), Bubble Sort from S: [2,4] to L: [7,8] (2-4×), Binary Search from S: [5,20] to L: [41,70] (2-14× on the lower bound, 3.5× on the upper bound). These are meaningful extrapolations, but they are modest relative to what "length generalization" could mean — a model that has truly internalized addition should add 100-digit or 500-digit numbers with the same procedure it uses for 10-digit numbers. The paper does not test whether TAIL's performance continues to hold at lengths substantially beyond the L range (e.g., L+ = [100, 200] for addition or [20, 50] for sorting).

The consequence is that we do not know whether TAIL enables unbounded length generalization (the model can process arbitrarily long inputs) or merely bounded extrapolation (the model generalizes to inputs somewhat longer than training, with the generalization gap widening as length increases). Figure 3 shows that several tasks (Dijkstra, 0-1 Knapsack, Permutation Combination) exhibit visible downward slopes from M to L even with TAIL, suggesting the generalization is not flat — accuracy decreases with length, and the curve may continue downward at lengths beyond those tested. The length generalization activation experiment (Appendix D, Figure D1) shows that adding a small amount of long data (<8:1:1>) improves performance on L-range tasks, which is a positive finding for data efficiency but also indicates that S-only training leaves performance on the table — the model has not fully extracted the length-invariant algorithm from short sequences alone.

Evidence in the paper: The per-task accuracy curves in Figure 3 show varying degrees of S-to-L degradation: Compare Numbers, Bubble Sort, and Any Substring are near-flat (strong generalization), while Dijkstra, 0-1 Knapsack, and Levenshtein Distance show clear downward slopes (weaker generalization). Table 2 confirms this: for DP (0-1 Knapsack), full TAIL achieves 90.2 on M but only 71.8 on L (an 18.4-point drop), and for Greedy (Dijkstra), 91.8 on M vs. 62.0 on L (a 29.8-point drop). These drops are smaller than the baselines' but are not zero — the model is not perfectly length-invariant. The paper does not test any lengths beyond the L ranges specified in Table E1, so the asymptotic behavior is unknown.

Mitigation status: The paper does not frame the limited extrapolation range as a limitation. The length generalization activation experiment (Appendix D) partially addresses the concern by showing that adding a small fraction of longer data (<8:1:1>) rapidly improves L-range performance, and the authors conclude that "TAIL has the potential to expand to much longer sequences at a lower cost in the future." But this is a mitigation strategy (add some long data), not evidence that the pure S-only generalization would extend to arbitrary lengths. A practitioner who needs to handle 500-digit addition after training on 10-30 digit examples cannot rely on the paper's current evidence — they would need to test this extrapolation themselves, and the downward accuracy slopes for some tasks in Figure 3 suggest caution.

No Systematic Accounting for Inference Cost or Latency

TAIL's CoT sequences are long — they unroll loops into linear traces, decompose operations into atomic states, and explicitly re-output operands through Memory Fetcher. The paper reports average token counts for one task (Compare Numbers: 1,455 tokens for TAIL-CoT vs. 1,461 for DeepSeek-R1, Table I1) and presents this as evidence that TAIL is cost-competitive. But this comparison is against a 671B model — at 7B parameters, TAIL's per-token generation cost is vastly lower than DeepSeek-R1's, so the relevant comparison for inference cost is against other 7B-scale approaches (base model few-shot, simpler CoT formats like Index Hint, etc.). The paper never compares the token efficiency of TAIL to simpler fine-tuned models or to the base model with shorter CoT.

The consequence is that a practitioner cannot assess the cost-quality tradeoff of TAIL. For a given task, how much longer is TAIL-CoT compared to standard CoT? How does the per-token inference cost scale with input length? For tasks with $O(n^2)$ algorithmic complexity (bubble sort, DP table filling), the CoT length grows quadratically with input size — the cost of processing a 50-element sort is not 5× the cost of a 10-element sort but roughly 25×. The paper's evaluation reports accuracy across length ranges but never reports the corresponding token costs, making it impossible to judge whether TAIL's accuracy improvements justify the increased inference cost compared to simpler approaches.

Furthermore, TAIL's sequential unrolling of linear transitions creates inherent latency that parallel-sampling approaches avoid. A model generating a 10,000-token TAIL-CoT for a long addition problem must do so autoregressively, one token at a time — there's no parallelism within a single CoT generation. For latency-sensitive applications, this is a substantial practical constraint that the paper does not discuss.

Evidence in the paper: Token counts are reported only for the Compare Numbers task in Table I1 (and only in comparison to DeepSeek-R1), not for any of the other 17 tasks. The data proportion experiments (Appendix D) keep total training samples constant but do not report total training tokens, so the cost of training on <8:1:1> vs. <1:0:0> (where L-range samples are longer and thus cost more tokens) is not quantified. The paper's metric of "efficiency" is purely in terms of sample count, not token count or FLOPs.

Mitigation status: The paper does not acknowledge the absence of cost accounting as a limitation. The CoT length comparison in Table I1 is presented as evidence of efficiency ("significantly higher accuracy at comparable CoT length"), but this framing is specific to the DeepSeek-R1 comparison and does not establish cost-efficiency relative to simpler approaches. Future work that reports tokens-per-query and FLOPs-per-query alongside accuracy for all tasks and all length ranges would be needed for practitioners to make informed deployment decisions.

Compositional Generalization Across Tasks Is Absent

The paper demonstrates that TAIL enables length generalization within individual tasks — training on short binary search examples enables long binary search. But it also shows, in Appendix H, that this generalization does not transfer across tasks within the same algorithmic paradigm. Training on 0-1 Knapsack does not improve performance on Levenshtein Distance, even though both are dynamic programming problems that share structural similarities (filling a table based on recurrence relations). The paper states this bluntly:

"the combinatorial generalization property is not significant, which is the target of our future works"

Figure H1 shows that SFT(Rest) — fine-tuning on all tasks within an algorithm except the target — produces near-zero accuracy (below 5% for many configurations) on the held-out task.

The consequence is that TAIL as currently formulated produces task-specific specialists, not general algorithmic reasoners. A model fine-tuned on TAIL-CoT for binary search can binary search on arrays of any tested length. It cannot sort, compute Levenshtein distance, or solve any other algorithmic problem, even those within the same paradigm (Divide & Conquer also includes Merge Sort, but this isn't tested). This means deploying TAIL requires retraining a separate model (or a separate LoRA adapter) for each task — there's no single "TAIL model" that can handle arbitrary computable problems. This substantially limits practical applicability: a coding assistant that needs to handle multiple algorithmic patterns would need either a massive multi-task model (which the paper does not test) or a router that dispatches to task-specific fine-tuned models.

Evidence in the paper: Appendix H (Figure H1) provides the quantitative evidence for DP and Greedy algorithms. The paper acknowledges this limitation explicitly in both Section 6 and Appendix L: "our experiments indicate that compositional generalization still leaves room for improvement." The result is not surprising given that each task uses a different program with different CoT structure — the model is learning to imitate one specific program, not to extract the meta-pattern of "dynamic programming" across different instantiations. But it's a meaningful limitation because it undermines one interpretation of TAIL's universality: TAIL provides a universal template for constructing CoT, but the resulting trained models are task-specific.

Mitigation status: The authors flag compositional generalization as a primary target for future work: "In future work, we will take individual tasks as the entry point, to explore more diverse data composition strategies, with the goal of achieving compositional generalization" (Appendix L). No concrete approach is proposed. This limitation is significant because it interacts with the program authoring cost: if each new task requires both (a) writing a new instrumented program and (b) fine-tuning a separate model, the total cost of deploying TAIL across N tasks scales roughly linearly with N. If compositional generalization could be achieved, writing programs for a few representative tasks per algorithm might suffice, reducing the human effort substantially.

No Evidence Beyond a Single Model Family and Synthetic Setting

All experiments use Qwen2.5-7B fine-tuned on purely synthetic data generated by hand-written Python programs. The paper does not test TAIL on any other model architecture (e.g., LLaMA, DeepSeek-V3, Gemma, Mistral), any other model scale (1.5B, 13B, 72B), any non-synthetic benchmark (GSM8K, MATH, HumanEval, MBPP), or any few-shot prompting setting (using TAIL-structured examples without fine-tuning). The authors state in Section 4:

"We believe this model is representative of the capabilities of many contemporary LLMs"

but this belief is not empirically validated — the claim that TAIL's principles apply universally to Transformer-based LLMs is plausible but untested.

The consequence is that we do not know whether TAIL's effectiveness is specific to Qwen2.5-7B (its pretraining data mixture, its tokenizer, its architectural details) or generalizes to other models. It is possible that Qwen2.5-7B has particular properties (e.g., its position encodings, its attention implementation, its pretraining on code data that includes algorithmic patterns) that make it especially amenable to learning from TAIL-structured CoT, and that other model families would benefit less. Without testing on at least one alternative model family, the "universal" framing is aspirational.

Furthermore, all 18 tasks are synthetic — they are clean, unambiguous, algorithmic problems with no distracting context, no missing information, and no ambiguity in the problem specification. Real-world algorithmic reasoning rarely appears in this form. Math word problems embed algorithmic computations in natural language narratives; code generation requires recognizing which algorithm to apply, not just executing a specified one; data manipulation queries involve parsing messy inputs before the algorithm begins. The synthetic setting abstracts away all of these challenges, so we cannot assess whether TAIL's benefits survive the transition to realistic tasks.

Evidence in the paper: The evaluation uses exclusively the 18 synthetic tasks in Table B1. The base model comparison (Qwen2.5-7B) and the instruct model comparison (Qwen2.5-7B Instruct) show that TAIL substantially improves over these specific models, but no other model families are tested. Appendix L acknowledges the gap between open-source and closed-source models ("several closed-source models (e.g., O4-mini) were able to solve these problems well") but does not test whether fine-tuning a closed-source-capable open-source model on TAIL data would close this gap.

Mitigation status: The authors do not present this as a limitation they intend to address, beyond the general statement about bridging the "gap with close-source models" (Appendix L). Testing on additional model families and on non-synthetic tasks is standard practice for establishing the robustness of a training method, and its absence limits the strength of the universality claim. A practitioner considering TAIL for a non-Qwen model or a real-world task would need to run their own validation experiments — the paper provides no evidence either way.

7. Implications and Future Directions

How This Work Changes the Landscape

This paper causes a reframing of the length generalization problem from a collection of task-specific CoT format tweaks into a single design methodology grounded in algorithmic execution structure. It is not a paradigm shift — the field has long known that Transformers are Turing-complete in principle (Li et al., 2024) and that structured CoT helps reasoning (Wei et al., 2022). Rather, it is a conceptual unification that identifies which structural properties of CoT matter for length generalization and provides a constructive recipe — instrument a correct program to dump its execution trace — for achieving those properties across a broad class of problems.

The magnitude of the reframing is substantial within the specific subfield of length generalization but bounded by the scope of computable problems. Before this work, the default approach to length generalization was to design a bespoke CoT format encoding task-specific inductive biases: positional indexing for symbolic matching (Index Hint), digit reversal for arithmetic (Reversed Format), sequence padding for uniform formatting (Jelassi et al., 2023). Each method worked for its target task class and failed elsewhere, with no clear principle for generalizing the approach. TAIL replaces this with a principled design rule: for any computable problem, structure the CoT to imitate the execution trace of the algorithm that solves it, enforcing three properties — flat sequential unrolling (Linear Transition), minimal primitive operations (Atomic State), and explicit operand retrieval before computation (Memory Fetcher). The rule is universal within its domain: it applies to any problem solvable by a deterministic algorithm, as validated on 18 tasks across 8 paradigms.

This reframing resolves a latent contradiction in the prior literature. On one side, several works (Zhou et al., 2023; 2024; Lee et al., 2023; Shen et al., 2023) showed that specific CoT modifications could improve length generalization on specific tasks, implying that length generalization was trainable through better CoT design. On the other side, other works (Saparov & He, 2022; Anil et al., 2022) showed that LLMs fundamentally struggle with length generalization, and Saparov et al. (2024) demonstrated that Transformers "struggle to learn to search" — implying a deeper architectural limitation. TAIL reconciles these findings by showing that the failure is not architectural (Transformers can learn to execute algorithms from structured traces) but data-structural: standard CoT formats fail to induce algorithmic learning because they permit shortcuts, while TAIL's structured traces eliminate the shortcuts. This resolution shifts the research emphasis from architectural fixes (new position encodings, looped transformers, specialized attention patterns) toward data synthesis methodology — the bottleneck is not what the model can represent but what the training data causes it to learn.

The thinking-style ablation (Figure 4) is the diagnostic result that makes this reframing stick. By showing that stripping all natural-language narrative from TAIL-CoT leaves performance unchanged, the paper isolates the active ingredient: structural fidelity to algorithmic execution, not the surface-level "reasoning style" that has been the focus of much CoT research (Suzgun & Kalai, 2024; Zheng et al., 2023). This finding should redirect effort away from crafting more elaborate or more human-like reasoning narratives and toward improving the structural completeness and atomicity of the CoT trace. It also provides a diagnostic criterion for future work: if a CoT modification improves length generalization, is it because it makes the algorithmic structure more explicit (good, scales with length), or because it adds heuristic exploration (good for in-distribution accuracy but brittle under length shift)?

The paper also diminishes the attractiveness of certain research directions. Architectural modifications for length generalization (specialized position encodings, looped transformer blocks, attention pattern modifications) were already limited by their lack of transfer to production-scale LLMs; TAIL's results suggest they may also be unnecessary — a well-structured dataset applied to a standard architecture achieves strong length generalization without any architectural changes. Similarly, the reasoning-model paradigm of expanding CoT length through reinforcement learning (as in DeepSeek-R1) is shown to be poorly suited for length generalization: DeepSeek-R1's long CoT (comparable in token count to TAIL-CoT, Table I1) achieves substantially lower accuracy and degrades sharply on longer sequences because its mechanism is heuristic exploration rather than structured execution. This does not mean reasoning models are "wrong" — they clearly improve performance on many benchmarks — but it establishes a boundary condition: exploration-driven CoT scaling does not confer length generalization, and may even be antagonistic to it by reinforcing the habit of trying multiple approaches instead of committing to one systematic procedure.

Follow-Up Research This Work Enables

Stress-testing the extrapolation frontier: where does TAIL's length generalization break? The paper tests extrapolation from Short (S) to Long (L) ranges, where L represents roughly 2–5× the training lengths. Several tasks (Dijkstra, 0-1 Knapsack, Permutation Combination) show visible downward accuracy slopes from M to L (Figure 3; Table 2: Dijkstra drops from 91.8 at M to 62.0 at L, a 29.8-point gap). The natural next experiment is to construct an L+ range (e.g., Large Number Addition with [100, 200] digits, Bubble Sort with [15, 20] elements, Binary Search with [100, 200] elements) and measure whether the accuracy curve plateaus at some asymptotic value or continues toward zero. A flat asymptotic accuracy above random would indicate the model has learned a robust algorithmic procedure that degrades gracefully; a continued downward trend toward zero would indicate the model is still using length-dependent heuristics that eventually break. This experiment would distinguish between "TAIL enables bounded extrapolation" and "TAIL enables true length invariance," and the answer matters for deployment in settings where inputs can be arbitrarily long.

Multi-task TAIL: can a single model learn 18 algorithms simultaneously without interference? The paper trains separate models for each of the 18 tasks, with no multi-task experiment. The compositional generalization results (Appendix H) are pessimistic about cross-task transfer, but they test transfer from trained tasks to held-out tasks — a different question than whether a single model can learn all 18 algorithms when trained on all 18 simultaneously. A concrete experiment: fine-tune Qwen2.5-7B on the union of TAIL-CoT data from all 18 tasks (mixing S-range data from each) and evaluate length generalization on each task at S, M, and L ranges. The hypothesis to test is whether the three TAIL modules create sufficiently structured and distinct CoT patterns that the model can learn each algorithm without catastrophic interference, or whether the shared autoregressive generation format causes the model to confuse similar algorithmic patterns (e.g., binary search midpoints vs. quicksort pivots). If multi-task training succeeds, it would demonstrate that TAIL's structure enables algorithmic skill composition, making a single deployed model capable of handling diverse computable problems — a substantial advance over the current task-specific specialist paradigm. If it fails, it would reveal a fundamental limitation: TAIL-structured CoT may be learnable only when the model's entire capacity is devoted to a single algorithmic pattern.

Does TAIL scale with model size, and is there a minimum scale for algorithmic imitation? All experiments use Qwen2.5-7B. An open question is whether the ability to learn algorithmic execution from TAIL-structured traces is emergent at a certain parameter scale or holds across model sizes. A scaling study would fine-tune models at 0.5B, 1.5B, 7B, and (if feasible) 72B parameters on the same TAIL-CoT data for a subset of tasks (e.g., one task from each of the eight algorithmic paradigms) and measure length generalization at S, M, and L ranges. The key comparisons: (a) Does a 0.5B model achieve any length generalization with TAIL, or is there a threshold below which even perfectly structured data cannot induce algorithmic learning? (b) Does the S-to-L accuracy gap shrink with model size — i.e., do larger models achieve flatter generalization curves? (c) Does the "length generalization activation" phenomenon (Appendix D) interact with scale — do larger models need even fewer long examples to saturate? This experiment would provide practical guidance for deployment (pick the smallest model that achieves target accuracy) and theoretical insight into the relationship between model capacity and the ability to internalize procedural knowledge from structured traces.

TAIL for code generation: from execution traces to program synthesis. The paper's method generates CoT by instrumenting a known correct program to dump its execution trace. A natural extension is to reverse the direction: given a problem specification, can a model trained on TAIL-structured traces of multiple algorithms learn to select and execute the right algorithm without being told which one to use? Concretely, construct a dataset where queries are natural-language problem descriptions (e.g., "Find the index of X in the sorted list Y" or "Find the shortest path from A to B in the graph with edges E") without naming the algorithm, and the TAIL-CoT output includes the execution trace of the appropriate algorithm. Train a model on this dataset and test whether it can select the correct algorithm (binary search vs. Dijkstra vs. DP) for unseen problem instances, then execute it correctly on out-of-distribution lengths. This experiment would test whether TAIL's structural traces can teach algorithm recognition and selection in addition to algorithm execution, bridging from the paper's synthetic setting (where the algorithm is specified in the task definition) to more realistic code generation and problem-solving scenarios where algorithm selection is part of the challenge. A strong negative result (the model can execute algorithms when told which one to use but cannot select among them) would clarify that TAIL teaches how to execute but not what to execute — a critical distinction for general reasoning.

Extending TAIL to nondeterministic and approximate reasoning. The paper explicitly bounds TAIL to deterministic computable problems (Section 6, Appendix L). An ambitious follow-up would explore whether the three modules — Linear Transition, Atomic State, and Memory Fetcher — can be adapted to tasks where the solution is not a single deterministic trace. For example, in mathematical proof generation, the "algorithm" is not a fixed procedure but a search through a space of inference rules; the CoT could be structured as a linear trace of inference steps (Linear Transition), each step applying a single inference rule (Atomic State) with explicit citation of the premises used (Memory Fetcher). The training data would come from formal proof assistants (Lean, Coq) where the execution trace is the proof term. The hypothesis to test is whether the three-module structure generalizes beyond deterministic algorithms to any procedure with well-defined primitive steps, even when those steps involve search, backtracking, or nondeterministic choice. A concrete experiment: construct TAIL-structured CoT from proof traces in a formal theorem-proving benchmark (e.g., MiniF2F, ProofNet), fine-tune a model, and test whether the model can generate correct proofs for theorems with more steps or longer hypotheses than seen during training. This would test the boundary of TAIL's "computable problems" assumption and potentially extend its applicability to a much broader class of reasoning tasks.

Verifier-guided self-improvement for algorithmic fidelity. TAIL as presented is a pure SFT method: the model learns to imitate program traces. But at inference, the model can generate traces that look like TAIL-CoT (they contain Memory Fetcher-like operand re-outputs, Atomic State-like step decomposition, Linear Transition markings) without actually executing the algorithm correctly — the surface form may be preserved while the computation is wrong. A follow-up could train an outcome-supervised verifier (or use the ground-truth program itself as an oracle) to detect when a generated TAIL-CoT trace contains an execution error, and use reinforcement learning (similar to DeepSeek-R1's RL objective but with algorithmic fidelity as the reward) to fine-tune the model to minimize execution errors. The key metric would be algorithmic fidelity: does the generated trace, if executed by a Python interpreter (reversing the instrumentation), produce the correct answer? This would transform TAIL from an imitation learning method into a self-correcting execution engine, potentially pushing accuracy on the hardest tasks (Dijkstra at 62.0 L, 0-1 Knapsack at 71.8 L) toward ceiling by penalizing surface-level imitation that masks computational errors.

Practical Applications and Downstream Use Cases

Synthetic data generation for algorithmic reasoning benchmarks. TAIL provides a direct, scalable method for generating training data for any task solvable by a deterministic algorithm. For organizations building LLM-based systems that must perform reliable algorithmic computation — financial calculations (compound interest, loan amortization, tax computation), logistics optimization (routing, scheduling, inventory DP), or data processing (sorting, filtering, aggregation with complex conditions) — TAIL offers a recipe: implement the algorithm as an instrumented Python program, generate 100,000+ TAIL-CoT training examples, and fine-tune a 7B-class model. The paper's numbers provide concrete expectations: for Large Number Addition, 100,000 S-range TAIL-CoT examples yield 86.5% accuracy at L-range (50-digit operands), compared to 24.0% with the best prior method (Index Hint). For a financial institution needing reliable 50-digit arithmetic (relevant for cryptographic or high-precision applications), the 62.5-percentage-point improvement over Index Hint is the difference between unusable and production-ready. The cost is the one-time software engineering effort of implementing the algorithm with TAIL instrumentation, plus the compute to generate training data and fine-tune — both fixed costs that amortize over arbitrarily many inference queries.

On-device algorithmic assistants with small models. The paper shows that a 7B model fine-tuned on TAIL-CoT can outperform a 671B general-purpose reasoning model (DeepSeek-R1) on structured algorithmic tasks, at comparable inference token counts (Table I1: 1,455 vs. 1,461 tokens on Compare Numbers). This suggests a deployment architecture where a small, on-device model (7B or smaller, depending on the scaling study proposed above) handles algorithmic reasoning tasks locally, avoiding the latency, cost, and privacy concerns of cloud API calls. A concrete scenario: a spreadsheet application that embeds a 7B TAIL-fine-tuned model to handle formula computation, sorting, filtering, and pivot-table generation on user data entirely on-device. The length generalization property is critical here: a spreadsheet user might sort 10 rows or 10,000 rows, and the assistant must work reliably across that range. The paper's Bubble Sort results (near-saturation at L-range with only S-range training) suggest TAIL can provide this reliability. The key engineering question not answered by the paper is how to package TAIL-trained models for multiple algorithms into a single on-device deployment, given the current task-specific training paradigm and the absence of multi-task results.

Trustworthy CoT for regulated decision-making. In domains where algorithmic decisions must be auditable — credit scoring, insurance underwriting, benefits eligibility determination — the "show your work" requirement is not optional. Standard LLM CoT is post-hoc rationalization that may not reflect the actual computation. TAIL-CoT, generated from a known correct program trace, provides a CoT that is verifiably faithful to the algorithm because its structure (Linear Transition of Atomic States with explicit Memory Fetcher) enables automated checking: a verifier can replay the trace step by step and confirm that each Atomic State's computation follows from its retrieved operands. This creates a deployment pathway where the model generates a TAIL-CoT trace, an automated checker validates the trace against the algorithmic specification, and only validated outputs are presented to the user or downstream system. The paper's 18 synthetic tasks are far simpler than real regulatory algorithms, but the principle — structural faithfulness enables automated verification — transfers. A concrete pilot would implement TAIL for a specific regulated computation (e.g., overtime pay calculation under labor law, which involves deterministic rules with branching conditions), generate audit-trail CoT, and measure both accuracy and verifier-detected error rates across input complexity levels.