In the search for truth—whether it is a doctor diagnosing a patient, a chemist identifying a reaction pathway, or an AI learning a logical rule—the space of possible explanations is effectively infinite. A system could propose a million complex reasons for a set of observations, most of which would be nonsensical or overfitted.
To solve this, researchers across five decades have converged on a shared strategy: Simplicity-First Search. Instead of trying to prune a massive space of complex theories, these systems start with the simplest possible model and only add complexity when the data forces them to. This approach, rooted in the principle of parsimony (Occam’s Razor), transforms an intractable search problem into a structured, iterative discovery process.
The Computational Power of Parsimony
The principle of parsimony is often treated as a philosophical preference, but in automated reasoning, it serves as a critical computational filter. As John Seely Brown noted in Steps Toward Automatic Theory Formation, favoring the simplest theories—such as those with minimal disjunctions—allows a system to distinguish universal rules from the "noise" of idiosyncratic data.
In the context of abduction (generating the best explanation for facts), Harry E. Pople argued in On the Mechanization of Abductive Logic that parsimony is achieved by unifying disparate observations into a single cause. By merging branches of a search tree to find a common ancestor, a system can explain multiple independent symptoms through one underlying hypothesis. This "logical factoring" ensures the machine doesn't just find an explanation, but the most efficient one.
Iterative Complexity Growth
How does a machine practically implement this bias? The most common mechanism is an iterative search strategy that tests models in increasing order of complexity.
- Start Minimal: Begin with the smallest possible representation (e.g., a single logical clause, one chemical species, or one failure).
- Test Against Data: If the simple model fits the observations, stop.
- Increment Complexity: If the model is refuted, allow for one additional term, step, or entity and repeat.
This strategy was formalized early by N. G. Zagoruyko and K. F. Samokhvalov in their Hypothesis of Simplicity in Pattern Recognition. They demonstrated that by only introducing complex relations when simpler ones fail, a system ensures its classifications remain structurally lean.
Modern systems like INCAL, developed by Samuel Kolb and colleagues, apply this to learn complex SMT (Satisfiability Modulo Theories) constraints. By iteratively increasing the number of literals in a formula, they discover the simplest symbolic representation that satisfies numerical and Boolean data without manual tuning. Similarly, the SPELL system uses "bounded fitting" to search for Description Logic concepts, ensuring that the most parsimonious concept is identified first, which provides both speed and interpretability.
Taming the Combinatorial Explosion
The primary reason this works is tractability. In scientific discovery, the number of possible pathways is astronomical. Bruce G. Buchanan and Edward A. Feigenbaum showed in Meta-DENDRAL that heuristic pruning based on simplicity is essential to make the search for chemical rules computationally feasible.
Raúl E. Valdés-Pérez applied this to the MECHEM system, which discovered chemical reaction pathways. By increasing the number of intermediate steps only when simpler hypotheses were refuted, MECHEM could navigate an infinite hypothesis space to find credible scientific truths, including the Nobel-winning urea cycle.
This "Goldilocks" approach—finding a model that is just complex enough but no more—is also central to physical simulations. Yumi Iwasaki and Alon Y. Levy argued in Automated Model Selection for Simulation that starting with an abstract model and adding detail only when necessary is far more efficient than the traditional method of pruning a maximal, overly detailed model.
Minimal Cardinality in Diagnosis and Planning
In domains like medicine or plan recognition, simplicity is often defined as minimal cardinality: the fewest number of causes or goals required to explain the evidence.
- Diagnosis: James A. Reggia and colleagues in A New Inference Method for Frame-Based Expert Systems formalized this as a set-covering problem, where the goal is to find the smallest set of disorders that accounts for all symptoms. This prevents the system from suggesting three rare diseases when one common one would suffice.
- Plan Recognition: Marc B. Vilain demonstrated that plan recognition can be treated like parsing a grammar, where the system seeks a "minimal covering model"—the fewest top-level goals that explain a sequence of actions.
- Story Understanding: Early systems like ARTHUR, described by Richard H. Granger, used parsimony to resolve ambiguity in narratives, favoring interpretations where the minimum number of inferred goals explained the maximum number of observed events.
Why Simplicity Works
Simplicity-first search works because it aligns the search order with the likelihood of the hypothesis. In symbolic domains, complexity is a proxy for the probability of a theory being an accidental fit (overfitting). By searching from simple to complex, AI systems ensure that their "theories" are not just logically sound, but are the most robust and interpretable explanations possible. Whether it is Alberto Camacho learning temporal logic formulas or Reijo Jaakkola building interpretable Boolean classifiers, the goal remains the same: find the shortest path to the truth.