{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T11:03:18Z","timestamp":1784199798269,"version":"3.55.0"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"PLDI","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2025,6,10]]},"abstract":"<jats:p>\n                    Domain-specific languages (DSLs) for machine learning are revolutionizing the speed and efficiency of machine learning workloads as they enable users easy access to high-performance compiler optimizations and accelerators. However, to take advantage of these capabilities, a user must first translate their legacy code from the language it is currently written in, into the new DSL. The process of automatically lifting code into these DSLs has been identified by several recent works, which propose program synthesis as a solution. However, synthesis is expensive and struggles to scale without carefully designed and hard-wired heuristics. In this paper, we present an approach for lifting that combines an enumerative synthesis approach with a Large Language Model used to\n                    <jats:italic toggle=\"yes\">automatically<\/jats:italic>\n                    learn the domain-specific heuristics for program lifting, in the form of a probabilistic grammar. Our approach outperforms the state-of-the-art tools in this area, despite only using\n                    <jats:italic toggle=\"yes\">learned<\/jats:italic>\n                    heuristics.\n                  <\/jats:p>","DOI":"10.1145\/3729330","type":"journal-article","created":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T16:02:27Z","timestamp":1749830547000},"page":"1984-2006","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Guided Tensor Lifting"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-4619-3476","authenticated-orcid":false,"given":"Yixuan","family":"Li","sequence":"first","affiliation":[{"name":"University of Edinburgh, Edinburgh, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2767-1130","authenticated-orcid":false,"given":"Jos\u00e9 Wesley de Souza","family":"Magalh\u00e3es","sequence":"additional","affiliation":[{"name":"University of Edinburgh, Edinburgh, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5774-3970","authenticated-orcid":false,"given":"Alexander","family":"Brauckmann","sequence":"additional","affiliation":[{"name":"University of Edinburgh, Edinburgh, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1619-5052","authenticated-orcid":false,"given":"Michael F. P.","family":"O'Boyle","sequence":"additional","affiliation":[{"name":"University of Edinburgh, Edinburgh, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9032-7661","authenticated-orcid":false,"given":"Elizabeth","family":"Polgreen","sequence":"additional","affiliation":[{"name":"University of Edinburgh, Edinburgh, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,13]]},"reference":[{"key":"e_1_3_2_2_1","doi-asserted-by":"publisher","unstructured":"Mart\u00edn Abadi Ashish Agarwal Paul Barham Eugene Brevdo Zhifeng Chen Craig Citro Greg S. Corrado Andy Davis Jeffrey Dean Matthieu Devin Sanjay Ghemawat Ian Goodfellow Andrew Harp Geoffrey Irving Michael Isard Yangqing Jia Rafal Jozefowicz Lukasz Kaiser Manjunath Kudlur Josh Levenberg Dan Mane Rajat Monga Sherry Moore Derek Murray Chris Olah Mike Schuster Jonathon Shlens Benoit Steiner Ilya Sutskever Kunal Talwar Paul Tucker Vincent Vanhoucke Vijay Vasudevan Fernanda Viegas Oriol Vinyals Pete Warden Martin Wattenberg Martin Wicke Yuan Yu and Xiaoqiang Zheng. 2016. TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems. doi:10.48550\/arXiv.1603.04467 arXiv:1603.04467 [cs.DC]","DOI":"10.48550\/arXiv.1603.04467"},{"key":"e_1_3_2_3_1","unstructured":"Matej Balog Alexander L. Gaunt Marc Brockschmidt Sebastian Nowozin and Daniel Tarlow. 2017. DeepCoder: Learning to Write Programs. arXiv:1611.01989 [cs.LG] https:\/\/arxiv.org\/abs\/1611.01989."},{"key":"e_1_3_2_4_1","doi-asserted-by":"publisher","unstructured":"Shraddha Barke Emmanuel Anaya Gonzalez Saketh Ram Kasibatla Taylor Berg-Kirkpatrick and Nadia Polikarpova. 2024. HYSYNTH: Context-Free LLM Approximation for Guiding Program Synthesis. arXiv preprint arXiv:2405.15880 (2024). doi:10.48550\/arXiv.2405.15880","DOI":"10.48550\/arXiv.2405.15880"},{"key":"e_1_3_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3360594"},{"key":"e_1_3_2_6_1","unstructured":"Sahil Bhatia Jie Qiu Sanjit A Seshia and Alvin Cheung. 2024. Can LLMs Perform Verified Lifting of Code? Technical Report (2024). https:\/\/www2.eecs.berkeley.edu\/Pubs\/TechRpts\/2024\/EECS-2024-11.pdf"},{"key":"e_1_3_2_7_1","unstructured":"James Bradbury Roy Frostig Peter Hawkins Matthew James Johnson Chris Leary Dougal Maclaurin George Necula Adam Paszke Jake VanderPlas Skye Wanderman-Milne and Qiao Zhang. 2018. JAX: composable transformations of Python+NumPy programs. http:\/\/github.com\/google\/jax"},{"key":"e_1_3_2_8_1","doi-asserted-by":"publisher","unstructured":"Alexander Brauckmann Elizabeth Polgreen Tobias Grosser and Michael F. P. O\u2019Boyle. 2024. mlirSynth: Automatic Retargetable Program Raising in Multi-Level IR using Program Synthesis. In Proceedings of the 32nd International Conference on Parallel Architectures and Compilation Techniques (Vienna AE Austria) (PACT \u201923). IEEE Press 39\u201350. doi:10.1109\/PACT58117.2023.00012","DOI":"10.1109\/PACT58117.2023.00012"},{"key":"e_1_3_2_9_1","doi-asserted-by":"publisher","unstructured":"Xinyun Chen Chang Liu and Dawn Song. 2018. Tree-to-Tree Neural Networks for Program Translation. In Proceedings of the 32nd International Conference on Neural Information Processing Systems (Montr\u00e9al Canada) (NIPS\u201918). Curran Associates Inc. Red Hook NY USA 2552\u20132562. doi:10.5555\/3327144.3327180","DOI":"10.5555\/3327144.3327180"},{"key":"e_1_3_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3459010"},{"key":"e_1_3_2_11_1","unstructured":"Mehdi Drissi Olivia Watkins Aditya Khant Vivaswat Ojha Pedro Sandoval Rakia Segev Eric Weiner and Robert Keller. 2018. Program Language Translation Using a Grammar-Driven Tree-to-Tree Model. arXiv:1807.01784 [cs.LG]. https:\/\/arxiv.org\/abs\/1807.01784"},{"key":"e_1_3_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/643470.643472"},{"key":"e_1_3_2_13_1","doi-asserted-by":"publisher","unstructured":"Philip Ginsbach Bruce Collie and Michael FP O\u2019Boyle. 2020. Automatically harnessing sparse acceleration. In Proceedings of the 29th International Conference on Compiler Construction. 179\u2013190. doi:10.1145\/3377555.3377893","DOI":"10.1145\/3377555.3377893"},{"key":"e_1_3_2_14_1","unstructured":"Awni Hannun Jagrit Digani Angelos Katharopoulos and Ronan Collobert. 2023. MLX: Efficient and flexible machine learning on Apple silicon. https:\/\/github.com\/ml-explore"},{"key":"e_1_3_2_15_1","doi-asserted-by":"publisher","unstructured":"Charles R Harris K Jarrod Millman St\u00e9fan J Van Der Walt Ralf Gommers Pauli Virtanen David Cournapeau Eric Wieser Julian Taylor Sebastian Berg Nathaniel J Smith et al. 2020. Array programming with NumPy. Nature 585 7825 (2020) 357\u2013362. doi:10.1038\/s41586-020-2649-2","DOI":"10.1038\/s41586-020-2649-2"},{"key":"e_1_3_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2980983.2908117"},{"key":"e_1_3_2_17_1","doi-asserted-by":"publisher","unstructured":"Fredrik Kjolstad Stephen Chou David Lugato Shoaib Kamil and Saman Amarasinghe. 2017. Taco: A tool to generate tensor algebra kernels. In 2017 32nd IEEE\/ACM International Conference on Automated Software Engineering (ASE). 943\u2013948. doi:10.1109\/ASE.2017.8115709","DOI":"10.1109\/ASE.2017.8115709"},{"key":"e_1_3_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133901"},{"key":"e_1_3_2_19_1","doi-asserted-by":"publisher","unstructured":"Daniel Kroening and Michael Tautschnig. 2014. CBMC \u2013 C Bounded Model Checker. In Tools and Algorithms for the Construction and Analysis of Systems Erika \u00c1brah\u00e1m and Klaus Havelund (Eds.). Springer Berlin Heidelberg Berlin Heidelberg 389\u2013391. doi:10.1007\/978-3-642-54862-8_26","DOI":"10.1007\/978-3-642-54862-8_26"},{"key":"e_1_3_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3656445"},{"key":"e_1_3_2_21_1","unstructured":"Chris Lattner Mehdi Amini Uday Bondhugula Albert Cohen Andy Davis Jacques Pienaar River Riddle Tatiana Shpeisman Nicolas Vasilache and Oleksandr Zinenko. 2020. MLIR: A Compiler Infrastructure for the End of Moore\u2019s Law. arXiv:2002.11054 [cs.PL] https:\/\/arxiv.org\/abs\/2002.11054"},{"key":"e_1_3_2_22_1","doi-asserted-by":"publisher","unstructured":"Woosuk Lee Kihong Heo Rajeev Alur and Mayur Naik. 2018. Accelerating search-based program synthesis using learned probabilistic models. In Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation (Philadelphia PA USA) (PLDI 2018). Association for Computing Machinery New York NY USA 436\u2013449. doi:10.1145\/3192366.3192410","DOI":"10.1145\/3192366.3192410"},{"key":"e_1_3_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3296979.3192410"},{"key":"e_1_3_2_24_1","doi-asserted-by":"publisher","unstructured":"Yixuan Li Julian Parsert and Elizabeth Polgreen. 2024. Guiding Enumerative Program Synthesis with Large Language Models. In Computer Aided Verification (Montreal Canada) (CAV 2024). Springer Nature Switzerland Cham 280\u2013301. doi:10.1007\/978-3-031-65630-9_15","DOI":"10.1007\/978-3-031-65630-9_15"},{"key":"e_1_3_2_25_1","unstructured":"llama 2024. llamacpp. https:\/\/github.com\/leloykun\/llama2.cpp\/. Accessed: 2024\u201301\u201319."},{"key":"e_1_3_2_26_1","doi-asserted-by":"publisher","unstructured":"Jos\u00e9 Wesley de Souza Magalh\u00e3es Jackson Woodruff Elizabeth Polgreen and Michael F. P. O\u2019Boyle. 2023. C2TACO: Lifting Tensor Code to TACO. In Proceedings of the 22nd ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences (Cascais Portugal) (GPCE 2023). Association for Computing Machinery New York NY USA 42\u201356. doi:10.1145\/3624007.3624053","DOI":"10.1145\/3624007.3624053"},{"key":"e_1_3_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3527315"},{"key":"e_1_3_2_28_1","doi-asserted-by":"publisher","unstructured":"Pablo Antonio Mart\u00ednez Jackson Woodruff Jordi Armengol-Estap\u00e9 Gregorio Bernab\u00e9 Jos\u00e9 Manuel Garc\u00eda and Michael F. P. O\u2019Boyle. 2023. Matching Linear Algebra and Tensor Code to Specialized Hardware Accelerators. In Proceedings of the 32nd ACM SIGPLAN International Conference on Compiler Construction (Montr\u00e9al QC Canada) (CC 2023). Association for Computing Machinery New York NY USA 85\u201397. doi:10.1145\/3578360.3580262","DOI":"10.1145\/3578360.3580262"},{"key":"e_1_3_2_29_1","doi-asserted-by":"publisher","unstructured":"Daye Nam Baishakhi Ray Seohyun Kim Xianshan Qu and Satish Chandra. 2022. Predictive synthesis of API-centric code. In Proceedings of the 6th ACM SIGPLAN International Symposium on Machine Programming (San Diego CA USA) (MAPS 2022). Association for Computing Machinery New York NY USA 40\u201349. doi:10.1145\/3520312.3534866","DOI":"10.1145\/3520312.3534866"},{"key":"e_1_3_2_30_1","unstructured":"Maxwell Nye Luke Hewitt Joshua Tenenbaum and Armando Solar-Lezama. 2019. Learning to Infer Program Sketches. In Proceedings of the 36th International Conference on Machine Learning (Proceedings of Machine Learning Research Vol. 97) Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.). PMLR 4861\u20134870. https:\/\/proceedings.mlr.press\/v97\/nye19a.html."},{"key":"e_1_3_2_31_1","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.2001.1815"},{"key":"e_1_3_2_32_1","unstructured":"Augustus Odena Kensen Shi David Bieber Rishabh Singh Charles Sutton and Hanjun Dai. 2021. BUSTLE: Bottom-Up Program Synthesis Through Learning-Guided Exploration. arXiv:2007.14381 [cs.PL] https:\/\/arxiv.org\/abs\/2007.14381."},{"key":"e_1_3_2_33_1","unstructured":"Theo X. Olausson Jeevana Priya Inala Chenglong Wang Jianfeng Gao and Armando Solar-Lezama. 2024. Is Self-Repair a Silver Bullet for Code Generation?. In The Twelfth International Conference on Learning Representations. https:\/\/openreview.net\/forum?id=y0GJXRungR."},{"key":"e_1_3_2_34_1","unstructured":"OpenAI. 2024. GPT-4 Technical Report. arXiv:2303.08774 [cs.CL] https:\/\/arxiv.org\/abs\/2303.08774."},{"key":"e_1_3_2_35_1","doi-asserted-by":"publisher","unstructured":"Adam Paszke Sam Gross Francisco Massa Adam Lerer James Bradbury Gregory Chanan Trevor Killeen Zeming Lin Natalia Gimelshein Luca Antiga Alban Desmaison Andreas Kopf Edward Yang Zachary DeVito Martin Raison Alykhan Tejani Sasank Chilamkurthy Benoit Steiner Lu Fang Junjie Bai and Soumith Chintala. 2019. PyTorch: An Imperative Style High-Performance Deep Learning Library. In Advances in Neural Information Processing Systems Vol. 32. Curran Associates Inc. 8026\u20138037. doi:10.5555\/3454287.3455008.","DOI":"10.5555\/3454287.3455008"},{"key":"e_1_3_2_36_1","doi-asserted-by":"publisher","unstructured":"Jie Qiu Colin Cai Sahil Bhatia Niranjan Hasabnis Sanjit A. Seshia and Alvin Cheung. 2024. Tenspiler: A Verified-Lifting-Based Compiler for Tensor Operations. In 38th European Conference on Object-Oriented Programming (ECOOP 2024) (Leibniz International Proceedings in Informatics (LIPIcs) Vol. 313) Jonathan Aldrich and Guido Salvaneschi (Eds.). Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik Dagstuhl Germany 32:1\u201332:28. doi:10.4230\/LIPIcs.ECOOP.2024.32","DOI":"10.4230\/LIPIcs.ECOOP.2024.32"},{"key":"e_1_3_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2462176"},{"key":"e_1_3_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3517034"},{"key":"e_1_3_2_39_1","unstructured":"Kensen Shi Hanjun Dai Kevin Ellis and Charles Sutton. 2022. CrossBeam: Learning to Search in Bottom-Up Program Synthesis. arXiv:2203.10452 [cs.LG] https:\/\/arxiv.org\/abs\/2203.10452"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3729330","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T10:03:16Z","timestamp":1784196196000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3729330"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,10]]},"references-count":38,"journal-issue":{"issue":"PLDI","published-print":{"date-parts":[[2025,6,10]]}},"alternative-id":["10.1145\/3729330"],"URL":"https:\/\/doi.org\/10.1145\/3729330","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,10]]},"assertion":[{"value":"2024-11-15","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-06","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-06-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}