cs.AIOct 3, 2026

Functionally Equivalent or Not? Graph-Grounded Differential Surrogate Execution for Code Equivalence

Authors: Amit Kachroo, Like Hui, Haitao Mao, Yuhao Zhang, Nguyen Vo

Organizations: AWS AI Labs Santa Clara, California, USA · AWS AI Labs New York, USA

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Determining whether two programs are functionally equivalent is central to code modernization, patch validation, refactoring, and code-generation evaluation. Yet the usual signals are incomplete: tests cover only finite inputs, textual similarity confuses implementation with behavior, and unconstrained LLM judgments are difficult to audit. Direct execution is often impossible when a program depends on an obsolete, licensed, unavailable, or unsafe environment. We introduce FEAgent, a selective equivalence assessor agent that combines typed program-graph evidence with differential surrogate execution. FEAgent first aligns public interfaces and behaviorally relevant graph anchors, then issues bounded queries over call-flow, control-flow, data-flow, type, import, and effect relations. Next, a branch-aware generator agent proposes discriminating inputs, and two blinded LLM surrogates independently predict source and target observables. Every claim and predicted divergence is recorded in an evidence ledger. A deterministic reconciler then returns EQUIVALENT, INEQUIVALENT, or UNCLEAR rather than forcing a verdict when paths are uncovered or evidence conflicts. We evaluate FEAgent on function-level equivalence and repository-level bug patches, where the existing oracle is a benchmark label or a passing test suite. Every disagreement with that oracle is adjudicated by direct execution, revealing errors in benchmark labels and behavioral divergences missed by unit-test-only scoring. On EquiBench, execution confirms FEAgent's disagreements with published labels on 216 of 1,200 evaluated pairs (18.0%); on SWE-bench Verified, 94 of 331 test-passing agent patches (28.4%) diverge from the reference patch. FEAgent thus serves as an audit layer between testing and formal verification, keeping its evidence reviewable and its uncertainty explicit without claiming a proof of equivalence.

Figures & tables

