Measuring in-context algorithmic reasoning in language models against an exact Bayes-optimal standard

Imagine you are trying to teach a robot to solve a puzzle. You show it a few examples: "If I put a red block here, a blue block appears there." Then you ask it to predict what happens next. Sometimes the robot gets it right, but is it actually thinking about the rules of the puzzle, or is it just guessing based on how the words usually sound together? This is the big mystery behind modern "Large Language Models" (LLMs), the super-smart AI chatbots we use today. Scientists call this "in-context learning"—the ability to learn a new task just by reading a few examples in a prompt. The problem is, we don't really have a perfect ruler to measure if the robot is truly reasoning or just pattern-matching. Usually, we can only compare one robot to another, or to a human, but we don't know the "God's eye view" of what the perfect answer should be.

To fix this, the authors of this paper built a special, tiny, and perfectly controlled universe. They created a benchmark called F-ICL. Think of it as a giant, exhaustive library of every possible simple computer program that could solve a specific type of binary puzzle (using only 0s and 1s). Because they listed every single one of these 1.5 billion tiny programs, they can calculate the mathematically perfect answer for any puzzle. This perfect answer is called the "Bayes-optimal" solution. It's the gold standard: the absolute best possible guess a machine could make given the evidence. Now, they can finally hold up a real AI model against this gold standard and see exactly how far off it is. It's like having a perfect map of a city and then checking if a GPS app is actually guiding you along the shortest route, or if it's just guessing based on traffic patterns it saw yesterday.

The Great Reasoning Gap

The researchers took a massive panel of 105 different AI models—ranging from open-source projects to the most advanced "frontier" systems from top tech labs—and put them through the F-ICL test. They wanted to see if these models could act like perfect Bayesian reasoners, updating their beliefs logically as new evidence came in.

Here is the surprising twist: The models are great at giving the right answer, but terrible at reasoning like a perfect machine.

Even though some models got the final answer correct up to 92% of the time, their internal "guessing distribution" (the way they weigh different possibilities) was often worse than a simple random guesser. In fact, 45 out of 46 models performed worse than a "keystroke reference." Imagine a monkey randomly hitting keys on a keyboard; this random monkey actually produced a probability distribution that was closer to the perfect mathematical truth than most of the advanced AI models did. The models weren't just slightly off; they were confidently wrong about the underlying logic.

The "Over-Commitment" Glitch

One of the most playful and revealing findings is how the models behave when you give them just one example. A perfect reasoner would get slightly better with every new clue. But these AI models often get worse after seeing just one example before they start to get better.

It's like if you showed a detective a single clue about a crime, and instead of thinking carefully, they immediately shouted, "I know who did it!" and locked onto the wrong suspect. Only after you showed them a few more clues did they slowly backpedal and start to look at the evidence again. The paper found that 69 out of 81 model runs made this mistake, jumping to conclusions too fast. They are "over-committing" to the first piece of data they see, rather than waiting to see the whole picture.

Size Doesn't Fix the Logic

You might think that bigger, smarter models would fix this. The paper tested models with billions of parameters (the "brain size" of the AI), from tiny 0.8 billion ones to massive 675 billion ones. The result? Bigger models got better at getting the right answer, but they didn't get any better at reasoning.

The gap between the model's behavior and the perfect mathematical standard stayed exactly the same, no matter how huge the model was. Whether the model had 1 billion parameters or 600 billion, it still struggled to match the perfect "Bayes-optimal" logic. It's as if you gave a student a bigger and bigger library of books (more data), but they still didn't learn how to use a map; they just got better at memorizing the book titles.

The "Safety" and "Training" Trap

The paper also looked at what happens when models are "post-trained"—that is, when humans tweak them to be more helpful, follow instructions, or be "safe." Surprisingly, this training made the reasoning gap wider.

When models were tuned to be "instruction-following" or to "think" more, they actually moved further away from the perfect logical standard. It seems that teaching a model to be polite or to follow a specific chat format might be teaching it to ignore the raw, logical structure of the problem. It's like teaching a chess player to always say "Good game" after a match; they might become more pleasant, but they might forget the actual rules of the game.

The Frontier is Stalling

The researchers also looked at the newest, most expensive models from the biggest tech companies, released over the last two years. They found that fidelity to the perfect logical standard has not improved at all. The newest models are just as far from the perfect reasoner as the older ones were. In fact, the oldest model they tested (from May 2024) was actually the most faithful to the logical standard, while the newest ones were slightly worse.

The "Termination" Trouble

One specific reason the models scored so low was how they handled the end of a sentence. The perfect mathematical model knows exactly when a sequence of 0s and 1s should stop. The AI models, however, were very bad at this. They often guessed that a sequence should end when it shouldn't, or kept going when it should have stopped. This specific error made up nearly 90% of their mistakes. It's as if the models were great at writing the story but terrible at knowing when to put a period at the end.

The Verdict

The paper concludes that while these AI models are incredibly good at pattern completion—finding the most likely next word based on what they've seen before—they are not yet doing genuine algorithmic reasoning. They are not building a mental model of the rules; they are just stitching together patterns.

The authors released their benchmark, F-ICL, as an open tool so other scientists can keep testing this. They found that current models are stuck in a "pattern-matching" zone, sitting between a random guess and a perfect logical reasoner, but much closer to the random guess. Until models can close this gap, they might be great at writing essays or coding snippets, but they aren't truly "thinking" in the way we hope they will. The gap isn't fixed by making the models bigger or training them longer; it seems to require a fundamental change in how they process information.