Introduction
When describing problems to an AI, human users often include superfluous details based on their own conceptualization rather than the core requirements of the task. For instance, a user might specify a sequence of moves for a puzzle when the order of those moves is irrelevant to the final outcome. Standard solvers often waste significant computational resources exploring these unnecessary permutations. This paper introduces STRATA, a formal framework designed to automatically simplify problem specifications through reformulation, transforming behavioral equivalences into identities to reduce search spaces.
The STRATA Framework
The STRATA system operates through a three-stage pipeline: Abstraction, Design, and Implementation. The primary focus of this research is the Abstraction phase, where a concrete user specification is lifted into a more efficient, abstract representation.
In this model, the system moves from a detailed "User Specification" to an "Abstract Specification." This abstraction allows the subsequent "Design" phase to produce an "Abstract Algorithm" which is finally refined into a "Concrete Algorithm" for execution. By simplifying the problem at the highest level, the complexity of the search for a solution is drastically reduced.
Core Mechanisms of Abstraction
STRATA employs two primary methods to achieve problem simplification:
- Behavioral Abstraction: This method utilizes a library of predefined implementation maps. If the system can prove that a problem's output remains invariant under certain operations—such as reordering elements in a list—it can map the problem from a complex theory (e.g., Lists) to a simpler one (e.g., Bags or multisets).
- Behavioral Congruence: This is the paper's central technical contribution. When no predefined map exists, STRATA generates a new abstract theory by identifying objects that behave identically relative to the input/output relation. It then forces these objects to be equal in a new representation.
To ensure these abstractions remain logically consistent, the system uses Protection to remove functions that would distinguish between equivalent objects (like removing head and tail when moving from lists to bags) and Splitting to isolate data types used for conflicting purposes.
The Abstraction Lattice
A key insight of this work is that the space of possible problem reformulations can be modeled as a semi-lattice. The original problem formulation sits at the bottom, containing the most detail, while the most abstract problem class—which considers only the final I/O result—sits at the top.
By navigating this lattice, STRATA can find an optimal level of abstraction that preserves the problem's core constraints while discarding irrelevant details. This process effectively turns an equivalence relation ("these two things are close enough") into a formal equality ("these two things are the same").
Evaluation and Results
The framework was evaluated using the Arrow Puzzle, a state-space search problem. STRATA successfully reformulated the puzzle from an exponential search over sequences of operators to a search over bags, then sets, and finally a simple bit-wise XOR calculation. This demonstrates a formal path from high-level conceptualization to highly efficient, low-level automatic programming.
Limitations and Future Work
While the formal framework is robust, several challenges remain. The search for the "best" abstraction within the lattice can be infinite without proper heuristics. Additionally, the system relies heavily on the RAINBOW inference system to prove behavioral equivalence theorems, which is a computationally intensive task. At the time of publication, STRATA was in the implementation phase, with future work focused on scaling these automated proofs and refining the search through the abstraction space.
Summary updated