Elamur Research⌕
☰
home / papers / 2025 / EquiBench: Benchmarking Large Language Models' Reasoning about Program Semantics via Equivalence Checking

EquiBench: Benchmarking Large Language Models' Reasoning about Program Semantics via Equivalence Checking

Paper · 2025 · Anjiang Wei, Jiannan Cao, Ran Li et al.

Summary

EquiBench asks whether large language models actually grasp what code does or mostly react to how it looks. The test is equivalence checking: a model gets two programs and must decide whether they always give the same output for every input. The authors built 2400 labeled pairs in Python, C, CUDA and x86-64 assembly, split into six categories. All pairs come from a fully automated pipeline:

  • dead code elimination for C,
  • tensor-compiler scheduling for CUDA,
  • superoptimization for assembly,
  • algorithm changes and variable renaming in online-judge solutions.

These techniques give trustworthy labels without exhaustive execution, and they produce harder pairs than shallow syntactic edits. Across 19 state-of-the-art LLMs, the best results in the two toughest categories are only slightly above random guessing. Renaming-only pairs, by contrast, are nearly solved. The analysis indicates that models lean on surface similarity rather than semantic reasoning. The benchmark is modular and can be extended, which makes it a useful probe for code-assistant tasks such as refactoring, optimization and transpilation.

Key points

  • Coverage: 2400 program pairs, 4 languages and 6 categories (DCE, CUDA, x86-64, OJ_A, OJ_V, OJ_VA). The dataset and code are public on GitHub (Anjiang-Wei/equibench).
  • Hardest categories: top accuracies are 63.8% and 76.2%, against a 50% random baseline. Variable-renaming pairs reach up to 96.5%.
  • Best model: OpenAI o4-mini has the highest overall accuracy (82.3%) but scores only 60.8% on CUDA.
  • Prompting and fine-tuning help little:
    • Few-shot and Chain-of-Thought prompting barely change results.
    • LoRA fine-tuning of Qwen2.5-14B-Instruct on 1,200 examples raises accuracy from 59.8% to 63.2%.
    • SemCoder lifts DeepSeek-Coder-6.7B from 49.9% to 54.9%.
  • Comparison with earlier datasets: EQBENCH has only 272 pairs, and SeqCoBench uses only statement-level syntactic edits.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🏢GoogleMountain View · United States430 works · 424,363 citations🎓Stanford UniversityStanford · United States434 works · 314,419 citations🎓Massachusetts Institute of TechnologyCambridge · United States211 works · 69,000 citations🎓Nanjing UniversityNanjing · China74 works · 7,814 citations🏢IntelSanta Clara · United States15 works · 41,257 citations

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 worksInformation Systems · 1,437 works

🧭 Topics 2Research subjects and languages the work is about.Reasoning · 1,426 worksGPU & parallel computing · 19 works

Cite

Cite as Anjiang Wei, Jiannan Cao, Ran Li, Hongyu Chen, Yuhui Zhang, Ziheng Wang, Yuan Liu, Thiago S. F. X. Teixeira, Diyi Yang, Ke Wang and Alex Aiken. 2025. EquiBench: Benchmarking Large Language Models' Reasoning about Program Semantics via Equivalence Checking. Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2025.emnlp-main.1718

