🤖 machine learning

Program Semantic Inequivalence Game with Large Language Models

This paper introduces a semi-adversarial "Semantic Inequivalence Game" (SInQ) where generator and evaluator agents collaboratively synthesize training data to enhance Large Language Models' program semantic reasoning, demonstrating significant improvements in cross-language vulnerability detection and complex identifier swap tasks.

Original authors: Antonio Valerio Miceli-Barone, Vaishak Belle, Ali Payani

Published 2026-08-13

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Antonio Valerio Miceli-Barone, Vaishak Belle, Ali Payani

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are teaching a brilliant but literal-minded robot how to write computer code. You might think, "If I show it a million examples of how to build a house, it will know how to build a skyscraper." But computers are tricky. They are great at copying patterns, but they often stumble when asked to understand the deep logic behind the code—like why a tiny change in a recipe might make a cake collapse, or how a hidden backdoor could let a thief into a digital house. This is the world of "program semantics," the study of what code actually does versus what it looks like it does.

To teach a robot this deep logic, we usually need a human teacher to point out every mistake, which is slow and expensive. Alternatively, we can let the robot practice on its own, but it often just practices the easy stuff and ignores the hard puzzles. This paper explores a new way to train these AI "coders" by turning them into players in a high-stakes game of logic. Instead of just memorizing answers, the AI has to learn to spot the invisible differences between two pieces of code that look almost identical. If it can master this game, it might become much better at finding security bugs and writing safer software, even in languages it has never seen before.

The Great Code Detective Game

The authors of this paper, Antonio Valerio Miceli Barone, Vaishak Belle, and Ali Payani, have invented a clever training method called the Semantic Inequivalence Game (or SInQ for short). Think of it as a digital game of "Spot the Difference," but played by two AI agents who are constantly trying to outsmart each other.

The Players: Alice and Bob
Imagine two AI detectives, Alice and Bob, sitting across from each other.

