Program Semantic Inequivalence Game with Large Language Models

Antonio Valerio Miceli-Barone, Vaishak Belle, Ali Payani · 2025

Read Program Semantic Inequivalence Game with Large Language Models by Antonio Valerio Miceli-Barone, Vaishak Belle, Ali Payani (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-03818.txt.

Introduction

Antonio Valerio Miceli-Barone, Vaishak Belle, and Ali Payani present a game-based way to teach language models about code in a 2025 arXiv paper. Models do well on everyday coding tasks but can fail when a task needs deep reasoning about what code does. Good training examples for such reasoning are hard to find.

Their game, called SInQ, pits two agents against each other. One agent makes variants of real programs that behave in distinct ways. The other must find inputs where the variants act differently. Training this way improved results on several benchmarks. Gains appeared even in spotting flaws in C and C++ code, though training used only Python.

Catalog record

CREATORAntonio Valerio Miceli-Barone, Vaishak Belle, Ali Payani
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE49 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-03818

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Program Semantic Inequivalence Game with Large Language Models Antonio Valerio Miceli-Barone, Vaishak Belle, Ali Payani Abstract Large Language Models (LLMs) can achieve strong performance on everyday coding tasks, but they can fail on complex tasks that require non-trivial reasoning about program semantics. Finding training examples to teach LLMs to solve these tasks can be challenging. In this work, we explore a method to synthetically generate code reasoning training data based on a semantic inequivalence game ( SInQ ): a generator agent creates program variants that are semantically distinct, derived from a dataset of real-world programming tasks, while an evaluator agent has to identify input examples that cause the original programs and the generated variants to diverge in their behaviour, with the agents training each other semi-adversarially. We prove that this setup enables theoretically unlimited improvement through self-play in the limit of infinite computational resources. We evaluated our approach on multiple code generation and understanding benchmarks, including cross-language vulnerability detection ( Lu et al. 2021 ) , where our method improves vulnerability detection in C/C++ code despite being trained exclusively on Python code, and the challenging Python builtin identifier swap benchmark ( Miceli Barone et al. 2023 ) , showing that whereas modern LLMs still struggle with this benchmark, our approach yields substantial improvements. We release the code needed to replicate the experiments, as well as the generated synthetic data, which can be used to fine-tune LLMs 1 1 1 https://github.com/Avmb/semantic_neq_game . 1 Introduction Assistants based on Large Language Models (LLMs) are widely used by programmers to assist with coding tasks. While they perform well on common tasks, they still struggle with non-trivial reasoning about program semantics ( Miceli Barone et al. 2023 ; Maveli et al. 2025 ) . This limitation can lead to subtle bugs or prevent the detection of preexisting vulnerabilities and adversarial backdoors ( Dinh et al. 2023 ; Dou et al. 2024 ) , ultimately compromising the safety and security of generated code ( Wang et al. 2024 ; Mohsin et al. 2024 ) . LLMs’ code generation and understanding capabilities are typically improved by fine-tuning on a mixture of human-annotated and synthetically generated data. For example, the Llama-3 recipe ( Llama3 2024 ) provides a prototypical approach. However, human annotation is expensive and fails to cover many non-trivial scenarios. Typical synthetic generation approaches rely on LLMs to generate coding problem statements along with corresponding solutions and unit tests, then validate solutions by executing them against the tests. While this allows for large-scale dataset creation, it may still provide limited coverage of problem types and introduce noise, as unit tests do not always align well with problem statements, particularly in edge cases. Self-play involves training AI agents by pitting them against each other in adversarial games, incentivizing them to discover and defend against unusual scenarios. This approach has enabled AI systems to achieve human-level or even superhuman performance in games such as Go ( Silver et al. 2016 ; Silver et al. 2017b ) , Chess ( Silver et al. 2017a ) , Dota 2 ( OpenAI et al. 2019 ) , StarCraft II ( Arulkumaran et al. 2019 ) , and even social games involving dialogue, such as Diplomacy ( FAIR 2022 ) . However, self-play methods typically require external engines to enforce game rules and compute scores, making them challenging to apply to open-ended tasks like coding. Recreational competitive coding environments such as CROBOTS 2 2 2 https://github.com/tpoindex/crobots are overly domain-specific and impose strict performance limits, making them unsuitable for training agents in general code reasoning. In this work, we introduce a game based on program semantic equivalence (or inequivalence) designed to train agents in code reasoning across arbitrary domains. By design, this game has no theoretical performance cap. We use it to train LLMs through self-play, demonstrating significant performance improvements on challenging tasks. 2 Proposed method Our approach involves two LLM agents engaging in a game where the generator agent, "Alice," creates challenging code understanding problems for the evaluator agent, "Bob," to solve. Alice’s goal is to deceive Bob into making mistakes, requiring her to generate difficult instances. However, Alice must also provide solutions, meaning the instances cannot be unsolvable or excessively difficult. We train Alice to become more effective at misleading Bob and Bob to become better at resisting deception, encouraging both agents to develop a deeper understanding of program semantics. Our approach is based on the semantic equivalence of programs. This allows for precise verification of solutions, unlike problems based on natural language specifications or unit tests, which offer only partial coverage. Moreover, it is fundamentally linked to computability theory through reductions to Rice’s theorem and the Halting problem. In practical applications, reasoning about program equivalence and inequivalence is valuable for identifying bugs and security vulnerabilities introduced during code refactoring. 2.1 The semantic equivalence game Two programs P and Q are semantically equivalent if, for any given input x , they produce the same output y and either both halt or neither does. Determining semantic equivalence is a fundamental problem in program verification and compiler design. It is undecidable in the general case as a direct consequence of Rice’s theorem ( Rice 1953 ) , which implies that any deductive reasoning problem expressible in first-order logic can be reduced to it. We define the semantic equivalence game as a one-shot interaction between two players: the generator , "Alice," and the evaluator , "Bob": 1. Alice receives a program P and generates another program Q , which may be either equivalent or inequivalent to P . 2. If P and Q are equivalent, Alice must provide a machine-checkable proof. If they are inequivalent, Alice must supply a diverging input x that causes them to produce different outputs or exhibit different halting behaviours. 3. The equivalence proof or diverging input is verified. If incorrect, Alice loses. 4. Bob receives P and Q and must determine whether they are equivalent. If Bob is correct, he wins and Alice loses; if he is wrong, Alice wins. Alice’s objective is to generate challenging instances for Bob, while Bob’s goal is to solve them. Both agents improve iteratively through repeated play. The source programs P provided to Alice are sampled from a dataset, such as a collection of short, self-contained programming exercises spanning a variety of tasks (e.g., MBPP ( Austin et al. 2021 ) ). This ensures the game remains grounded in real-world coding problems. If Alice were allowed to generate both P and Q , she might develop an incentive to produce obscure, obfuscated code that does not contribute to Bob’s general reasoning skills. Due to the undecidability of semantic equivalence, a perfect Bob cannot exist. This results in a "full-employment theorem" ( Appel & Ginsburg 1998 ) for Alice: in principle, she can always find new ways to fool Bob. This iterative process leads to increasingly stronger Bobs, who in turn train progressively stronger Alices. Unlike games such as Go or Chess, where perfect play is theoretically possible, the semantic equivalence game has no theoretical performance cap —agents can continue learning new coding logic indefinitely, constrained only by model capacity and computational resources. The main drawback of the semantic equivalence game is its reliance

Read the complete text