PaperlayerView exact revision on arXiv

Source-linked AI summary

ReSyn: A Generalized Recursive Regular Expression Synthesis Framework

Seongmin Kim, Hyunjoon Cheon, Su-Hyeon Kim, Yo-Sub Han, Sang-Ki Ko

arXiv:2603.24624v2cs.PLcs.SE

TL;DR

Existing regex synthesizers are often evaluated on simplified benchmarks that miss the nesting and Union complexity of real-world regexes. The paper introduces ReSyn, a synthesizer-agnostic recursive decomposition framework, together with the parameter-efficient Set2Regex model. ReSyn improves synthesis on challenging benchmarks, while its combination with Set2Regex achieves the reported state-of-the-art result.

  • Problem

    Existing neural regex synthesizers are evaluated on simplified benchmarks that fail to reflect the structural complexity of real-world regexes.

  • Method

    ReSyn combines canonicalized data, a synthesizer-agnostic recursive decomposition algorithm, and Set2Regex, a 10M-parameter permutation-invariant base synthesizer.

  • Results

    ReSyn significantly improves synthesis success rates on complex benchmarks, and Set2Regex matches a 300M-parameter baseline with 30× fewer parameters.

  • Takeaways & Limitations

    Recursive decomposition adapts synthesis problem size to model capability and yields significant gains in challenging real-world scenarios.

  • Takeaways & Limitations

    Current metrics such as MCC can reward malformed regexes because negative examples may lack structural edge cases.

Abstract

from arXiv · show

Existing Programming-By-Example (PBE) systems often rely on simplified benchmarks that fail to capture the high structural complexity of real-world regexes, such as deeper nesting and frequent use of union operations. To overcome the resulting performance drop, we propose ReSyn, a synthesizer-agnostic divide-and-conquer framework that decomposes complex synthesis problem into manageable sub-problems. We also introduce Set2Regex, a parameter-efficient synthesizer capturing the permutation invariance of examples. Experimental results demonstrate that ReSyn significantly boosts accuracy across various synthesizers, and its combination with Set2Regex establishes a new state-of-the-art on challenging real-world benchmark. The complete source code, datasets, and pre-trained model checkpoints are publicly available at https://github.com/mrseongminkim/ReSyn.

1 Introduction

Existing regex-synthesis benchmarks often simplify away the nesting, AST depth, and Union usage found in real-world regexes. ReSyn addresses this mismatch with canonicalized data, a parameter-efficient Set2Regex synthesizer, and recursive learned decomposition.

  • Benchmark Gap: Neural regex synthesizers are often evaluated on simplified settings that do not reflect real-world structural complexity.These settings can restrict character classes and operators, unlike practical regexes.
  • Benchmark Gap: Real-world RegExLib regexes contain over 2× more AST nodes than simplified versions and 3.6× more than synthetic benchmarks.They also use the Union operator far more heavily than predominantly linear existing benchmarks.
  • Challenges: Complex regexes challenge enumeration solvers and Seq2Seq models because depth, hierarchy, long-range dependencies, and example-order sensitivity hinder synthesis.Existing divide-and-conquer methods also rely on rigid assumptions and lack true recursion.
  • Proposed Response: ReSyn combines regex canonicalization, Set2Regex, and a synthesizer-agnostic recursive divide-and-conquer framework.Its learned decomposition modules adaptively address complex synthesis problems.
  • Contributions: Set2Regex is a 10M-parameter model that matches a 300M-parameter baseline by using a Hierarchical Set Encoder.ReSyn further improves synthesis success rates on complex benchmarks such as RegExLib.

2 Related Work

Prior regex-synthesis methods use monolithic search, auxiliary supervision, data-level separation, or fixed structural heuristics. ReSyn instead uses a learnable router to recursively choose concatenation or union decomposition without additional supervision.

  • Example-Based and Neural Regex Synthesis: Traditional example-based methods synthesize complete regexes monolithically through exhaustive or evolutionary search, which struggles with combinatorial complexity.Divide-and-conquer methods reduce overall synthesis time by solving partial problems over example subsets.
  • Regex Decomposition: Some regex-decomposition methods depend on natural-language descriptions or externally generated sketches, limiting purely example-driven applicability.These approaches synthesize sub-regexes independently or refine initial sketches against positive examples.
  • Regex Decomposition: Earlier example-only approaches handle Union through separate-and-conquer, while later methods impose priors such as common-substring heuristics.These strategies do not provide generalized recursive decomposition across structural patterns.
  • Positioning of Our Work: ReSyn uses a learnable ROUTER to select Concatenation decomposition through SEGMENTER or Union decomposition through PARTITIONER.The framework composes results bottom-up without requiring additional supervision.

