Synthesizing Algorithms with Performance Constraints

Robert McCartneyAAAI 1987

Introduction

Presented at AAAI-87, MEDUSA is an experimental system designed to automate the creation of algorithms. While automated programming systems often struggle with the "combinatorial explosion" of searching through infinite possible code combinations, MEDUSA utilizes performance requirements—specifically asymptotic time complexity—as a primary filter to prune the search space effectively.

The Challenge of Algorithm Synthesis

Algorithm synthesis involves transforming a functional specification ("what to do") into an efficient implementation ("how to do it"). This process is notoriously difficult, traditionally requiring significant domain-specific knowledge and intuitive leaps. Previous systems were often either too general, leading to exhaustive searches, or required heavy user guidance. MEDUSA addresses this by focusing on planar intersection problems in computational geometry and using Big-Oh complexity as a constraint to maintain tractability.

Methodology: Cost-Constrained Refinement

MEDUSA employs a top-down refinement process, treating synthesis as a grammar generation problem where terminal nodes are known primitive algorithms. The system utilizes four primary subtask generation methods:

  1. Skeletal Algorithms: Templates for general paradigms like binary divide-and-conquer or mergesort.
  2. Logical Transformations: Using domain knowledge to simplify tasks (e.g., equating containment to subset and boundary intersection checks).
  3. Case Decomposition: Breaking a problem into disjoint scenarios, such as whether boundaries intersect or not.
  4. Dual Transforms: Mapping problems into a different mathematical space (e.g., points to lines) to find more efficient solutions.
Figure 1: Case decomposition for the 'A and B intersect?' problem, illustrating how high-level geometric queries are broken down into primitive subtasks.

A critical feature of MEDUSA is Cost Pruning. Every task is assigned a Big-Oh budget. If a proposed decomposition exceeds this budget, it is immediately discarded. Furthermore, the system uses a "Typical Cost" heuristic, favoring algorithms whose average performance matches the constraint, assuming that more complex templates are often more robust or easier to refine.

Evaluation and Results

MEDUSA was evaluated against a benchmark suite of 19 computational geometry problems. The system successfully synthesized all 19 algorithms without human intervention, deriving non-trivial solutions such as $O(N \log N)$ for arbitrary rectangle intersection and $O(N)$ for convex polygon intersection.

Table 1: A list of geometric tasks and the performance constraints synthesized by MEDUSA.

Conclusion and Future Work

The primary insight from MEDUSA is that performance constraints make synthesis easier by significantly reducing the search space. By treating complexity as a search filter rather than just a final goal, the system avoids the search-space explosion that plagued earlier synthesis attempts. However, limitations remain, such as the high computational cost of exploring dual transforms and the sensitivity of the system to manually estimated "typical costs." Future work aims to improve the ordering of dependent subtasks and refine comparison metrics for more complex geometric scenarios.

Summary updated

BibTeX
@inproceedings{mccartney1987synthesizing,
  author = {Robert McCartney},
  title = {{Synthesizing Algorithms with Performance Constraints}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1987},
}
Figure