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

Jul 16, 2026

Programming-by-example (PBE) systems infer programs from a small input–output example set, but robustness work often assumes wrong examples arise from random noise. This paper analyzes a stronger, fixed-set adversary who observes the synthesizer and selects corruptions that maximally damage the returned program. It formalizes worst-case corruption for finite PBE version spaces, implements exact and heuristic corruption searches for a string-transformation DSL, and proposes version-space partition aggregation (VPA) with semantic-signature voting. Experiments bound and partially negate robustness: low-margin tasks expose an adversarial dimension missed by noisy-PBE evaluation, and VPA recovers only when clean semantics preserve a vote margin.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages12

Reading Time30 min

Introduction

Background on Programming by Example (PBE)

Related Robust PBE and Noisy-Example Models

Motivation from Deployed Spreadsheet/DSL Workflows

Research Question and Scope

Fixed-Set Robustness in Programming by Example: Example Corruption and Semantic Partition Recovery Yuan Si and Jialu Zhang∗ University of Waterloo, Waterloo, Canada [yuan.si@uwaterloo.ca](yuan.si@uwaterloo.ca), [jialu.zhang@uwaterloo.ca](jialu.zhang@uwaterloo.ca) arXiv :2607 .0 1280v 1 [ cs .LG] 1 Jul 2026 Abstract—Programming-by-example systems infer programs from a small set of input-output examples. Robust PBE work usually models wrong examples as samples from a stochastic noise process and then minimizes an expected or empirical loss. This paper studies a different failure mode: an adversary who sees the synthesizer and chooses the examples whose corruption most damages the returned program. We formalize fixed-set worstcase corruption for finite PBE version spaces, implement exactwithin-bounded-pool and heuristic corruption searches for a string-transformation DSL, and introduce version-space partition aggregation (VPA), a defense that synthesizes on disjoint example groups and votes by semantic signatures. The central claim is deliberately bounded and partly negative: low-margin PBE tasks have an adversarial robustness dimension that randomtypo and noisy-PBE evaluations miss, while semantic partition aggregation helps only when the clean semantics keep a partition vote margin, which often fails on realistic tasks. Evidence from curated/generated DSL tasks, accepted public SyGuS PBE SLIA slices, SYNTRA Playgol v2, and noisy-PBE objective baselines supports that boundary. One curated edit flips all 8 spike tasks while 200-trial typo, DSL-pool, and distance-matched random controls succeed on 10.3%, 11.0%, and 16.7%; generated margin- 1 rows flip under budget 1 yet VPA recovers them; on public SyGuS the vote margin is near one, so an adaptive attacker drives VPA accuracy to zero; accepted public SyGuS slices move across exact-within-pool budget boundaries; and Playgol shows positive paired-bootstrap gaps against typo and same-pool random controls on the 141 accepted rows. A small exact-output prompt harness over 20 controlled margin-1 tasks shows the same qualitative clean-to-attacked pattern across local and API models, but it is treated as a scope check, not a broad LLM benchmark. I. INTRODUCTION Programming by example (PBE) is attractive because it turns a few concrete input-output pairs into an executable transformation. Spreadsheet users, data-cleaning tools, code assistants, and LLM prompts all rely on this interface. The interface also creates a small and high-leverage attack surface. When a PBE solver sees only three or five examples, a single corrupted example can change the set of programs that are consistent with the specification. If the wrong program is simpler, better ranked, or better supported by the remaining examples, the synthesizer can return code that is exactly conCorresponding author: Jialu Zhang. sistent with the corrupted examples and semantically wrong on future inputs. Existing robust PBE work gives important tools for noisy data. Handa and Rinard synthesize over noisy inputoutput examples with finite-tree-automata encodings and loss/complexity objectives, then formalize guarantees under noise-source assumptions [14], [15] . Rose accelerates this objective with abstraction refinement [16] . RobustFill trains neural PBE models to tolerate realistic I/O noise such as typos [17], and Raychev et al. learn programs from noisy datasets through a sampler and regularized generator [18] . These models are a natural first line of defense, yet they optimize for noise drawn from a source or observed in adataset. They leave open the fixed-set question: which small edit would an informed adversary choose after seeing the synthesizer? This distinction matters in deployed workflows. FlashFill’s original paper opens from the observation that more than 500 million people use spreadsheets and describes an Excel addin that synthesizes string transformations from input-output examples [33] . Micr

FAQs

What is version-space partition aggregation (VPA), and when does it help?

VPA synthesizes on disjoint example groups and votes by semantic signatures. It helps only when clean semantics maintain a partition-vote margin; adaptive attacks can drive VPA accuracy to zero when the margin is near one.

Jul 16, 2026

Upload by Lucas Martin