ai-research-survey

scan.json (19835B)

---

 {
   "paper": {
     "title": "Correctness-Guaranteed Code Generation via Constrained Decoding",
     "authors": ["Lingxiao Li", "Salar Rahili", "Yiwei Zhao"],
     "year": 2025,
     "venue": "COLM 2025",
     "arxiv_id": "2508.15866"
   },
   "checklist": {
     "artifacts": {
       "code_released": {
         "applies": true,
         "answer": false,
         "justification": "No repository URL or code archive is provided in the paper. The paper does not mention releasing source code."
       },
       "data_released": {
         "applies": true,
         "answer": false,
         "justification": "The 8 talent category prompts and handcrafted examples are described in appendices but no downloadable dataset or data archive is provided."
       },
       "environment_specified": {
         "applies": true,
         "answer": false,
         "justification": "The paper mentions using 8 A100 GPUs and VLLM but does not provide a requirements.txt, Dockerfile, or detailed environment setup with library versions."
       },
       "reproduction_instructions": {
         "applies": true,
         "answer": false,
         "justification": "No step-by-step reproduction instructions, README, or runnable scripts are provided."
       }
     },
     "statistical_methodology": {
       "confidence_intervals_or_error_bars": {
         "applies": true,
         "answer": false,
         "justification": "Results in Figure 3 show histograms of score distributions across 80 data points per method but no confidence intervals or error bars are reported."
       },
       "significance_tests": {
         "applies": true,
         "answer": false,
         "justification": "The paper claims its method achieves the highest success rate and quality but provides no statistical significance tests comparing methods."
       },
       "effect_sizes_reported": {
         "applies": true,
         "answer": true,
         "justification": "Figure 3 provides score distributions and counts per bin (e.g., 53 in 80-100 for Ours-Reflection vs 38 for Claude). Table 1 reports tokens/sec (7.64 vs 2.04 and 1.47) giving magnitude of speedup."
       },
       "sample_size_justified": {
         "applies": true,
         "answer": false,
         "justification": "8 prompts x 10 runs = 80 data points per method. No justification for why 8 prompts or 10 runs is sufficient."
       },
       "variance_reported": {
         "applies": true,
         "answer": false,
         "justification": "No standard deviation, IQR, or spread measures are reported. Only histogram distributions are shown."
       }
     },
     "evaluation_design": {
       "baselines_included": {
         "applies": true,
         "answer": true,
         "justification": "Baselines include unconstrained generation with Claude-3.5-Sonnet and Qwen2.5-32B-Coder, both with and without reflection (Section 6.2)."
       },
       "baselines_contemporary": {
         "applies": true,
         "answer": true,
         "justification": "Claude-3.5-Sonnet and Qwen2.5-32B-Coder are contemporary strong coding LLMs. Table 1 also compares against Willard & Louf (2023) and Koo et al. (2024) for speed."
       },
       "ablation_study": {
         "applies": true,
         "answer": true,
         "justification": "The reflection variant serves as a partial ablation. The comparison between constrained and unconstrained with the same model (Qwen2.5-32B-Coder) isolates the constrained decoding contribution."
       },
       "multiple_metrics": {
         "applies": true,
         "answer": true,
         "justification": "The paper reports success rate (whether generation terminates and produces valid code), quality scores (1-100 via LLM judge), and inference speed (tokens/sec in Table 1)."
       },
       "human_evaluation": {
         "applies": true,
         "answer": false,
         "justification": "Quality evaluation is done entirely by Claude-3.5-Sonnet as an LLM judge. No human evaluation of generated code quality is reported."
       },
       "held_out_test_set": {
         "applies": true,
         "answer": false,
         "justification": "The 8 talent category prompts are used for evaluation but there is no separation into dev/test sets. The same prompts are used for all methods."
       },
       "per_category_breakdown": {
         "applies": true,
         "answer": true,
         "justification": "Figure 3 provides score distributions broken down by score ranges (0-19, 20-39, etc.) for each method. Appendix C.8 details the 8 individual prompts."
       },
       "failure_cases_discussed": {
         "applies": true,
         "answer": true,
         "justification": "Section 6.2 and Appendix C.9-C.10 discuss failure cases: the method fails when generation does not terminate due to distribution distortion causing indefinite repetition."
       },
       "negative_results_reported": {
         "applies": true,
         "answer": true,
         "justification": "The paper honestly reports that Algorithm 1 is not guaranteed to terminate (Section 6.1), that constrained decoding can distort distributions (Appendix C.9), and that Claude-3.5-Sonnet outperforms in the 90-100 score range (38 vs 33 data points)."
       }
     },
     "claims_and_evidence": {
       "abstract_claims_supported": {
         "applies": true,
         "answer": true,
         "justification": "The abstract claims semantic correctness guarantees (supported by Theorem 5.1, 6.1), runtime correctness validation in a roguelike game (supported by DCI experiments in Section 6), and the constrained decoding algorithm with non-extensible property (formally defined and proven)."
       },
       "causal_claims_justified": {
         "applies": true,
         "answer": true,
         "justification": "The main causal claim is that constrained decoding improves correctness. This is supported by controlled comparison: same model (Qwen2.5-32B-Coder) with and without constrained decoding, isolating the variable."
       },
       "generalization_bounded": {
         "applies": true,
         "answer": true,
         "justification": "The paper is explicit that results are demonstrated through sLua (a custom language) and the DCI game. It states the framework is 'language-agnostic' but demonstrates only on sLua, and acknowledges limitations of the language restrictions."
       },
       "alternative_explanations_discussed": {
         "applies": true,
         "answer": true,
         "justification": "The paper discusses distribution distortion as an alternative explanation for failures (Appendix C.9), and acknowledges that Claude-3.5-Sonnet may produce higher quality code in the top range due to being a stronger base model."
       }
     },
     "setup_transparency": {
       "model_versions_specified": {
         "applies": true,
         "answer": false,
         "justification": "The paper uses 'Claude-3.5-Sonnet' and 'Qwen2.5-32B-Coder' without specific version snapshots or API dates. No snapshot date for Claude-3.5-Sonnet is given."
       },
       "prompts_provided": {
         "applies": true,
         "answer": true,
         "justification": "Appendix C.6-C.8 provide the agent workflow, system prompts, and the 8 talent category prompts used for evaluation. In-context examples are described in detail."
       },
       "hyperparameters_reported": {
         "applies": true,
         "answer": false,
         "justification": "No temperature, top-p, or sampling parameters are reported for the LLM generation. The 1500 token limit for termination is stated but standard hyperparameters are missing."
       },
       "scaffolding_described": {
         "applies": true,
         "answer": true,
         "justification": "Algorithm 1 fully describes the constrained decoding scaffolding. Appendix C.6 describes the simple LLM agent used to guide category generation. The ToP framework is described in detail in Section 4."
       },
       "data_preprocessing_documented": {
         "applies": true,
         "answer": true,
         "justification": "The paper documents how talent categories are structured (4 talents + up to 4 effects), how effects are generated first then talents, and how generated scripts are registered in the environment for future prompts (Section 6.2)."
       }
     },
     "limitations_and_scope": {
       "limitations_section_present": {
         "applies": true,
         "answer": true,
         "justification": "The paper discusses limitations throughout: Algorithm 1 may not terminate (Section 6.1), distribution distortion issues (Appendix C.9), and language feature restrictions for runtime guarantees."
       },
       "threats_to_validity_specific": {
         "applies": true,
         "answer": true,
         "justification": "Specific threats are discussed: nontermination of generation due to distribution distortion (Appendix C.9), the tradeoff of expressiveness for safety by restricting language features, and the limitation to sLua rather than general languages."
       },
       "scope_boundaries_stated": {
         "applies": true,
         "answer": true,
         "justification": "The paper explicitly states it demonstrates on sLua only, that dynamic data structures and nil pointers are not supported, and that the runtime guarantee requires specific API design choices and language restrictions."
       }
     },
     "data_integrity": {
       "raw_data_available": {
         "applies": true,
         "answer": false,
         "justification": "No raw experimental data (individual scores, generated scripts, timing measurements) is made available for independent verification."
       },
       "data_collection_described": {
         "applies": true,
         "answer": true,
         "justification": "Section 6.2 describes: 8 prompts, 10 runs each, scores from Claude-3.5-Sonnet judge, failure counted as 0. Table 1 describes single-run timing measurement setup."
       },
       "recruitment_methods_described": {
         "applies": false,
         "answer": false,
         "justification": "No human participants. Data consists of automated benchmark runs on programmatic tasks."
       },
       "data_pipeline_documented": {
         "applies": true,
         "answer": true,
         "justification": "The pipeline is documented: prompts -> generation (with/without constrained decoding) -> LLM-judge scoring -> histogram aggregation. Failure handling (unsuccessful = score 0, 1500 token termination limit) is stated."
       }
     },
     "conflicts_of_interest": {
       "funding_disclosed": {
         "applies": true,
         "answer": false,
         "justification": "No funding statement is present. All authors are from Netflix but no explicit funding acknowledgment is provided."
       },
       "affiliations_disclosed": {
         "applies": true,
         "answer": true,
         "justification": "All three authors are listed with Netflix affiliation on the first page."
       },
       "funder_independent_of_outcome": {
         "applies": true,
         "answer": false,
         "justification": "All authors are Netflix employees. Netflix could benefit from demonstrating effective code generation for game mechanics. No statement about funder independence from outcomes."
       },
       "financial_interests_declared": {
         "applies": true,
         "answer": false,
         "justification": "No competing interests or financial interests statement is provided in the paper."
       }
     },
     "contamination": {
       "training_cutoff_stated": {
         "applies": false,
         "answer": false,
         "justification": "The paper does not evaluate pre-trained model capability on a standard benchmark. It evaluates a constrained decoding method on a custom task (DCI game mechanics) that could not be in training data."
       },
       "train_test_overlap_discussed": {
         "applies": false,
         "answer": false,
         "justification": "The evaluation task (generating sLua scripts for a custom game DCI) is novel and created by the authors, so train/test overlap is not a concern."
       },
       "benchmark_contamination_addressed": {
         "applies": false,
         "answer": false,
         "justification": "No standard benchmark is used. The evaluation is on a custom game scripting task created by the authors."
       }
     },
     "human_studies": {
       "pre_registered": {
         "applies": false,
         "answer": false,
         "justification": "No human participants in this study."
       },
       "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 1 reports tokens/sec for each method (18.89 unconstrained, 7.64 ours, 2.04 and 1.47 for alternatives) and compilation overhead percentages."
       },
       "compute_budget_stated": {
         "applies": true,
         "answer": true,
         "justification": "The paper states experiments were run on 8 A100 GPUs (Table 1 caption). Inference speed is benchmarked."
       }
     }
   },
   "claims": [
     {
       "claim": "The constrained decoding method generates semantically correct sLua programs that conform to prescribed scripting APIs.",
       "evidence": "Theorem 5.1 proves linear-time parsing; Theorem 6.1 proves runtime error-free execution for DCI scripts. Section 6.2 shows 0% syntax/semantic errors in successful generations.",
       "supported": "strong"
     },
     {
       "claim": "The method with reflection achieves the highest success rate and quality scores compared to unconstrained baselines.",
       "evidence": "Figure 3: Ours-Reflection has 53 scores in 80-100 range out of 80 runs. Unconstrained Qwen has 49, Claude has 49. However Claude has 38 in 90-100 vs 33 for ours.",
       "supported": "moderate"
     },
     {
       "claim": "Adaptive rejection sampling is more than three times faster than alternative regex-compilation approaches for constrained decoding.",
       "evidence": "Table 1: 7.64 tokens/sec (ours) vs 2.04 (Willard & Louf) and 1.47 (Koo et al.), with only 4.98% compilation overhead vs 73-79%.",
       "supported": "strong"
     },
     {
       "claim": "Generated scripts are guaranteed to terminate and execute without runtime errors in the game engine.",
       "evidence": "Theorem 6.1, proved in Appendix C.5, combines safe callback patterns, bounded loop iterations, lexical scope function references, and capped recursion depth.",
       "supported": "strong"
     }
   ],
   "methodology_tags": ["benchmark-eval", "theoretical"],
   "key_findings": "The paper presents a constrained decoding algorithm using a Tree of Parsers (ToP) that generates semantically correct programs by incorporating context-sensitive parsing during LM token generation. Demonstrated on sLua (a typed Lua variant) for a roguelike game, the method achieves provable runtime correctness guarantees (Theorem 6.1) while maintaining competitive code quality. Adaptive rejection sampling provides a 3x+ speedup over alternative constrained decoding approaches. The main limitation is that the algorithm itself may not terminate due to distribution distortion in autoregressive generation.",
   "red_flags": [
     {
       "flag": "LLM-as-judge evaluation",
       "detail": "Code quality is evaluated solely by Claude-3.5-Sonnet scoring 1-100. No human evaluation of generated code quality is performed, and the reliability of this LLM judge is not validated."
     },
     {
       "flag": "Small evaluation scale",
       "detail": "Only 8 talent category prompts are used for evaluation, each run 10 times. This is a narrow evaluation setting for claims about correctness-guaranteed code generation."
     },
     {
       "flag": "No code or data release",
       "detail": "Despite being a systems paper with a concrete implementation (sLua parser, DCI game, constrained decoding algorithm), no source code or data is released for reproduction."
     }
   ],
   "cited_papers": [
     {
       "title": "Monitor-guided decoding of code LMs with static analysis of repository context",
       "authors": ["Lakshya A Agrawal", "Aditya Kanade", "Navin Goyal", "Shuvendu Lahiri", "Sriram Rajamani"],
       "year": 2023,
       "relevance": "Prior work on constrained decoding for code with semantic correctness via static analysis."
     },
     {
       "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": "Pioneered completion engine approach for semantic constrained decoding in code generation."
     },
     {
       "title": "Type-constrained code generation with language models",
       "authors": ["Niels Mundler", "Jingxuan He", "Hao Wang", "Koushik Sen", "Dawn Song", "Martin Vechev"],
       "year": 2025,
       "relevance": "Concurrent work on type-constrained decoding using prefix automata to reduce compilation errors."
     },
     {
       "title": "Efficient guided generation for LLMs",
       "authors": ["Brandon T Willard", "Remi Louf"],
       "year": 2023,
       "arxiv_id": "2307.09702",
       "relevance": "Foundational work on regex/CFG-based constrained decoding for LLMs, used as speed baseline."
     },
     {
       "title": "Automata-based constraints for language model decoding",
       "authors": ["Terry Koo", "Frederick Liu", "Luheng He"],
       "year": 2024,
       "arxiv_id": "2407.08103",
       "relevance": "Automata-based constrained decoding approach using finite-state transducers, used as speed baseline."
     },
     {
       "title": "XGrammar: Flexible and efficient structured generation engine for large language models",
       "authors": ["Yixin Dong", "Charlie F Ruan", "Yaxing Cai", "Ruihang Lai", "Ziyi Xu", "Yilong Zhao", "Tianqi Chen"],
       "year": 2024,
       "arxiv_id": "2411.15100",
       "relevance": "Structured generation engine for LLMs supporting CFG constraints."
     },
     {
       "title": "Improving LLM code generation with grammar augmentation",
       "authors": ["Shubham Ugare", "Tarun Suresh", "Hangoo Kang", "Sasa Misailovic", "Gagandeep Singh"],
       "year": 2024,
       "relevance": "Grammar-augmented approach to improve LLM code generation correctness."
     },
     {
       "title": "Grammar-aligned decoding",
       "authors": ["Kanghee Park", "Jiayu Wang", "Taylor Berg-Kirkpatrick", "Nadia Polikarpova", "Loris D'Antoni"],
       "year": 2024,
       "arxiv_id": "2405.21047",
       "relevance": "Discusses distribution distortion in grammar-constrained decoding, a key challenge addressed in this paper."
     },
     {
       "title": "GitHub Copilot AI pair programmer: Asset or liability?",
       "authors": ["Arghavan Moradi Dakhel", "Vahid Majdinasab", "Amin Nikanjam", "Foutse Khomh", "Michel C Desmarais", "Zhen Ming Jack Jiang"],
       "year": 2023,
       "relevance": "Evaluation of AI-assisted code generation tools relevant to the survey scope."
     }
   ]
 }