💬 NLP

Semantic Content Determines Algorithmic Performance

The paper introduces "WhatCounts," an atomic benchmark demonstrating that frontier LLMs fail to implement truly invariant algorithms, as their performance on simple counting tasks varies unpredictably by over 40% based solely on the semantic content of the items being counted, revealing hidden input-dependent biases that extend beyond mere reasoning complexity.

Original authors: Martiño Ríos-García, Nawaf Alampara, Kevin Maik Jablonka

Published 2026-01-30

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Martiño Ríos-García, Nawaf Alampara, Kevin Maik Jablonka

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

Imagine you have a very smart robot assistant. You ask it to do a simple job: "Count how many items are in this list."

In the world of computers, a true "algorithm" (a set of instructions) is like a perfect, blind robot. If you give it a list of 5 apples, it counts 5. If you give it a list of 5 rocks, it also counts 5. The robot doesn't care what it is counting; it only cares how many things are there. The meaning of the items shouldn't change the result.

This paper, titled "Semantic Content Determines Algorithmic Performance," reveals a surprising and slightly embarrassing truth about the most advanced AI models (Large Language Models or LLMs) we have today: They are not perfect blind robots. They are actually very sensitive to what they are counting.

Here is a breakdown of their findings using simple analogies:

1. The "WhatCounts" Test

The researchers created a super-simple test called WhatCounts.

The Setup: They gave the AI a list of items separated by pipes (like |).
The Rule: The list had no tricks. No duplicates, no confusing words, no "distractors." Just a clean list of 10 items.
The Variable: They changed what the items were. Sometimes it was 10 cities, sometimes 10 chemicals, sometimes 10 names, and sometimes 10 emojis.

The Result: The AI's accuracy swung wildly depending on the type of item.

If the list was Cities, the AI might get it right 95% of the time.
If the list was Chemicals, the same AI might only get it right 50% of the time.
The Gap: In some cases, the difference in accuracy was over 40%.

The Analogy: Imagine a cashier who is great at counting apples but somehow keeps losing count when you hand them oranges, even though the task is exactly the same. The cashier isn't bad at math; they are just weirdly biased by the type of fruit.

2. It's Not a "Counting" Problem

The researchers wanted to know why this happened. They ran several experiments to rule out common excuses:

Is it because some words are longer? (Token Count)
- Test: They made sure every list had the exact same number of "tokens" (computer words), even if the items were different.
- Result: The bias remained. It wasn't about length.
Is it because the AI can't see where one item ends and the next begins? (Identification)
- Test: They asked the AI to just wrap each item in XML tags (like <item>City</item>) instead of counting them.
- Result: The AI was excellent at identifying the items. It knew exactly where the cities and chemicals started and stopped. The problem wasn't seeing the items; it was counting them.
Is it because the AI needs to "think harder"? (Reasoning)
- Test: They forced the AI to use more "reasoning effort" (think step-by-step).
- Result: Surprisingly, making the AI think harder didn't fix the problem. In fact, for the smartest models, thinking harder sometimes made the gap between "easy" items and "hard" items even wider.

3. The "Unstable" Nature of the Bias

The researchers also looked at how these models are trained. They found that the bias is unpredictable.

If you take two models that are almost identical but trained on slightly different data, one might be great at counting chemicals but bad at counting names.
The other might be the exact opposite.
The Analogy: It's like two students who studied the same textbook. Student A is great at solving math problems about "apples" but fails at "oranges." Student B is the reverse. You can't predict which student will fail just by looking at their general grade; it depends entirely on the specific topic.

4. Why This Matters (The "Agent" Problem)

The paper shows that this isn't just a trivia game. These models are increasingly being used as "agents" that do work for us, like running code or managing databases.

The Scenario: Imagine an AI agent that needs to count items in a list to send a package. It uses a Python tool (a calculator) to help.
The Failure: Even when the AI has a calculator to help it count, it still gets confused if the items are "Chemicals" instead of "Cities."
The Consequence: If a system relies on the AI to count things correctly to make a decision (like "Do we have enough ingredients?"), the system might fail simply because the meaning of the words changed, not because the math was hard.

The Big Conclusion

The paper concludes that LLMs do not actually "implement" algorithms.