3 Proposed Method

The proposed method standardizes regex data, uses Set2Regex as a permutation-invariant base synthesizer, and recursively decomposes synthesis through learned modules. Its theoretical analysis connects concise regex construction to an NP-complete alignment problem, motivating learned approximation.

  • Data and Problem Setup: The method begins with regex canonicalization to standardize diverse expressions and reduce syntactic variation during learning.It also defines regex synthesis as finding a concise expression that accepts positives and rejects negatives.
  • Set2Regex: Set2Regex captures the permutation invariance of positive and negative examples with a hierarchical encoder-decoder architecture.Character-level and string-level processing produces contextualized embeddings and a global context for dual-attention decoding.
  • Recursive Decomposition: RESYN recursively composes partial regexes using three learnable modules: ROUTER, PARTITIONER, and SEGMENTER.It can wrap any base synthesizer and decompose through segmentation for Concatenation or partitioning for Union.
  • Recursive Decomposition: Segmentation splits each positive string into aligned segments, whereas partitioning groups similar strings into disjoint subsets for independent synthesis.The resulting partial regexes are composed bottom-up at the leaves and internal nodes.
  • Theoretical Hardness: The language expression cost equals optimal alignment cost, and optimal alignment is NP-complete, making the Concise Regex Problem NP-complete.This hardness motivates replacing combinatorial optimization with a learning-based approximation strategy.
  • Learning-Based Motivation: RESYN learns approximate alignment and decomposition patterns to navigate the search space of sub-regexes more efficiently than symbolic combinatorial search.The paper states that the approach can provide near-optimal solutions in polynomial time where traditional symbolic methods do not scale.

4 Experiments

Experiments evaluate ReSyn on benchmarks spanning increasing structural complexity and show that recursive decomposition improves synthesis, especially for deep, real-world regexes. Set2Regex provides a compact base model with competitive performance, while ablations expose the value of learned routing and structural evaluation.

  • Experimental Setup: The evaluation uses StructuredRegex, Snort, and RegExLib, with RegExLib representing the largest and structurally most complex benchmark.The suite contains 334, 352, and 1,752 instances, respectively; RegExLib includes diverse operators and deeper structures.
  • Experimental Results and Analysis: RESYN improves performance across base models and achieves its strongest gains on the complex RegExLib benchmark.With SET2REGEX, success rate reaches 68.26% (+29.33% absolute), while Semantic Accuracy reaches 41.61%.
  • Experimental Results and Analysis: Recursive RESYN remains robust as AST depth increases, whereas FOREST and SPLITREGEX degrade sharply beyond shallow patterns.Shallow splitting works for Depth ≤3, but RESYN maintains robust performance at Depth 5 and 6+.
  • Parameter Efficiency: Set2Regex uses 30× fewer parameters than PRAX while matching or exceeding its performance.It achieves 90.12% versus 85.03% on the synthetic benchmark and matches PRAX on RegExLib.
  • Comparison with Advanced Language Models: Against gpt-oss-120b, the 29.6M-parameter framework achieves higher Synthesis Success Rates and Semantic Accuracy across all benchmarks.RESYN also outperforms GPT-5 on StructuredRegex and Snort and achieves higher Semantic Accuracy on RegExLib with k = 500 beam search.
  • Case Study and Limitations: MCC can reward malformed regexes when negative examples lack structural edge cases, motivating semantic hard-negative mining.A SEGMENTER-only model obtains MCC 90.45 despite collapsing Union structure, while RESYN obtains 81.65 with structurally correct branches.
  • Ablation Study: The learned ROUTER balances synthesis success with structural integrity better than a fixed decomposition heuristic.The fixed strategy reaches 73.63% success but drops to 49.34 MCC, 9.63 below RESYN, because of over-decomposition.

5 Conclusions

The paper addresses the structural mismatch between neural regex synthesizers and real-world expressions with RESYN’s recursive decomposition strategy and SET2REGEX’s hierarchical set encoding. It argues that this approach improves synthesis on challenging structures and may generalize beyond regex synthesis.

  • Conclusions: RESYN combines data canonicalization, SET2REGEX, and recursive decomposition to address the nested structure of practical regular expressions.The framework includes a canonicalization pipeline, a hierarchical set encoder, and learnable recursive decomposition modules.
  • Conclusions: SET2REGEX models the set-based nature of PBE inputs with a hierarchical encoder and uses 30× fewer parameters than baselines.The model is described as parameter-efficient while achieving state-of-the-art efficiency.
  • Conclusions: The learnable ROUTER drives recursive decomposition, adapting problem size to model capability when non-recursive methods struggle with deep nesting.The paper states that this produces significant gains in challenging scenarios.
  • Conclusions: The authors propose divide-and-conquer synthesis as a potentially generalizable direction for program synthesis involving recursively structured target programs.This conclusion extends the proposed methodology beyond regular expressions without claiming broader empirical validation.
  • Conclusions: The framework is restricted to regular constructs and excludes non-regular features such as backreferences and look-around assertions.The dataset processing also removes expressions containing these features and non-printable ASCII characters.

