Elamur Research⌕
☰
home / papers / 2026 / PBEBench: A Multi-Step Programming by Examples Reasoning Benchmark inspired by Historical Linguistics

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

Paper · 2026 · Atharva Naik, Darsh Agrawal, Prakam et al.

Summary

Most reasoning benchmarks mix logical ability with domain knowledge. This paper tries to separate the two with a task modeled on Sound Law Induction (SLI) from historical linguistics. In SLI, linguists explain how ancestral words became modern forms by positing an ordered series of sound changes. The authors recast this as multi-step Programming by Example (PBE): given input–output string pairs, a solver must infer a cascade of find-and-replace rules that maps one to the other.

PBEBench is a symbolic generator that samples random strings and rule cascades. It can tune the number of examples, the alphabet, string lengths and cascade length. It can also enforce rule-ordering interactions from phonology (feeding, bleeding, counter-feeding, counter-bleeding), which the authors call BFCC relations. Because instances are freshly generated, the benchmark scales easily and resists contamination.

The authors test 13 reasoning and 8 non-reasoning LLMs and find a wide gap in favor of models that use long chain-of-thought. Long cascades remain largely unsolved even by the strongest models. PBEBench scores also track real SLI performance better than other inductive reasoning benchmarks do.

Key points

  • Datasets: the generator produces three datasets, including PBEBench-Lite, PBEBench-Lite-MoreEg (more examples per problem) and PBEBench-Lite-Perm. In the Perm variant, models must restore the correct order of a given rule set whose feeding/bleeding pairs have been swapped.
  • Hard instances: GPT-5 and gpt-oss-120b solve fewer than 5% of hard instances with long cascades, even with costly scaling of thinking and sampling budgets.
  • Source of difficulty: adding more examples per step matters less than longer cascades and richer BFCC interactions. Even in the Perm setting, where at most 24 orderings are valid, accuracy falls as cascades lengthen.
  • Link to real SLI: among open-source models, PBEBench-Lite correlates more strongly with real SLI results than CLUTRR or SLR-Bench do.
  • Release and limitations: code and data are available at github.com/cmu-llab/PBEBench. In the generated data, each rule changes relatively few words, whereas real sound laws typically affect many words at once.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Carnegie Mellon UniversityPittsburgh · United States539 works · 179,533 citations🎓The Ohio State UniversityColumbus · United States82 works · 18,502 citations

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 worksComputer Science Applications · 102 works

🧭 Topics 3Research subjects and languages the work is about.Reasoning · 1,426 worksEvaluation & benchmarks · 1,220 worksHistorical linguistics & language change · 249 works

Cite

Cite as Atharva Naik, Darsh Agrawal, Prakam, Yash Mathur, Manav Kapadnis, Yuwei An, Clayton Marr, Carolyn Rose and David Mortensen. 2026. PBEBench: A Multi-Step Programming by Examples Reasoning Benchmark inspired by Historical Linguistics. Findings of the Association for Computational Linguistics: ACL 2026.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2026.findings-acl.432