Figure 1: Graph-grounded differential assessment: FEAgent uses graph evidence to guide branch-targeting inputs; blinded surrogates independently predict source and target traces, and deterministic reconciliation returns Equivalent , Inequivalent , or Unclear judgment.
Figure 2: Combined algorithm–data divergence (OJ-VA case 370): For n=4n=4 and [0,0,2,2][0,0,2,2] , multiplicity-only validation discards the Counter keys and returns 44 , whereas exact sequence validation rejects the values and returns 00 .
Figure 3: Algorithmic divergence from numeric semantics (OJ-A case 10): For a benchmark-labeled equivalent pair, a=10a=10 , b=3b=3 , and n=16n=16 produce 4848 versus 5050 : replacing exact long division with rounded floating-point conversion changes the digit sum.
Audit SetEvaluatedDisagreement RateVerified GenuineECD
OJ_A400116 (29%)111 (95.7%)27.8%
OJ_VA400109 (27.25%)105 (96.3%)26.3%
OJ_V4005 (1.25%)0 (0%)0%
EquiBench Total1,200230 (19.2%)216 (93.9%)18.0%
SWE-bench Verified331109 (32.9%)94 (86.2%)28.4%
Table 1: Execution-grounded audit on EquiBench and SWE-bench Verified. ECD == execution-confirmed divergences / evaluated cases as defined in 2 . On SWE-bench Verified we evaluate the 331 instances resolved (i.e. every patch passes its tests) by mini-SWE-agent with GPT-OSS-120B.
Figure 4: Boundary-reference divergence (OJ-VA case 288): On {#..,...,...}\{\texttt{\#..},\texttt{...},\texttt{...}\} , boundary clamping makes the corner cell count itself as a neighbor and output Yes , whereas padded neighbor references correctly output No .
Figure 5: Graph-guided divergence in django-11066 . (a) Only guard-satisfying inputs reach clear_cache . (b) Both revisions return None , but the candidate clears only the default alias.
Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

FamilyRequired valuesCore attributes
Nodesrepository, file, namespace, type, function, parameter, statement, variable, literal, external symbolstable ID, language, qualified name, source span, parser confidence
Structural edgescontains, declares, imports, inherits, overridessource, target, resolution status
Behavioral edgescalls, CFG successor, control-depends, defines, uses, reads, writes, returns, throws, mutates, emits effectsource, target, guard/label, static/dynamic confidence
Function attributessignature, visibility, modifiers, return type, effect summarynormalized and original forms
Statement attributessyntax kind, branch predicate, constants, operatorssource text hash and span
External attributespackage/module, version constraint, contract sourceresolved, unresolved, or assumed
Appendix
Table 2: Minimum typed program-graph schema. Front ends may add language-specific nodes and relations, but cannot silently omit unresolved entities.
FieldRepresentationDefault comparator
Returntyped, canonical valueexact after type-aware canonicalization; declared tolerance for floating point
Exceptiontype, message projection, phaseexact type; configurable message projection
External effectsordered events over files, network, database, logs, processes, callbacksorder-sensitive unless specification declares commutativity
Input mutationbefore/after reachable object projectionstructural equality with alias identities retained
Persistent stateselected state projectiontask-defined equality
Terminationnormal, exception, timeout, divergenceexact class under resource policy τ\tau
Appendix
Table 3: Observable fields and default comparison behavior. Every task manifest explicitly enables, disables, or overrides each field.
DatasetLanguagePairsEquiv.Inequiv.Labeling source
OJ_APython400200200EquiBench [ Wei et al., 2025 ]
OJ_VPython400200200EquiBench [ Wei et al., 2025 ]
OJ_VAPython400200200EquiBench [ Wei et al., 2025 ]
Appendix
Table 4: EquiBench subsets used in the study. Equiv./Inequiv. give the published class balance.
More in this topic

Differential Testing

Differential testing compares programs or versions on the same inputs to find behavioral differences that may reveal bugs.

See all 17 papers

Explore similar work

CardsList
Aug 17, 2026

Executable Code Knowledge: Code as a Native, Validation-Carrying Knowledge Representation for AI Coding Agents

AI coding agents need more than relevant snippets: they need business semantics, validation evidence, relations, and assurance that their context is current. Existing systems usually infer or externalize this knowledge through retrieval, summaries, graphs, rules, or reverse specifications. We investigate a complementary representation in which selected code units directly carry agent-usable knowledge. We introduce Executable Code Knowledge (ECK) and define an Executable Code Knowledge Unit (ECKU) as a source-bound object combining stable identity, semantics, executable behavior, contracts, evidence, relations, provenance, validation state, and a query interface. Our Python prototype supports code-local authoring, manifest export, evidence execution, exact changed-line impact, freshness checking, and agent-facing projections. Across three real Python repositories and 26 controlled patch tasks, direct ECK provides executable test coverage for 11/11 evidence-bearing tasks and exact selectors for 9/11; hiding declared evidence reduces exact recovery to 1/11 (paired exact McNemar p=0.0078). ECK-derived rules recover 11/11 exact selectors, showing that rules are effective delivery artifacts while ECK supplies source binding, validation state, impact, and freshness. Exact changed-line impact matches independently authored labels on all 26 patches (12 unit links; precision, recall, and F1 all 1.000). AST-bounded fingerprints classify 50 positive changes and 17 unrelated same-file controls correctly, whereas static rules snapshots detect none of the 50 stale cases. Model-backed patch-review and cross-layer studies measure projection fidelity rather than independent impact discovery. These results support a hybrid architecture: retrieval for coverage, ECK for source and evidence governance, and projections for delivery.

Xueping Gao

Alibaba Cloud Hangzhou, China

Knowledge RepresentationAI Coding Agents
AskPDF
Jun 4, 2025

LLMs are Brittle to Simple Code Transformations: Introducing CETBench - A Benchmark for Code-Equivalence Checking

We study how well LLMs can determine whether two programs are functionally equivalent. This is an important problem because benchmarking code equivalence helps assess LLM capability in tasks such as code rewriting and translation. To this end, we introduce CETBench - Code Equivalence with Transformations Benchmark - built from a repository of programs that may solve the same or different tasks. Each dataset instance is created by sampling a program pair and applying a random sequence of predefined code transformations, yielding either equivalent or non-equivalent pairs. Our analysis shows that even simple transformations cause a significant performance drop in state-of-the-art LLMs on code-equivalence checking. These challenges are further amplified in the cross-lingual setting when comparing programs written in different languages. To remedy this, we present a simple fine-tuning-based approach to boost LLM performance on the transformed pairs of programs. Our approach for dataset generation is generic, supporting cross-lingual equivalence checking, the generation of program pairs with varying difficulty levels, and the application of diverse transformations. In our experiments, we perform ablations over the difficulty level of original programs, as well as the kind of transformations used in generating pairs for equivalence checking. Our analysis presents deep insights into the working of LLMs for the task of code-equivalence, and points to the fact that they may still be far from what could be termed as a semantic understanding of the underlying code.

Neeva Oza, Ishaan Govil, Parul Gupta +3

Indian Institute of Technology Delhi · IBM Research AI

LLM EvaluationLanguage Model RobustnessCode Language Models
AskPDF
Sep 3, 2026

SWE-Gate: Passing Functional Tests Is Not Enough for Software Engineering Agents

Repository-level software engineering benchmarks have significantly advanced the evaluation of coding agents, but existing benchmarks primarily measure whether generated patches pass functional tests and overlook review-derived acceptance constraints (review constraints) that often influence whether a patch is acceptable in real-world software development. We introduce SWE-Gate, a repository-level benchmark for software engineering agents that explicitly evaluates review constraint compliance alongside functional correctness. SWE-Gate derives review constraints from real pull request review comments and synthesizes repository-level repair instances around these constraints. Each instance provides separate functional and constraint tests, together with non-compliant and gold patches, enabling explicit separation between issue resolution capability and review constraint compliance. We construct SWE-Gate with 303 repository-level repair instances spanning 75 open-source Python repositories across diverse software domains. Experiments with four LLM backends spanning different capability levels under a common coding-agent scaffold reveal a substantial gap between functional success and success under the complete repair specification: among 644 repairs that pass the functional tests, 221 fail to satisfy the provided review constraints. These findings show that functional-only evaluation overestimates agents' ability to satisfy the full requirements of repository-level repair tasks. The replication package including code, data, and experimental results is available at https://github.com/DeepSoftwareAnalytics/SWE-Gate.

Xin He, Yanlin Wang, Mingwei Liu +3

School of Software Engineering, Sun Yat-sen University · College of Computer Science and Technology, Zhejiang University · School of Big Data and Software Engineering, Chongqing University +1

Software Engineering AgentsAutomated Program RepairSoftware Engineering BenchmarksLLM Agent EvaluationRepository-Level Program Repair
AskPDF