Fixed-Set Robustness in Programming by Example: Example Corruption and Semantic Partition Recovery

2026-07-01 · Source: Machine Learning · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Software Development & Engineering · Depth: Expert, quick

Summary

Fixed-Set Robustness in Programming by Example: Example Corruption and Semantic Partition Recovery investigates a novel adversarial attack on Programming-by-Example (PBE) systems. Unlike traditional noise models, this work focuses on an adversary who strategically corrupts input-output examples to maximize damage to the inferred program within finite PBE version spaces. The paper formalizes this fixed-set worst-case corruption, implementing search methods for a string-transformation DSL. It introduces version-space partition aggregation (VPA) as a defense mechanism, which synthesizes on disjoint example groups and votes by semantic signatures. Key findings indicate that low-margin PBE tasks possess an adversarial robustness dimension overlooked by random-typo and noisy-PBE evaluations. While VPA can recover some corrupted tasks, its effectiveness is limited to scenarios where clean semantics maintain a sufficient partition vote margin, a condition often unmet in realistic applications, as demonstrated across curated DSL tasks, public SyGuS slices, and Playgol v2 benchmarks.

Key takeaway

For Research Scientists developing Programming-by-Example (PBE) systems, you must account for adversarial example corruption, not just random noise. Your PBE system's robustness should be evaluated against targeted attacks that exploit low-margin tasks. If you implement defenses like version-space partition aggregation (VPA), carefully assess whether the clean semantics maintain a sufficient vote margin, as its effectiveness is highly conditional on this factor for real-world applicability.

Key insights

Adversarial example corruption reveals a critical robustness dimension in PBE systems missed by random noise models.

Principles

• PBE robustness needs adversarial modeling.
• Low-margin PBE tasks are vulnerable.
• Defense efficacy depends on semantic vote margin.

Method

Version-space partition aggregation (VPA) defends against adversarial corruption by synthesizing on disjoint example groups and voting based on semantic signatures.

In practice

• Evaluate PBE systems against targeted corruption.
• Consider VPA for specific low-margin tasks.
• Analyze semantic vote margins for defense viability.

Topics

• Programming by Example
• Adversarial Robustness
• Example Corruption
• Version-Space Partition Aggregation
• String Transformation DSL
• SyGuS PBE_SLIA
• Playgol v2

Best for: AI Scientist, Machine Learning Engineer, Research Scientist

Related on AIssential

• Toward Trustworthy AI: Multi-Target Adversarial Attacks and Robust Defenses for Continuous Data Summarization — Adversarial attacks on data summarization can compromise trustworthy AI, necessitating robust defenses formulated via DR-submodular optimization.
• Benchmarking Instance-Dependent Label Noise with Controlled Corruptions — CILN generates explicit, controllable instance-dependent label noise via input corruptions, revealing new algorithm failure modes.
• Evaluating the Robustness of Proof Autoformalization in Lean 4 — Current LLM-based proof autoformalization models lack robustness to stylistic changes and specific alterations in informal mathematical proofs.
• Beyond Semantic Relevance: Counterfactual Risk Minimization for Robust Retrieval-Augmented Generation — CoRM-RAG enhances RAG robustness by optimizing for decision safety against user biases, not just semantic relevance.
• ERTS: Adversarial Robustness Testing of Ethical AI via Semantic Perturbation in a Bounded Consequence Space — AI ethical judgment can be robustly tested against semantic perturbations in a bounded consequence space.
• Distributionally Robust Set Representation Learning Under Inference-Time Element Corruption — SW-DRSO enhances set representation learning robustness by optimizing for worst-case inference-time corruption using a barycentric adversary.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by Machine Learning.