@s_batzoglou
Iām happy to share INDUCTION: Finite-Structure Concept Synthesis in First-Order Logic, accepted to ICML 2026 as a spotlight. The benchmark aims to test models in their ability to generalize from examples: find compact logical rules that explain many given examples. Each problem gives several small finite relational worlds, with objects labeled as belonging or not belonging to a hidden concept. The model must output one first-order formula phi(x) that captures the concept. An important twist is that getting the examples right is not enough: models can sometimes fit the input worlds with large case-splitting formulas. We therefore score both correctness and formula size, and test whether formulas generalize to held-out worlds. The benchmark is designed to be feasible but not easy for frontier models. This table shows performance in three tasks. In FullObs, all facts are observed, and the formula must match the target concept across several worlds. In CI, the model sees YES and NO worlds. The goal is not to invert labels on the NO worlds, but to avoid formulas that exactly explain those contrastive worlds. In EC, some facts are unknown. A formula is valid if, for each world, there exists some completion of the unknown facts under which the formula matches the target labels. One main result is that validity can be misleading. Some model outputs are compact and close to the intended rule. Others are correct on the input worlds but use huge formulas with large disjunctions that branch on accidental properties of the finite structures. Those bloated formulas usually do not generalize. When we sample new held-out worlds from the same generator and label them by the planted rule, compact near-gold formulas generalize much better than bloated ones.
