Yuan Si and Jialu Zhang have published a new paper on July 1, 2026, focusing on fixed-set robustness in programming by example (PBE) systems. Their work addresses the challenge of adversarial corruption of examples used to infer programs, proposing innovative methods to enhance robustness against intentional misuse.
Understanding Fixed-Set Robustness in PBE
Programming-by-example systems aim to derive programs from limited input-output pairs. Traditional PBE approaches often treat erroneous examples as random noise. However, Si and Zhang's research identifies a more deliberate failure mode, where an adversary intentionally corrupts examples to undermine the program's effectiveness. This paper introduces a formalization of fixed-set worst-case corruption, particularly for finite PBE version spaces.
The authors present two search strategies for corruption: exact-within-bounded-pool and heuristic searches tailored for a string-transformation domain-specific language (DSL). These methods are designed to detect and counteract adversarial tactics effectively.
Version-Space Partition Aggregation as a Defense
One of the key innovations in this study is the introduction of version-space partition aggregation (VPA). This defense mechanism operates by synthesizing across disjoint groups of examples and leveraging semantic signatures to cast votes on the most accurate outputs. The research highlights that low-margin PBE tasks possess an adversarial robustness dimension often overlooked in random typo evaluations.
