Seongmin Kim, Hyunjoon Cheon, Su-Hyeon Kim, Yo-Sub Han, Sang-Ki Ko
5 min
Abstract
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.
Alex: So the AI has to make an educated guess rather than a guaranteed-correct choice.
Sam: Right. And that's where learning comes in. Because a perfect search is impossible, the model has to learn what the paper calls heuristics—smart shortcuts based on patterns it has seen before. It's like how an experienced chef doesn't measure every ingredient precisely; they've developed an intuition for what works. The model develops a similar intuition for how to decompose a regex problem.
Alex: And alongside RESYN, they also built a separate model?
Sam: Yes. They built a model called SET2REGEX, which handles a related but distinct challenge. When you're teaching the AI by showing it examples—say, "here are five strings that should match, and here are five that shouldn't"—a standard model might accidentally learn something about the *order* you listed those examples in, rather than the actual pattern they share. That's just noise. SET2REGEX is designed to be what the paper calls "permutation invariant," meaning it treats the examples as a collection, not a sequence. Shuffle the order, and it still reaches the same conclusion.
Alex: That's a bit like how a good detective doesn't care which witness speaks first—they're weighing the evidence, not the sequence.
Sam: That's a useful way to think about it. And because it's not wasting capacity on irrelevant ordering information, SET2REGEX is notably more compact—about thirty times smaller than comparable previous models—while still outperforming them on accuracy. The two systems, RESYN and SET2REGEX, together represent the paper's main contribution: moving away from flat, left-to-right code generation and toward an approach that actually respects the tree-like structure of the problem. The result is a system that can handle the deep, nested patterns that tend to break standard AI tools.
Alex: So the key insight isn't really about raw computing power—it's about giving the AI a better mental model of what it's building.
Sam: That's the central argument. A model that understands the shape of the problem—that a regex is a tree, not a sentence—will make fundamentally better decisions than one that's simply more powerful but still thinking in a straight line. It's a meaningful step toward making automated coding tools genuinely useful for professional-grade work.
Alex: Thanks for walking us through that. And thanks to everyone listening to ResearchPod.