Skip to content
STIMSMITH

Program Reduction

Technique WIKI v1 · 6/24/2026

Program reduction is a prevalent technique used to facilitate compilers' debugging by automatically minimizing bug-triggering programs. It is applied across a range of domains, from compiler bug minimization to the analysis of neural code intelligence models and to CPU fuzzing test-case minimization.

Overview

Program reduction is a prevalent technique to facilitate compilers' debugging by automatically minimizing bug-triggering programs. Existing program reduction techniques are either generic across languages (e.g., Perses and Vulcan) or specifically customized for one certain language by employing language-specific features, like C-Reduce LPR: Large Language Models-Aided Program Reduction.

Taxonomy of Approaches

Program reduction techniques broadly fall into two categories:

  • Language-generic (syntax-level) reducers. Tools such as Perses and Vulcan operate at the syntactic level and can be applied across multiple programming languages without language-specific customization.
  • Language-specific (semantic-level) reducers. Tools such as C-Reduce exploit language-specific features to perform aggressive semantic transformations tailored to a single language.

A key open question is striking the balance between generality across multiple programming languages and specificity to individual languages in program reduction.

Hybrid Approaches with LLMs

LPR is the first technique utilizing LLMs to perform language-specific program reduction for multiple languages. Its core insight is to combine both language-generic syntax-level program reduction (e.g., Perses) and language-specific semantic-level program transformations learned by LLMs.

The LPR workflow alternates between the two components:

  • Language-generic program reducers efficiently reduce programs to 1-tree-minimality, which is small enough to be manageable for LLMs.
  • LLMs transform programs via learned semantics to expose new reduction opportunities for the language-generic program reducers to further reduce the programs.

Evaluations on 50 benchmarks across three languages (C, Rust, and JavaScript) reported that LPR surpasses Vulcan by producing 24.93%, 4.47%, and 11.71% smaller programs on benchmarks in C, Rust, and JavaScript, respectively. LPR and Vulcan were shown to complement each other: by running Vulcan on LPR's output for C programs, program sizes comparable to those reduced by C-Reduce can be achieved. In efficiency, LPR takes 10.77%, 34.88%, and 36.96% less time than Vulcan to finish all benchmarks in C, Rust, and JavaScript, separately.

Program Reduction for Neural Code Intelligence Models

Program reduction has also been adapted for explainability of neural code intelligence (CI) models, which are typically opaque black boxes. Input program reduction techniques have been proposed to identify key features (tokens) in input programs that drive predictions.

A syntax-guided program reduction technique considers the grammar of the input programs during reduction. Experiments on multiple models across different types of input programs show that the syntax-guided approach is faster and provides smaller sets of key tokens in reduced programs compared to a syntax-unaware baseline. The key tokens identified through this process have also been used to generate adversarial examples for up to 65% of the input programs Syntax-Guided Program Reduction for Understanding Neural Code Intelligence Models.

Program Reduction in CPU Fuzzing

In CPU fuzzing, generated test cases can be long, and CPU bugs are revealed by programs not terminating due to the entanglement of data and control flows. To understand the underlying CPU bug, it is necessary to reduce the programs to a minimal form while preserving the instructions and states that trigger the bug.

The Cascade approach performs program reduction by progressively transforming some instructions into direct jumps that skip the last basic blocks, observing whether the bug is still triggered. The process identifies:

  • The bug's tail (last) instruction. Found via a binary search for the last basic block which, when omitted along with its successors, erases the buggy behavior. To remove such a final sequence, the predecessor's hopping instruction is replaced with a direct jump toward the final block.
  • The bug's head (first) instruction. Removing predecessor instructions can influence the architectural state. The approach therefore preserves the architectural state while simplifying the microarchitectural state by inserting a context setter basic block. A context setter uses an ISS to infer the architectural context (registers, privilege level, performance counter values) and reloads it using simple instructions, after which the head instruction is identified similarly to the tail.
  • Sandwich instructions. Remaining middle instructions are iteratively removed where possible.

This program reduction capability is part of the Cascade CPU fuzzing framework, evaluated on RISC-V CPUs and Yosys (Cascade artifacts, Cascade paper PDF).

Key Concepts

  • 1-tree-minimality — a syntactic minimality notion used as an intermediate reduction target that is tractable for language-generic reducers and small enough to expose further opportunities to LLM-driven semantic transformations.
  • Tail/Head instruction identification — a binary-search-based approach to locating the minimal instruction sequence that still triggers a bug.
  • Context setter — inserted during reduction to preserve architectural state (registers, CSRs, privilege) while the microarchitectural state is simplified.
  • Syntax-guided reduction — leveraging grammar of the source language to guide token-level reduction for CI model interpretability.

CITATIONS

11 sources
11 citations
[1] Program reduction is a prevalent technique to facilitate compilers' debugging by automatically minimizing bug-triggering programs. LPR: Large Language Models-Aided Program Reduction
[2] Existing program reduction techniques are either generic across languages (e.g., Perses and Vulcan) or specifically customized for one certain language by employing language-specific features, like C-Reduce. LPR: Large Language Models-Aided Program Reduction
[3] LPR is the first technique utilizing LLMs to perform language-specific program reduction for multiple languages, alternating language-generic syntax-level reduction (e.g., Perses) and language-specific semantic-level transformations learned by LLMs. LPR: Large Language Models-Aided Program Reduction
[4] On 50 benchmarks across C, Rust, and JavaScript, LPR produces 24.93%, 4.47%, and 11.71% smaller programs than Vulcan respectively, and takes 10.77%, 34.88%, and 36.96% less time. LPR: Large Language Models-Aided Program Reduction
[5] By using Vulcan on LPR's output for C programs, program sizes comparable to those reduced by C-Reduce are achieved. LPR: Large Language Models-Aided Program Reduction
[6] Syntax-guided program reduction considers the grammar of the input programs during reduction, is faster than syntax-unaware approaches, and yields smaller sets of key tokens. Syntax-Guided Program Reduction for Understanding Neural Code Intelligence Models
[7] Key tokens identified via input program reduction can be used to generate adversarial examples for up to 65% of the input programs. Syntax-Guided Program Reduction for Understanding Neural Code Intelligence Models
[8] Cascade generates long test cases and reduces programs to a minimal form by identifying the last (tail) and first (head) instructions that trigger a CPU bug. Cascade: CPU Fuzzing via Intricate Program Generation
[9] Cascade finds via binary search the last basic block which, when omitted along with its successors, erases the buggy behavior, and replaces the predecessor's hopping instruction with a direct jump toward the final block. Cascade: CPU Fuzzing via Intricate Program Generation
[10] Identifying the head preserves architectural state via a context setter basic block that uses an ISS to infer register values, privilege level, and performance counter values, then reloads them. Cascade: CPU Fuzzing via Intricate Program Generation
[11] Cascade's program reduction was evaluated on 37 new bugs found in 5 of 6 evaluated RISC-V CPUs and in Yosys. Cascade: CPU Fuzzing via Intricate Program Generation