💬 NLP

When LLMs Stop Following Steps: A Diagnostic Study of Procedural Execution in Language Models

This paper introduces a diagnostic benchmark demonstrating that while large language models achieve high accuracy on short procedural tasks, their ability to faithfully execute step-wise algorithms degrades significantly as complexity increases, revealing that strong benchmark performance often masks substantial weaknesses in instruction following.

Original authors: Sailesh Panda, Pritam Kadasi, Abhishek Upperwal, Mayank Singh

Published 2026-05-04

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Sailesh Panda, Pritam Kadasi, Abhishek Upperwal, Mayank Singh

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

The Big Idea: The "Recipe" Test

Imagine you give a chef a very specific, step-by-step recipe to bake a cake. The recipe says: "Mix flour and sugar. Then add eggs. Then stir for 10 seconds. Then bake."

You might expect the chef to follow every single instruction in order. But what if the chef, instead of following the steps, just guesses what a cake usually tastes like and hands you a result? Or what if they get halfway through, forget the last three steps, and just say, "Here's the cake"?

This paper is like a giant test kitchen where researchers gave 14 different "chef" AI models (Large Language Models) thousands of these specific recipes. The recipes were simple math problems, but they were designed to be long and tricky. The goal wasn't to see if the AI could do hard math, but to see if it could faithfully follow the instructions from start to finish.

The Setup: The "Endless Staircase"

The researchers built a special test with two main ways to make the task harder:

The Length of the Staircase: They gave the AI recipes with anywhere from 5 steps to 95 steps. Imagine a staircase. A 5-step staircase is easy to climb. A 95-step staircase is exhausting.
The "Look-Back" Rule: In some recipes, step 10 didn't just use the result from step 9. It might have said, "Go back and use the result from step 3." This is like telling a hiker, "Take a step forward, then go back to the third tree you passed and pick up a stone from there." It forces the AI to remember things from way back in the past.

What They Found: The "Memory Lapse"

The results were surprising. Even though the math was simple (just adding, subtracting, multiplying, or dividing), the AIs got worse and worse as the recipes got longer.

The Drop: On a short 5-step recipe, the AIs got the right answer about 61% of the time. But on a long 95-step recipe, their success rate plummeted to just 20%.
The "Look-Back" Trouble: When the AI had to remember steps from way back (like step 3), their performance dropped even further. It's as if the AI got confused about where it was in the story.

How the AIs Failed: The "Cheating" Chefs

The researchers didn't just look at the final answer; they watched how the AI tried to solve the problem. They found that the AIs often didn't actually do the work. Instead, they tried to "cheat" or "cut corners" in several funny ways:

The "Early Exit" (Under-execution): This was the most common failure. The AI would start the recipe, do a few steps, get bored or confused, and then just jump straight to the end, pretending it finished everything. It's like a student who writes the first sentence of an essay, then skips to the conclusion without writing the middle.
The "Hallucinated" Steps: Sometimes the AI would invent extra steps that weren't in the recipe at all. It's like a chef adding "sprinkle unicorn dust" when the recipe never said to do that.
The "Self-Correction" Trap: Sometimes the AI would get the answer wrong, realize it, and try to fix it later in the text. But by the time it fixed it, it had already messed up the final result.
The "Pattern Matcher": Instead of doing the math, some AIs seemed to guess the answer based on what the numbers looked like, rather than actually following the steps.

The Main Takeaway

The paper concludes that just because an AI gives you a "plausible" final answer, it doesn't mean it actually did the work.

Think of it like a student taking a test. If they get the right answer, you might think they studied. But this paper shows that sometimes, they are just guessing or remembering the answer from a previous test, rather than actually solving the problem step-by-step.

In short: Current AI models are great at sounding smart and giving a final result, but they struggle to act like a reliable robot that follows a long, boring list of instructions exactly as written. When the instructions get too long or require remembering too much from the past, the AI tends to lose track and stop following the rules.

1. Problem Statement

While Large Language Models (LLMs) demonstrate strong performance on reasoning benchmarks, high final-answer accuracy does not guarantee that the model has faithfully executed the specific procedure provided in the prompt. Models often rely on shortcuts, pattern matching, memorized associations, or unstable intermediate computations to arrive at a plausible answer without actually following the prescribed steps.

This distinction is critical for applications requiring strict adherence to algorithms (e.g., numerical calculations, rule-based decision-making, and structured workflows). The paper addresses the gap between "appearing to reason" and "faithfully executing instructions," particularly as task complexity increases.

2. Methodology

The authors introduce a controlled diagnostic benchmark designed to isolate procedural execution failures from ambiguity in task interpretation.

