Bidirectional Regex Inference

This work is based on the Parallel Regular Expression Synthesiser (PaRESy) by Mojtaba Valizadeh and Martin Berger.

For more details on their work, refer to their paper.

Introduction

This work aims to explore new approaches for scaling Regex Inference by sacrificing minimality while preserving precision. The inference process takes as input a set of positive strings, a set of negative strings, and a cost function. It then produces a regular expression that accepts all positive strings, rejects all negative strings, and remains as close to minimal cost as possible.

In this work, a simple grammar have been used for the REs:

R ::= Φ|ε|a|R?|R*|R.R|R+R|R&R

For minimality, a cost function is defined that assigns a positive integer to each constructor in the regular expression (RE). The total cost of an RE is the sum of its constructors’ costs. This approach helps prevent overfitting and avoids producing the trivial RE that is simply the union of all positive strings.

PaRESy performs an exhaustive bottom-up search on the GPU. It represents (REs) as Characteristic Sequences (CSs) in Infix-Closure (IC) form. This work introduces a complementary top-down search that uses the same representation. Although both approaches have exponential search spaces, the bottom-up search expands the search space gradually, whereas the top-down search encounters a much more rapid combinatorial explosion. Consequently, effective heuristics are essential for guiding the top-down search.

The proposed bidirectional approach combines bottom-up and top-down search. It allows both search directions to cooperate while maintaining exactness. Although the resulting regular expression is not guaranteed to be minimal, the search is guided toward minimal solutions.

Bottom-UP

One of the proposed heuristics is the analytic heuristic, which is derived from statistics collected by a modified version of the bottom-up algorithm called bottom-up-cuda. This GPU implementation supports arbitrary IC sizes and outputs the decomposition of discovered solutions into their constituent characteristic sequences. Rather than terminating after finding the first solution, it continues searching to collect additional solutions. The primary purpose of bottom-up-cuda is to generate data that can be used to construct more effective heuristics.

You can build the bottom-up-cuda by running the following:

   cmake -S . -B build-bottom-up-cuda -DBUILD_BOTTOM_UP_CUDA=ON
   cmake --build build-bottom-up-cuda --config Release

You can run the benchmarks using the benchmark_runner_bottom_up.ipynb notebook. This notebook executes the bottom-up algorithm on all benchmark instances in a specified directory and stores the results in bottom_up_results.json. The execution is resumable, allowing you to stop the notebook at any time and continue later without losing progress.

The benchmark instances are located in the benchmarks directory. Additional benchmarks can be generated by running the benchmarks_gen.ipynb notebook.

Bidirectional

The main contribution of this work is the bidirectional project, which implements the proposed algorithm as a single-threaded CPU application. The project includes a Python script, stats_extractor.py, that processes the output of bottom-up-cuda and injects the extracted statistics into analytic_top_down_samplers.cpp, where they are used by the bidirectional search algorithm. The proposed heuristics are intentionally simple and computationally inexpensive, making them suitable for use alongside optimization techniques such as AlphaEvolve.

You can build the bidirectional by running the following:

   cmake -S . -B build-bidirectional -DBUILD_BIDIRECTIONAL=ON
   cmake --build build-bidirectional --config Release

Use the benchmark_runner.ipynb notebook to run the bidirectional algorithm on a directory of benchmark instances. The notebook also compares the generated results against those produced by bottom-up-cuda.

Heuristic Optimization

The heuristic functions can be optimized using OpenEvolve, an open-source framework inspired by AlphaEvolve that also supports MAP-Elites for quality-diversity optimization. A complete OpenEvolve configuration is already included in this repository.

An OpenEvolve configuration is already provided. To begin the optimization process, first clone the repository:

cd "Open Evolve"
git clone https://github.com/algorithmicsuperintelligence/openevolve.git
mv openevolve/.git .
rm -rf openevolve
git reset --hard HEAD

Next, copy the required project files into the OpenEvolve workspace:

mkdir -p REI/code/

cp ../CMakeLists.txt REI/code/
cp -r ../bidirectional REI/code/
cp -r ../shared REI/code/

cp ../bottom_up_results.json REI/

cp -r ../benchmarks/ REI/

Finally, configure your LLM provider by specifying the API key and model, then launch the optimization by running:

OpenEvolve/REI/start_evolution.py

The evolution process can be customized by editing the following files:

• OpenEvolve/REI/start_evolution.py – Configure the optimization process, including the prompt, number of iterations, API key, model, and other evolution parameters.
• OpenEvolve/REI/evaluator.py – Define the evaluation function. By default, candidate heuristics are rewarded for successfully solving benchmark instances, producing solutions close to minimal, minimizing the explored search space, and performing well on more difficult benchmarks (larger IC sizes).
• OpenEvolve/REI/code_to_query.py – Specify which parts of the codebase are exposed to the LLM and are eligible for evolution.