Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes a novel method for employing neural networks to aid in solving an NP-hard problem. The authors use the divide-and-conquer approach to regular expression generation, by generating the regex one piece at a time. They use Recurrent Neural Network to predict which substrings should be tackled by the same sub-regular expression, and then combine multiple subregular expressions into a single regular expression.
The authors demonstrate how their proposed approach is helpful in combination with different regular expression generation tools, and demonstrate improved overall performance in all cases. In the experiments where SplitRegex algorithm is applied in combination with a fast regex generator (BF), their experiments indicate that some of the speed is getting traded off for semantic accuracy. In the experiments with the slowest regex generator (RegexGenerator++), they manage to speed up its computation time to go from timing out before producing any regexes to successfully producing regexes in 20% of the time. Finally, in the experiments with AlphaRegex they demonstrate that both success rate and the accuracy go up on all benchmark datasets.
main_review: Strengths: 
- this is a novel application for recurrent neural networks, and I am excited to see such innovative uses of neural heuristic solutions for otherwise unsolvable, hard problems
- the experiments section is solid, and presents a few different baselines and benchmark datasets, both including real, practical examples, and synthetically generated ones.
- the authors demonstrate and motivate the benefit that SplitRegex adds when applied in combination with existing regular expression generators
- the paper is well-written and is easy to read and follow

Weaknesses:
- My main concern is about the approach for generating negative strings. For example, the authors do not specify whether they make sure that their negative examples are *not* matched by their regular expression. I also have doubts whether substituting a random symbol in a string really produces a very challenging counter-example; I think this is further illustrated in the Figure 3, where the performance of the model goes up as the size of the alphabet increases - because the task gets easier. The authors have presented a "hard" negative example "aabbccc", which can be incorrectly parsed by a regular expression that is too generic, but generating this "hard" negative from positive example "aabbcc" is less likely if the size of the alphabet is larger. One thing I would probably suggest to do instead could be introducing the noise at the level of regular expression itself, and then sampling strings from the "negative or incorrect" regular expression, but this might not be a catch-all solution either, besides the fact that deciding whether two regexes are the same or not is not trivial. I definitely think that further experimentation in this area would improve the value of the paper. 

- I also have a reservation about the 3 seconds time limit, as it seems to be chosen arbitrarily. I understand that it might not be practical to experiment with a larger time limit for a really large, randomly generated dataset, but at least attempting evaluating some of the smaller datasets would be great. and I am also not convinced that it is chosen wisely from the empirical perspective, because one of the baselines does not find *any* regular expressions in that amount of time, which makes including it less valuable and less informative for the reader.

- the paper could be improved via further editing and proof-reading, some of the smaller typos I noticed: 
> "do not produce desired regexes within a give time limit." -> "a given"
> "For each regex, we randomly generate 20 positive and negative examples of length up to certain length" 
> "Recurrent network networks"
summary_of_the_review: This is a novel approach to a problem that does not have feasible exact solutions, and I think it is an interesting use of neural networks. The proposed approach is relatively light-weight and demonstrates improvement in both run-time and performance quality in most cases. It has been evaluated quite rigorously, further evaluation can improve the quality of the paper, but even as it is, the proposed approach demonstrates non-trivial improvement for real-world scenario datasets, which I believe warrants acceptance of this paper.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposed a way of synthesizing RegEx from positive and negative sample specifications. The main idea is to split the positive samples into segments, such that one can leverage any existing RegEx synthesis tool to synthesize the sub-regex out of the segments of specifications. Finally the entire RegEx is obtained via the concatenation of these sub-RegExes. The paper proposes to split the specifications using RNN, which is trained via synthetically generated data. Experiments on synthetic and some benchmark datasets show that the proposed method is able to outperform the existing counterparts in most cases.
main_review: Overall the idea is neat and simple, and the consistent improvement from the existing toolkits is appealing. I have several comments below: 