Task Formulation:
- Inputs: Two numeric variables ( $x$ and $y$ ).
- Procedure: A step-wise arithmetic algorithm written in natural language. The algorithm initializes $S_1=x$ and $S_2=y$ , then defines a sequence of intermediate variables ( $S_3, S_4, \dots$ ) using basic arithmetic operations ( $+, -, \times, \div$ ).
- Goal: The model must execute the algorithm exactly as written and return the final computed value.
- Ground Truth: Deterministic and easily verifiable via an external executor, eliminating ambiguity.
Complexity Axes:
1. Algorithm Length: The number of steps ( $T$ ) varies from 5 to 95 (in increments of 10).
2. Look-back Dependencies: To stress-test state tracking, the benchmark introduces dependencies where a current step may require retrieving intermediate variables from previous steps.
  - Look-back 1: Depends only on the immediate previous step.
  - Look-back 7: Depends on any of the previous 7 steps.
Dataset Construction:
- Scale: 55 datasets totaling 55,000 examples.
- Variables: Combinations of input ranges ( $[0,1], [1,10], [10,100]$ ), data types (integer vs. float), and operation variants (mixed, addition-only, subtraction-only, etc.).
Models Evaluated:
- 14 Models: Spanning various scales (1.5B to 685B parameters) and families (DeepSeek, Qwen, Mistral, OLMo, OpenAI, etc.), including both standard instruction-tuned and reasoning-oriented models.
Evaluation Metrics:
- First-Answer Accuracy: Correctness of the first extracted answer.
- Correct@Any: Correctness if any answer span in the output is correct (captures self-correction).
- Non-null Answer Rate: Percentage of outputs containing a valid <answer> tag.
- Step-Following Behavior: Categorization into Exact (correct steps), Under-execution (premature termination), and Over-execution (extra steps).

3. Key Contributions

Diagnostic Benchmark: A novel, controlled environment specifically designed to measure procedural fidelity rather than just final answer correctness.
Empirical Evidence of "Procedural Illusion": Demonstrates that even when the full algorithm is explicitly provided, LLMs frequently fail to execute it faithfully as complexity grows.
Failure Mode Analysis: Identifies specific generation-level failure modes (e.g., under-execution, missing answers, premature answers) that are invisible when looking solely at final accuracy.
Dependency Depth Sensitivity: Shows that models struggle significantly not just with long sequences, but with non-local state retrieval (look-back dependencies).

4. Key Results

Accuracy Degradation with Complexity:
- Step Count: Average first-answer accuracy drops drastically from 61% at 5 steps to 20% at 95 steps.
- Look-back Depth: Increasing look-back dependency from 1 to 7 reduces average accuracy by an additional 18.43 percentage points, indicating a specific weakness in tracking non-local intermediate states.
Generation-Level Failure Modes:
- Under-execution: As step count increases, the proportion of "under-executed" generations (stopping before the final step) rises from 24.25% to 50.87%.
- Exact Execution: Drops from 70.88% to 46.84%.
- Premature Answers: Many models generate an answer early in the output without completing the reasoning trace, suggesting reliance on pattern matching rather than execution.
Input and Task Factors:
- Operation Type: Addition and subtraction tasks generally yield higher accuracy than multiplication and division.
- Magnitude: While numerical magnitude affects performance in specific variants (e.g., multiplication), it does not fully explain the broad degradation in accuracy. The primary driver is the procedural burden of tracking state.
- Model Scale: Larger models generally perform better, but the trend of declining accuracy with complexity holds across all model sizes.
Self-Correction:
- While "Correct@Any" is often higher than "First-Answer Accuracy," it reveals that models often make initial errors and attempt to self-correct, yet still fail to maintain the strict procedural flow required.

5. Significance and Implications

Limitations of Current Reasoning: The study challenges the assumption that "Chain-of-Thought" or longer reasoning traces equate to faithful instruction following. Models often "hallucinate" the process or skip steps entirely while producing a plausible final number.
Safety and Reliability: For high-stakes applications (e.g., financial calculations, policy enforcement), relying on LLMs to execute explicit multi-step procedures is currently risky, as they may fail silently by skipping steps or hallucinating intermediate states.
Future Directions: The findings suggest a need for:
- New training objectives that explicitly penalize procedural deviations.
- Tool-augmented agents (using external calculators/executors) to handle the deterministic parts of algorithms.
- Architectural improvements for better long-horizon state tracking and non-local dependency resolution.

In conclusion, the paper provides a rigorous lens to evaluate whether LLMs truly "think" through a problem or merely "guess" the outcome, revealing substantial weaknesses in faithful instruction execution as procedural complexity scales.