Program Reduction: A Comprehensive Survey

Abstract

Program reduction transforms a failure-inducing program into a smaller program that preserves the failure of interest. The design space of modern reducers extends well beyond deletion plus an oracle that decides whether a candidate still triggers the failure: they differ in program representation, transformation space, search and guidance, stopping criteria, oracle engineering, and validity control. This survey covers the families that populate that space: list-based Delta Debugging, hierarchical, syntax-guided, language-specific semantic, search-prioritized, and large language model-aided reducers. These families coexist rather than supersede one another, because each resolves those design choices differently. We compare how these choices affect portability, effectiveness, efficiency, and practical utility, and examine open challenges in validity, oracle cost, benchmark design, and reproducible evaluation.