ReSyn: A Generalized Recursive Regular Expression Synthesis Framework

## The Problem: Real-World Regexes Break Existing Synthesis Tools

Programming-by-Example (PBE) systems can automatically generate regular expressions from input-output examples, but they consistently fail on real-world regex patterns. The gap exists because standard benchmarks use artificially simple regexes with shallow nesting and minimal union operations (the `|` operator for alternatives). When these systems encounter actual user regexes—which feature deep nesting, frequent unions, and intricate combinations—accuracy plummets. Existing synthesizers trained on toy problems simply don't generalize.

## How ReSyn Works: Recursive Decomposition

The authors' core insight is to break hard synthesis problems into easier pieces. ReSyn uses a divide-and-conquer strategy: instead of trying to synthesize one complex regex from scratch, it recursively decomposes the problem into sub-problems that are individually solvable, then combines the solutions back together.

The framework is synthesizer-agnostic, meaning it works as a wrapper around any existing regex synthesis tool. You feed it examples, the framework figures out where to split the problem, routes chunks to whatever base synthesizer you're using, and stitches results together—all automatically. This is powerful because improvements in the framework benefit all downstream synthesizers without requiring them to change.

## Set2Regex: A Purpose-Built Neural Synthesizer

Alongside the decomposition framework, the authors introduce Set2Regex, a neural-based synthesizer designed specifically for the regex domain. A key insight is that the order of examples shouldn't matter—if a regex matches examples {A, B, C}, it equally matches {C, A, B}. This *permutation invariance* is a structural property that standard sequence models (like transformers trained left-to-right) fail to capture naturally.

Set2Regex incorporates this invariance directly into its architecture, using parameter-efficient design to keep the model compact while handling examples as unordered sets. This makes it sample-efficient and interpretable compared to generic neural synthesizers.

## Why It Matters

The results demonstrate substantial improvements. ReSyn applied to existing synthesizers boosts their accuracy across benchmarks, and when combined with Set2Regex on real-world regex datasets, it achieves new state-of-the-art performance. The framework is practical: it's synthesizer-agnostic (so it applies broadly), code and models are open-sourced, and it scales to the structural complexity where prior systems failed.

The contribution is two-fold: a general meta-strategy (decomposition) that any synthesizer can leverage, and a domain-aware neural model (Set2Regex) that respects regex-specific structure. Together, they address a real bottleneck in automated regex synthesis—handling the wild complexity that existing tools simply cannot tackle.