{"id":"95f1c701-8022-4d74-bcb7-bb7d40b1c300","arxiv_id":"1908.03316","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Regel parses English descriptions into hierarchical sketches that guide a programming-by-example engine, solving 80% of 322 regex benchmarks versus 43% for language-only and 26% for example-only baselines.","lead":"A new tool called Regel writes regular expressions by combining a plain-English description with a few example strings, outperforming tools that use only one of those. In tests on 322 regex-writing tasks, Regel found the intended answer 80% of the time, versus 43% for a language-only tool and 26% for an example-only tool.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The 80% figure is supported only by an oracle that supplies perfectly targeted counterexamples; the paper never tests whether real users can produce those examples, so the central accuracy claim is conditional.","rationale":"The paper is careful in its formal parts: Theorems 5.4, 5.7, and A.3 state correctness of the pruning and SMT-based constant inference, and the empirical design includes two datasets, ablations, an AlphaRegex comparison, and a user study. Those are real strengths. The vulnerability is at the boundary between the headline evaluation and the user model it presupposes. Section 9.1's protocol supplies perfectly targeted counterexamples; the user study only shows that people can use Regel to finish tasks, not that they can generate such counterexamples on demand. Because the claimed advantage over single-modality baselines is quantified through this protocol, the 80% number is conditional on the oracle. The proposed test would settle the point by recomputing the headline under feedback that is actually available to users. This is the same load-bearing concern the reader identified, so the verdict stays CONDITIONAL.","tokens_in":30553,"tokens_out":15145,"duration_ms":179842,"concrete_test":"Re-run the Section 9.1 evaluation replacing the oracle with a non-oracle feedback model: after a failed synthesis, the next two examples must be drawn only from the user-visible task materials (the original StackOverflow thread text and examples, or the DeepRegex annotations), with no example chosen because an equivalence check showed it rules out the returned regex. Also report the combined iteration-0 accuracy from Figure 14. If the resulting iteration-4 accuracy is materially below the reported 259/322, the abstract should say '80% with oracle-provided counterexamples,' not '80% accuracy.'","verdict_should_be":"UNCHANGED","load_bearing_attack":"The abstract's headline is the 80%/43%/26% comparison, and the number that anchors it is the StackOverflow result of 74/122 plus the DeepRegex result of 185/200. For that 80% to be a user-facing accuracy, the interactive loop of Section 9.1 must be executable by a real user: after Regel returns an incorrect regex, the user must provide two examples 'guaranteed to rule out the returned incorrect regex.' That is an oracle assumption, not a user capability. The paper's user study does not test it: it compares final task success with and without Regel, but it does not measure whether participants could, on demand, produce counterexamples that are guaranteed to discriminate the returned regex from the intended one, and Section 9.3 explicitly disclaims that the study is not an in-the-wild evaluation. The magnitude matters. On the DeepRegex set, Regel already solves 151/200 (75.5%) from the initial examples and reaches 185/200 only after oracle iterations; the combined iteration-0 accuracy over all 322 benchmarks is not reported. If the extra successes depend on oracle-selected discriminating strings, the 80% claim is not a claim about what users can achieve. The qualitative conclusion that adding a sketch helps is well supported; the precise accuracy number is not.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents Regel, a tool that synthesizes regular expressions from a combination of natural-language descriptions and positive/negative examples. The natural-language input is parsed into a hierarchical sketch (h-sketch) by a SEMPRE-based semantic parser, and a programming-by-example engine then searches for a concrete regex that completes the sketch and satisfies the examples. The search is made practical by sketch-guided over- and under-approximations for pruning, and by representing repetition counts as symbolic integers whose feasible ranges are constrained via an SMT encoding over string lengths. The paper evaluates Regel on 200 adapted DeepRegex benchmarks and 122 StackOverflow benchmarks, reporting that Regel solves 80% of the combined 322 benchmarks, versus 43% for DeepRegex and 26% for a PBE-only baseline. It also reports an ablation showing the PBE engine is substantially faster than an adapted AlphaRegex, and a 20-participant user study in which participants complete tasks more often with Regel than without it.","tokens_in":30799,"tokens_out":8001,"duration_ms":85148,"significance":"If the reported results hold, this is a useful contribution to program synthesis from weak specifications: the hierarchical-sketch idea is natural, the combination of semantic parsing with PBE is well motivated, and the appendices provide detailed correctness proofs for the approximation and SMT-encoding procedures. The evaluation is unusually careful in several respects: the authors disclose how the DeepRegex data set was filtered and adapted, they provide ablations isolating the two pruning mechanisms, and they include a user study with explicit disclaimers about its scope. The qualitative conclusion that adding a natural-language sketch to a PBE engine improves both success rate and speed is credible and well supported by the iteration-0 results on the DeepRegex set. However, the headline 80% accuracy number is not a user-attainable accuracy as stated, because it depends on an oracle that supplies perfectly targeted counterexamples over up to four interaction rounds; this is the central load-bearing issue for the paper's main quantitative claim.","major_comments":[{"comment":"The headline accuracy of 80% is achieved only after up to four rounds in which the evaluator provides 'two additional examples that are guaranteed to rule out the returned incorrect regex' (Section 9.1). Producing such examples requires knowing the intended regex, so this is an oracle simulation rather than a realistic user-facing accuracy. On the DeepRegex set, Regel already solves 151/200 at iteration 0 and reaches 185/200 only after oracle iterations; the combined iteration-0 accuracy over all 322 benchmarks is not reported in the text. The user study (Section 9.3 and Appendix F) does not close this gap: participants are allowed to enter any two new examples, and the study records only final task success, not whether participants could produce counterexamples that are guaranteed to discriminate the synthesized regex from the intended one. The abstract and Result 1 should report the iteration-0 accuracy as the primary user-facing number, or the paper should provide direct evidence about users' ability to supply discriminating counterexamples.","section":"Section 9.1, Result 1, and Abstract"},{"comment":"The DeepRegex comparison is performed on a substantially adapted and filtered subset of the original DeepRegex data: benchmarks corresponding to the empty language were removed, examples inconsistent with the target regex were discarded, and only 200 of 800 annotated tasks were retained after filtering. This is a defensible way to construct a multi-modal benchmark, but it changes the difficulty and the input format relative to the original DeepRegex data set. The statement that 'DeepRegex solves only 43%' should be explicitly qualified as applying to this reconstructed, filtered set; otherwise a reader may reasonably interpret the number as a statement about DeepRegex on the original data set, where the task and inputs are different.","section":"Section 8 and Appendix C"},{"comment":"The semantic-parser training labels are derived from the target regexes. For the DeepRegex set, the h-sketches used for training are generated by replacing the root operator of the target regex with a hole; for the StackOverflow set, the h-sketches are manually constructed by the authors, who knew the target regex while reading each English description. This is not circular in the narrow sense that test-time sketches are produced by the parser, but it means the natural-language component is trained and evaluated on sketches that encode ground-truth structural information. The paper should discuss the sensitivity of the reported accuracy to the quality of the parser supervision; at minimum, an experiment with coarser or automatically derived sketches for the StackOverflow set would help establish that the multi-modal advantage is not an artifact of manually crafted sketches.","section":"Appendix E and Section 6.3"}],"minor_comments":[{"comment":"The abstract and conclusion should state that the 80% figure is obtained after up to four interaction rounds under the oracle-counterexample protocol; the current wording presents it as a single-shot accuracy.","section":"Abstract and Conclusion"},{"comment":"The combined iteration-0 counts for Regel and the baselines should be reported in the text; currently only the StackOverflow final value (74/122) is stated, and the initial values are only visible graphically.","section":"Figure 14"},{"comment":"The '10x faster' claim is based on 'the first 1000 sketches that can be solved by all variants'; this is a selective workload, and reporting total solved versus time or area under the curve would make the comparison more robust.","section":"Section 9.2, Result 2"},{"comment":"The paper cites SemRegex [50] as a recent NL-only regex synthesizer but does not compare against it, despite calling DeepRegex 'state-of-the-art'; the characterization should be qualified.","section":"Related Work and Section 9.1"},{"comment":"The proof of Theorem A.3 refers to 'Theorem A' where it presumably means the correctness theorem for Encode (Theorem A.4); the cross-reference should be fixed.","section":"Appendix A, Theorem A.3"},{"comment":"Bounding every symbolic integer by MAX, the length of the longest example, is only complete when the repeated sub-regex cannot match the empty string; this assumption should be stated explicitly.","section":"Section 5.2, footnote 5"},{"comment":"The overview uses constrained holes written as □{S} without the depth parameter d that is introduced formally in Figure 5; aligning the notation early would reduce confusion.","section":"Section 2 and Figure 5"}],"recommendation":"major_revision","confidential_remarks":"The paper makes a strong systems contribution, and the central algorithmic ideas appear sound. However, the 80% accuracy number is likely to be quoted without its interaction-oracle qualifier, so I recommend that the editor require the authors to reframe the headline claim and to add a direct treatment of the oracle assumption. Also, reference [10] appears to be a self-citation to this same arXiv paper; this should be checked before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know about this paper. First, the core idea is real: parsing English into a hierarchical sketch and using that sketch to guide a regex PBE engine is a genuine step beyond NL-only or example-only synthesis, and the paper makes a convincing case that the two modalities complement each other. Second, the headline 80% is conditional in a way the abstract does not fully own: it is measured after up to four rounds of oracle-provided counterexamples that are guaranteed to rule out the previously returned regex. That is a much stronger assumption about user behavior than anything the user study tests.\n\nWhat is actually good: the h-sketch representation is a nice bridge between semantic parsing and enumerative synthesis; the sketch-guided over- and under-approximation prunes more precisely than AlphaRegex's version; and the SMT-based handling of symbolic integers in Repeat constructs is clever. The ablation shows both techniques pull their weight, and the order-of-magnitude speedup over an adapted AlphaRegex is believable. The hand-written proofs in Appendix A cover the main correctness claims. On the empirical side, the evaluation spans two different datasets and a user study, and the user study does show a large effect (73% vs 28% success), even if the participant pool is small and skewed toward CS students.\n\nThe soft spots are real but not disqualifying. The 80% figure is the obvious one: on DeepRegex, Regel already solves 151/200 from the initial examples, and reaches 185/200 only after oracle iterations; the StackOverflow iteration-0 number is not reported at all, so the combined 80% is entirely a post-oracle number. The paper itself comes close to admitting this in Section 9.1, and the user study does not measure whether real users can produce counterexamples that discriminate the returned regex from the intended one. Also, the data is filtered (empty-language regexes removed from DeepRegex) and partly manually annotated (StackOverflow), and no artifact is released, which makes independent verification harder. The training sketches for DeepRegex are derived from the target regex's root operator, but on a separate training split, so this is a concern about tailoring, not circularity.\n\nNone of this sinks the qualitative conclusion that a hierarchical sketch helps a lot. It does mean the quantitative headline should be reported with iteration counts and, ideally, with a user study that isolates counterexample quality. I would send this to referees: the synthesis engine is a real contribution and the weaknesses are addressable. If I were reviewing, I would ask for iteration-by-iteration accuracy on both datasets, a clear statement about the oracle assumption, and a serious try at releasing code and data.","headline":"A solid synthesis paper with a genuinely new multi-modal idea, but the headline 80% accuracy number is an oracle-in-the-loop figure, not a one-shot user number.","tokens_in":31333,"tokens_out":2210,"would_cite":true,"duration_ms":27481,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Combining English with examples solves 80% of regex benchmarks, the paper reports.","keywords":["regular expression synthesis","programming by example","natural language understanding","hierarchical sketches","program synthesis","semantic parsing","SMT-based pruning","multi-modal specification"],"falsifier":"A controlled experiment in which human participants, not an oracle, provide the next examples after each incorrect regex on the same 322 benchmarks would settle whether the 80% accuracy survives realistic feedback; if the accuracy collapses toward the example-only baseline, the multimodal advantage depends on perfect counterexample selection rather than on the sketch mechanism itself.","tokens_in":30356,"feed_emoji":"🔤","tokens_out":4422,"duration_ms":45481,"temperature":0.7,"pith_summary":"The paper proposes Regel, a synthesizer that builds regular expressions from both an English description and positive/negative examples. It argues the two modalities complement each other: natural language alone is ambiguous, while examples alone underdetermine the intended pattern. The central mechanism parses the English text into a hierarchical sketch, a regex skeleton with constrained holes, and feeds that sketch to a programming-by-example engine that searches for a completion consistent with the examples. On 322 benchmarks, Regel solves 80% within four interaction rounds, compared with 43% for a language-only baseline and 26% for an example-only baseline. The paper also reports that sketch-guided pruning and symbolic-integer reasoning make its search roughly an order of magnitude faster than an adapted prior example-based synthesizer.","feed_headline":"Examples plus English crack 80% of regex tasks","feed_subtitle":"Tool Regel beats language-only and example-only baselines on 322 real and adapted benchmarks.","key_machinery":"The load-bearing object is the hierarchical sketch, or h-sketch: a regex abstract syntax tree in which leaves may be constrained holes, written $\\square_d{S}$, meaning the unknown sub-regex has depth at most $d$ and must contain at least one of the hinted components in $S$ as a leaf. The h-sketch guides top-down enumerative search over partial regexes, and for each partial regex the engine computes over- and under-approximations from the sketch's hints to reject infeasible branches without losing completeness. Repeat bounds are represented as symbolic integers, encoded into an SMT formula over string lengths, and used to prune families of regexes at once rather than enumerating every constant. The sketch itself is produced from English by a semantic parser with a learned ranking over candidate derivations.","core_discovery":"The paper's central claim is that a natural-language-derived hierarchical sketch is the decisive ingredient for regex synthesis: it lets a programming-by-example engine prioritize which partial regexes to expand and which to prune, and it supports a symbolic representation of repeat bounds that the engine refines with an SMT solver. The headline empirical claim is that, with up to four rounds of counterexample feedback, Regel synthesizes the intended regex for 80% of 322 benchmarks, whereas the English-only baseline succeeds on 43% and the example-only baseline on 26%. The paper also claims that both pruning ideas contribute measurably to speed, and that in a 20-participant user study users solved 73.3% of tasks with Regel versus 28.3% without it.","pith_inferences":["The paper's headline accuracy depends on an oracle that, after every wrong regex, supplies two new examples guaranteed to rule out exactly that regex; real users cannot reliably produce such perfectly targeted counterexamples without already knowing the target pattern, so interactive accuracy in practice may be lower.","The same h-sketch-plus-PBE recipe could transfer to other synthesis domains where English gives structural hints but examples pin down details, such as data transformation or query synthesis.","A testable extension would replace the oracle with human-generated counterexamples on the same 322 benchmarks and measure how quickly the accuracy curve approaches 80%; the paper's user study measures task success, not this curve.","The failure analysis suggests the main ceiling is not search but sketch quality: failures cluster on high-level concepts like dates and ranges that the grammar does not know, so enriching the grammar with domain concepts is a plausible next step."],"forward_implications":["If the central claim holds, a multimodal specification is substantially more effective for regex synthesis than either English alone or examples alone, with accuracy roughly doubling over the language-only baseline.","The sketch-guided pruning and symbolic-integer reasoning make the search fast enough for interactive use, so a user can receive candidate regexes within seconds and refine them with new examples.","The synthesis method is agnostic to the particular NLP technique: any component that emits hierarchical sketches could replace the semantic parser without changing the PBE engine.","On the harder StackOverflow benchmark subset, Regel reaches 60.7% accuracy where the language-only baseline reaches 2.4%, suggesting the multimodal advantage grows with task difficulty.","The user-study result, if it transfers, implies that tool assistance roughly doubles the chance that a non-expert finishes a regex task correctly within a time budget."],"supporting_citations":[{"why":"Supplies the English-only baseline and the adapted 200-benchmark dataset used for evaluation.","marker":"[30]"},{"why":"Provides the earlier example-based regex synthesizer whose over- and under-approximation pruning is adapted and then outperformed.","marker":"[27]"},{"why":"Provides the semantic-parsing framework on which the sketch generator is built.","marker":"[7]"},{"why":"Supplies the SMT solver used to prune infeasible symbolic-integer assignments.","marker":"[12]"},{"why":"Provides the automaton library used for regex membership and equivalence checking in the implementation.","marker":"[33]"},{"why":"Defines the sketching approach whose constraint-solving role is contrasted with Regel's use of SMT for pruning rather than direct solving.","marker":"[28]"},{"why":"Represents the programming-by-example string-processing tradition that the example-based component builds on.","marker":"[18]"}],"fun_headline_variants":["Multi-modal regex: English + examples yields 80% accuracy","Regel: English sketch boosts regex synthesis to 80%","Natural language hints triple regex synthesis accuracy","English plus examples: Regel hits 80% on regex tasks","Regel: English description guides regex examples to 80% accuracy"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The evaluation assumes that whenever Regel returns a wrong regex, an oracle immediately supplies two new examples guaranteed to rule out exactly that regex; real users cannot usually produce such perfectly targeted counterexamples without already knowing the answer.","fun_headline_variants_meta":{"raw":{"variants":["Multi-modal regex: English + examples yields 80% accuracy","Regel: English sketch boosts regex synthesis to 80%","Natural language hints triple regex synthesis accuracy","English plus examples: Regel hits 80% on regex tasks","Regel: English description guides regex examples to 80% accuracy"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000871,"raw_usage":{"total_tokens":3757,"prompt_tokens":916,"completion_tokens":2841,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":532,"completion_tokens_details":{"reasoning_tokens":2759}},"tokens_in":532,"tokens_out":2841,"duration_ms":22261,"temperature":1.0,"reasoning_tokens":2759,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:17:22.839288+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A controlled experiment in which human participants, not an oracle, provide the next examples after each incorrect regex on the same 322 benchmarks would settle whether the 80% accuracy survives realistic feedback; if the accuracy collapses toward the example-only baseline, the multimodal advantage depends on perfect counterexample selection rather than on the sketch mechanism itself.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the English-only baseline and the adapted 200-benchmark dataset used for evaluation."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the earlier example-based regex synthesizer whose over- and under-approximation pruning is adapted and then outperformed."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the semantic-parsing framework on which the sketch generator is built."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the SMT solver used to prune infeasible symbolic-integer assignments."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the automaton library used for regex membership and equivalence checking in the implementation."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the sketching approach whose constraint-solving role is contrasted with Regel's use of SMT for pruning rather than direct solving."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Represents the programming-by-example string-processing tradition that the example-based component builds on."}],"review_version":1}