1. The modeling part seems a bit arbitrary. While I understand that this paper is a kind of proof-of-concept, the segmentation model can potentially be improved in the following ways: 
- The RNN mentioned in appendix A is unidirectional. However one may want to at least use bidirectional ones in Sec 3.2, for RNN_enc1 (or Transformers)
Ideally the component of RNN_enc2 should be order invariant (i.e., encode a set of strings, rather than a list of strings with particular order), something like DeepSet should be considered
- Ideally the predicted segmental label should be permutation invariant as well. 
- Regarding the evaluation of the segmentation model itself, one can use the optimal transport metrics, following the practice in the literature. 
I would suggest the authors investigate a bit more carefully into the literature of segmentation models, either supervised or unsupervised. 

2. Is it possible to evaluate the performance based on the ground-truth split, rather than the model predicted splits? In this way we can get to know what is the upper bound of the performance, and see how far away we are from this upper bound. 

3. The model relies on the existing synthesis tools for the sub-RegExpr synthesis, so the bottleneck would be the synthesis of the most difficult sub-expression. Imagine if the sequence is formed from a single segment and in this case the proposed model would not help in any way. I’m wondering how often this happens, or if there’s a dominant segment that takes the most amount of time, how much speed up can we get with the neural split model? 

summary_of_the_review: The paper presents a practical and neat idea for RegEx synthesis that can leverage existing synthesis tools as subroutines, based on the proposed neural-split model. However the neural splitter is not technically solid, and there can be more experimental studies for the sake of completeness and the understanding of current limitations.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a method to synthesize regular expressions by first splitting positive examples and synthesizing regexes for those and then combining these while using negative examples as an additional constraint. They perform experiments on few regex baselines and show better results in one of the two metrices.
main_review: *Strengths*
- The motivation of the work is well laid out.

*Weaknesses*
 - Lack of clarity: I found many important details from the paper missing. Some of them include:
 (i) What is L ? It is stated directly in Section 3 without defining what it is and then used consistently there after without any clarification.
 (ii) Why is there a disparity between the performance of SplitRegex in terms of the two metrics (success rate and semantic regex accuracy)? From Table 1 we can see that across all datasets, SplitRegex is better only in terms of semantic regex similarity but not the success rate. Moreover, I would have expected the combination of SplitRegex with Blue-Fringe to be better in terms of semantic similarity keeping in view that without SplitRegex, Blue-Fringe is the best framework. This disparity is worrying for me and understanding why this occurs is required to put more faith in the SplitRegex system.
(iii) There are some questionable design choices made by the authors elucidating in Section 3.1 as well as the treatment of the wildcard pattern. It seems to me that these decisions were made to fit the SplitRegex framework in particular without proper motivations justifying why these choices make sense on a system design level.
(iv) It is not clear to me why SplitRegex works better with an increase in alphabet size while other approaches have the opposite behaviour.
(v) Though the paper claims in the conclusions that their framework is " ...very effective in reducing the time complexity of regex synthesis", this has not been shown experimentally.  

-  Weak experimental results: To me, the poor performance of SplitRegex in terms of success rate is concerning ( see point (ii) above)
-  Missing related works: There are very closely related works based on the idea of divide and conquer in program synthesis that are missing from the paper. Some include:

   [1] Shrivastava, Disha, H. Larochelle and Daniel Tarlow. “Learning to Combine Per-Example Solutions for Neural Program Synthesis.” NeurIPS, 2021. They find solutions that satisfy a single example (split) and then learn to combine the solutions (combine) using a neural network.

   [2] Shraddha Barke, Hila Peleg, and Nadia Polikarpova. 2020. Just-in-time learning for bottom-up enumerative synthesis. Proc. ACM Program. Lang. 4, OOPSLA, Article 227 (November 2020), 29 pages. DOI:https://doi.org/10.1145/3428295

- Less novel: In lieu of the other works mentioned above that have already explored the idea of example splitting and then combining the solutions for neural program synthesis, the contributions of the paper seem incremental.