Alice is the trickster. She is given a piece of code (let's call it Program P) and her job is to create a "fake" version (Program Q) that looks almost exactly the same but behaves slightly differently. She also has to find a specific "test input" (like a specific number or word) that proves the two programs are different. If she can't find a difference, she loses.
Bob is the detective. He is shown both programs, P and Q. His job is to figure out: "Are these actually different?" If they are, he must find the specific test input that exposes the difference. If he finds it, he wins. If he misses it, Alice wins.

The Training Loop
At first, Alice is bad at making tricky fakes, and Bob is good at spotting them. But as they play over and over, they get better. Alice learns to make fakes that are harder to spot, and Bob learns to look for deeper, more subtle clues. They are training each other in a "self-play" loop, similar to how a grandmaster chess player might practice against a computer that gets smarter every time they play.

The magic here is that they don't need a human teacher to say, "Good job!" or "Wrong answer." The game has a built-in referee: a computer sandbox. They simply run the two programs with the test input. If the results are different, the input is valid, and the game is fair. If the results are the same, the trick failed. This means the AI learns by doing, not by guessing.

What They Found

The researchers tested this game on two different AI models (gpt-4o-mini and gpt-4.1-nano) to see if playing this game made them better at real-world coding tasks.

1. The "Python Identifier Swap" Challenge
They tested the AI on a notoriously difficult puzzle called the "Python builtin identifier swap." Imagine a program where the words print and len (which are standard tools in Python) are swapped around. To a human, it's confusing; to an AI, it's a nightmare because the code looks normal but acts weird.

The Result: The AI that played the game (Bob) got significantly better at spotting the trick on one of the models. For gpt-4o-mini, the accuracy jumped from a very low 1.65% to 5.35% without any extra hints. However, the results were mixed for the other model: on gpt-4.1-nano, the training actually made performance slightly worse without extra hints, and using a "chain-of-thought" approach (where the AI talks through its reasoning) caused accuracy to drop further. This suggests that while the game taught the AI to look deeper, the benefits depend heavily on the specific model used.

2. Finding Security Bugs (Vulnerability Detection)
The team also tested if this training helped the AI find security holes in code. They used two benchmarks:

PySecDB: A dataset of Python code changes to see if they fixed security issues.
CodeXGLUE: A dataset of C/C++ code (a different programming language than the one the AI was trained on!) to find known bugs.
The Result: The AI that played the game showed small but consistent improvements in finding these bugs, even in the C/C++ language it had never seen during training. This is a big deal because it suggests the AI learned a general skill for "logic spotting" rather than just memorizing Python answers.

3. Writing New Code
Finally, they checked if the game helped the AI write new code from scratch. The results were mixed. The AI didn't get much better at writing code, but it didn't get worse either. The authors suggest this makes sense: they trained the "detective" (Bob), not the "writer" (Alice), so the detective got sharper at spotting errors, but didn't necessarily become a better author.

The Big Picture

The paper suggests that this "Semantic Inequivalence Game" is a powerful way to teach AI to understand the logic of code, not just the patterns. By forcing the AI to find the tiny, invisible differences between two programs, it learns to be more careful and more logical.

However, the authors are careful to note that this isn't a magic wand that solves all coding problems. The improvements were real but modest in some areas, and the method depends on the AI being able to run the code to check the answers. They also point out that they only trained the AI for a few rounds due to budget limits, so there might be even more potential if they played the game for longer.

In short, by turning code training into a game of "find the difference," the researchers showed that AI can learn to be a sharper, more logical detective, capable of spotting security risks and confusing logic that other models might miss. It's a step toward making AI not just a code generator, but a true code reasoner.

Technical Summary: Program Semantic Inequivalence Game with Large Language Models

Problem Statement
While Large Language Models (LLMs) demonstrate proficiency in routine coding tasks, they frequently fail at non-trivial reasoning regarding program semantics. This deficiency leads to subtle bugs, missed vulnerabilities, and security backdoors. Existing methods to improve LLMs, such as human annotation, are expensive and cover few non-trivial scenarios. Conversely, typical synthetic data pipelines generate problem statements and unit tests that are validated by execution; however, these often introduce noise due to misalignment between unit tests and problem statements in edge cases, and they provide limited coverage of complex problem types.

Methodology: The Semantic Inequivalence Game (SInQ)
The authors propose a self-play framework called the Semantic Inequivalence Game (SInQ) to synthetically generate code reasoning training data. The game involves two agents, "Alice" (generator) and "Bob" (evaluator), engaging in a semi-adversarial interaction grounded in real-world programming tasks:

Game Mechanics:
- Alice receives a source program $P$ and must generate a variant program $Q$ that is semantically inequivalent to $P$ , along with a "diverging input" $x$ such that $P(x) \neq Q(x)$ .
- Bob receives $P$ and $Q$ and attempts to identify a diverging input $\hat{x}$ (which may differ from Alice's $x$ ).
- Verification: Correctness is determined solely by executing the programs on the candidate inputs. If Bob finds an input where outputs differ, he wins; otherwise, Alice wins. This approach avoids the need for formal proofs or natural language specifications, relying instead on the operational semantics of the language.
Training Protocol:
- The authors implement this via Supervised Fine-Tuning (SFT) with difficulty targeting, as reinforcement learning was unavailable on the API used during experiments.
- Difficulty Estimation: The difficulty of a $(P, Q)$ pair is defined by the probability that Bob fails to find a diverging input. Alice is prompted to generate examples targeting a specific difficulty (typically the maximum, 10).
- Iterative Refinement: Alice is trained on rounds of data generated against a fixed Bob. Once Alice converges (producing consistently hard examples), Bob is fine-tuned on the successful pairs where he correctly identified diverging inputs. This cycle repeats.
- Data Grounding: Source programs $P$ are sampled from the MBPP dataset (code fields only), ensuring the game remains grounded in real-world logic rather than obfuscated or synthetic puzzles.
- Termination Handling: To approximate non-termination detection, a randomized time limit is imposed, preventing agents from exploiting fixed timeouts.

Key Contributions

Novel Training Paradigm: Introduction of a self-play game based on program semantic inequivalence, designed to have no theoretical performance cap. Unlike games like Go or Chess, the task is undecidable in the general case (linked to Rice's Theorem), allowing agents to learn arbitrarily complex logic while remaining grounded in real code.
Neurosymbolic Integration: The method operates in the neurosymbolic tradition, using a symbolic verifier (program execution) to provide a hard, checkable reward signal, while the neural component (LLM) performs the search for diverging inputs.
Synthetic Data Generation: A pipeline to generate high-quality, difficult reasoning examples that are validated by execution rather than static analysis or human annotation.

Experimental Results
The authors evaluated the fine-tuned "Bob" models (denoted sinq-gpt-4o-mini and sinq-gpt-4.1-nano) on several benchmarks:

Intrinsic Evaluation (The Game Itself):
- On the semantic inequivalence game, the trained Bob showed significant improvement over the untrained baseline, solving a higher percentage of instances generated by the final Alice on both MBPP-train and held-out MBPP-test sources.
Extrinsic Evaluation (Code Understanding):
- Python Builtin Identifier Swap: On this challenging benchmark involving reassignment of built-in functions (e.g., len, print), the sinq-gpt-4o-mini model achieved substantial accuracy improvements (+3.7% without Chain-of-Thought). However, results for sinq-gpt-4.1-nano were mixed, showing no improvement or slight degradation, indicating that transferability is not guaranteed across all base models.
- Vulnerability Detection:
  - PySecDB (Python): The method yielded small but consistent improvements in detecting security fixes in Python commits.
  - CodeXGLUE (C/C++): Notably, models fine-tuned exclusively on Python code showed improved vulnerability detection in C/C++ snippets, suggesting the learned reasoning skills generalize across programming languages.
- Code Generation: On MBPP and HumanEval benchmarks, the results were neutral to slightly positive/negative. The authors note that since Bob is an evaluator, not a generator, improvements in generation tasks were not the primary expectation, though performance was generally maintained.

Significance and Claims
The paper claims that the Semantic Inequivalence Game provides a robust method for teaching LLMs to reason about program semantics without relying on human labels or formal verification tools that are often unavailable for real-world code.

Generalization: The approach demonstrates that skills learned through this adversarial game can transfer to tasks the model was never explicitly trained on, including cross-language vulnerability detection and handling out-of-distribution code snippets.
Scalability: By relying on execution-based verification rather than learned reward models, the method avoids the "gaming" of reward signals and theoretically allows for continuous improvement as the agents become more sophisticated.
Modesty: The authors explicitly state that the transfer of skills is not a universal property of the method (as evidenced by the mixed results on the identifier swap benchmark for different base models) and that the current implementation is limited by budget constraints (single-round training for Bob, specific model sizes). They position the strength of the symbolic verifier as the primary axis for future improvement.

The Great Code Detective Game

What They Found

The Big Picture

Technical Summary: Program Semantic Inequivalence Game with Large Language Models

More like this