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

arXiv: https://arxiv.org/abs/2502.12466 · HTML: https://mlsanity.com/paper/2502.12466/

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning for agents, planning and code, one of 17 directions in LLM reasoning.
- Builds on 26 of its 58 references that are in the map.
- First posted on arXiv 18 Feb 2025.

## Placed in

- LLM reasoning / [Reasoning for agents, planning and code](https://mlsanity.com/lr/reasoning-for-agents-planning-and-code/)

## Builds on (most cited first, 26 of 26)

- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Think you have Solved Question Answering? Try ARC, the AI2 Reasoning Challenge](https://mlsanity.com/paper/1803.05457/) (2018)
- [Program Synthesis with Large Language Models](https://mlsanity.com/paper/2108.07732/) (2021)
- [Sparks of Artificial General Intelligence: Early experiments with GPT-4](https://mlsanity.com/paper/2303.12712/) (2023)
- [LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code](https://mlsanity.com/paper/2403.07974/) (2024)
- [Least-to-Most Prompting Enables Complex Reasoning in Large Language Models](https://mlsanity.com/paper/2205.10625/) (2022)
- [Towards Reasoning in Large Language Models: A Survey](https://mlsanity.com/paper/2212.10403/) (2022)
- [GSM-Symbolic: Understanding the Limitations of Mathematical Reasoning in Large Language Models](https://mlsanity.com/paper/2410.05229/) (2024)
- [Large Language Models Are Reasoning Teachers](https://mlsanity.com/paper/2212.10071/) (2022)
- [CRUXEval: A Benchmark for Code Reasoning, Understanding and Execution](https://mlsanity.com/paper/2401.03065/) (2024)
- [CodeNet: A Large-Scale AI for Code Dataset for Learning a Diversity of Coding Tasks](https://mlsanity.com/paper/2105.12655/) (2021)
- [Learning Performance-Improving Code Edits](https://mlsanity.com/paper/2302.07867/) (2023)
- [NExT: Teaching Large Language Models to Reason about Code Execution](https://mlsanity.com/paper/2404.14662/) (2024)
- [Large Language Models for Compiler Optimization](https://mlsanity.com/paper/2309.07062/) (2023)
- [Meta Large Language Model Compiler: Foundation Models of Compiler Optimization](https://mlsanity.com/paper/2407.02524/) (2024)
- [Code Execution with Pre-trained Language Models](https://mlsanity.com/paper/2305.05383/) (2023)
- [CodeMind: Evaluating Large Language Models for Code Reasoning](https://mlsanity.com/paper/2402.09664/) (2024)
- [AlphaTrans: A Neuro-Symbolic Compositional Approach for Repository-Level Code Translation and Validation](https://mlsanity.com/paper/2410.24117/) (2024)
- [SemCoder: Training Code Language Models with Comprehensive Semantics Reasoning](https://mlsanity.com/paper/2406.01006/) (2024)
- [KernelGPT: Enhanced Kernel Fuzzing via Large Language Models](https://mlsanity.com/paper/2401.00563/) (2023)
- [Code Simulation Challenges for Large Language Models](https://mlsanity.com/paper/2401.09074/) (2024)
- [Transformer-Based Models Are Not Yet Perfect At Learning to Emulate Structural Recursion](https://mlsanity.com/paper/2401.12947/) (2024)
- [What can Large Language Models Capture about Code Functional Equivalence?](https://mlsanity.com/paper/2408.11081/) (2024)
- [LLM-SQL-Solver: Can LLMs Determine SQL Equivalence?](https://mlsanity.com/paper/2312.10321/) (2023)
- [Can the Rookies Cut the Tough Cookie? Exploring the Use of LLMs for SQL Equivalence Checking](https://mlsanity.com/paper/2412.05561/) (2024)

## Built on by (most cited first, 24 of 24)

- [Towards Reasoning Era: A Survey of Long Chain-of-Thought for Reasoning Large Language Models](https://mlsanity.com/paper/2503.09567/) (2025)
- [CodeARC: Benchmarking Reasoning Capabilities of LLM Agents for Inductive Program Synthesis](https://mlsanity.com/paper/2503.23145/) (2025)
- [From Code Foundation Models to Agents and Applications: A Comprehensive Survey and Practical Guide to Code Intelligence](https://mlsanity.com/paper/2511.18538/) (2025)
- [Can We Predict Before Executing Machine Learning Agents?](https://mlsanity.com/paper/2601.05930/) (2026)
- [SciCoQA: Quality Assurance for Scientific Paper--Code Alignment](https://mlsanity.com/paper/2601.12910/) (2026)
- [OSVBench: Benchmarking LLMs on Specification Generation Tasks for Operating System Verification](https://mlsanity.com/paper/2504.20964/) (2025)
- [LLMs Lean on Priors, Not Programming Language Semantics](https://mlsanity.com/paper/2510.03415/) (2025)
- [RepoReasoner: Evaluating Repository-Level Code Reasoning Ability of Long-Context Language Models](https://mlsanity.com/paper/2607.25996/) (2026)
- [MatchFixAgent: Language-Agnostic Autonomous Repository-Level Code Translation Validation and Repair](https://mlsanity.com/paper/2509.16187/) (2025)
- [Towards Verified Code Reasoning by LLMs](https://mlsanity.com/paper/2509.26546/) (2025)
- [InnoGym: Benchmarking the Innovation Potential of AI Agents](https://mlsanity.com/paper/2512.01822/) (2025)
- [Evaluating Code Reasoning Abilities of Large Language Models Under Real-World Settings](https://mlsanity.com/paper/2512.14917/) (2025)
- [Exposing Weaknesses of Large Reasoning Models through Graph Algorithm Problems](https://mlsanity.com/paper/2602.06319/) (2026)
- [Decaf: Improving Neural Decompilation with Automatic Feedback and Search](https://mlsanity.com/paper/2605.11501/) (2026)
- [(How) Do Large Language Models Understand High-Level Message Sequence Charts?](https://mlsanity.com/paper/2605.13773/) (2026)
- [What are the Right Symmetries for Formal Theorem Proving?](https://mlsanity.com/paper/2605.22257/) (2026)
- [Improving LLM Code Reasoning via Semantic Equivalence Self-Play with Formal Verification](https://mlsanity.com/paper/2604.17010/) (2026)
- [ASSEMBLAGE-DEEPHISTORY: A Cross-Build Binary Dataset with Temporal Coverage](https://mlsanity.com/paper/2605.21615/) (2026)
- [Partial Contracts Suffice: Sound, LLM-Inferred Regression Verification](https://mlsanity.com/paper/2607.10291/) (2026)
- [ModelEquivBench: Certifying Multi-Relational Evaluation of LLM-Generated Optimization Models](https://mlsanity.com/paper/2607.29431/) (2026)
- [AsmEvo: Agentic Assembly-Level Optimization of AMD GPU Kernels with Functional Equivalence Verification](https://mlsanity.com/paper/2608.20711/) (2026)
- [AG-CoT: Verified Algorithmic Traces for LLM Program Synthesis on Clifford Circuits](https://mlsanity.com/paper/2609.33192/) (2026)
- [LongHarness Bench: Stress-Testing Language Model Harnesses for Long-Context Reasoning](https://mlsanity.com/paper/2609.38137/) (2026)
- [Functionally Equivalent or Not? Graph-Grounded Differential Surrogate Execution for Code Equivalence](https://mlsanity.com/paper/2610.04371/) (2026)

## Abstract (arXiv)

As large language models (LLMs) become integral to code-related tasks, a central question emerges: Do LLMs truly understand program semantics? We introduce EquiBench, a new benchmark for evaluating LLMs through equivalence checking, i.e., determining whether two programs produce identical outputs for all possible inputs. Unlike prior code generation benchmarks, this task directly tests a model's ability to reason about program semantics. EquiBench consists of 2400 program pairs across four languages and six categories. These pairs are generated through program analysis, compiler scheduling, and superoptimization, ensuring high-confidence labels, nontrivial difficulty, and full automation. We evaluate 19 state-of-the-art LLMs and find that in the most challenging categories, the best accuracies are 63.8% and 76.2%, only modestly above the 50% random baseline. Further analysis reveals that models often rely on syntactic similarity rather than exhibiting robust reasoning about program semantics, highlighting current limitations. Our code and dataset are publicly available at https://github.com/Anjiang-Wei/equibench