B.3 Literal Anonymization

Literal anonymization abstracts longer literals into special tokens so recursive splitting emphasizes sub-expression boundaries rather than memorized textual content.

  • B.3 Literal Anonymization: The canonicalization pipeline represents regexes with an Abstract Syntax Tree containing six distinct node types.The AST serves as an intermediate representation for modular optimization.
  • B.3 Literal Anonymization: Literals of length 2 or greater are replaced with special Anonymization Tokens.The tokens are selected from non-printable ASCII ranges to avoid conflicts with regex operators and printable characters.
  • B.3 Literal Anonymization: The abstraction treats long literals as atomic blocks, reducing vocabulary size and limiting overfitting to specific keywords or character sequences.This supports the framework’s focus on structural boundaries during recursive splitting.

B.4 Serialization

RESYN serializes optimized ASTs back into concise regex strings by respecting operator precedence, compacting character classes, and simplifying repetition bounds.

  • B.4 Serialization: Serialization adds parentheses only when required by operator precedence, such as when Union occurs inside Repetition or Concatenation.Redundant parentheses are omitted to maintain brevity.
  • B.4 Serialization: Character classes are compacted using named classes, consecutive-character ranges, and individual literals when no broader compact form applies.Examples include \d, \w, [0-9 a-z], and [0-2a-c].
  • B.4 Serialization: Repetition bounds are rewritten into standard quantifiers when possible, including {0, ∞} →*, {1, ∞} →+, and {0, 1} →?.Exact fixed bounds become {n}, while other cases retain explicit {m, n} notation.
  • B.4 Serialization: RESYN begins inference from the positive and negative example sets and recursively handles nontrivial synthesis problems.A singleton positive set bypasses neural components and returns its escaped literal directly.
  • B.4 Serialization: When decomposition is needed, RESYN recursively invokes either PARTITIONER or SEGMENTER while forbidding consecutive use of the same strategy.Partitioning that produces only singleton subsets is rejected to prevent mere example enumeration.
  • B.4 Serialization: A deterministic fallback tests base character classes with repetition quantifiers and returns the first pattern consistent with the examples.The search order prioritizes narrower classes before broader classes or the wildcard to avoid over-generalization.

E.1 ROUTER

The ROUTER selects among synthesis, partitioning, and segmentation based on positive examples, enabling RESYN to recursively match decomposition strategies to regex structure.

  • E.1 ROUTER: The ROUTER is a policy network that uses positive examples to determine the decomposition strategy.It shares the Hierarchical Encoder architecture with SET2REGEX but is adapted for control logic.
  • E.1 ROUTER: The running example separates user, domain, and TLD components through segmentation before recursively applying partitioning or synthesis.This illustrates how different subsets can receive different strategies within one derivation.
  • E.1 ROUTER: The ROUTER maps a set-level context vector c to probabilities over Synthesize, Partition, and Segment actions.The policy is computed from the final context vector.
  • E.1 ROUTER: Selecting Synthesize invokes an off-the-shelf regex synthesizer, whereas Partition or Segment triggers the corresponding recursive decomposition module.The selected action determines whether the current problem is solved directly or decomposed further.
  • E.1 ROUTER: Router labels are derived from the target AST: Union maps to Partition, Concatenation maps to Segment, and other operators map to Synthesize.These labels provide supervision for learning the routing policy.

E.2 PARTITIONER

