Elamur Research⌕
☰
home / papers / 2025 / InductionBench: LLMs Fail in the Simplest Complexity Class

InductionBench: LLMs Fail in the Simplest Complexity Class

Paper · 2025 · Wenyue Hua, Tyler Wong, Fei Sun et al.

Summary

Most reasoning benchmarks for LLMs test deduction: the rules are given (axioms, programming syntax) and must be applied. This paper asks whether models can do the reverse and infer hidden rules from observations, a skill central to scientific discovery. The authors introduce InductionBench. In it, a model receives a finite set of input–output string pairs and must recover the transformation that produced them. The tasks come from the lowest tier of the subregular hierarchy of string-to-string functions: ISL, L-OSL and R-OSL. For these classes, it has been proven that a polynomial number of examples suffices to learn them in polynomial time, and each has a unique minimal transducer. As a result, the authors can check both correctness and whether a model finds the most concise rule set. Data is generated randomly, so the benchmark can be refreshed to counter memorization, and scoring is fully automatic. Difficulty is controlled through the Markov window k, alphabet size |Σ| and the number of minimal rules. Even strong models such as o3-mini perform poorly on these tasks. This exposes a real gap in LLM inductive reasoning, despite their success on mathematics and coding.

Key points

  • The benchmark covers three function classes: Input-Strictly-Local (ISL), Left Output-Strictly-Local (L-OSL) and Right Output-Strictly-Local (R-OSL). All three are proper subclasses of subsequential functions.
  • Increasing the window k hurts models much more than enlarging the alphabet. This suggests that the depth of sequential dependencies matters more than symbol variety. The number of minimal rules also strongly affects difficulty.
  • In tests with Llama-3.3 70B, 1–3 in-context examples helped only when k and the vocabulary were small. The gains became negligible as complexity grew.
  • Two extra variants reduce the risk of "hacking" the benchmark with known learning algorithms:
    • one variant hides the function class and k;
    • another adds an Input-Output Strictly Local (IOSL) class, for which no reliable learner from finite samples is known.
  • Limitations: all data is synthetic, and access to o1 was restricted. Code and data are released at github.com/wenyueh/inductive_reasoning_benchmark.

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

🎓University of California, Santa BarbaraSanta Barbara · United States57 works · 9,752 citations🎓Rutgers, The State University of New JerseyNew Brunswick · United States36 works · 12,026 citations🎓University of ArizonaTucson · United States38 works · 10,603 citations

 Fields, topics and concepts

📚 Shelves 4The 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 works

🧭 Topics 1Research subjects and languages the work is about.Language models & pretraining · 3,320 works

Cite

Cite as Wenyue Hua, Tyler Wong, Fei Sun, Liangming Pan, Adam Jardine and William Yang Wang. 2025. InductionBench: LLMs Fail in the Simplest Complexity Class. Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers).

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2025.acl-long.1287

@inproceedings{hua2025inductionbench,
  title = {{InductionBench: LLMs Fail in the Simplest Complexity Class}},
  author = {Wenyue Hua, Tyler Wong, Fei Sun, Liangming Pan, Adam Jardine and William Yang Wang},
  booktitle = {Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)},
  year = {2025},
  doi = {10.18653/v1/2025.acl-long.1287},
  url = {https://doi.org/10.18653/v1/2025.acl-long.1287}
}