True Algorithm: A rule that works the same way no matter what you plug into it. (Like a vending machine: put in a coin, get a soda. It doesn't matter if the coin is a quarter or a euro; the machine just counts the value).
LLM Behavior: They are approximating algorithms. They are pattern-matching. They have learned that "counting cities" usually looks a certain way in their training data, and "counting chemicals" looks different. They aren't following a rigid rule; they are guessing based on the flavor of the words.

In short: If you ask a human to count 10 things, they count 10. If you ask a top-tier AI to count 10 things, the answer might depend on whether those things are "emojis" or "chemicals." The AI is not a calculator; it is a very good guesser that gets tripped up by the meaning of the words.

Technical Summary: Semantic Content Determines Algorithmic Performance

Problem Statement

The paper addresses a fundamental question regarding the nature of Large Language Models (LLMs): do they implement algorithms, or do they merely approximate them? An algorithm, by definition, should be invariant to the semantic content of its arguments; counting ten items should yield the same result whether the items are cities, chemicals, names, or emojis. However, prior work has established that LLM performance is sensitive to prompt phrasing, list length, and tokenization artifacts. The authors posit that if LLMs truly implement algorithms, their errors should reflect general limitations (e.g., context windows) rather than systematic dependence on what is being counted. If performance varies based on semantic class, the model is likely pattern-matching rather than executing a generalizable procedure. This fragility is critical because LLMs are increasingly deployed in production pipelines where primitive operators (like counting) serve as building blocks for agents and complex workflows.

Methodology: WhatCounts

To isolate semantic invariance from other confounding factors, the authors introduce WhatCounts, an atomic benchmark designed to test counting performance in isolation.

Experimental Design: The benchmark presents LLMs with unambiguous, delimited lists containing valid, non-duplicate items from a single semantic class. The task is strictly to count the items.
Semantic Classes: Six distinct classes were evaluated: addresses, chemicals, cities, full names of people, phone numbers, and emojis.
Controls: The study rigorously controls for:
- List Length: Varying counts across specific ranges (e.g., 7–17, 85–115) to avoid rounding biases.
- Tokenization: Ensuring lists have identical token counts across classes to rule out token-length effects.
- Formatting: Using a consistent separator (pipe |) and testing explicit separator mentions.
- Reasoning: Testing with and without Chain-of-Thought (CoT) and varying reasoning effort levels.
Ablation Studies: The authors performed specific ablations to distinguish between identification (segmenting items) and aggregation (counting them):
- Identification Test: Models were asked to wrap items in XML tags rather than count them.
- Aggregation Test: Models were asked to count items that were already wrapped in XML tags.
- Token Shuffling: Tokens within each item were shuffled to corrupt semantic meaning while preserving token statistics.
Models Evaluated: Four frontier models were tested: o3 (OpenAI), Claude-sonnet-4 (Anthropic), DeepSeek-V3, and Kimi-K2 (Moonshot AI). Additionally, fine-tuned variants of Tulu2-13B trained on different datasets (StackExchange, Nectar, HH-RLHF) using DPO and PPO were evaluated to study training impact.

Key Results

1. Significant Semantic Variance

Frontier LLMs exhibit over 40% accuracy variation depending solely on the semantic class of the items being counted, despite identical formatting and list lengths.

Semantic Gap ( $\Delta_{sem}$ ): Defined as the difference between the maximum and minimum accuracy across semantic classes for a given model.
Counter-Intuitive Finding: The models with the highest average accuracy (e.g., o3) often exhibited the largest semantic gaps, suggesting that stronger models are not necessarily more robust to semantic fragility.

2. Ruling Out Surface Explanations

The authors systematically ruled out alternative explanations for the variance:

Token Count: Controlling for token count did not eliminate the gap; in some cases, fixing token counts increased the semantic gap.
Structure Recognition: Explicitly mentioning the separator or wrapping items in XML tags did not remove the variance. Models could successfully identify and wrap items (high accuracy) but failed to count them accurately, indicating the failure lies in aggregation, not identification.
Reasoning Effort: Increasing reasoning effort (e.g., in o3) did not improve counting accuracy and, in some cases, increased the semantic gap.
Token Shuffling: Shuffling tokens within items (destroying semantic meaning) significantly altered performance, suggesting the models rely on the semantic distribution of tokens rather than purely structural counting.

3. Instability and Training Impact

Unpredictable Shifts: Fine-tuning models on unrelated datasets (e.g., StackExchange vs. Nectar) caused the specific semantic classes that succeeded or failed to shift unpredictably. This indicates the fragility is a property of the learned weights rather than the architecture.
Agentic Failure: In an agentic environment where models used a Python execution tool to count items, the semantic gap persisted and even increased relative to base models. This demonstrates that the fragility propagates to tool-use scenarios, undermining the reliability of "prompt programming" assumptions.

Key Contributions

WhatCounts Benchmark: A minimal, atomic benchmark isolating semantic invariance in counting, free from confounds like tokenization ambiguity or multi-step reasoning.
Semantic Dependence of Algorithms: Empirical evidence that counting accuracy varies by over 40% across semantic classes under identical conditions, proving that LLMs do not implement invariant algorithms but rather argument-dependent approximations.
Unstable Failure Modes: Demonstration that semantic biases shift unpredictably with fine-tuning on unrelated data, confirming the gap is driven by model weights.
Downstream Risk: Evidence that semantic fragility in primitive operators undermines production reliability, as shown in agentic use cases where tool usage does not mitigate the error.

Significance and Claims

The paper concludes that LLMs do not implement algorithms; they approximate them, and the approximation is argument-dependent. This challenges the assumption underlying "prompt programming" that a prompted algorithm will behave like a traditional algorithm (indifferent to the semantic class of its arguments).

The authors argue that if even the simplest primitive (counting) carries hidden dependencies on input meaning, then any LLM "function" (sorting, searching, extracting) may carry similar hidden dependencies. This has profound implications for the reliability of agentic pipelines, where content-conditioned failures in low-level operators can propagate into system-level brittleness. The work suggests that current evaluations may be overestimating robustness by failing to account for semantic class variance, and that future benchmarks must isolate this axis to properly assess model capabilities.