# PBEBench: A Multi-Step Programming by Examples Reasoning Benchmark inspired by Historical Linguistics arXiv: https://arxiv.org/abs/2505.23126 ยท HTML: https://mlsanity.com/paper/2505.23126/ ## Key facts - Cited by 2 papers in the map (data through 14 Oct 2026). - Placed in Reasoning benchmarks and evaluation, one of 17 directions in LLM reasoning. - Builds on 29 of its 68 references that are in the map. - First posted on arXiv 29 May 2025. ## Placed in - LLM reasoning / [Reasoning benchmarks and evaluation](https://mlsanity.com/lr/reasoning-benchmarks-and-evaluation/) ## Builds on (most cited first, 29 of 29) - [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021) - [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021) - [HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering](https://mlsanity.com/paper/1809.09600/) (2018) - [Program Synthesis with Large Language Models](https://mlsanity.com/paper/2108.07732/) (2021) - [LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code](https://mlsanity.com/paper/2403.07974/) (2024) - [Challenging BIG-Bench Tasks and Whether Chain-of-Thought Can Solve Them](https://mlsanity.com/paper/2210.09261/) (2022) - [s1: Simple test-time scaling](https://mlsanity.com/paper/2501.19393/) (2025) - [DeepSeek-Coder: When the Large Language Model Meets Programming -- The Rise of Code Intelligence](https://mlsanity.com/paper/2401.14196/) (2024) - [DROP: A Reading Comprehension Benchmark Requiring Discrete Reasoning Over Paragraphs](https://mlsanity.com/paper/1903.00161/) (2019) - [Towards AI-Complete Question Answering: A Set of Prerequisite Toy Tasks](https://mlsanity.com/paper/1502.05698/) (2015) - [Measuring Compositional Generalization: A Comprehensive Method on Realistic Data](https://mlsanity.com/paper/1912.09713/) (2019) - [CLUTRR: A Diagnostic Benchmark for Inductive Reasoning from Text](https://mlsanity.com/paper/1908.06177/) (2019) - [DeepCoder: Learning to Write Programs](https://mlsanity.com/paper/1611.01989/) (2016) - [RobustFill: Neural Program Learning under Noisy I/O](https://mlsanity.com/paper/1703.07469/) (2017) - [ARC Prize 2024: Technical Report](https://mlsanity.com/paper/2412.04604/) (2024) - [TestGenEval: A Real World Unit Test Generation and Test Completion Benchmark](https://mlsanity.com/paper/2410.00752/) (2024) - [RefactorBench: Evaluating Stateful Reasoning in Language Agents Through Code](https://mlsanity.com/paper/2503.07832/) (2025) - [Large Language Models as Test Case Generators: Performance Evaluation and Enhancement](https://mlsanity.com/paper/2404.13340/) (2024) - [Is Programming by Example solved by LLMs?](https://mlsanity.com/paper/2406.08316/) (2024) - [Training Neural Networks as Recognizers of Formal Languages](https://mlsanity.com/paper/2411.07107/) (2024) - [Ab Antiquo: Neural Proto-language Reconstruction](https://mlsanity.com/paper/1908.02477/) (2019) - [MathConstruct: Challenging LLM Reasoning with Constructive Proofs](https://mlsanity.com/paper/2502.10197/) (2025) - [Case2Code: Scalable Synthetic Data for Code Generation](https://mlsanity.com/paper/2407.12504/) (2024) - [Improved Neural Protoform Reconstruction via Reflex Prediction](https://mlsanity.com/paper/2403.18769/) (2024) - [Program-Aided Reasoners (better) Know What They Know](https://mlsanity.com/paper/2311.09553/) (2023) - [Semisupervised Neural Proto-Language Reconstruction](https://mlsanity.com/paper/2406.05930/) (2024) - [Programming by Examples Meets Historical Linguistics: A Large Language Model Based Approach to Sound Law Induction](https://mlsanity.com/paper/2501.16524/) (2025) - [Transformed Protoform Reconstruction](https://mlsanity.com/paper/2307.01896/) (2023) - [Can Large Language Models Code Like a Linguist?: A Case Study in Low Resource Sound Law Induction](https://mlsanity.com/paper/2406.12725/) (2024) ## Built on by (most cited first, 2 of 2) - [ReaComp: Compiling LLM Reasoning into Symbolic Solvers for Efficient Program Synthesis](https://mlsanity.com/paper/2605.05485/) (2026) - [RevengeBench: Reverse Engineering Code-Space Policies from Behavioral Experiments](https://mlsanity.com/paper/2606.26094/) (2026) ## Abstract (arXiv) Although many benchmarks evaluate the reasoning abilities of Large Language Models (LLMs) within domains such as mathematics, coding, or data wrangling, few abstract away from domain specifics to examine reasoning as a capability in and of itself. We contribute a novel type of benchmark evaluating the inductive reasoning capabilities of LLMs that is inspired by the forward reconstruction task from historical linguistics but is formulated in an extremely simple, general way (in the form of Programming by Examples). The task involves generating a cascade of simple string rewrite programs to transform a given list of input strings into a list of desired output strings. We present a fully automated pipeline that programmatically generates problems of this type with controllable difficulty, enabling scalable evaluation of reasoning models while avoiding contamination. Using this approach, we construct two benchmarks: PBEBench-Lite, which efficiently stratifies models of varying capabilities, and PBEBench, which requires models to induce programs similar in complexity to those constructed by historical linguists. Our experiments reveal a substantial performance gap between models that leverage test-time compute or LCoT (long chain-of-thought) reasoning and those that do not. Moreover, although recent models show promise, the solve rate for both of them drops below 5% for hard instances of the PBEBench dataset (ground truth cascade lengths of 20 and 30, respectively), falling well short of realistic historical linguistics requirements even with computationally expensive, popular scaling techniques from the PBE and reasoning literature. Additionally, we also study the effectiveness of different scaling strategies and the impact of various hyperparameters on the difficulty of the generated data using gpt-oss-120b, the best-performing open-source model.