-  Narrow scope: It is not exactly clear to me how the approach will be used for other domains say string manipulations programs or straight-line code or programs containing data and control-flow structures. It seems the approach is catered specifically to regular expressions that make the approach extremely narrow in scope and hence less significant.

*Suggestions/Comments*
- Figure 1 and Figure 2 can be combined into a single Figure. Both have a lot of redundant information.
- Results on other values of timeout and other domains ( apart from Regex) will be useful.
summary_of_the_review: The paper has less technical novelty, weak experimental results, lack of clarity, missing related works and narrow scope in terms of applicability to other programs that are not regex. I will suggest improvement in writing in terms of clarity and a thorough evaluation across other DSLs.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies the problem of synthesizing regular expressions given positive/negative examples (no textual description). The core of the proposed method is a neural network that takes the examples and splits all of them into several parts. Then, an external search-based system is used to generate regex for each part. Finally, the regexes for the parts are concatenated into one overall regex.
The proposed system is evaluated against several baselines (the same external systems applied not to parts but to complete regexes) and is shown to bring benefits.
main_review: Overall, I think that the proposed idea is itself simple, which means it should be easy to use, and at the same time it could potentially be useful for the task. However, I have several comments/questions, which limit my understanding and make the potential impact less clear. Resolving these would greatly strengthen the paper.

1. It is not clear if the proposed approach has an upper limit on the hardness regexes it can generate. Without this understanding, the usefulness of the approach is not clear.

2. Related to the previous question, how does the complexity of the regexes in this submission compare to the regexes used in the multi-modal settings such as Ye et al. (2020) and TransRegex (Li et al., 2021)? It is possible to evaluate the proposed method on their datasets while ignoring the textual inputs? 

Benchmarking Multimodal Regex Synthesis with Complex Structures.
Xi Ye, Qiaochu Chen, Isil Dillig, and Greg Durrett. Proceedings of ACL 2020.

3. In the proposed approach, the results NeuralSplitter are final in the sense that after computing the output of the network (splits of the input examples) it cannot be changed and there is no search over these splits. It looks like an error of this stage can be fatal for the overall method. Evaluating how bad this effect is would strengthen the paper. 

4. I don't understand why the results of the Blue-Fringe baseline are evaluated so differently w.r.t. the two metrics. Such difference should be easy to see qualitatively on several examples.

5. The overall performance of the SplitRegex (from table 1) is around 60%, which is higher than the baselines, but it still means that there are lots of errors. Showing and analyzing the error cases (on top of Successful examples in Table 3) would greatly strengthen the paper.

6. I also feel like another metric is missing: the percentage of the regexes that are generated correctly in the sense that all the unseen by the generation process positive and negative examples (the ones used in semantic regex accuracy) are recognized correctly within the time limit. This metric is stricter and will indicate how many regexes are actually correctly generated.

7. It looks like none of the baselines uses a neural network. Is it actually true that no published work put positive/negative regex examples into a neural network?

8. [Clarity] I did not find a description of how numerical targets of NeuralSplitter (like 1223344) were defined. I have my guesses but am not sure.
summary_of_the_review: Overall, I think that the proposed idea is itself simple, which means it should be easy to use, and at the same time it could potentially be useful for the task. However, I have several comments/questions, which limit my understanding and make the potential impact less clear. Resolving these would greatly strengthen the paper. The issues lie at the intersection of clarity, positioning, and evaluation.
review_title: null

Meta-review: There were genuine differences of opinion here. I saw reviews of 8,6,5,5.
In these cases, I do try to check if the 8 has a really compelling argument and err on the side of accepting, but here I think both the positive and negative reviews have fair points, so I am inclined to recommend rejection here.

I think the good news is that a lot of the negative stuff was around scoping/writing/related-work, and so it should be (relatively) easy to shore up this submission into something that will get better reviews in the next conference cycle.
Decision: Reject