{"id":"be14595c-718f-4569-8cfc-45e56d37c8aa","arxiv_id":"1908.05848","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A sketch-driven framework that combines natural language and string examples outperforms direct neural regex generation, including on a new 62-instance Stack Overflow benchmark.","lead":"This paper builds a two-step system that turns English descriptions plus example strings into regular expressions: first a parser turns the text into a partial regex sketch, then a synthesizer fills the gaps using the examples. It beats earlier models on older benchmarks and solves over half of a new real-world Stack Overflow set that neural baselines almost entirely fail on.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The 'solves 57%' claim is top-25 oracle recall, not the success rate of the stated selection rule; this more directly threatens the abstract's central claim than grammar coverage.","rationale":"The reader's weakest_assumption is that the hand-crafted SEMPRE grammar may not cover real-world StackOverflow descriptions, limiting external validity. I agree that is a real limitation, but it concerns generalization beyond the curated 62 posts. The more immediate problem is internal to the reported evaluation: the paper's own test-time selection procedure returns one regex, while the headline 'solves 57%' is computed as top-25 recall. Since the examples can be consistent with multiple regexes, top-25 accuracy is an oracle ceiling and not the success rate of the deployed algorithm. The paper's failure case (g) demonstrates exactly this phenomenon: the synthesizer finds an example-consistent regex that is not the ground truth. This concern is concrete and can be settled by re-running the evaluation under the stated selection policy. If the end-to-end number is close to 56.5%, the abstract survives; if it is closer to 31.1%, the central claim needs substantial qualification. I do not see a reason to reject the paper: the framework, ablations, and released code are valuable, and the issue is one of evaluation reporting rather than a fraudulent or unsound construction. The reader's CONDITIONAL verdict is therefore unchanged, though the condition should explicitly require reporting the true end-to-end solve rate on StackOverflow.","tokens_in":16366,"tokens_out":8397,"duration_ms":86226,"concrete_test":"Rerun the StackOverflow evaluation with the exact test-time policy from Section 6: for each benchmark, generate the k-best sketch list, run the synthesizer on each sketch, and return the regex from the highest-ranked sketch that yields any example-consistent regex; score that returned regex by semantic equivalence to the ground truth. Compare this end-to-end accuracy with the reported top-25 accuracy of 56.5% and top-1 accuracy of 31.1%. If the end-to-end number is materially below 56.5%, the abstract should be revised to report the actual solve rate and to present top-N accuracy as an oracle upper bound rather than as 'solves.'","verdict_should_be":"UNCHANGED","load_bearing_attack":"The headline result on StackOverflow is not the end-to-end success rate of the proposed algorithm. Table 3 defines top-N accuracy by counting a benchmark correct if any of the top-N sketches synthesizes to the correct regex, and the best reported number is top-25 accuracy of 56.5%. However, Section 6 states that at test time the system 'picks the output of the highest-ranked sketch yielding an example-consistent regex as the answer.' Under-specified examples can admit multiple consistent regexes, and the paper's own failure case (g) shows the synthesizer returning a consistent but wrong regex. Top-25 accuracy therefore ignores cases where a higher-ranked sketch already produced a wrong consistent regex, or where the correct sketch appears after an earlier sketch with no consistent completion. The actual solve rate of the deployed selection rule is an upper-bound-free number that must lie somewhere between the reported top-1 value of 31.1% and the top-25 value of 56.5%, and it could be much closer to 31.1%. Thus the abstract's 'solves 57% of the real-world dataset' overstates what a user would receive. This is more directly load-bearing than the reader's grammar-coverage concern: even granting perfect grammar coverage of the 62 curated posts, the user-facing claim is not supported unless the actual selection rule achieves the reported number. The paper should report end-to-end accuracy under the stated selection policy, not only top-N oracle recall.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a sketch-driven framework for synthesizing regular expressions from natural-language descriptions and positive/negative string examples. A semantic parser (a neural seq2seq model or a SEMPRE grammar-based parser) first maps the description to a sketch: an incomplete regex tree containing constrained holes. An enumerative program synthesizer then instantiates the holes under the guidance of the examples. Training is done either by MLE on heuristic pseudo-gold sketches or by MML that rewards sketches whose synthesized regex is functionally equivalent to the gold regex. Experiments cover the KB13 and TURK datasets plus a new 62-example Stack Overflow dataset. The best sketch-driven variants improve on earlier translation-based baselines on the prior datasets, and the grammar-based parser reaches 31.1% top-1 and 56.5% top-25 accuracy on Stack Overflow, while translated neural baselines mostly fail.","tokens_in":16705,"tokens_out":6820,"duration_ms":63523,"significance":"If the headline claims are taken at face value, the paper makes a useful contribution: it demonstrates that an intermediate sketch lets a synthesizer exploit examples more effectively than direct neural translation with post-filtering, and it provides one of the first evaluations on real Stack Overflow regex requests. The authors release code, data, and a readable grammar, which supports reproducibility, and the two-stage parser/synthesizer decomposition is clean and modular. However, the main real-world claim is currently supported by a top-N oracle metric that does not match the stated test-time selection rule, so the practical significance of the Stack Overflow result is substantially weaker than the abstract suggests. The prior-dataset state-of-the-art claim is better supported, but it needs a precise qualification.","major_comments":[{"comment":"The abstract and Section 1 state that the system 'solves 57%' of the Stack Overflow dataset, but the best number in Table 3 is 56.5% and it is defined as top-25 accuracy: a benchmark counts as solved if any of the top-25 sketches synthesizes to the correct regex. Section 6 describes a different test-time policy: 'We pick the output of the highest-ranked sketch yielding an example-consistent regex as the answer.' Under-specified examples can admit many consistent regexes, and Figure 6 failure case (g) is exactly a case where the synthesizer returns a consistent but wrong regex. The top-N oracle therefore overestimates the success of the deployed selection rule; the actual end-to-end accuracy under that rule could be much closer to the top-1 value of 31.1% than to 56.5%. Please report the accuracy of the stated selection rule (for example, top-1, top-5, and top-25 under that rule) and revise the abstract and Section 1 accordingly.","section":"Abstract; Section 1; Section 6.2, Table 3"},{"comment":"The claim that sketch-driven approaches 'outperform these previous approaches even when they are extended to benefit from examples' is stronger than the table shows. In the no-sketch-supervision block, DEEP SKETCH MLE reaches 76.2% on KB13 versus 77.7% for DEEP REGEX MLE+FILTER, and in the strongest MML comparison DEEP SKETCH MML reaches 84.3% on TURK, tying DEEP REGEX MML+FILTER at 84.3%. The state-of-the-art claim is supported by the best MML and pseudogold variants, but the sentence should be qualified to those variants rather than stated for all sketch-driven approaches.","section":"Section 6.1, Table 2"},{"comment":"Section 3.2 asserts that the hand-crafted unified grammar of roughly 70 lexical and 60 compositional rules is 'sufficient to cover the fairly narrow domain of regex descriptions,' and the entire Stack Overflow evaluation in Section 6.2 depends on this grammar. The paper gives no coverage statistics: how often does the grammar produce at least one sketch for the collected posts, and how stable is the 56.5% figure across the five folds? With only 62 benchmarks, such an analysis is feasible and would materially affect the external-validity claim that the framework solves real-world posts. Please add this analysis or weaken the generalization claim.","section":"Section 3.2; Section 6.2"}],"minor_comments":[{"comment":"The row 'DEEP REGEX MLE' appears twice with identical values; remove the duplicate.","section":"Table 2"},{"comment":"In the paragraph describing warm-starting the neural sketch models, the parenthetical '(DEEP REGEX MML)' appears to be a typo and should presumably read '(DEEP SKETCH MML)'.","section":"Section 6.1"},{"comment":"For the EMPTY SKETCH row, top-5 and top-25 are listed as '−'; clarify whether these were not run or whether the accuracy was 0%.","section":"Table 3"},{"comment":"In the description of manually labeled sketches for Stack Overflow, the phrase 'based on information from the gold sketch' should probably refer to the ground truth regex, since no gold sketch exists yet at that point.","section":"Section 5.2"},{"comment":"The sentence 'Finally, we take the the derivations over the entire natural language description' contains a duplicated 'the'.","section":"Section 3.2"}],"recommendation":"major_revision","confidential_remarks":"To the editor: the main issue is the mismatch between the top-N oracle metric and the stated test-time selection rule for the Stack Overflow evaluation. This is load-bearing for the abstract's headline claim and must be fixed before acceptance. The Table 2 overclaim is easily corrected by qualification. I do not see grounds for rejection: the framework is sound, the experiments are reproducible, and the best MML and pseudogold variants do achieve the reported state-of-the-art on the prior datasets. Please ask the authors to report end-to-end accuracy under the stated selection policy and to add a grammar-coverage analysis if feasible."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things worth knowing up front. The paper makes a real contribution: a sketch-with-holes intermediate representation that lets a semantic parser commit to partial structure while a synthesizer fills the gaps from string examples, and an MML training objective that rewards sketches leading to correct synthesized regexes. That is genuinely different from prior regex-from-NL systems, which used examples only as a post-filter. The second thing is that the abstract's 'solves 57%' is not a user-facing solve rate. It is top-25 oracle accuracy from Table 3: a benchmark counts as solved if any of the top 25 sketches synthesizes to the correct regex. The deployment rule in Section 6 picks the highest-ranked sketch that yields an example-consistent regex. With under-specified examples, multiple consistent regexes exist — the paper's own failure case (g) returns a consistent but wrong regex — so a correct sketch later in the list can be blocked by an earlier wrong-but-consistent one. The real end-to-end number is not reported; it is below 56.5% and could be close to the top-1 value of 31.1%. The stress-test note is right, and this concern is more load-bearing than grammar coverage.\n\nWhat is new and good: the two-stage framework is clean and modular; the ablations are careful; the gains on KB13 and TURK are consistent; the grammar-based parser is a nice fit for low-data regimes; the data-efficiency and beam-size experiments are informative. The new 62-post StackOverflow dataset, with code and data released, is a useful resource. The authors are also honest about the warm start in Section 6.1: the 'no sketch supervision' neural model is bootstrapped from grammar sketches selected using ground-truth correctness. That is not the same as training purely from weak supervision, and the abstract overstates it.\n\nSoft spots in proportion: the missing end-to-end accuracy on StackOverflow is the main one. No error bars on 62 examples is minor but real. Grammar coverage is an open question, but I would not call it fatal. Examples for prior datasets are machine-generated, which makes the comparison fair but synthetic. The citation pattern and data release look honest; no circularity in the evaluation.\n\nWho this is for: anyone working on semantic parsing, program synthesis from examples, or regex tooling. It deserves a serious referee. I would ask the authors to report end-to-end accuracy under their stated selection rule and correct the abstract before acceptance.","headline":"Solid two-stage sketch-driven regex synthesis with real gains; the abstract's 'solves 57%' is top-25 oracle recall, not end-to-end accuracy, so the headline overstates what a user would receive.","tokens_in":17213,"tokens_out":4285,"would_cite":true,"duration_ms":42367,"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":"This paper argues that regular expressions should be generated from natural language by first parsing the text into an incomplete sketch with holes, then using positive and negative examples to fill those holes, and reports that this…","keywords":["regular expression synthesis","natural language to program","sketch-based synthesis","program synthesis from examples","semantic parsing","weak supervision","Stack Overflow dataset","constrained holes"],"falsifier":"Take the 62 Stack Overflow posts, add a new set of regex-tagged posts without applying the original curation filters, and count how often the grammar parser produces a parse that leads to a consistent regex; if the solve rate drops sharply on uncurated posts, the reported 57 percent is an artifact of the chosen posts rather than a general method.","tokens_in":16185,"feed_emoji":"🧩","tokens_out":8701,"duration_ms":79049,"temperature":0.7,"pith_summary":"This paper argues that regular expressions are best generated from natural language by first parsing the description into an incomplete program, or sketch, and then letting a program synthesizer fill in the missing pieces using positive and negative string examples. The claim is that this two-stage decomposition beats direct neural translation from text to regex, and the experiments support it on two standard benchmarks and on a new collection of 62 real Stack Overflow posts. If the claim is right, systems that combine language understanding with example-driven search can handle long, under-specified descriptions that end-to-end neural models miss. The paper reports state-of-the-art accuracy on the older benchmarks and a 57 percent solve rate on the real-world set, where transferred neural baselines essentially fail.","feed_headline":"Sketch-first system solves 57% of real-world regex requests","feed_subtitle":"It parses plain English into a partial regex, then user examples fill the holes, beating neural translation on real posts.","key_machinery":"The load-bearing mechanism is the sketch, an unfinished regex in which the ordinary DSL operators may contain constrained holes written $\\square\\{S_1,\\dots,S_m\\}$. A concrete regex is admitted by the sketch if at least one subtree of the finished expression matches one of the listed $S_i$, so the hole acts as a soft hint rather than a hard template. The parser produces one or more such sketches from the language, and the synthesizer completes them by enumerating programs from the DSL in increasing depth, preferring programs that overlap with the hole's components, and keeping the first completion consistent with all positive and negative examples.","core_discovery":"The paper's central claim is that the best way to synthesize a regular expression from a natural-language description is to treat the description as a source of partial structure, not as a complete specification. A parser, either grammar-based or neural, turns the text into a sketch, a regex tree with constrained holes standing in for unspecified pieces; a program synthesizer then enumerates instantiations of that sketch and returns the first one consistent with the user's positive and negative string examples. On the KB13 and TURK benchmarks the authors report state-of-the-art semantic accuracy, and on 62 real Stack Overflow posts the grammar-sketch model, trained without sketch supervision, solves 56.5 percent of cases within its top 25 outputs, where a transferred neural translation model solves none or near none. The authors interpret this as evidence that decomposing language interpretation from example-guided search makes regex synthesis robust to long, under-specified, and typo-laden real-world descriptions.","pith_inferences":["If the hand-built grammar is the main bottleneck, scaling the parser with many more real-world posts should raise the reported solve rate; the paper's weak-supervision training suggests the sketches themselves do not need manual labels.","The same sketch-and-complete pattern is likely to transfer to other program-synthesis tasks where language is under-specified, such as spreadsheet transformations or database queries, provided the user can supply input-output examples.","A testable extension is that failure cases attributed to missing corner-case examples should improve sharply when a few additional user-supplied negative examples are added, since the synthesizer's search is what fails to disambiguate the intent.","The reported 57 percent figure probably understates what a stronger neural sketch parser trained on real-world-scale data would achieve, because the grammar constrains the sketches while the synthesizer itself is already effective."],"forward_implications":["Where direct sequence-to-sequence translation needs large training sets, sketch-driven synthesis stays effective with a few hundred examples, because the language-to-sketch mapping is simpler to learn than the language-to-regex mapping.","Filtering a neural model's k-best outputs by examples helps, but sketch-driven search helps more: consistency with the examples improves substantially, and the relative rate of inconsistent outputs drops by more than half.","The same framework can be instantiated with different parsers and synthesizers, so progress in either component can be imported without redesigning the whole pipeline.","On real user posts, the grammar-sketch model succeeds even without hand-labeled sketches, meaning weak supervision from the correctness of the synthesized regex is enough in a data-poor regime.","Users of Stack Overflow typically provide enough positive and negative examples to put the synthesizer in an effective regime, which is why the method works on real posts despite short or ambiguous language."],"supporting_citations":[{"why":"Supplies the KB13 benchmark and a semantic-unification baseline for regex generation from natural language.","marker":"Kushman and Barzilay (2013)"},{"why":"Supplies the TURK dataset and the DeepRegex sequence-to-sequence baseline that the sketch-driven approach is compared against.","marker":"Locascio et al. (2016)"},{"why":"Supplies the grammar-based semantic parsing approach that the paper adapts into its grammar sketch parser.","marker":"Berant et al. (2013)"},{"why":"Supplies the attention-based sequence-to-sequence architecture used by the neural sketch parser.","marker":"Luong et al. (2015)"},{"why":"Supplies the enumerative regex synthesizer that is generalized to search over sketches instead of enumerating programs from scratch.","marker":"Lee et al. (2016)"},{"why":"Supplies the SemRegex baseline and semantic-accuracy numbers used for comparison on prior datasets.","marker":"Zhong et al. (2018a)"},{"why":"Supplies the automaton library used to automatically generate positive and negative examples from ground-truth regexes.","marker":"Møller (2017)"},{"why":"Supplies the maximum marginal likelihood gradient approximation used to train parsers from weak supervision.","marker":"Guu et al. (2017)"}],"fun_headline_variants":["Sketch-first regex synthesis beats neural on real-world posts","Regex from NL plus examples: sketch then fill holes","Partial sketch completed by examples wins on real data","Synthesizing regex: language gives structure, examples fill gaps","Decompose regex task into sketch and example-guided search"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The real-world results rest on the assumption that a hand-built grammar of roughly 70 lexical and 60 compositional rules covers the ways people actually describe regular expressions on Stack Overflow, because a description the grammar cannot parse yields no useful sketch.","fun_headline_variants_meta":{"raw":{"variants":["Sketch-first regex synthesis beats neural on real-world posts","Regex from NL plus examples: sketch then fill holes","Partial sketch completed by examples wins on real data","Synthesizing regex: language gives structure, examples fill gaps","Decompose regex task into sketch and example-guided search"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000359,"raw_usage":{"total_tokens":1947,"prompt_tokens":950,"completion_tokens":997,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":566,"completion_tokens_details":{"reasoning_tokens":932}},"tokens_in":566,"tokens_out":997,"duration_ms":8936,"temperature":1.0,"reasoning_tokens":932,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:03:27.846488+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take the 62 Stack Overflow posts, add a new set of regex-tagged posts without applying the original curation filters, and count how often the grammar parser produces a parse that leads to a consistent regex; if the solve rate drops sharply on uncurated posts, the reported 57 percent is an artifact of the chosen posts rather than a general method.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the KB13 benchmark and a semantic-unification baseline for regex generation from natural language."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the TURK dataset and the DeepRegex sequence-to-sequence baseline that the sketch-driven approach is compared against."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the grammar-based semantic parsing approach that the paper adapts into its grammar sketch parser."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the attention-based sequence-to-sequence architecture used by the neural sketch parser."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the enumerative regex synthesizer that is generalized to search over sketches instead of enumerating programs from scratch."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the maximum marginal likelihood gradient approximation used to train parsers from weak supervision."}],"review_version":1}