@inproceedings{naik2026pbebench,
  title = {{PBEBench: A Multi-Step Programming by Examples Reasoning Benchmark inspired by Historical Linguistics}},
  author = {Atharva Naik, Darsh Agrawal, Prakam, Yash Mathur, Manav Kapadnis, Yuwei An, Clayton Marr, Carolyn Rose and David Mortensen},
  booktitle = {Findings of the Association for Computational Linguistics: ACL 2026},
  year = {2026},
  doi = {10.18653/v1/2026.findings-acl.432},
  url = {https://doi.org/10.18653/v1/2026.findings-acl.432}
}

References

49 references, 13 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Mistral AI. 2024. Codestral-22b-v0.1. https://huggingface.co/mistralai/ Codestral-22B-v0.1. Released under the Mistral AI Non-Production License (MNPL); retrieved May 9, 2025. ↗
  2. Rajeev Alur, Dana Fisman, and Rishabh Singh. 2013. Syntax-guided synthesis. In Proceedings of the International Conference on Formal Methods in Computer-Aided Design (FMCAD), pages 1–8. find
  3. Anthropic. 2024. Sonnet. https://console.anthropic.com/. Output generated by Claude 3.5; retrieved May 9, 2025. ↗
  4. Anthropic. 2025a. Claude opus 4 model overview. Anthropic model card / announcement. Released May 22, 2025; 200,000 token context window. find
  5. Anthropic. 2025b. Claude sonnet 4 model overview. Anthropic Models Overview Webpage. API name: claude-sonnet-4-20250514, 200K token context window, high-performance model with exceptional reasoning and efficiency. find
  6. Anthropic. 2025. Sonnet. https://console.anthropic.com/. Output generated by Claude 3.7; retrieved May 9, 2025. ↗
  7. Jacob Austin, Augustus Odena, Maxwell Nye, and et al. 2021. Program synthesis with large language models. In International Conference on Learning Representations (ICLR). ArXiv:2108.07732.
  8. Matej Balog, Alexander L. Gaunt, Marc Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. 2017. Deepcoder: Learning to write programs. In International Conference on Learning Representations (ICLR). find
  9. Mark Chen, Jerry Tworek, Heewoo Jun, and et al. 2021a. Evaluating large language models trained on code. arXiv preprint arXiv:2107.03374.
  10. Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde De Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, and 1 others. 2021b. Evaluating large language models trained on code. arXiv preprint arXiv:2107.03374.
  11. François Chollet. 2019. On the measure of intelligence. Preprint, arXiv:1911.01547. 8886 10 find
  12. Karl Cobbe, Vineet Kosaraju, Timothy Lillicrap, Chris Paine, Jacob Hilton, and et al. 2021. Training verifiers to solve math word problems. In Advances in Neural Information Processing Systems. ArXiv:2107.00250.
  13. Gheorghe Comanici, Eric Bieber, Mike Schaekermann, Ice Pasupat, Noveen Sachdeva, Inderjit Dhillon, Marcel Blistein, Ori Ram, Dan Zhang, Evan Rosen, and 1 others. 2025. Gemini 2.5: Pushing the frontier with advanced reasoning, multimodality, long context, and next generation agentic capabilities. arX…
  14. DeepSeek-AI. 2025. Deepseek-r1: Incentivizing reasoning capability in llms via reinforcement learning. Preprint, arXiv:2501.12948.
  15. Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel rahman Mohamed, and Pushmeet Kohli. 2017. Robustfill: Neural program learning under noisy i/o. Preprint, arXiv:1703.07469. find
  16. Dheeru Dua, Yizhong Wang, Pradeep Dasigi, Gabriel Stanovsky, Sameer Singh, and Matt Gardner. 2019. Drop: A reading comprehension benchmark requiring discrete reasoning over paragraphs. In North American Chapter of the Association for Computational Linguistics.
  17. Dhruv Gautam, Spandan Garg, Jinu Jang, Neel Sundaresan, and Roshanak Zilouchian Moghaddam. Refactorbench: Evaluating stateful reasoning in language agents through code. In The Thirteenth International Conference on Learning Representations. find
  18. Daniel Gildea and Daniel Jurafsky. 1995. Automatic induction of finite state transducers for simple phonological rules. In 33rd Annual Meeting of the Association for Computational Linguistics, pages 9–15, Cambridge, Massachusetts, USA. Association for Computational Linguistics. find
  19. Sumit Gulwani. 2010. Dimensions in program synthesis. In Proceedings of the 12th International ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming, PPDP ’10, page 13–24, New York, NY, USA. Association for Computing Machinery. find
  20. Sumit Gulwani. 2011. Automating string processing in spreadsheets using input-output examples. In Proceedings of the 38th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL), pages 317–330. ACM. find
  21. Daya Guo, Qihao Zhu, Dejian Yang, Zhenda Xie, Kai Dong, Wentao Zhang, Guanting Chen, Xiao Bi, Y. Wu, Y. K. Li, Fuli Luo, Yingfei Xiong, and Wenfeng Liang. 2024. Deepseek-coder: When the large language model meets programming – the rise of code intelligence. Preprint, arXiv:2401.14196. find
  22. Lukas Helff, Ahmad Omar, Felix Friedrich, Antonia Wüst, Hikaru Shindo, Tim Woydt, Rupert Mitchell, Patrick Schramowski, Wolfgang Stammer, and Kristian Kersting. 2025. Slr: Automated synthesis for scalable logical reasoning. In First Workshop on Foundations of Reasoning in Language Models. find
  23. Henry M Hoenigswald. 1960. Language change and linguistic reconstruction. (No Title). find
  24. Kush Jain, Gabriel Synnaeve, and Baptiste Rozière. 2025. Testgeneval: A real world unit test generation and test completion benchmark. Preprint, arXiv:2410.00752. — [arXiv:2410.00752](https://arxiv.org/abs/2410.00752) find
  25. Daniel Keysers, Nathanael Schärli, Nathan Scales, and et al. 2020. Measuring compositional generalization: A comprehensive method on realistic data. Transactions of the Association for Computational Linguistics, 8:328–344. find
  26. Paul Kiparsky. 1968. Linguistic universals and linguistic change. In Emmon W. Bach and Robert Thomas Harms, editors, Universals in Linguistic Theory. (Edited by Emmon Bach, Robert T. Harms ... Contributing Authors, Charles J. Fillmore ... Paul Kiparsky ... James D. McCawley.)., pages 170–202. Holt,… find
  27. Paul Kiparsky. 1971. Historical linguistics. In William Orr Dingwall, editor, A Survey of Linguistic Science. ERIC. find
  28. Brenden M. Lake and Marco Baroni. 2018. Generalization without systematicity: Compositional generalization in recurrent networks. In Proceedings of the 35th International Conference on Machine Learning (ICML), pages 2879–2888. find
  29. A. Lawsen. 2025. Comment on the illusion of thinking: Understanding the strengths and limitations of reasoning models via the lens of problem complexity. Preprint, arXiv:2506.09250. — [arXiv:2506.09250](https://arxiv.org/abs/2506.09250) find
  30. Kefan Li and Yuan Yuan. 2024. Large language models as test case generators: Performance evaluation and enhancement. Preprint, arXiv:2404.13340. — [arXiv:2404.13340](https://arxiv.org/abs/2404.13340) find
  31. Wen-Ding Li and Kevin Ellis. 2024. Is programming by example solved by LLMs? In The Thirty-eighth Annual Conference on Neural Information Processing Systems. find
  32. Kaijing Ma, Xinrun Du, Yunran Wang, Haoran Zhang, Zhoufutu Wen, Xingwei Qu, Jian Yang, Jiaheng Liu, Minghao Liu, Xiang Yue, and 1 others. 2024. Kor-bench: Benchmarking language models on knowledge- orthogonal reasoning tasks. arXiv preprint arXiv:2410.06526. — [arXiv:2410.06526](https://arxiv.org/abs/2410.06526) find
  33. Niklas Muennighoff, Zitong Yang, Weijia Shi, Xiang Lisa Li, Li Fei-Fei, Hannaneh Hajishirzi, Luke Zettlemoyer, Percy Liang, Emmanuel Candès, and Tatsunori Hashimoto. 2025. s1: Simple test-time scaling. arXiv preprint arXiv:2501.19393. 8887 11
  34. Atharva Naik, Darsh Agrawal, Hong Sng, Clayton Marr, Kexun Zhang, Nathaniel R Robinson, Kalvin Chang, Rebecca Byrnes, Aravind Mysore, Carolyn Rose, and David R Mortensen. 2025a. Programming by examples meets historical linguistics: A large language model based approach to sound law induction. Prepri… — [arXiv:2501.16524](https://arxiv.org/abs/2501.16524) find
  35. Atharva Naik, Darsh Agrawal, Hong Sng, Clayton Marr, Kexun Zhang, Nathaniel R Robinson, Kalvin Chang, Rebecca Byrnes, Aravind Mysore, Carolyn Rose, and 1 others. 2025b. Programming by examples meets historical linguistics: A large language model based approach to sound law induction. arXiv preprint… — [arXiv:2501.16524](https://arxiv.org/abs/2501.16524) find
  36. Jason Weston, Antoine Bordes, Sumit Chopra, Alexander M Rush, Bart Van Merriënboer, Armand Joulin, and Tomas Mikolov. 2015. Towards ai-complete question answering: A set of prerequisite toy tasks. arXiv preprint arXiv:1502.05698.
  37. Atharva Naik, Kexun Zhang, Nathaniel Robinson, Aravind Mysore, Clayton Marr, Hong Sng, Rebecca Byrnes, Anna Cai, Kalvin Chang, and David Mortensen. 2024. Can large language models code like a linguist?: A case study in low resource sound law induction. arXiv preprint arXiv:2406.12725. — [arXiv:2406.12725](https://arxiv.org/abs/2406.12725) find
  38. OpenAI. 2024. Gpt o3-mini. https://platform.openai.com/. Output generated by GPT o3-mini; retrieved May 9, 2025. ↗
  39. OpenAI. 2025. Gpt-5. Official model release; OpenAI blog post. find
  40. OpenAI. 2025. Gpt o4-mini. https://platform.openai.com/. Output generated by GPT o4-mini; retrieved May 9, 2025. ↗
  41. OpenAI. 2025. gpt-oss-120b & gpt-oss-20b model card. arXiv preprint, model card. Preprint, arXiv:2508.10925.
  42. Yunfan Shao, Linyang Li, Yichuan Ma, Peiji Li, Demin Song, Qinyuan Cheng, Shimin Li, Xiaonan Li, Pengyu Wang, Qipeng Guo, Hang Yan, Xipeng Qiu, Xuanjing Huang, and Dahua Lin. 2025. Case2Code: Scalable synthetic data for code generation. In Proceedings of the 31st International Conference on Computat…
  43. Parshin Shojaee, Iman Mirzadeh, Keivan Alizadeh, Maxwell Horton, Samy Bengio, and Mehrdad Farajtabar. 2025. The illusion of thinking: Understanding the strengths and limitations of reasoning models via the lens of problem complexity. Preprint, arXiv:2506.06941. find
  44. Koustuv Sinha, Shagun Sodhani, Jin Dong, Joelle Pineau, and William L Hamilton. 2019. Clutrr: A diagnostic benchmark for inductive reasoning from text. arXiv preprint arXiv:1908.06177. find
  45. Mirac Suzgun, Nathan Scales, Nathanael Schärli, Sebastian Gehrmann, Yi Tay, Hyung Won Chung, Aakanksha Chowdhery, Quoc V Le, Ed H Chi, Denny Zhou, , and Jason Wei. 2022. Challenging big-bench tasks and whether chain-of-thought can solve them. arXiv preprint arXiv:2210.09261.
  46. Qwen Team. 2024. Qwen2.5: A party of foundation models. find
  47. Qwen Team. 2025b. Qwq-32b: Embracing the power of reinforcement learning. find
  48. Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William W. Cohen, Ruslan Salakhutdinov, and Christopher D. Manning. 2018. HotpotQA: A dataset for diverse, explainable multi-hop question answering. In Conference on Empirical Methods in Natural Language Processing (EMNLP).
  49. Zhe Zhang, Runlin Liu, Aishan Liu, Xingyu Liu, Xiang Gao, and Hailong Sun. 2025. Dynamic benchmark construction for evaluating large language models on real-world codes. Preprint, arXiv:2508.07180. — [arXiv:2508.07180](https://arxiv.org/abs/2508.07180) find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/naik-2026-pbebench-multi-step-programming-examples/