kleene2-5m-b16-t128)Kleene is a graph-to-sequence model that writes a simple regular expression (regex) for a deterministic finite automaton (DFA). It was built for RegexSolver, an open-source engine for set operations on regular languages, which checks every regex the model proposes against the automaton before using it.
Converting an automaton into a regex is a classic problem. The standard method, state elimination, always gives a correct result, but the regex it produces can grow exponentially with the number of states and quickly becomes unreadable. With greedy decoding, this model finds a correct regex for 48.7% of the DFAs of dfa2regex-synth-bench, and for 77% of those its regex is simpler than state elimination's, often by orders of magnitude.
This card describes release v1.1 of kleene2-5m-b16-t128, the smaller of the two Kleene 2 models. It was trained to imitate the larger one, kleene2-9m-b16-t128, with 57% of its parameters; the larger model is more accurate. Every result in this card is for greedy decoding, which generates a single regex by picking the most likely token at each step. The changelog lists the changes between releases.
| Developed by | Alexandre van Beurden |
| Model type | Graph-to-sequence transformer: a graph transformer encoder over the DFA and an autoregressive transformer decoder over the regex tokens |
| Parameters | 5,188,330 (float32) |
| Input | A minimal DFA in canonical form, with at most 16 bases (trained on DFAs of up to 16 states) |
| Output | A regex of at most 126 tokens |
| Release | v1.1, November 2026 |
| Runtime | Rust, with candle, through RegexSolver 1.2.0 or later |
| License | MIT |
| Related models | kleene2-9m-b16-t128, its teacher; kleene1-9m-b16-t128, the previous generation |
As in RegexSolver, the transitions of a DFA are labelled with bases: disjoint character ranges, of which each transition covers one or more (why this representation). The model works on bases rather than on individual characters. Its input is the DFA as a graph with one node per state and one edge per transition and base, and its output is a regex in prefix-order tokens, where each character class is a set of bases. The inputs section of config.json documents the encoding.
The encoder has 4 message-passing and 2 global attention layers, the decoder has 4 layers, and the model dimension is 192. In the name, kleene2 is the generation (input encoding, vocabulary and file format), 5m the number of parameters, b16 the maximum number of bases, and t128 the maximum number of decoder positions (126 regex tokens, plus a start and an end token). The second generation was trained from scratch on new data, and its input leaves out the characters that no transition uses, so that a* and .* are the same input for it.
The model is named after Stephen Kleene (1909–1994), the mathematician who invented regular expressions and showed that they describe exactly the languages recognized by finite automata.
Primary use. The model is meant to be run by RegexSolver, to turn automata into regexes that people can read, for example to show the result of an intersection or a difference of regexes as a regex. RegexSolver checks each regex the model proposes for equivalence with the automaton, then keeps either the model's regex or state elimination's, whichever is simpler. This model is meant for uses where a smaller model matters more than accuracy; otherwise, kleene2-9m-b16-t128 finds more correct regexes.
Out of scope.
The model runs through RegexSolver's neural-synthesis feature, and Kleene 2 models need RegexSolver 1.2.0 or later. The neural-synthesis-hub feature also lets RegexSolver download the model from the Hugging Face Hub:
use regexsolver::neural_synthesis::{Device, NeuralSynthesizer};
// From the Hub, pinned to a release (`from_hub` loads the latest one)...
let synthesizer = NeuralSynthesizer::from_hub_revision("alexvbrdn/kleene2-5m-b16-t128", "v1.1", Device::best_available())?;
// ...or from this repository's files.
let synthesizer = NeuralSynthesizer::from_files("config.json", "model.safetensors", Device::Cpu)?;
let regex = automaton.to_regex_with(&synthesizer)?;
RegexSolver determinizes and minimizes the automaton before giving it to the model. By default, it then runs a beam search of width 4 instead of greedy decoding, checks the up to 4 regexes it finds, and keeps the simplest correct one. with_beam(1) decodes greedily, which is what this card evaluates. A wider beam (with_beam) or added samples (with_candidates) find a correct regex more often, at the cost of decoding and checking more regexes.
When the model finds no correct regex, or when the DFA exceeds the model's limits, RegexSolver splits the DFA into smaller pieces and runs the model on each of them; with_decomposition(false) turns this decomposition off. GPU and faster CPU backends are available as neural-synthesis-* features.
config.json also gives the model's success rate: how often, on the benchmark's dev split, its greedy decoding is correct for DFAs of a given number of states and bases and a given complexity of state elimination's regex. RegexSolver does not run the model on an automaton, or a piece of one, whose success rate is below 5%: it goes straight to the decomposition, or to state elimination for a piece that cannot be split further. On the benchmark's dev split, this skips the model for 23% of the DFAs and loses about 0.35% of its correct greedy regexes. with_min_success changes the threshold, and 0 always runs the model.
The DFA in Figure 1 accepts the strings over a–e, g and h that end with hb or hbh.
Figure 1. The minimal DFA of the example. Accepting states have a double circle; the rejecting sink state is not drawn.
State elimination converts it into this regex:
[a-eg]*h(b(hb)*(h{2}|([a-eg]|h[ac-eg])[a-eg]*h)|([ac-eg][a-eg]*)?h)*b(hb)*h?
With greedy decoding, the model generates this one:
[a-egh]*hbh?
The first regex has a cognitive complexity of 44.0 and the second 5.0. Cognitive complexity is the readability measure that RegexSolver and the model rely on; it is defined below. The example was chosen to illustrate the model, and the evaluation shows how often it succeeds.
The model is evaluated on the dev split of dfa2regex-synth-bench (version bench-v1, evaluator 1.0.0): 80,251 synthetic minimal DFAs with 3 to 16 states and 1 to 16 bases, none of which is in the training data. The model generates one regex per DFA with greedy decoding, and the benchmark's evaluator checks it against the DFA and measures it.
Cognitive complexity is the readability measure defined by RegexSolver (implementation). It does not depend on which characters a regex uses, and is computed as follows:
1 + depth for each branch after the first;1 + depth: 0.5 for ?, * and +, 1 for {n}, 1.5 for {n,} and 2 for {m,n}. A quantified group is read one level deeper, and a quantifier containing another one costs an extra 1 + depth.Table 1. Results on the dev split of dfa2regex-synth-bench, in %, with greedy decoding. State elimination is the reference that the score is measured against; the best value of each column is in bold.
| Model | Parameters | Score | Correct | Correct and simpler |
|---|---|---|---|---|
kleene2-5m-b16-t128 v1.1 (this model) |
5.2M | 18.0 | 48.7 | 37.5 |
kleene2-9m-b16-t128 v1.1 |
9.2M | 19.8 | 52.6 | 41.1 |
kleene1-9m-b16-t128 v1.3 |
9.2M | 16.3 | 45.0 | 34.5 |
| State elimination | – | 0.0 | 100.0 | 0.0 |
The 95% confidence intervals are about ±0.2 points for the score and ±0.35 points for the other two columns. The score counts only the model's regex for the whole DFA; decomposition, which RegexSolver enables by default, can make the output simpler still.
Figure 2. Share of correct regexes by (a) number of states and (b) number of bases, for the three Kleene models. The benchmark has no DFA with 1 or 2 states.
kleene2-5m-b16-t128 is more accurate than Kleene 1 v1.3 on DFAs with 3 or 4 states and with 8 to 16 states, and up to 1.2 points less accurate with 5 to 7. Its lead is largest on DFAs with many bases: with 13 to 16 bases, it is correct for 18.7% of the DFAs, against 6.4% for Kleene 1 v1.3. With 2 to 8 bases, it is less accurate than Kleene 1 v1.3, by up to 6.5 points.
Figure 3. Share of correct regexes (%) for each number of states and of bases. Hatched cells have fewer than 20 DFAs; blank cells are sizes the benchmark has no DFA of (DFAs with a single base exist only from 10 states).
Correctness falls as the number of bases grows. DFAs with 5 to 9 states and 13 bases or more are the hardest: the model solves 2% to 12% of them, against 20% to 26% for those with 11 to 16 states. With 3 states, it is correct for 85% to 97% of the DFAs with up to 15 bases.
Figure 4. The model's regex against state elimination's, on the 39,052 DFAs it solves. (a) The model's complexity as a share of state elimination's, DFA by DFA. (b) The share of DFAs for which the model's regex is simpler, as simple or more complex, by complexity of state elimination's regex (the number of DFAs in each bin is in parentheses).
On the DFAs it solves, the model's regex is simpler than state elimination's for 77.0%, as simple for 21.6% and more complex for 1.5%. Its median complexity there is 14.5, against 32.5 for state elimination, and the gap widens as state elimination's regex grows. Nearly all the regexes that are only as simple are for DFAs whose state elimination regex has a complexity under 100, where there is little to simplify, and every regex more complex than state elimination's is for a DFA whose state elimination regex has a complexity of 100 or less. RegexSolver keeps state elimination's regex in those cases.
The benchmark's hidden test split (80,207 DFAs) is used only to check that dev results hold. On it, the model scores 17.8% and is correct for 48.6%, which passes the benchmark's check that the score does not drop by more than the 95% interval of the difference.
The training code and dataset are not published.
Data. The dataset contains 2,901,131 synthetic minimal DFAs with up to 16 states and 16 bases: 2,817,411 for training, 19,213 for validation and 64,507 held out. A first generation of 2,000,000 DFAs came from random regexes (51%), set operations (26%), DFAs built to a given number of states and bases (20%) and the enumeration of small DFAs (3%), deduplicated and balanced over the number of states, bases and accepting states. It was then completed with 872,642 DFAs from a second generation, for the sizes the first one covered poorly, and with 29,321 DFAs that had no target until a model found one. Each DFA's target is the simplest regex found for it within 126 tokens, by cognitive complexity. The targets came from the generation itself and from regexes found by Kleene 1 v1.3 and by Kleene 2 models, as described below. No DFA of dfa2regex-synth-bench is in the dataset.
Distillation. The model is trained with cross-entropy on the target tokens, using AdamW (Loshchilov and Hutter, 2019) with a batch size of 256, and a peak learning rate of 4e-4 when training from scratch and of 1.5e-4 when fine-tuning. Its targets come from kleene2-9m-b16-t128, the teacher: wherever the teacher's correct regex for a training DFA is as simple as the target or simpler, it becomes the target. The model is first trained from scratch on the targets of an earlier version of the teacher, then fine-tuned in two rounds on those of the teacher's release v1.0, and in three more rounds, each starting from the previous one, on those of its release v1.1. Every new target is checked against its DFA.
Reinforcement learning. After each of these stages, the model is fine-tuned with group relative policy optimization (GRPO, Shao et al., 2024), with rewards computed by checking each regex rather than by a learned reward model. For each training DFA, it samples 8 regexes; a wrong regex gets a reward of 0, and a correct one 1 plus its relative complexity gain over the simplest regex known for the DFA, adjusted by up to 0.5 according to how it compares with the other correct samples of its group. The model learns to favour the regexes that score above their group's average, with a KL penalty keeping it close to its starting point.
Compute. About 8 hours on a single NVIDIA RTX PRO 4000 Blackwell GPU for training, the teacher's targets and evaluation, on top of the teacher's own training, and about 11 hours on a laptop with an Intel Core Ultra 7 258V CPU to generate the data. Release v1.1 added about 6.5 hours on the same GPU for the targets of the teacher's release v1.1, training and evaluation.
Results are measured on dfa2regex-synth-bench bench-v1, dev split, with greedy decoding.
kleene2-9m-b16-t128 v1.1, in three more supervised rounds, then GRPO. Score 18.0%, correctness 48.7%. On the DFAs that both v1.1 and v1.0 solve, v1.1's regex is simpler for 2,093 and v1.0's for 570.kleene2-9m-b16-t128 v1.0. Score 17.0%, correctness 46.8%.@misc{vanbeurden2026kleene2,
author = {van Beurden, Alexandre},
title = {Kleene 2: a graph-to-sequence model for simple regular expressions from DFAs},
year = {2026},
howpublished = {\url{https://huggingface.co/alexvbrdn/kleene2-5m-b16-t128}}
}
alexvbrdn/kleene2-9m-b16-t128