Reasoning with Simplifying Assumptions: A Methodology and Example
Introduction
In the field of automated reasoning and program synthesis, the computational cost of theorem proving often acts as a significant bottleneck. When a system attempts to synthesize a program that adheres to a specific specification, it must continuously verify a multitude of logical conditions. Traditional AI systems frequently struggle by attempting to prove every detail—such as ensuring every variable is defined or every type is correct—before determining if a particular solution path is even viable.
This paper proposes a formal methodology inspired by human problem-solving: the use of "simplifying assumptions." Just as a physicist might initially ignore friction to grasp the core mechanics of a system, an automated reasoner can defer messy edge cases until a promising "main story" is established.
Methodology
The authors introduce a framework where a Simplified Theory operates alongside a Full Theory. This process involves three primary steps:
- Categorization: Axioms within the full theory are divided into "Main Conclusions" (propositions that drive the reasoning forward, like function return types) and "Default Assumptions" (tedious details that are usually true, such as whether an input is defined).
- Theory Construction: The simplified theory is constructed using these main conclusions as premises. By bypassing the complex logical checks required by the full theory, the simplified version becomes significantly "cheaper" to compute.
- Discharging Assumptions: Once a reasoning path is deemed promising, the system "discharges" the simplifying assumptions. It retracts the simplified premises and re-evaluates the logic using the full axioms to ensure complete correctness.
This methodology was implemented in Cake, a reasoning system that utilizes "Noticers" to trigger axioms and a dependency-tracking system to facilitate "dependency-directed backtracking" when assumptions fail.
Logical Relationships
A critical insight of this work is that a simplified theory is not merely a subset of the full theory. As illustrated in the various logical configurations below, the relationship can be complex.
The simplified theory is often stronger than the full theory, meaning it claims more things are true than the full theory can strictly prove. It may also overlap with the full theory in ways that require a robust retraction mechanism. If a contradiction arises, the system must distinguish between a fundamentally flawed solution and a simple failure of a "don't worry" assumption.
Key Results and Efficiency Gains
The authors demonstrated the power of this approach through the formalization of typed partial functions. In a full theory, every function application might require the creation of five new terms and four clauses. In contrast, the simplified theory requires only a single term. Given that the cost of reasoning (specifically congruence closure) scales rapidly with the number of terms, this reduction represents a massive efficiency gain.
The simplified theory serves as an excellent predictor: if a candidate solution fails within the simplified framework, it is almost certain to fail in the full theory, allowing the search to prune unproductive branches early.
Future Directions
Future work aims to apply this "peeling the onion" approach to even more complex domains, such as aliasing (where multiple variables point to the same data). The authors suggest a default assumption of "no aliasing," with checks only triggered upon detecting potential conflicts. Additionally, refining the concept of "undefined" to distinguish between type errors, non-termination, and out-of-bounds errors could provide more granular feedback for the synthesis process.
Summary updated