💬 NLP

PBEBench: A Multi-Step Programming by Examples Reasoning Benchmark inspired by Historical Linguistics

This paper introduces PBEBench, a novel benchmark inspired by historical linguistics that evaluates the inductive reasoning capabilities of Large Language Models by requiring them to generate sequences of string rewrite programs to transform inputs into outputs, revealing that even advanced models struggle significantly with complex, multi-step reasoning tasks.

Original authors: Atharva Naik, Prakam, Yash Mathur, Darsh Agrawal, Manav Kapadnis, Yuwei An, Clayton Marr, Carolyn Rose, David Mortensen

Published 2026-02-10

📖 3 min read☕ Coffee break read

CC BY 4.0

Original authors: Atharva Naik, Prakam, Yash Mathur, Darsh Agrawal, Manav Kapadnis, Yuwei An, Clayton Marr, Carolyn Rose, David Mortensen

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 are trying to solve a mystery where a series of secret transformations has turned a set of original objects into a new set of objects. To solve the mystery, you don't just need to know what changed; you need to figure out the exact order in which the changes happened.

This paper introduces PBEBench, a new way to test if Artificial Intelligence (AI) is actually "thinking" or if it’s just guessing based on patterns it has seen before.

The Core Concept: The "Recipe" Mystery

Think of the AI as a chef being handed two plates of food: a "Before" plate (raw ingredients) and an "After" plate (a finished cake). The AI is told that the cake was made using a specific sequence of steps—like “Slice the apple,” then “Add sugar,” then “Bake.”

However, the AI is given a "scrambled" version of the instructions. It might be told: “Here are the steps: Bake, Slice, Add Sugar. Now, tell me the correct order to get from the raw ingredients to the cake.”

If the AI says, "Bake, then Slice," it fails miserably—you can't slice a cake that's already baked and cooled! The order is everything.

The Inspiration: Historical Linguistics

The researchers got this idea from Historical Linguistics (the study of how languages change over thousands of years).

Languages evolve through "sound laws." For example, a word might change its vowel, and then a letter at the end might disappear. If the letter disappears first, the vowel might never have changed. Linguists call these interactions "Feeding" (one change creates the perfect condition for the next) or "Bleeding" (one change destroys the opportunity for the next).

PBEBench turns these complex linguistic rules into a "string-rewriting" game (like a digital version of Scrabble where letters transform into other letters) to see if AI can handle these delicate, step-by-step logical dependencies.

What did they find? (The "Brain" Test)

The researchers tested many of the world's most powerful AIs (like GPT-5 and Claude). Here is what they discovered:

The "Thinking" Gap: AIs that are designed to "think" more deeply (using a process called "Chain-of-Thought") are much better at this than standard AIs. It’s the difference between a student who scribbles a quick answer and a student who shows all their work on a scratchpad.
The Complexity Wall: Even the smartest AIs (like GPT-5) eventually hit a wall. As the "recipe" gets longer (more steps) and the rules get more tangled (more "Feeding" and "Bleeding" interactions), the AI's performance crashes. It’s like asking a human to remember a 50-step instruction manual—eventually, even the best minds start making mistakes.
The "Overthinking" Trap: Some models actually perform worse when they try to think too much. They get lost in their own logic, creating "recipes" that are way too complicated for the simple task at hand.

Why does this matter?

Most AI benchmarks test "knowledge"—like asking an AI, "Who was the third president of the US?" But PBEBench doesn't care about facts. It tests pure reasoning.

By creating a benchmark that is "knowledge-free," the researchers have built a way to measure the "raw horsepower" of an AI's logic. This helps us understand if we are building machines that truly understand the structure of the world, or just very fancy parrots that are great at memorizing the dictionary.

Technical Summary: PBEBench: A Multi-Step Programming by Examples Reasoning Benchmark

