ai-research-survey

scan.json (26275B)

---

 {
   "paper": {
     "title": "ChopChop: A Programmable Framework for Semantically Constraining the Output of Language Models",
     "authors": ["Shaan Nagy", "Timothy Zhou", "Nadia Polikarpova", "Loris D'Antoni"],
     "year": 2026,
     "venue": "Proc. ACM Program. Lang. (POPL)",
     "arxiv_id": "2509.00360",
     "doi": "10.1145/3776708"
   },
   "checklist": {
     "artifacts": {
       "code_released": {
         "applies": true,
         "answer": true,
         "justification": "Section 'Data-Availability Statement' states: 'The code for this paper is available on GitHub. An artifact containing a Docker image is available on Zenodo [33].' Reference [33] points to a Zenodo artifact with DOI 10.5281/zenodo.17337963."
       },
       "data_released": {
         "applies": true,
         "answer": true,
         "justification": "The benchmarks are fully enumerated in the appendix: 10 equivalence-guided decoding benchmarks are listed in Section A.4, and 72 MBPP TypeScript tasks from MultiPL-E (a public dataset) are listed by name in Section A.3.2. The Zenodo artifact also contains these."
       },
       "environment_specified": {
         "applies": true,
         "answer": true,
         "justification": "The Zenodo artifact [33] contains a Docker image, which provides a fully reproducible environment. Hardware is specified in Section 6.1: 'Supermicro SYS-4029GP-TRT with two Intel(R) Xeon(R) Gold 6230 CPUs, 384 GB RAM, a 4 TB SSD, and eight Nvidia Geforce RTX 2080Ti GPUs.'"
       },
       "reproduction_instructions": {
         "applies": true,
         "answer": true,
         "justification": "A Docker image artifact is provided on Zenodo [33], which is designed for reproducibility. The full set of prompts, benchmarks, and rewrite rules are provided in the appendix (Sections A.3.2, A.4)."
       }
     },
     "statistical_methodology": {
       "confidence_intervals_or_error_bars": {
         "applies": true,
         "answer": false,
         "justification": "Tables 1 and 2 report only point estimates (counts of successful generations and mean overhead in ms/token). No confidence intervals, error bars, or uncertainty measures are reported."
       },
       "significance_tests": {
         "applies": true,
         "answer": false,
         "justification": "The paper makes comparative claims (e.g., 'improving the performance of DeepSeek-Coder-6.7b, CodeLlama-7B, and CodeLlama-13B by an average of 28.0%, 10.1%, and 23.2%') but no statistical significance tests are reported."
       },
       "effect_sizes_reported": {
         "applies": true,
         "answer": true,
         "justification": "The paper reports percentage improvements with baseline context: '28.0%, 10.1%, and 23.2% across all temperatures' (Section 6.2.1). Table 1 provides raw counts for all conditions, allowing readers to compute exact effect sizes."
       },
       "sample_size_justified": {
         "applies": true,
         "answer": false,
         "justification": "The equivalence benchmark has only 10 tasks and the TypeScript benchmark uses 72/809 tasks from MBPP. No justification is given for why 10 equivalence tasks are sufficient, and the choice of 72 TypeScript tasks is driven by their language fragment, not by power analysis."
       },
       "variance_reported": {
         "applies": true,
         "answer": false,
         "justification": "Each benchmark/model/temperature combination appears to be a single run. No variance, standard deviation, or multiple-run results are reported. Table 1 shows single-run counts only."
       }
     },
     "evaluation_design": {
       "baselines_included": {
         "applies": true,
         "answer": true,
         "justification": "Section 6.1 defines two baselines: unconstrained decoding and grammar-constrained decoding (GCD). For TypeScript, the tool by Mündler et al. [32] is also compared."
       },
       "baselines_contemporary": {
         "applies": true,
         "answer": true,
         "justification": "Mündler et al. [32] (2025) is a recent contemporary baseline for type-constrained decoding. Grammar-constrained decoding is the standard approach in the field. These are appropriate and competitive baselines."
       },
       "ablation_study": {
         "applies": true,
         "answer": true,
         "justification": "The comparison of unconstrained vs. grammar-constrained vs. semantic-constrained decoding effectively serves as an ablation, showing the contribution of syntactic constraints alone vs. adding semantic constraints. The 'No Delimit' vs. 'Delimit' variants and the 'Rules + No Delimit' vs. 'Rules + Delimit' variants (Table 3) further isolate prompt effects."
       },
       "multiple_metrics": {
         "applies": true,
         "answer": true,
         "justification": "The paper reports both effectiveness (success rate/count of correct programs, Table 1) and overhead (ms/token latency, Table 2), as well as the distribution of tokens tried before finding a realizable one (Figure 12)."
       },
       "human_evaluation": {
         "applies": true,
         "answer": true,
         "justification": "Section 6.2.1 states: 'we manually check the unconstrained and syntax-constrained data for false negatives (programs that could be considered equivalent, but are not proved equivalent by our rewrite rules). We only found 8 such instances out of the 600 total programs.' Section 6.2.2 provides qualitative evaluation of generated outputs."
       },
       "held_out_test_set": {
         "applies": false,
         "answer": false,
         "justification": "This paper does not train or tune any model. It evaluates a decoding framework on fixed benchmarks, so train/test splitting is not applicable."
       },
       "per_category_breakdown": {
         "applies": true,
         "answer": true,
         "justification": "Table 1 breaks results down by model (3 models), temperature (5 settings), benchmark type (equivalence No Delimit, equivalence Delimit, TypeScript), and decoding strategy. Additional breakdowns appear in Table 3 (with rewrite rules in prompt)."
       },
       "failure_cases_discussed": {
         "applies": true,
         "answer": true,
         "justification": "Section 6.2.2 discusses failure modes: natural language parsed as valid grammar (Figure 11a), inequivalent programs (Figure 11b), const mutation errors (Figure 11c), and cases where 'the LM is typically unable to recover because it has already committed to a solution.' The paper also discusses timeouts from deeply nested arithmetic expressions."
       },
       "negative_results_reported": {
         "applies": true,
         "answer": true,
         "justification": "The paper reports that grammar-constrained decoding performs worse than unconstrained generation for TypeScript (Section 6.2.1). It also reports that Mündler et al. [32] outperforms ChopChop at medium and high temperatures for TypeScript due to supporting a larger language fragment. Performance degradation at high temperatures is also reported."
       }
     },
     "claims_and_evidence": {
       "abstract_claims_supported": {
         "applies": true,
         "answer": true,
         "justification": "The abstract claims ChopChop 'improves success rates while maintaining practical decoding latency,' which is supported by Table 1 (improved success rates) and Table 2 (overhead of tens to hundreds of ms/token, compared to 81 ms baseline for unconstrained CodeLlama-13B)."
       },
       "causal_claims_justified": {
         "applies": true,
         "answer": true,
         "justification": "The causal claims are of the form 'applying semantic constrained decoding improves success rates.' This is justified by controlled single-variable manipulation: the only difference between conditions is the decoding strategy, with the same model, temperature, benchmarks, and prompts held constant."
       },
       "generalization_bounded": {
         "applies": true,
         "answer": true,
         "justification": "The paper is careful to scope its claims. It specifies the exact language fragments (a toy functional language and a subset of TypeScript), the specific models tested (DeepSeek-Coder-6.7b, CodeLlama-7B, CodeLlama-13B), and acknowledges limitations such as the smaller TypeScript fragment compared to Mündler et al."
       },
       "alternative_explanations_discussed": {
         "applies": true,
         "answer": true,
         "justification": "Section 6.2.1 discusses alternative explanations for baselines' poor performance: the toy language being out-of-distribution, models emitting natural language, and the rewrite rules not capturing all equivalences (only 8 false negatives out of 600). Section 6.2.1 also discusses why GCD underperforms unconstrained decoding for TypeScript (language fragment limitation)."
       }
     },
     "setup_transparency": {
       "model_versions_specified": {
         "applies": true,
         "answer": true,
         "justification": "Section 6.1 specifies: 'DeepSeek-Coder-6.7b, CodeLlama-7B, and CodeLlama-13B' with 'instruction-tuned versions.' These are specific model names with sizes. The paper notes these are open-weight models run locally, so API versioning is not applicable."
       },
       "prompts_provided": {
         "applies": true,
         "answer": true,
         "justification": "Full prompt text is provided in Section A.3.2 (TypeScript context) and Section A.4 (equivalence context, including the code examples). The exact benchmark inputs (function signatures for TypeScript, programs for equivalence) are also listed."
       },
       "hyperparameters_reported": {
         "applies": true,
         "answer": true,
         "justification": "Section 6.1 specifies five sampling temperatures (0.01, 0.3, 0.5, 0.7, 1.0) and a 150-second timeout. The naive sampling strategy (backtrack by one token on rejection) is described. The paper states these are 'instruction-tuned versions' of the models."
       },
       "scaffolding_described": {
         "applies": false,
         "answer": false,
         "justification": "ChopChop is not an agentic scaffolding system. It is a constrained decoding framework that operates at the token generation level. There are no agents, tools, retry loops, or feedback mechanisms beyond the constrained decoding algorithm itself, which is thoroughly described."
       },
       "data_preprocessing_documented": {
         "applies": true,
         "answer": true,
         "justification": "Section 6.1 describes how benchmarks were selected: 72/809 MBPP tasks that can be solved in the TypeScript language fragment. The prompting strategy is documented. For equivalence, 10 benchmark tasks were manually created and listed in full."
       }
     },
     "limitations_and_scope": {
       "limitations_section_present": {
         "applies": true,
         "answer": true,
         "justification": "Section 8 (Conclusion) contains substantive discussion of limitations: users must write pruners as corecursive functions that return regular spaces, the implementation is 'relatively unoptimized, incurring noticeable per-token overhead,' and the type pruner uses bounded depth-3 types sacrificing soundness for deeply nested types (Section A.3.1)."
       },
       "threats_to_validity_specific": {
         "applies": true,
         "answer": true,
         "justification": "The paper discusses specific threats: the toy language being out-of-distribution (Section 6.2.1), the TypeScript fragment being smaller than Mündler et al.'s (Section 6.2.1), equivalence being approximate via rewrite rules (Section 6.2.1, 8 false negatives found), constrained decoding skewing LM token distributions (Section 6.2.2), and type bounding sacrificing soundness (Section A.3.1)."
       },
       "scope_boundaries_stated": {
         "applies": true,
         "answer": true,
         "justification": "The paper explicitly states it tests on small-to-medium models (6.7B-13B), uses only a subset of TypeScript, and its equivalence checker is approximate. Section 8 notes that 'users of ChopChop must directly define a pruner... as a corecursive function on program spaces' and that this function 'must return a space that is regular,' limiting applicability."
       }
     },
     "data_integrity": {
       "raw_data_available": {
         "applies": true,
         "answer": true,
         "justification": "The Zenodo artifact [33] contains a Docker image for reproducing the experiments. The full benchmark lists are in the appendix. This enables independent verification of results."
       },
       "data_collection_described": {
         "applies": true,
         "answer": true,
         "justification": "The equivalence benchmarks are 10 manually created tasks (listed in Section A.4). The TypeScript benchmarks are 72 tasks from MBPP/MultiPL-E, selected by filtering for tasks solvable in the supported language fragment (Section 6.1)."
       },
       "recruitment_methods_described": {
         "applies": false,
         "answer": false,
         "justification": "No human participants were involved. The data consists of standard benchmarks (MBPP/MultiPL-E) and manually created tasks."
       },
       "data_pipeline_documented": {
         "applies": true,
         "answer": true,
         "justification": "Section 6.1 describes the pipeline: for each benchmark/model/decoder/temperature, run constrained decoding until END token or 150s timeout; a run is successful if a complete program is emitted that satisfies semantic constraints. The TypeScript task selection (72/809 from MBPP) is documented."
       }
     },
     "conflicts_of_interest": {
       "funding_disclosed": {
         "applies": true,
         "answer": true,
         "justification": "The Acknowledgments section lists: Microsoft Faculty Fellowship, UCSD JSOE Scholarship, NSF grants CCF-2422214, CCF-2506134, CCF-2446711, and NSF Graduate Research Fellowship DGE-2038238."
       },
       "affiliations_disclosed": {
         "applies": true,
         "answer": true,
         "justification": "All authors are from UC San Diego. The paper explicitly discloses: 'Loris D'Antoni holds concurrent appointments as a Professor at the University of California San Diego and as an Amazon Scholar. This paper describes work performed at the University of California San Diego and is not associated with Amazon.'"
       },
       "funder_independent_of_outcome": {
         "applies": true,
         "answer": true,
         "justification": "Funding is from NSF and Microsoft Faculty Fellowship. The paper does not evaluate any Microsoft or NSF product. The Amazon affiliation is explicitly stated as not associated with this work. The funders have no stake in the specific results."
       },
       "financial_interests_declared": {
         "applies": true,
         "answer": false,
         "justification": "No competing interests or financial disclosure statement is present. The Amazon Scholar affiliation is disclosed but there is no explicit competing interests declaration."
       }
     },
     "contamination": {
       "training_cutoff_stated": {
         "applies": true,
         "answer": false,
         "justification": "The paper uses DeepSeek-Coder-6.7b, CodeLlama-7B, and CodeLlama-13B but does not state their training data cutoff dates. This is relevant because the MBPP benchmark and MultiPL-E could be in the training data."
       },
       "train_test_overlap_discussed": {
         "applies": true,
         "answer": false,
         "justification": "No discussion of whether the MBPP/MultiPL-E benchmark tasks appeared in the training data of the models used. MBPP was published in 2021, predating all models used."
       },
       "benchmark_contamination_addressed": {
         "applies": true,
         "answer": false,
         "justification": "MBPP (2021) and MultiPL-E (2022) were both published before the training cutoffs of all three models. The paper does not discuss contamination risk for the TypeScript benchmark tasks. The 10 equivalence tasks appear to be novel (manually created), which would mitigate contamination for that benchmark."
       }
     },
     "human_studies": {
       "pre_registered": {
         "applies": false,
         "answer": false,
         "justification": "No human participants in this study. It evaluates automated systems on benchmarks."
       },
       "irb_or_ethics_approval": {
         "applies": false,
         "answer": false,
         "justification": "No human participants in this study."
       },
       "demographics_reported": {
         "applies": false,
         "answer": false,
         "justification": "No human participants in this study."
       },
       "inclusion_exclusion_criteria": {
         "applies": false,
         "answer": false,
         "justification": "No human participants in this study."
       },
       "randomization_described": {
         "applies": false,
         "answer": false,
         "justification": "No human participants in this study."
       },
       "blinding_described": {
         "applies": false,
         "answer": false,
         "justification": "No human participants in this study."
       },
       "attrition_reported": {
         "applies": false,
         "answer": false,
         "justification": "No human participants in this study."
       }
     },
     "cost_and_practicality": {
       "inference_cost_reported": {
         "applies": true,
         "answer": true,
         "justification": "Table 2 reports overhead in milliseconds per produced token for all model/benchmark/temperature combinations. Section 6.3 also reports that 'CodeLlama-13B takes on average 81 ms to produce a token when unconstrained' for reference, and that '96.4% of the tokens produced during semantic constrained decoding for TypeScript pass on the first try.'"
       },
       "compute_budget_stated": {
         "applies": true,
         "answer": true,
         "justification": "Hardware is fully specified (Section 6.1): Supermicro SYS-4029GP-TRT with 2x Xeon Gold 6230 CPUs, 384GB RAM, 8x RTX 2080Ti GPUs. Per-token overhead is reported in Table 2. The 150-second timeout per run is stated."
       }
     }
   },
   "claims": [
     {
       "claim": "ChopChop improves success rates of language models for generating semantically valid programs compared to unconstrained and grammar-constrained decoding.",
       "evidence": "Table 1 shows semantic constrained decoding consistently outperforms baselines across models and temperatures. For equivalence-guided decoding (No Delimit), ChopChop achieves 33-43 successes vs. 0 for baselines. For TypeScript, it improves by 28.0%, 10.1%, and 23.2% for the three models (Section 6.2.1).",
       "supported": "strong"
     },
     {
       "claim": "ChopChop maintains practical decoding latency with small overhead per token.",
       "evidence": "Table 2 reports overhead ranging from tens to a few hundred milliseconds per token. Section 6.3 notes CodeLlama-13B takes 81ms per token unconstrained, and 96.4% of tokens pass semantic checking on the first try.",
       "supported": "strong"
     },
     {
       "claim": "Semantic constrained decoding is sound: any output program satisfies the user-provided semantic constraints.",
       "evidence": "Theorem 3.3 proves soundness of semantic constrained decoding. The proof in Appendix A.1 shows that the algorithm only returns outputs that pass the constraint check on Line 6 of Algorithm 1.",
       "supported": "strong"
     },
     {
       "claim": "Semantic constrained decoding is complete up to top-p and top-k sampling when the realizability checker is complete.",
       "evidence": "Theorem 3.4 and proof in Appendix A.1 establish this formally.",
       "supported": "strong"
     },
     {
       "claim": "Grammar-constrained decoding alone performs worse than unconstrained generation for TypeScript.",
       "evidence": "Table 1 shows GCD yields 126, 289, 236 total successes vs. unconstrained's 214, 308, 259 for the three models. Section 6.2.1 attributes this to limiting the grammar to a small TypeScript fragment that prevents otherwise compilable programs.",
       "supported": "strong"
     },
     {
       "claim": "Mündler et al. performs slightly better than ChopChop at medium temperatures and significantly better at high temperatures for TypeScript.",
       "evidence": "Table 1 shows Mündler et al. achieving 337, 351, 347 total vs. ChopChop's 274, 339, 319 for the three models. Section 6.2.1 attributes this to Mündler et al. supporting a larger language fragment.",
       "supported": "strong"
     }
   ],
   "methodology_tags": ["benchmark-eval", "theoretical"],
   "key_findings": "ChopChop introduces the first programmable framework for semantic constrained decoding of language models, allowing users to define constraints over abstract syntax trees rather than string representations. Across two case studies (equivalence-guided decoding and type-safe TypeScript generation) with three small-to-medium LMs at five temperatures, ChopChop consistently outperforms unconstrained and grammar-only baselines, with especially dramatic gains for equivalence-guided decoding where baselines score near zero. The overhead is practical (tens to hundreds of ms/token) and the theoretical framework provides formal soundness and completeness guarantees.",
   "red_flags": [
     {
       "flag": "Very small equivalence benchmark",
       "detail": "The equivalence-guided decoding evaluation uses only 10 manually created benchmark tasks. While the dramatic improvement (0 vs. 33-45 successes) is convincing directionally, 10 tasks is very small for drawing robust quantitative conclusions."
     },
     {
       "flag": "No variance or repeated runs",
       "detail": "Each benchmark/model/temperature combination appears to be evaluated once. For stochastic decoding (temperatures > 0.01), results could vary across runs. No standard deviations or confidence intervals are reported."
     },
     {
       "flag": "Benchmark contamination not addressed",
       "detail": "The TypeScript benchmarks come from MBPP (2021) and MultiPL-E (2022), which predate all three models' training. Contamination could inflate baseline performance (making ChopChop's improvement look smaller) or affect the nature of errors. This is not discussed."
     },
     {
       "flag": "Only small/medium models tested",
       "detail": "All models are 6.7B-13B parameters. It is unclear whether the improvements would hold for larger, more capable models that may already produce semantically valid code more frequently without constraints."
     }
   ],
   "cited_papers": [
     {
       "title": "Monitor-guided decoding of code LMs with static analysis of repository context",
       "authors": ["Lakshya A Agrawal", "Aditya Kanade", "Navin Goyal", "Shuvendu K. Lahiri", "Sriram K. Rajamani"],
       "year": 2023,
       "doi": "10.5555/3666122.3667523",
       "relevance": "Proposes the monitor-based framework for constrained decoding with static analysis, a direct predecessor to ChopChop's semantic constrained decoding."
     },
     {
       "title": "Type-Constrained Code Generation with Language Models",
       "authors": ["Niels Mündler", "Jingxuan He", "Hao Wang", "Koushik Sen", "Dawn Song", "Martin Vechev"],
       "year": 2025,
       "doi": "10.1145/3729274",
       "relevance": "Implements type-constrained decoding for TypeScript, serving as a direct baseline comparison for ChopChop's type-safe decoding case study."
     },
     {
       "title": "Grammar-aligned decoding",
       "authors": ["Kanghee Park", "Jiayu Wang", "Taylor Berg-Kirkpatrick", "Nadia Polikarpova", "Loris D'Antoni"],
       "year": 2025,
       "doi": "10.52202/079017-0774",
       "relevance": "Addresses the token distribution skewing problem in grammar-constrained decoding, directly relevant to improving constrained decoding quality."
     },
     {
       "title": "Flexible and Efficient Grammar-Constrained Decoding",
       "authors": ["Kanghee Park", "Timothy Zhou", "Loris D'Antoni"],
       "year": 2025,
       "arxiv_id": "2502.05111",
       "relevance": "Presents efficient grammar-constrained decoding techniques that could be integrated with ChopChop as a preprocessing step."
     },
     {
       "title": "SynCode: LLM Generation with Grammar Augmentation",
       "authors": ["Shubham Ugare", "Tarun Suresh", "Hangoo Kang", "Sasa Misailovic", "Gagandeep Singh"],
       "year": 2025,
       "relevance": "Grammar-augmented LLM generation framework, representative of the grammar-constrained decoding baseline approach."
     },
     {
       "title": "Grammar-Constrained Decoding for Structured NLP Tasks without Finetuning",
       "authors": ["Saibo Geng", "Martin Josifoski", "Maxime Peyrard", "Robert West"],
       "year": 2023,
       "doi": "10.18653/v1/2023.emnlp-main.674",
       "relevance": "Early work on grammar-constrained decoding for structured outputs, foundational to the constrained decoding field."
     },
     {
       "title": "Program Synthesis with Large Language Models",
       "authors": ["Jacob Austin", "Augustus Odena", "Maxwell Nye"],
       "year": 2021,
       "arxiv_id": "2108.07732",
       "relevance": "Introduces the MBPP benchmark used in ChopChop's TypeScript evaluation."
     },
     {
       "title": "MultiPL-E: A Scalable and Extensible Approach to Benchmarking Neural Code Generation",
       "authors": ["Federico Cassano", "John Gouwar", "Daniel Nguyen"],
       "year": 2022,
       "arxiv_id": "2208.08227",
       "relevance": "Provides the TypeScript translations of MBPP tasks used as benchmarks in ChopChop's type-safe decoding evaluation."
     },
     {
       "title": "Efficient Guided Generation for Large Language Models",
       "authors": ["Brandon T. Willard", "Rémi Louf"],
       "year": 2023,
       "arxiv_id": "2307.09702",
       "relevance": "Foundational work on efficient constrained generation for LLMs, part of the grammar-constrained decoding literature."
     },
     {
       "title": "Synchromesh: Reliable code generation from pre-trained language models",
       "authors": ["Gabriel Poesia", "Oleksandr Polozov", "Vu Le", "Ashish Tiwari", "Gustavo Soares", "Christopher Meek", "Sumit Gulwani"],
       "year": 2022,
       "arxiv_id": "2201.11227",
       "relevance": "Proposes completion engines for reliable code generation from LLMs, a framework closely related to ChopChop's constrained decoding approach."
     }
   ]
 }