@inproceedings{wei2025equibench,
  title = {{EquiBench: Benchmarking Large Language Models' Reasoning about Program Semantics via Equivalence Checking}},
  author = {Anjiang Wei, Jiannan Cao, Ran Li, Hongyu Chen, Yuhui Zhang, Ziheng Wang, Yuan Liu, Thiago S. F. X. Teixeira, Diyi Yang, Ke Wang and Alex Aiken},
  booktitle = {Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing},
  year = {2025},
  doi = {10.18653/v1/2025.emnlp-main.1718},
  url = {https://doi.org/10.18653/v1/2025.emnlp-main.1718}
}

References

58 references, 13 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoc Le, and 1 others. 2021. Program synthesis with large language models. arXiv preprint arXiv:2108.07732.
  2. Sahar Badihi, Faridah Akinotcho, Yi Li, and Julia Rubin. 2020. Ardiff: scaling program equivalence checking via iterative abstraction and refinement of common code. In Proceedings of the 28th ACM joint meeting on European software engineering conference and symposium on the foundations of software e… find
  3. Sahar Badihi, Yi Li, and Julia Rubin. 2021. Eqbench: A dataset of equivalent and non-equivalent program pairs. In 2021 IEEE/ACM 18th International Conference on Mining Software Repositories (MSR), pages 610–614. IEEE. find
  4. Sébastien Bubeck, Varun Chandrasekaran, Ronen Eldan, Johannes Gehrke, Eric Horvitz, Ece Kamar, Peter Lee, Yin Tat Lee, Yuanzhi Li, Scott Lundberg, and 1 others. 2023. Sparks of artificial general intelligence: Early experiments with gpt-4. arXiv preprint arXiv:2303.12712.
  5. Liangyu Chen, Bo Li, Sheng Shen, Jingkang Yang, Chunyuan Li, Kurt Keutzer, Trevor Darrell, and Ziwei Liu. 2024. Large language models are visual reasoning coordinators. Advances in Neural Information Processing Systems, 36. find
  6. Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde De Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, and 1 others. 2021. Evaluating large language models trained on code. arXiv preprint arXiv:2107.03374.
  7. Minyu Chen, Guoqiang Li, Ling-I Wu, and Ruibang Liu. 2025. Dce-llm: Dead code elimination with large language models. In Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), pa… find
  8. Tianqi Chen, Thierry Moreau, Ziheng Jiang, Lianmin Zheng, Eddie Yan, Haichen Shen, Meghan Cowan, Leyuan Wang, Yuwei Hu, Luis Ceze, and 1 others. 2018. Tvm: An automated end-to-end optimizing compiler for deep learning. In 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18)…
  9. Berkeley Churchill, Oded Padon, Rahul Sharma, and Alex Aiken. 2019. Semantic program alignment for equivalence checking. In Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 1027– 1040. find
  10. Peter Clark, Isaac Cowhey, Oren Etzioni, Tushar Khot, Ashish Sabharwal, Carissa Schoenick, and Oyvind Tafjord. 2018. Think you have solved question answering? try arc, the ai2 reasoning challenge. arXiv preprint arXiv:1803.05457.
  11. Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, and 1 others. 2021. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168.
  12. Chris Cummins, Volker Seeker, Dejan Grubisic, Mostafa Elhoushi, Youwei Liang, Baptiste Roziere, Jonas Gehring, Fabian Gloeckle, Kim Hazelwood, Gabriel Synnaeve, and 1 others. 2023. Large language models for compiler optimization. arXiv preprint arXiv:2309.07062. find
  13. Chris Cummins, Volker Seeker, Dejan Grubisic, Baptiste Roziere, Jonas Gehring, Gabriel Synnaeve, and Hugh Leather. 2024. Meta large language model compiler: Foundation models of compiler optimization. arXiv preprint arXiv:2407.02524. find
  14. Manjeet Dahiya and Sorav Bansal. 2017. Black-box equivalence checking across compiler optimizations. In Asian Symposium on Programming Languages and Systems, pages 127–147. Springer. find
  15. Yinlin Deng, Chunqiu Steven Xia, Haoran Peng, Chenyuan Yang, and Lingming Zhang. 2023. Large language models are zero-shot fuzzers: Fuzzing deep-learning libraries via large language models. In Proceedings of the 32nd ACM SIGSOFT international symposium on software testing and analysis, pages 423–43… find
  16. Haoran Ding, Zhaoguo Wang, Yicun Yang, Dexin Zhang, Zhenglin Xu, Haibo Chen, Ruzica Piskac, and Jinyang Li. 2023. Proving query equivalence using linear integer arithmetic. Proceedings of the ACM on Management of Data, 1(4):1–26. find
  17. Yangruibo Ding, Jinjun Peng, Marcus J Min, Gail Kaiser, Junfeng Yang, and Baishakhi Ray. 2024. Semcoder: Training code language models with comprehensive semantics reasoning. arXiv preprint arXiv:2406.01006. — [arXiv:2406.01006](https://arxiv.org/abs/2406.01006) find
  18. Dennis Felsing, Sarah Grebing, Vladimir Klebanov, Philipp Rümmer, and Mattias Ulbrich. 2014. Automating regression verification. In Proceedings of the 29th ACM/IEEE international conference on Automated software engineering, pages 349–360. find
  19. Daniel Flook. 2025. Python variable renaming tool. https://github.com/dflook/python-minifier. ↗
  20. Zeyu Gao, Hao Wang, Yuanda Wang, and Chao Zhang. 2024. Virtual compiler is all you need for assembly code search. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 3040–3051. find
  21. Alex Gu, Baptiste Rozière, Hugh Leather, Armando Solar-Lezama, Gabriel Synnaeve, and Sida I Wang. 2024. Cruxeval: A benchmark for code reasoning, understanding and execution. arXiv preprint arXiv:2401.03065.
  22. Shubhani Gupta, Aseem Saxena, Anmol Mahajan, and Sorav Bansal. 2018. Effective use of smt solvers for program equivalence checking through invariant-sketching and query-decomposition. In International Conference on Theory and Applications of Satisfiability Testing, pages 365–382. Springer. find
  23. Namgyu Ho, Laura Schmid, and Se-Young Yun. 2022. Large language models are reasoning teachers. arXiv preprint arXiv:2212.10071.
  24. Jie Huang and Kevin Chen-Chuan Chang. 2022. Towards reasoning in large language models: A survey. arXiv preprint arXiv:2212.10403.
  25. Ali Reza Ibrahimzada, Kaiyao Ke, Mrigank Pawagi, Muhammad Salman Abid, Rangeet Pan, Saurabh Sinha, and Reyhaneh Jabbarvand. 2024. Repository-level compositional code translation and validation. arXiv preprint arXiv:2410.24117. — [arXiv:2410.24117](https://arxiv.org/abs/2410.24117) find
  26. Naman Jain, King Han, Alex Gu, Wen-Ding Li, Fanjia Yan, Tianjun Zhang, Sida Wang, Armando Solar-Lezama, Koushik Sen, and Ion Stoica. 2024. Livecodebench: Holistic and contamination free evaluation of large language models for code. arXiv preprint arXiv:2403.07974.
  27. Lingxiao Jiang and Zhendong Su. 2009. Automatic mining of functionally equivalent code fragments via random testing. In Proceedings of the eighteenth international symposium on Software testing and analysis, pages 81–92. find
  28. Jason R Koenig, Oded Padon, and Alex Aiken. 2021. Adaptive restarts for stochastic synthesis. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation, pages 696–709. find
  29. Emanuele La Malfa, Christoph Weinhuber, Orazio Torre, Fangru Lin, Samuele Marro, Anthony Cohn, Nigel Shadbolt, and Michael Wooldridge. 2024. Code simulation challenges for large language models. arXiv preprint arXiv:2401.09074. — [arXiv:2401.09074](https://arxiv.org/abs/2401.09074) find
  30. Chris Lattner and Vikram Adve. 2004. Llvm: A compilation framework for lifelong program analysis & transformation. In International symposium on code generation and optimization, 2004. find
  31. Changshu Liu, Shizhuo Dylan Zhang, Ali Reza Ibrahimzada, and Reyhaneh Jabbarvand. 2024. Codemind: A framework to challenge large language models for code reasoning. arXiv preprint arXiv:2402.09664. — [arXiv:2402.09664](https://arxiv.org/abs/2402.09664) find
  32. Chenxiao Liu, Shuai Lu, Weizhu Chen, Daxin Jiang, Alexey Svyatkovskiy, Shengyu Fu, Neel Sundaresan, and Nan Duan. 2023. Code execution with pre-trained language models. arXiv preprint arXiv:2305.05383. find
  33. Shuai Lu, Daya Guo, Shuo Ren, Junjie Huang, Alexey Svyatkovskiy, Ambrosio Blanco, Colin Clement, Dawn Drain, Daxin Jiang, Duyu Tang, Ge Li, Lidong Zhou, Linjun Shou, Long Zhou, Michele Tufano, MING GONG, Ming Zhou, Nan Duan, Neel Sundaresan, and 3 others. 2021. CodeXGLUE: A machine learning benchmar… find
  34. Nickil Maveli, Antonio Vergari, and Shay B Cohen. 2024. What can large language models capture about code functional equivalence? arXiv preprint arXiv:2408.11081. find
  35. Iman Mirzadeh, Keivan Alizadeh, Hooman Shahrokhi, Oncel Tuzel, Samy Bengio, and Mehrdad Farajtabar. 2024. Gsm-symbolic: Understanding the limitations of mathematical reasoning in large language models. arXiv preprint arXiv:2410.05229.
  36. Federico Mora, Yi Li, Julia Rubin, and Marsha Chechik. 2018. Client-specific equivalence checking. In Proceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering, pages 441–451. find
  37. Ansong Ni, Miltiadis Allamanis, Arman Cohan, Yinlin Deng, Kensen Shi, Charles Sutton, and Pengcheng Yin. 2024. Next: Teaching large language models to reason about code execution. arXiv preprint arXiv:2404.14662. find
  38. Shankara Pailoor, Yuepeng Wang, and Işıl Dillig. 2024. Semantic code refactoring for abstract data types. Proceedings of the ACM on Programming Languages, 8(POPL):816–847. find
  39. Rangeet Pan, Ali Reza Ibrahimzada, Rahul Krishna, Divya Sankar, Lambert Pouguem Wassi, Michele Merler, Boris Sobolev, Raju Pavuluri, Saurabh Sinha, and Reyhaneh Jabbarvand. 2024. Lost in translation: A study of bugs introduced by large language models while translating code. In Proceedings of the IE… find
  40. Ruchir Puri, David S Kung, Geert Janssen, Wei Zhang, Giacomo Domeniconi, Vladimir Zolotov, Julian Dolby, Jie Chen, Mihir Choudhury, Lindsey Decker, and 1 others. 2021. Codenet: A large-scale ai for code dataset for learning a diversity of coding tasks. arXiv preprint arXiv:2105.12655. find
  41. Eric Schkufza, Rahul Sharma, and Alex Aiken. 2013. Stochastic superoptimization. ACM SIGARCH Computer Architecture News, 41(1):305–316. find
  42. Chenyuan Yang, Zijie Zhao, and Lingming Zhang. 2023. Kernelgpt: Enhanced kernel fuzzing via large language models. arXiv preprint arXiv:2401.00563. — [arXiv:2401.00563](https://arxiv.org/abs/2401.00563) find
  43. Saul Schleimer, Daniel S Wilkerson, and Alex Aiken. 2003. Winnowing: local algorithms for document fingerprinting. In Proceedings of the 2003 ACM SIGMOD international conference on Management of data, pages 76–85. find
  44. Xuejun Yang, Yang Chen, Eric Eide, and John Regehr. 2011. Finding and understanding bugs in c compilers. In Proceedings of the 32nd ACM SIGPLAN conference on Programming language design and implementation, pages 283–294. find
  45. Rahul Sharma, Eric Schkufza, Berkeley Churchill, and Alex Aiken. 2013. Data-driven equivalence checking. In Proceedings of the 2013 ACM SIGPLAN international conference on Object oriented programming systems languages & applications, pages 391–406. find
  46. Zhen Yang, Fang Liu, Zhongxing Yu, Jacky Wai Keung, Jia Li, Shuo Liu, Yifan Hong, Xiaoxue Ma, Zhi Jin, and Ge Li. 2024b. Exploring and unleashing the power of large language models in automated code translation. Proceedings of the ACM on Software Engineering, 1(FSE):1585–1608. find
  47. Alexander Shypula, Aman Madaan, Yimeng Zeng, Uri Alon, Jacob Gardner, Milad Hashemi, Graham Neubig, Parthasarathy Ranganathan, Osbert Bastani, and Amir Yazdanbakhsh. 2023. Learning performance-improving code edits. arXiv preprint arXiv:2302.07867. find
  48. Dylan Zhang, Curt Tigges, Zory Zhang, Stella Biderman, Maxim Raginsky, and Talia Ringer. 2024. Transformer-based models are not yet perfect at learning to emulate structural recursion. arXiv preprint arXiv:2401.12947. — [arXiv:2401.12947](https://arxiv.org/abs/2401.12947) find
  49. Danilo Silva and Marco Tulio Valente. 2017. Refdiff: Detecting refactorings in version histories. In 2017 IEEE/ACM 14th International Conference on Mining Software Repositories (MSR), pages 269–279. IEEE. find
  50. Fuheng Zhao, Lawrence Lim, Ishtiyaque Ahmad, Divyakant Agrawal, and Amr El Abbadi. 2023. Llm-sql-solver: Can llms determine sql equivalence? arXiv preprint arXiv:2312.10321. — [arXiv:2312.10321](https://arxiv.org/abs/2312.10321) find
  51. Rajat Singh and Srikanta Bedathur. 2024. Exploring the use of llms for sql equivalence checking. arXiv preprint arXiv:2412.05561. — [arXiv:2412.05561](https://arxiv.org/abs/2412.05561) find
  52. Lianmin Zheng, Ruochen Liu, Junru Shao, Tianqi Chen, Joseph E Gonzalez, Ion Stoica, and Ameer Haj Ali. 2021. Tenset: A large-scale program performance dataset for learned tensor compilers. In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 1). find
  53. Theodoros Theodoridis, Manuel Rigger, and Zhendong Su. 2022. Finding missed optimizations through the lens of dead code elimination. In Proceedings of the 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, pages 697–709. find
  54. Zhao Tian, Honglin Shu, Dong Wang, Xuejie Cao, Yasutaka Kamei, and Junjie Chen. 2024. Large language models for equivalent mutant detection: How far are we? In Proceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis, pages 1733–1745. find
  55. Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoc Le, and 1 others. 2022. Least-to-most prompting enables complex reasoning in large language models. arXiv preprint arXiv:2205.10625.
  56. Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, and 1 others. 2022. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824– 24837.
  57. Martin White, Michele Tufano, Christopher Vendome, and Denys Poshyvanyk. 2016. Deep learning code fragments for code clone detection. In Proceedings of the 31st IEEE/ACM international conference on automated software engineering, pages 87–98. find
  58. Chenyuan Yang, Yinlin Deng, Runyu Lu, Jiayi Yao, Jiawei Liu, Reyhaneh Jabbarvand, and Lingming Zhang. 2024a. Whitefox: White-box compiler fuzzing empowered by large language models. Proceedings of the ACM on Programming Languages, 8(OOPSLA2):709–735. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/wei-2025-equibench-benchmarking-large-language-models/