{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T11:52:48Z","timestamp":1791460368490,"version":"4.3.4"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T00:00:00Z","timestamp":1767830400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"name":"National Science Foundation","award":["CCF-2422214"],"award-info":[{"award-number":["CCF-2422214"]}]},{"name":"National Science Foundation","award":["CCF-2506134"],"award-info":[{"award-number":["CCF-2506134"]}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2446711"],"award-info":[{"award-number":["CCF-2446711"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DGE-2038238"],"award-info":[{"award-number":["DGE-2038238"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Microsoft Faculty Fellowship","award":["N\/A"],"award-info":[{"award-number":["N\/A"]}]},{"name":"UCSD JSOE Fellowship","award":["N\/A"],"award-info":[{"award-number":["N\/A"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2026,1,8]]},"abstract":"<jats:p>Language models (LMs) can generate code but cannot guarantee its correctness\u2014often producing outputs that violate type safety, program invariants, or other semantic properties. Constrained decoding offers a solution by restricting generation to only produce programs that satisfy user-defined properties. However, existing methods are either limited to syntactic constraints or rely on brittle, ad hoc encodings of semantic properties over token sequences rather than program structure.<\/jats:p>\n                  <jats:p>\n                    We present\n                    <jats:sc>ChopChop<\/jats:sc>\n                    , the first programmable framework for constraining the output of LMs with respect to semantic properties.\n                    <jats:sc>ChopChop<\/jats:sc>\n                    introduces a principled way to construct constrained decoders based on analyzing the space of programs a prefix represents. It formulates this analysis as a realizability problem which is solved via coinduction, connecting token-level generation with structural reasoning over programs. We demonstrate\n                    <jats:sc>ChopChop<\/jats:sc>\n                    \u2019s generality by using it to enforce (1) equivalence to a reference program and (2) type safety. Across a range of models and tasks,\n                    <jats:sc>ChopChop<\/jats:sc>\n                    improves success rates while maintaining practical decoding latency.\n                  <\/jats:p>","DOI":"10.1145\/3776708","type":"journal-article","created":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T18:59:43Z","timestamp":1767898783000},"page":"1905-1932","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["ChopChop: A Programmable Framework for Semantically Constraining the Output of Language Models"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8015-5421","authenticated-orcid":false,"given":"Shaan","family":"Nagy","sequence":"first","affiliation":[{"name":"University of California at San Diego, La Jolla, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5262-0995","authenticated-orcid":false,"given":"Timothy","family":"Zhou","sequence":"additional","affiliation":[{"name":"University of California at San Diego, La Jolla, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5571-173X","authenticated-orcid":false,"given":"Nadia","family":"Polikarpova","sequence":"additional","affiliation":[{"name":"University of California at San Diego, La Jolla, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9625-4037","authenticated-orcid":false,"given":"Loris","family":"D'Antoni","sequence":"additional","affiliation":[{"name":"University of California at San Diego, La Jolla, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,1,8]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.5555\/3666122.3667523"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/FMCAD.2013.6679385"},{"key":"e_1_3_2_4_2","unstructured":"Jacob Austin Augustus Odena Maxwell Nye Maarten Bosma Henryk Michalewski David Dohan Ellen Jiang Carrie Cai Michael Terry Quoc Le and Charles Sutton. 2021. Program Synthesis with Large Language Models. arXiv:2108.07732 [cs.PL] https:\/\/arxiv.org\/abs\/2108.07732"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02444-3_14"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44202-9_11"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","unstructured":"Jasmin Christian Blanchette Andrei Popescu and Dmitriy Traytel. 2015. Foundational extensible corecursion: a proof assistant perspective. SIGPLAN Not. 50 9 (Aug. 2015) 192-204. doi:10.1145\/2858949.2784732","DOI":"10.1145\/2858949.2784732"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/321239.321249"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-1(2:4)2005"},{"key":"e_1_3_2_10_2","unstructured":"Federico Cassano John Gouwar Daniel Nguyen Sydney Nguyen Luna Phipps-Costin Donald Pinckney Ming-Ho Yee Yangtian Zi Carolyn Jane Anderson Molly Q Feldman Arjun Guha Michael Greenberg and Abhinav Jangda. 2022. MultiPL-E: A Scalable and Extensible Approach to Benchmarking Neural Code Generation. arXiv:2208.08227 [cs.LG] https:\/\/arxiv.org\/abs\/2208.08227"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-58085-9_72"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/512950.512973"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3408990"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3385992"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/2023.emnlp-main.674"},{"key":"e_1_3_2_16_2","unstructured":"GitHub. 2022. Top Programming Languages - Octoverse 2022. Online. https:\/\/octoverse.github.com\/2022\/top-programming-languages Accessed: 2025-07-07."},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-13185-1_2"},{"key":"e_1_3_2_18_2","article-title":"The Curious Case of Neural Text Degeneration","author":"Holtzman Ari","year":"2020","unstructured":"Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. 2020. The Curious Case of Neural Text Degeneration. In International Conference on Learning Representations (ICLR). https:\/\/openreview.net\/forum?id=rygGQyrFvH","journal-title":"International Conference on Learning Representations (ICLR)"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-25540-4_18"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3385979"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.3233\/FI-2017-1473"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-37036-6_4"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/3689744"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3571216"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3720515"},{"key":"e_1_3_2_26_2","first-page":"2019","volume-title":"Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation","author":"Krishnaswami Neelakantan R.","unstructured":"Neelakantan R. Krishnaswami and Jeremy Yallop. 2019. A typed, algebraic approach to parsing. In Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation (Phoenix, AZ, USA) (PLDI 2019). Association for Computing Machinery, New York, NY, USA, 379-393. https:\/\/doi.org\/10.1145\/3314221.3314625"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1025671410623"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0023771"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/2034773.2034801"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-54572-7_6"},{"key":"e_1_3_2_31_2","unstructured":"Micha\u0142 Moskal Hudson Cooper Aaron Pham Devise Lucato Steph Wolski and Ying Xiong. 2025. guidanceai\/llguidance. https:\/\/github.com\/guidance-ai\/llguidance"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/3729274"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","unstructured":"Shaan Nagy Timothy Zhou Loris D\u2019Antoni and Nadia Polikarpova. 2025. ChopChop Artifact. doi:10.5281\/zenodo.17337963","DOI":"10.5281\/zenodo.17337963"},{"key":"e_1_3_2_34_2","unstructured":"Shaan Nagy Timothy Zhou Nadia Polikarpova and Loris D\u2019Antoni. 2025. ChopChop: a Programmable Framework for Semantically Constraining the Output of Language Models. arXiv:2509.00360 [cs.PL] https:\/\/arxiv.org\/abs\/2509.00360"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","unstructured":"Peter-Michael Osera and Steve Zdancewic. 2015. Type-and-example-directed program synthesis. SIGPLAN Not. 50 6 (June 2015) 619-630. doi:10.1145\/2813885.2738007","DOI":"10.1145\/2813885.2738007"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.52202\/079017-0774"},{"key":"e_1_3_2_37_2","unstructured":"Kanghee Park Timothy Zhou and Loris D\u2019Antoni. 2025. Flexible and Efficient Grammar-Constrained Decoding. arXiv:2502.05111 [cs.CL] https:\/\/arxiv.org\/abs\/2502.05111"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/345099.345100"},{"key":"e_1_3_2_39_2","unstructured":"Gabriel Poesia Oleksandr Polozov Vu Le Ashish Tiwari Gustavo Soares Christopher Meek and Sumit Gulwani. 2022. Synchromesh: Reliable code generation from pre-trained language models. arXiv:2201.11227 [cs.LG] https:\/\/arxiv.org\/abs\/2201.11227"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/2814270.2814310"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2025.11"},{"key":"e_1_3_2_42_2","article-title":"SynCode: LLM Generation with Grammar Augmentation","author":"Ugare Shubham","year":"2025","unstructured":"Shubham Ugare, Tarun Suresh, Hangoo Kang, Sasa Misailovic, and Gagandeep Singh. 2025. SynCode: LLM Generation with Grammar Augmentation. Transactions on Machine Learning Research (2025). https:\/\/openreview.net\/forum?id=HiUZtgAPoH","journal-title":"Transactions on Machine Learning Research"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.5555\/3666122.3668959"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/3158151"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(98)00047-5"},{"key":"e_1_3_2_46_2","unstructured":"Brandon T. Willard and R\u00e9mi Louf. 2023. Efficient Guided Generation for Large Language Models. arXiv:2307.09702 [cs.CL] https:\/\/arxiv.org\/abs\/2307.09702"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/3434304"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/3591239"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3776708","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T13:44:31Z","timestamp":1784209471000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3776708"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,8]]},"references-count":47,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2026,1,8]]}},"alternative-id":["10.1145\/3776708"],"URL":"https:\/\/doi.org\/10.1145\/3776708","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,8]]},"assertion":[{"value":"2025-07-10","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-11-06","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-01-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}