# InductionBench: LLMs Fail in the Simplest Complexity Class

arXiv: https://arxiv.org/abs/2502.15823 · HTML: https://mlsanity.com/paper/2502.15823/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 46 references that are in the map.
- First posted on arXiv 20 Feb 2025.

## Builds on (most cited first, 18 of 18)

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [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)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [GPT-4o System Card](https://mlsanity.com/paper/2410.21276/) (2024)
- [SWE-bench: Can Language Models Resolve Real-World GitHub Issues?](https://mlsanity.com/paper/2310.06770/) (2023)
- [LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code](https://mlsanity.com/paper/2403.07974/) (2024)
- [MMLU-Pro: A More Robust and Challenging Multi-Task Language Understanding Benchmark](https://mlsanity.com/paper/2406.01574/) (2024)
- [GSM-Symbolic: Understanding the Limitations of Mathematical Reasoning in Large Language Models](https://mlsanity.com/paper/2410.05229/) (2024)
- [Long-context LLMs Struggle with Long In-context Learning](https://mlsanity.com/paper/2404.02060/) (2024)
- [FOLIO: Natural Language Reasoning with First-Order Logic](https://mlsanity.com/paper/2209.00840/) (2022)
- [ReClor: A Reading Comprehension Dataset Requiring Logical Reasoning](https://mlsanity.com/paper/2002.04326/) (2020)
- [DyVal: Dynamic Evaluation of Large Language Models for Reasoning Tasks](https://mlsanity.com/paper/2309.17167/) (2023)
- [Phenomenal Yet Puzzling: Testing Inductive Reasoning Capabilities of Language Models with Hypothesis Refinement](https://mlsanity.com/paper/2310.08559/) (2023)
- [NPHardEval: Dynamic Benchmark on Reasoning Ability of Large Language Models via Complexity Classes](https://mlsanity.com/paper/2312.14890/) (2023)
- [LogicBench: Towards Systematic Evaluation of Logical Reasoning Ability of Large Language Models](https://mlsanity.com/paper/2404.15522/) (2024)
- [Human few-shot learning of compositional instructions](https://mlsanity.com/paper/1901.04587/) (2019)
- [Disentangling Logic: The Role of Context in Large Language Model Reasoning Capabilities](https://mlsanity.com/paper/2406.02787/) (2024)

## Built on by (most cited first, 9 of 9)

- [HypoBench: Towards Systematic and Principled Benchmarking for Hypothesis Generation](https://mlsanity.com/paper/2504.11524/) (2025)
- [GEAR: A General Evaluation Framework for Abductive Reasoning](https://mlsanity.com/paper/2509.24096/) (2025)
- [From Reasoning to Learning: A Survey on Hypothesis Discovery and Rule Learning with Large Language Models](https://mlsanity.com/paper/2505.21935/) (2025)
- [Do Language Models Follow Occam's Razor? An Evaluation of Parsimony in Inductive and Abductive Reasoning](https://mlsanity.com/paper/2509.03345/) (2025)
- [A Minimum Description Length Approach to Regularization in Neural Networks](https://mlsanity.com/paper/2505.13398/) (2025)
- [Investigating Advanced Reasoning of Large Language Models via Black-Box Environment Interaction](https://mlsanity.com/paper/2508.19035/) (2025)
- [Advancing AI Research Assistants with Expert-Involved Learning](https://mlsanity.com/paper/2505.04638/) (2025)
- [SIMLIFE: Pattern Understanding for Long-Horizon Human-Agent Partnership](https://mlsanity.com/paper/2609.19610/) (2026)
- [From Transformers to Weighted Automata: Towards the Verification of Large Language Models](https://mlsanity.com/paper/2610.04569/) (2026)

## Abstract (arXiv)

Large language models (LLMs) have shown remarkable improvements in reasoning and many existing benchmarks have been addressed by models such as o1 and o3 either fully or partially. However, a majority of these benchmarks emphasize deductive reasoning, including mathematical and coding tasks in which rules such as mathematical axioms or programming syntax are clearly defined, based on which LLMs can plan and apply these rules to arrive at a solution. In contrast, inductive reasoning, where one infers the underlying rules from observed data, remains less explored. Such inductive processes lie at the heart of scientific discovery, as they enable researchers to extract general principles from empirical observations. To assess whether LLMs possess this capacity, we introduce InductionBench, a new benchmark designed to evaluate the inductive reasoning ability of LLMs. Our experimental findings reveal that even the most advanced models available struggle to master the simplest complexity classes within the subregular hierarchy of functions, highlighting a notable deficiency in current LLMs' inductive reasoning capabilities. Coda and data are available https://github.com/Wenyueh/inductive_reasoning_benchmark.