# InfeRE: Step-by-Step Regex Generation via Chain of Inference

arXiv: https://arxiv.org/abs/2308.04041 · HTML: https://mlsanity.com/paper/2308.04041/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 38 references that are in the map.
- First posted on arXiv 8 Aug 2023.

## Builds on (most cited first, 21 of 21)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [DIN-SQL: Decomposed In-Context Learning of Text-to-SQL with Self-Correction](https://mlsanity.com/paper/2304.11015/) (2023)
- [Large Language Models Are Reasoning Teachers](https://mlsanity.com/paper/2212.10071/) (2022)
- [WT5?! Training Text-to-Text Models to Explain their Predictions](https://mlsanity.com/paper/2004.14546/) (2020)
- [Reframing Human-AI Collaboration for Generating Free-Text Explanations](https://mlsanity.com/paper/2112.08674/) (2021)
- [Rationale-Augmented Ensembles in Language Models](https://mlsanity.com/paper/2207.00747/) (2022)
- [TRANX: A Transition-based Neural Abstract Syntax Parser for Semantic Parsing and Code Generation](https://mlsanity.com/paper/1810.02720/) (2018)
- [Neural Generation of Regular Expressions from Natural Language with Minimal Domain Knowledge](https://mlsanity.com/paper/1608.03000/) (2016)
- [Optimal Neural Program Synthesis from Multimodal Specifications](https://mlsanity.com/paper/2010.01678/) (2020)
- [Multi-modal Synthesis of Regular Expressions](https://mlsanity.com/paper/1908.03316/) (2019)
- [Incorporating Domain Knowledge through Task Augmentation for Front-End JavaScript Code Generation](https://mlsanity.com/paper/2208.10091/) (2022)
- [Sketch-Driven Regular Expression Generation from Natural Language and Examples](https://mlsanity.com/paper/1908.05848/) (2019)
- [Benchmarking Multimodal Regex Synthesis with Complex Structures](https://mlsanity.com/paper/2005.00663/) (2020)
- [TransRegex: Multi-modal Regular Expression Synthesis by Generate-and-Repair](https://mlsanity.com/paper/2012.15489/) (2020)
- [Marrying up Regular Expressions with Neural Networks: A Case Study for Spoken Language Understanding](https://mlsanity.com/paper/1805.05588/) (2018)
- [The impact of lexical and grammatical processing on generating code from natural language](https://mlsanity.com/paper/2202.13972/) (2022)
- [Why Aren't Regular Expressions a Lingua Franca? An Empirical Study on the Re-use and Portability of Regular Expressions](https://mlsanity.com/paper/2105.04397/) (2021)

## Built on by (most cited first, 5 of 5)

- [Can Language Models Pretend Solvers? Logic Code Simulation with LLMs](https://mlsanity.com/paper/2403.16097/) (2024)
- [COSMosFL: Ensemble of Small Language Models for Fault Localisation](https://mlsanity.com/paper/2502.02908/) (2025)
- [Empowering AI to Generate Better AI Code: Guided Generation of Deep Learning Projects with LLMs](https://mlsanity.com/paper/2504.15080/) (2025)
- [Lost in Translation? Converting RegExes for Log Parsing into Dynatrace Pattern Language](https://mlsanity.com/paper/2506.19539/) (2025)
- [Neurosymbolic Characterization for Reliable Access Control Policy Analysis](https://mlsanity.com/paper/2510.20692/) (2025)

## Abstract (arXiv)

Automatically generating regular expressions (abbrev. regexes) from natural language description (NL2RE) has been an emerging research area. Prior studies treat regex as a linear sequence of tokens and generate the final expressions autoregressively in a single pass. They did not take into account the step-by-step internal text-matching processes behind the final results. This significantly hinders the efficacy and interpretability of regex generation by neural language models. In this paper, we propose a new paradigm called InfeRE, which decomposes the generation of regexes into chains of step-by-step inference. To enhance the robustness, we introduce a self-consistency decoding mechanism that ensembles multiple outputs sampled from different models. We evaluate InfeRE on two publicly available datasets, NL-RX-Turk and KB13, and compare the results with state-of-the-art approaches and the popular tree-based generation approach TRANX. Experimental results show that InfeRE substantially outperforms previous baselines, yielding 16.3% and 14.7% improvement in DFA@5 accuracy on two datasets, respectively. Particularly, InfeRE outperforms the popular tree-based generation approach by 18.1% and 11.3% on both datasets, respectively, in terms of DFA@5 accuracy.