The PARTITIONER clusters positive examples by shared structural patterns, while the SEGMENTER learns character-level splits for concatenation problems. Their supervision is derived from top-level Union and Concatenation regex structures.

  • E.2 PARTITIONER: The PARTITIONER divides positive examples into disjoint subsets whose strings share structural patterns corresponding to common sub-regexes.It uses only positive examples and adapts SET2REGEX’s hierarchical encoder for clustering.
  • E.2 PARTITIONER: Unlike SET2REGEX, the PARTITIONER adds positional encodings and predicts cluster assignments autoregressively with a pointer-based decoder.Relative labels reuse prior cluster indices or introduce new indices as the input sequence is processed.
  • E.2 PARTITIONER: PARTITIONER supervision comes from Union-rooted regexes by grouping each string with the first matching Union branch and converting groups into relative labels.The first string receives cluster 0; later strings receive an existing or newly introduced cluster index.
  • SEGMENTER: The SEGMENTER finds split points for concatenation by jointly processing all examples with a standard Transformer encoder-decoder.Its design targets fine-grained character-level alignment across examples rather than independent string processing.
  • SEGMENTER: For Concatenation-rooted regexes, SEGMENTER labels each character by its corresponding sub-regex segment while conditioning on global context and earlier predictions.All strings are flattened with delimiters before autoregressive segment-index prediction.

F NP-hardness of Optimal Example Decomposition and Concise Regex Synthesis Problem

The paper formalizes concise regex synthesis and example decomposition through cost functions, then proves that optimal decomposition and concise regex inference are computationally intractable. The hardness proof connects alignment to shortest common supersequence.

  • Problem formulation: The paper uses symbol count as its regex cost because total regex length is bounded by a constant factor not exceeding 4 of the symbol count.This choice is made despite other possible criteria such as star height or minimum DFA size.
  • Problem formulation: The concise regex problem asks whether a finite sample set admits a regex or containing finite language with expression cost at most r.Expression cost counts symbols while excluding operators, and language expression cost minimizes this over regexes whose languages contain the sample set.
  • Decomposition and alignment: String decomposition cost minimizes the total lengths of reusable substrings that reconstruct every input string through non-decreasing substring mappings.The definition captures splitting examples into substrings and identifying matching groups.
  • Decomposition and alignment: For every finite language, optimal string decomposition cost equals optimal symbol-wise alignment cost.This equivalence is stated directly as cd(S) = c(S).
  • Hardness results: The optimal alignment problem is NP-complete, via a reduction from shortest common supersequence.A common supersequence induces an alignment with the same length, establishing NP-hardness.
  • Hardness results: Consequently, deciding whether decomposition cost cd(S) or concise regex cost cE(S) is at most r is NP-complete.The paper concludes that inferring a concise regex by decomposition is NP-complete.

G Detailed Dataset Construction and Example Generation

The dataset construction pipeline canonicalizes regexes, prevents structural leakage, augments training data with sub-regexes, and generates bounded positive and mutation-based negative examples.

  • Canonicalization and filtering: Regexes are canonicalized and split by AST signature so structurally equivalent training and evaluation expressions do not overlap.The separation ignores specific literals to prevent structural data leakage.
  • Canonicalization and filtering: Recursive sub-regex extraction increases the training set by about 28% by adding constituent expressions from complex regexes.For example, extraction from (R1|R2)* includes the original expression and its component sub-expressions.
  • Canonicalization and filtering: Filtering excludes regexes longer than 110 characters or with top-level Union operators exceeding 10 branches, followed by a 9:1 structurally disjoint train-validation split.The split preserves AST-signature separation.
  • Example generation: Each regex receives up to 10 positive examples, requires at least 2, and uses branch-aware sampling for Union expressions.Unbounded repetitions are capped at 20 during generation, with a 60second timeout per regex.
  • Example generation: Negative examples are generated by applying random insertion, deletion, and substitution mutations to positive examples.

I Detailed Training Configurations

The implementation uses shared neural dimensions and specialized training coverage for each ReSyn module, with AdamW-based optimization and a fallback synthesis procedure. Baselines use a unified zero-shot prompt constrained for RE2 compatibility.

  • Training coverage: SET2REGEX and ROUTER train on the full dataset, while PARTITIONER and SEGMENTER train only on Union- and Concatenation-rooted instances, respectively.All models use hidden size 256 with 8 attention heads.
  • Architecture and hardware: The character and string encoders have 2 layers, while SEGMENTER uses a 4-layer encoder-decoder, trained on a four-GPU RTX A6000 server.
  • Baselines: Both gpt-oss-120b and GPT-5 baselines use one zero-shot prompt template with strict constraints for compatibility with google-re2.
  • Optimization: All modules use AdamW with batch size 64, learning rate 5 × 10−4, warmup, cosine annealing, gradient clipping, and early stopping.Training runs for up to 100 epochs with patience 10 based on validation loss.
  • Optimization: NLL trains every module, with class weighting applied to ROUTER to mitigate decomposition-strategy label imbalance.
  • Recursive synthesis: RESYN recursively synthesizes from the example set, checks consistency, and returns failure when synthesis or validation fails.Singleton positive sets are handled by returning an escaped literal, except for the empty string.
Loading 2603.24624v2…