References

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

  1. Thomas Graf. 2022. Diving deeper into subregular syntax. Theoretical Linguistics, 48(3-4):245–278. find
  2. Arvind Arasu, Surajit Chaudhuri, and Raghav Kaushik. 2009. Learning string transformations from ex-Peter D Grünwald. 2007. The minimum description length principle. MIT press. find
  3. Simeng Han, Hailey Schoelkopf, Yilun Zhao, Zhenting Qi, Martin Riddell, Wenfei Zhou, James Coady, David Peng, Yujie Qiao, Luke Benson, et al. 2022. Folio: Natural language reasoning with first-order logic. arXiv preprint arXiv:2209.00840.
  4. Mark H Hansen and Bin Yu. 2001. Model selection and the principle of minimum description length. Journal of the american statistical association, 96(454):746– 774. find
  5. James Hawthorne. 2004. Inductive logic. find
  6. Jeffrey Heinz. 2018. The computational nature of phonological generalizations. Phonological typology, phonetics and phonology, 23:126–195. find
  7. Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. 2021. Measuring mathematical problem solving with the math dataset. arXiv preprint arXiv:2103.03874.
  8. Wenyue Hua, Kaijie Zhu, Lingyao Li, Lizhou Fan, Shuhang Lin, Mingyu Jin, Haochen Xue, Zelong Li, JinDong Wang, and Yongfeng Zhang. 2024. Disentangling logic: The role of context in large language model reasoning capabilities. arXiv preprint arXiv:2406.02787. find
  9. Aaron Hurst, Adam Lerer, Adam P Goucher, Adam Perelman, Aditya Ramesh, Aidan Clark, AJ Ostrow, Akila Welihinda, Alan Hayes, Alec Radford, et al. 2024. Gpt-4o system card. arXiv preprint arXiv:2410.21276.
  10. Aaron Jaech, Adam Kalai, Adam Lerer, Adam Richardson, Ahmed El-Kishky, Aiden Low, Alec Helyar, Aleksander Madry, Alex Beutel, Alex Carney, et al. 2024. Openai o1 system card. arXiv preprint arXiv:2412.16720.
  11. Gerhard Jäger and James Rogers. 2012. Formal language theory: refining the chomsky hierarchy. Philosophical Transactions of the Royal Society B: Biological Sciences, 367(1598):1956–1970. find
  12. Naman Jain, King Han, Alex Gu, Wen-Ding Li, Fanjia Yan, Tianjun Zhang, Sida Wang, Armando Solar-Lezama, Koushik Sen, and Ion Stoica. 2024. Livecodebench: Holistic and contamination free evaluation of large language models for code. arXiv preprint arXiv:2403.07974.
  13. Adam Jardine, Jane Chandlee, Rémi Eyraud, and Jeffrey Heinz. 2014. Very efficient learning of structured classes of subsequential functions from positive data. In International Conference on Grammatical Inference, pages 94–108. PMLR. find
  14. Carlos E Jimenez, John Yang, Alexander Wettig, Shunyu Yao, Kexin Pei, Ofir Press, and Karthik Narasimhan. 2023. Swe-bench: Can language models resolve real-world github issues? arXiv preprint arXiv:2310.06770.
  15. Brenden M Lake, Tal Linzen, and Marco Baroni. 2019. Human few-shot learning of compositional instructions. arXiv preprint arXiv:1901.04587. find
  16. Tianle Li, Ge Zhang, Quy Duc Do, Xiang Yue, and Wenhu Chen. 2024. Long-context llms struggle with long in-context learning. arXiv preprint arXiv:2404.02060.
  17. Aixin Liu, Bei Feng, Bing Xue, Bingxuan Wang, Bochao Wu, Chengda Lu, Chenggang Zhao, Chengqi Deng, Chenyu Zhang, Chong Ruan, et al. 2024a. Deepseek-v3 technical report. arXiv preprint arXiv:2412.19437. find
  18. Emmy Liu, Graham Neubig, and Jacob Andreas. 2024b. An incomplete loop: Deductive, inductive, and abductive learning in large language models. arXiv preprint arXiv:2404.03028.
  19. Iman Mirzadeh, Keivan Alizadeh, Hooman Shahrokhi, Oncel Tuzel, Samy Bengio, and Mehrdad Farajtabar. 2024. Gsm-symbolic: Understanding the limitations of mathematical reasoning in large language models. arXiv preprint arXiv:2410.05229.
  20. Mehryar Mohri. 1997. Finite-state transducers in language and speech processing. Computational linguistics, 23(2):269–311.
  21. José Oncina and Pedro Garcia. 1991. Inductive learning of subsequential functions. Univ. Politécnica de Valencia, Tech. Rep. DSIC II, 31. find
  22. Mihir Parmar, Nisarg Patel, Neeraj Varshney, Mutsumi Nakamura, Man Luo, Santosh Mashetty, Arindam Mitra, and Chitta Baral. 2024. Logicbench: Towards systematic evaluation of logical reasoning ability of large language models. In Proceedings of the 62nd Annual Meeting of the Association for Computati…
  23. Linlu Qiu, Liwei Jiang, Ximing Lu, Melanie Sclar, Valentina Pyatkin, Chandra Bhagavatula, Bailin Wang, Yoon Kim, Yejin Choi, Nouha Dziri, et al. 2023. Phenomenal yet puzzling: Testing inductive reasoning capabilities of language models with hypothesis refinement. arXiv preprint arXiv:2310.08559. find
  24. Emmanuel Roche and Yves Schabes. 1997. Finite-state language processing, volume 115. MIT press Cambridge, MA. find
  25. James Rogers and Geoffrey K Pullum. 2011. Aural pattern recognition experiments and the subregular hierarchy. Journal of Logic, Language and Information, 20:329–342. find
  26. Giorgio Satta and John Henderson. 1997. String transformation learning. In 35th Annual Meeting of the Association for Computational Linguistics and 8th Conference of the European Chapter of the Association for Computational Linguistics, pages 444–451. find
  27. Bianca Truthe. 2018. Hierarchy of subregular language families. find
  28. Yubo Wang, Xueguang Ma, Ge Zhang, Yuansheng Ni, Abhranil Chandra, Shiguang Guo, Weiming Ren, Aaran Arulraj, Xuan He, Ziyan Jiang, et al. 2024. Mmlu-pro: A more robust and challenging multi-task language understanding benchmark. arXiv preprint arXiv:2406.01574.
  29. Weihao Yu, Zihang Jiang, Yanfei Dong, and Jiashi Feng. 2020. Reclor: A reading comprehension dataset requiring logical reasoning. arXiv preprint arXiv:2002.04326.
  30. Kaijie Zhu, Jiaao Chen, Jindong Wang, Neil Zhenqiang Gong, Diyi Yang, and Xing Xie. 2023. Dyval: Dynamic evaluation of large language models for reasoning tasks. In The Twelfth International Conference on Learning Representations. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/hua-2025-inductionbench-llms-fail-simplest-complexity/