PBEBench is a novel, automated benchmark designed to evaluate the multi-step inductive reasoning capabilities of Large Language Models (LLMs). Unlike existing benchmarks that often conflate reasoning with domain-specific knowledge (e.g., coding or math), PBEBench isolates pure inductive reasoning through a knowledge-free, string-transformation framework.

1. The Problem: Reasoning vs. Knowledge

The authors identify a gap in current LLM evaluation: most benchmarks require specialized background knowledge, making it difficult to determine if a model is truly "reasoning" or simply retrieving learned patterns.

The benchmark is inspired by Sound Law Induction (SLI) in historical linguistics, where linguists must infer an ordered sequence of sound changes (rules) that transform ancestral words into modern ones. The core challenge is not just finding individual rules, but understanding the ordering constraints between them. In linguistics, rules can feed (create context for another rule), bleed (remove context for another), or exhibit counter-relations. This creates a complex, sequential dependency problem that is difficult for models to solve without precise planning and intermediate state tracking.

2. Methodology

The researchers developed a symbolic Problem Proposer and a Problem Solver framework:

Problem Proposer (Symbolic System):
- Generates instances consisting of input strings, a sequence of "find-and-replace" programs (the cascade), and the resulting output strings.
- Controllable Difficulty: It uses rejection sampling to ensure a balanced distribution of BFCC relations (Feeding, Bleeding, Counter-Feeding, and Counter-Bleeding).
- Scalability: Because it is symbolic, it can generate infinite, novel, and contamination-resistant instances by varying cascade length ( $L$ ), alphabet size, and string length.
Problem Solver (The LLM):
- Models are tasked with two primary challenges: Multi-step PBE (inducing the full program cascade from input-output pairs) and Program Reordering (recovering the correct order of a scrambled sequence of programs).
Scaling Strategies: The study investigates two ways to improve performance: increasing the sampling budget (trying more candidate solutions) and increasing the thinking budget (allowing for longer Chain-of-Thought/test-time compute).

3. Key Contributions

A Formalized Reasoning Framework: It translates complex linguistic phenomena (BFCC relations) into a simple, formally specified, and scalable string-rewrite task.
Contamination Resistance: Since instances are generated programmatically with controllable parameters, the benchmark is inherently resistant to data leakage.
Provably Correct Classification: The paper provides a theoretical framework (and algorithms) to automatically and correctly classify the interaction types between any two rewrite rules.
Predictive Validity: The authors demonstrate that PBEBench scores are highly predictive of a model's ability to perform real-world Sound Law Induction (SLI) compared to other benchmarks.

4. Key Results

Reasoning Gap: There is a massive performance gap between "reasoning" models (e.g., GPT-5, Claude-4-Sonnet-Thinking, DeepSeek-R1) and "non-reasoning" models. Reasoning models significantly outperform non-reasoning ones, even when the latter are larger.
The "Complexity Wall": Even the most advanced models (GPT-5 and gpt-oss-120b) struggle as the cascade length increases. At lengths of 20–30, solve rates drop below 5%, indicating a fundamental limit in current LLM sequential planning.
Interaction Bottlenecks: Difficulty is driven more by the interaction structure (the presence of feeding/bleeding relations) and cascade length than by the number of examples provided.
Scaling Efficiency: For reasoning models, increasing the thinking budget (allowing more tokens for CoT) is more effective and cost-efficient than simply increasing the sampling budget.
Model Tendencies: Models tend to "underthink" (producing overly simple programs) or "overthink" (producing overly complex, invalid programs), often failing to capture the necessary BFCC interactions required for a correct solution.

5. Significance

PBEBench provides a rigorous "stress test" for the next generation of reasoning models. By isolating the ability to compose interacting transformations, it offers a way to measure system-2 reasoning—the ability to plan, simulate intermediate states, and respect logical constraints—without the interference of domain-specific data contamination. It serves as a vital tool for researchers aiming to move LLMs from pattern matching toward true, multi-step inductive logic.