INDUCTION: Finite-Structure Concept Synthesis in First-Order Logic
Abstract
bstract: Large language and reasoning models can be prompted to generate well-formed first-order formulas, but we still lack evaluations of their ability to produce correct, compact explanations under fully specified, mechanically checkable semantics. We study finite-structure concept synthesis: given several small finite relational worlds that are labeled extensionally with a unary target predicate , the learner must output a single first-order formula that recovers (explains) uniformly across worlds. Because the domains are finite, correctness is solver-verifiable via exact model checking and SMT. We introduce INDUCTION, a benchmark suite that (to our knowledge) provides the first challenging, end-to-end evaluation of first-order definition synthesis from extensional relational evidence in a fully abstract interface. INDUCTION includes three tightly related regimes---FullObs (full observation), CI (contrastive Yes/No worlds), and EC (partial observation under existential completion)---and reports gold-relative, budgeted metrics that penalize formula bloat. Across tasks we observe sharp difficulty gradients and persistent hard structural families; moreover, held-out world evaluation shows that among training-correct solutions, low-bloat formulas generalize far better than highly bloated ones, motivating bloat-aware scoring as a first-class metric for symbolic induction.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Lineage
Builds on2
Related papers
- Can LLM Aid in Solving Constraints with Inductive Definitions?Weizhi Feng, Shidong Shen, Jiaxiang Liu, Taolue Chen et al.FM 2026
- Provenance-guided synthesis of Datalog programsMukund Raghothaman, Jonathan Mendelson, David Zhao, Mayur Naik et al.POPL 2020 · 49 citations
- PBEBench: A Multi-Step Programming by Examples Reasoning Benchmark inspired by Historical LinguisticsAtharva Naik, Prakam, Yash Mathur, Darsh Agrawal et al.ACL Findings 2026
- Separating the Wheat from the Chaff: Understanding (In-)Completeness of Proof Mechanisms for Separation Logic with Inductive DefinitionsNeta Elad, Adithya Murali, Sharon ShohamPOPL 2026
- GeoILP: A Synthetic Dataset to Guide Large-Scale Rule InductionSi Chen, Richong Zhang, Xu ZhangICLR 2025
