Research map / Large language models / Agents, code and math
Exploiting Code Symmetries for Learning Program Semantics
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes SymC, a self-attention variant provably equivariant to permutation symmetries (automorphisms of a program dependence graph), trained from scratch to give invariant predictions for five program analysis tasks.
Problem
Code LLMs are not robust to semantics-preserving code transformations such as statement permutations, so their predictions change under symmetry-preserving edits, and pre-training or augmentation give no invariance guarantee.
Approach
Define code symmetries as automorphisms of a program dependence graph (PDG) and bias multi-head self-attention with positive/negative longest-path distance matrices, making the representation provably equivariant and the pooled or token-level predictions invariant to these permutations.
Key results
- SymC has 0% violation rate under statement permutations while CodeLlama violates 18% and GPT-4 43% on function name prediction, with mean LLM violation of 31.4%.
- SymC (67.7M params, trained from scratch) reaches 68.8 F1 on defect prediction vs. 67.1 for UnixCoder and 63.3 for CodeT5.
- SymC outperforms PalmTree by 33.8% and 30.7% on seen and unseen binary transformations, respectively.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SymC instead of PalmTree | Function signature prediction · Function signature prediction under semantics-preserving permutations | F1: 0.59 -> 0.88 | Helped |
| Use SymC instead of PalmTree | Memory region prediction · Memory region prediction under semantics-preserving permutations | F1: 0.57 -> 0.86 | Helped |
| Use SymC instead of PalmTree-O | Function similarity detection · Function similarity detection under semantics-preserving permutations | AUC: 0.8 -> 0.96 | Helped |
| Use SymC instead of PalmTree on unseen source transformations | Function name prediction · Unseen source-code transformations beyond permutations | F1: 30.8% | Helped |
| Use SymC instead of Code Llama on unseen source transformations | Function name prediction · Unseen source-code transformations beyond permutations | F1: 10% | Hurt |
| Use equivariant rather than invariant self-attention layers (ablation) | SymC · Memory region prediction | F1: 0.73; 60.7% | Helped |
| Add one epoch of masked-language-model pre-training (ablation) | SymC · Memory region prediction | F1: 10.8% | Helped |
| Increase pre-training from 1 epoch to 5 epochs (ablation) | SymC · Memory region prediction | F1: 3.2% | Helped |
| Use PDG-equivariant attention rather than fully permutation-equivariant attention with identical distance values (ablation) | SymC · Memory region prediction | F1: 14.5% | Helped |
| Use PDG-equivariant attention rather than non-equivariant relative positional embeddings (ablation) | SymC · Memory region prediction | F1: 36.4% | Helped |
Surprising findings
- CodeLlama outperforms SymC by about 10% on unseen source transformations, attributed to its natural-language pre-training.
- Enforcing invariance in early layers hurts performance; equivariant early layers with invariant pooling at the end work better.
Limitations
- Conservative static PDG construction may miss valid symmetries and only considers symmetries holding for all inputs.
- Only permutation groups are handled; insertions and deletions require semigroups not covered.
- PDG construction adds overhead per sample and is done at source/assembly level rather than IR level.
Experimental setup
Datasets: Java method name dataset (11 projects, 707K methods) Defects4J 27 open-source binary projects compiled with GCC and Clang, O0-O3, Hikari obfuscations
Benchmarks: function name prediction (Java, Hadoop test set) defect prediction (Defects4J) function signature prediction (stripped binaries) memory region prediction (stripped binaries) function similarity detection (stripped binaries)
Metrics: F1 AUC violation rate
Baselines: code2seq code2vec CodeLlama CodeT5 DOBF GGNN GPT-4 GraphCodeBERT WizardCoder PalmTree
Builds on: Transformer self-attention Graphormer-style distance encoding SymLM
Closest papers by meaning
- SemCoder: Training Code Language Models with Comprehensive Semantics Reasoning (NeurIPS 2024 · similarity 0.86)
- SelfCodeAlign: Self-Alignment for Code Generation (NeurIPS 2024 · similarity 0.86)
- Unsupervised Evaluation of Code LLMs with Round-Trip Correctness (ICML 2024 · similarity 0.86)
- Chain of Execution Supervision Promotes General Reasoning in Large Language Models (NeurIPS 2025 · similarity 0.86)
- Revisiting Chain-of-Thought in Code Generation: Do Language Models Need to Learn Reasoning before Coding? (ICML 2025 · similarity 0.85)
- AST-T5: Structure-Aware Pretraining for Code Generation and Understanding (ICML 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.