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: Welcome to another episode of ResearchPod. Today, we're looking at a paper about how AI writes code—specifically, a type of code called regular expressions, or "regex."
Sam: Right. So imagine you need to search through thousands of emails to find every address that follows a specific format, or scan server logs for error codes. Rather than reading every line yourself, a developer writes a short, dense pattern of characters that tells the computer exactly what to look for. That's a regular expression. The central puzzle this paper addresses is why AI models struggle to write the complex, nested versions of these patterns that real-world developers actually need.
Alex: So the paper is asking why AI tools fall apart when the task gets complicated?
Sam: Exactly. Here's the core issue. Existing AI models treat code the way you'd treat a sentence—one word after another, left to right, flat. But real-world regexes aren't flat. They're more like a tree, with branches inside branches. There's a technical term for this: hierarchical structure. When you force something hierarchical into a flat line, the model loses track of how the pieces relate to each other, and the whole thing breaks down.
Alex: That makes sense. It's like trying to summarize a book by just listing every word in order, rather than understanding the chapters and how the plot fits together.
Sam: That's a good way to put it. So the paper proposes a new framework called RESYN, which takes a divide-and-conquer approach. Instead of trying to generate the whole regex in one go, it breaks the problem into smaller pieces, solves each piece separately, and then assembles them. Think of it like a jigsaw puzzle—you don't just grab random pieces. You group them by color or edge shape first, build the sub-sections, and then connect those sections into the final picture.
Alex: So there's a step before the actual code-writing, where the system figures out how to divide the problem?
Sam: Exactly. RESYN uses what the paper calls a "router"—a component that decides how to split the task. It can either cut the problem into sequential parts, like chapters in a book, or group similar items together to handle what are called "union" operators—basically, places where the regex says "this OR that." The router has to make smart decisions about which approach fits each situation.
Alex: Why can't the computer just try every possible way to split the problem and pick the best one?
Sam: Because the paper proves that finding the truly optimal split is what computer scientists call "NP-hard." Think of it this way: if you have a problem with ten pieces, there might be hundreds of ways to divide it. With twenty pieces, there are millions. The number of possible combinations grows so fast that even a powerful computer can't check them all in any reasonable amount of time. It's not a matter of processing speed—it's a fundamental mathematical limit.
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.