Metric Program Synthesis for Inverse CSG

John K. Feser, Isil Dillig, Armando Solar-LezamaarXiv 2022 · DOI · arXiv

Abstract

Program synthesis often struggles with search space explosion in domains where exact observational equivalence is rare. We present SyMetric, a framework that utilizes "metric program synthesis" to group programs by observational similarity rather than strict identity. By combining a global coarse-grained search using Approximate Finite Tree Automata with a local distance-guided repair phase, SyMetric efficiently navigates massive search spaces. Our evaluation across geometry, regular expressions, and robotics demonstrates that SyMetric significantly outperforms traditional bottom-up synthesizers and approaches the performance of specialized neural models without requiring training data.

Introduction

The core challenge in Programming-by-Example (PBE) is the exponential growth of the search space. Traditional synthesizers mitigate this using observational equivalence: if two distinct code snippets produce identical outputs for a given input, one is discarded.

However, this pruning technique fails in many high-dimensional or continuous domains, such as generating 3D models (Inverse CSG) or robotic planning. In these contexts, two programs are rarely identical; a circle shifted by a single pixel is technically "different" from the target, even if it is 99% correct. Without exact matches, synthesizers cannot prune their search trees, leading to memory exhaustion even on relatively simple problems. SyMetric addresses this by replacing strict equivalence with a flexible notion of observational similarity.

Methods

SyMetric implements a two-phase synthesis strategy designed to balance exploration and precision:

  1. Global Coarse-Grained Search: Instead of seeking an immediate perfect match, SyMetric constructs an Approximate Finite Tree Automaton (XFTA). This structure clusters programs based on a distance metric—how "close" their output is to the target. It generates new programs by combining existing ones, groups them into clusters within a specific radius ($\epsilon$), and maintains only the top $w$ (beam width) clusters closest to the goal.
  2. Local Fine-Grained Search (Repair): Once a program is identified as "close enough," the system enters a repair mode. Guided by the distance metric, it applies syntactic rewrites—such as adjusting coordinates or swapping primitives—using a hill-climbing search to achieve a perfect match with the target examples.
An example of an Inverse CSG problem, showing the input image, the hierarchical solution structure, and the resulting program text.

Evaluation and Datasets

The researchers evaluated SyMetric across three distinct domains to test its generalizability:

  • Inverse CSG (Constructive Solid Geometry): A suite of 40 2D images, including complex shapes like keys and gears.
  • Regular Expressions (Regex): 122 tasks from Stack Overflow involving string matching based on natural language descriptions.
  • Tower Building: 34 benchmarks from AI planning research where a robot arm must stack blocks to match a target configuration.

Key Insights

  • Similarity as a Pruning Tool: In high-dimensional spaces, similarity is a far more powerful pruning signal than identity. By keeping only the "center" of a cluster for expansion, SyMetric maintains a diverse beam of candidates without redundant variations.
  • Domain Agnosticism: SyMetric is a general framework. Transitioning between domains (e.g., from geometry to Regex) only requires defining a new distance metric and a set of domain-specific rewrite rules.
  • The "Magnifying" Metric: For geometry, the authors developed a distance metric that becomes more sensitive as a candidate approaches the goal, facilitating faster convergence during the repair phase.

Results and Discussion

SyMetric demonstrated robust performance across all benchmarks:

  • Inverse CSG: It solved 78% of tasks, while traditional symbolic baselines failed on nearly every instance due to memory limits.
  • Regex: It achieved a 76% success rate, outperforming the state-of-the-art tool Regel (61%).
  • Tower Building: SyMetric significantly outperformed standard symbolic methods and rivaled specialized neural synthesizers, despite requiring no training data.

Despite its success, the system faces a "gap" problem: if a necessary sub-component is initially very distant from the final goal (e.g., a large object intended for subtraction), it may be pruned prematurely. Future work may involve using deep learning to automatically learn optimized distance metrics or predict effective rewrite rules to bridge these gaps.

Summary updated

Abstract

We present a new domain-agnostic synthesis technique for generating programs from input-output examples. Our method, called metric program synthesis, relaxes the well-known observational equivalence idea (used widely in bottom-up enumerative synthesis) into a weaker notion of observational similarity, with the goal of reducing the search space that the synthesizer needs to explore. Our method clusters programs into equivalence classes based on a distance metric and constructs a version space that compactly represents "approximately correct" programs. Then, given a "close enough" program sampled from this version space, our approach uses a distance-guided repair algorithm to find a program that exactly matches the given input-output examples. We have implemented our proposed metric program synthesis technique in a tool called SyMetric and evaluate it in three different domains considered in prior work. Our evaluation shows that SyMetric outperforms other domain-agnostic synthesizers that use observational equivalence and that it achieves results competitive with domain-specific synthesizers that are either designed for or trained on those domains.
BibTeX
@misc{feser2022metric,
  author = {John K. Feser and Isil Dillig and Armando Solar-Lezama},
  title = {{Metric Program Synthesis for Inverse CSG}},
  year = {2022},
  eprint = {2206.06164},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2206.06164},
}
Figure