Scythe: Semantic-Aware Rewriting for Fast,Effective Program Reduction

Scythe: Semantic-Aware Rewriting for Fast, Effective Program Reduction Ioanna Moraiti1 , Charalambos Mitropoulos2 , Artem Anchikov3 , Sotirios Ioannidis2 Dimitris Mitropoulos4,5 , Thodoris Sotiropoulos1 1

Unaffiliated, 2 Technical University of Crete, 3 ETH Zurich, University of Athens, 5 National Infrastructures for Research and Technology {ioannamoraiti@outlook.com, theosotr@windowslive.com}, {cmitropoulos, sioannidis}@tuc.gr, aanchikov@ethz.ch, dimitro@ba.uoa.gr

arXiv:2611.06515v1 [cs.SE] 4 Nov 2026

4

Abstract—Automated program reduction shrinks a program into a smaller one that preserves a property of interest. Languageagnostic grammar-based reducers are easy to retarget across languages, but because they reason only about syntax, they cannot perform the coupled edits needed to remove whole declarations, e.g., a method cannot be deleted while it is still called. As a result, they waste oracle calls on edits that cannot succeed and often leave irrelevant declarations behind. We present S CYTHE, a fast, semantic-aware pre-processing step that runs in front of any grammar-based reducer without modifying it. S CYTHE encodes the program as a typed declaration dependency graph and performs a set of semantic-aware operators that decouple declarations from their use sites, making them removable while keeping the program well-typed. Fine-grained token-level minimization is then left to the downstream reducer. On 73 benchmarks across C, Java, and Solidity, combining S CYTHE with P ERSES never yields a larger result than P ERSES alone, and a strictly smaller one on 70 of 73 cases. On average, the combination produces programs 55.6% smaller (up to 95.5%) and is 2.3× faster (up to 7.4×). S CYTHE also boosts L ATRA, a reducer that, unlike the purely syntactic P ERSES, also applies language-specific transformations: the combination produces programs 10.6% smaller (up to 61.8%) and is 2.4× faster on average. Video: https://youtu.be/uEq YYU0zZw Index Terms—Program reduction, delta debugging, compiler testing, semantics

I. I NTRODUCTION Automated program reduction is integral to debugging and bug deduplication in software systems that take programs as input, such as compilers, interpreters, and static analyzers. Given a program P that exhibits a property of interest, such as a compiler crash, a miscompilation, or a staticanalysis report, a reducer produces a smaller program P ′ that still exhibits it, querying an oracle (a script that checks the property) on each candidate [1]. Existing reducers fall into two families. Language-specific reducers, such as CReduce [1], apply transformations tailored to one language (e.g., C). These transformations make reduction effective, but the tools are hard to retarget to other languages. Languageagnostic, grammar-based reducers [2], [3] instead delete syntax while guaranteeing that the result still parses, so they can be retargeted to a new language simply by supplying its grammar. However, this generality comes at a cost. Language-agnostic reducers can be slow, even on small programs, and often leave behind code that is irrelevant to the property of interest.

Example: Consider a Java program that crashes the Java compiler (javac, JDK 8.0.32); it spans 300 lines with 16 top-level types, 55 methods, and heavy use of inheritance, generics, and lambdas. Figure 1a shows the version produced by P ERSES [2], a state-of-the-art language-agnostic reducer, after roughly five minutes. Several remaining declarations (e.g., class Base, field active, method label) are irrelevant to the bug, yet P ERSES cannot remove them because they are still referenced elsewhere. The problem: Programs targeted by reduction tools contain many declarations unrelated to the property of interest (here, most of the 16 types and 55 methods). The goal is to identify and remove these irrelevant declarations, ideally eliminating large blocks of code quickly with few oracle queries. However, doing so requires breaking the dependencies that tie each declaration to its use sites, edits that a language-agnostic reducer cannot perform. Our tool: We bridge the gap between language-agnostic and language-specific reducers with S CYTHE, a fast, semanticaware pre-processing step that runs before a language-agnostic reducer. It targets developers and testers of compilers, interpreters, and static analyzers, e.g., when reducing fuzzerfound bugs. S CYTHE removes whole classes, methods, and fields, applying a set of general, semantic-aware decoupling operators that rewrite a declaration’s use sites. The declaration then becomes removable while the program remains well-typed. S CYTHE supports C, Java, and Solidity, and is easily extensible to new languages. On our running example, the S CYTHE + P ERSES pipeline produces the smaller program of Figure 1b in about two minutes (2.1× speedup), with 43% fewer tokens than P ERSES alone. Across 73 benchmarks, S CYTHE never makes the output of P ERSES larger, at least halves it in 50 cases, and speeds up reduction by up to 7.4×. On Java, S CYTHE alone, in under a minute on average, already beats P ERSES on 23 of 34 benchmarks. Paired with L ATRA [4], S CYTHE yields programs 10.6% smaller (up to 61.8%) and reduction 2.4× faster on average, all without modifying the underlying reducers. II. C HALLENGES We identify two challenges that any reducer must overcome to remove irrelevant declarations (e.g., class Base, Figure 1a).

P

1 2 3 4 5 6 7 8 9 10 11 12 13 14

class Main { Widget active; static String label(short code) {return "tag"; } final boolean READY = new Widget("first").check(active, () −> { String text = "x"; return text; }) || active.check(new Widget(Main.label((short) 54)), ,→ null); } interface Supplier<R> {R get(); } class Base {Base(Boolean flag, boolean extra) {}} class Widget extends Base { Widget(String tag) {super(false, true); } Boolean check(Widget other, Supplier task) {return ,→ true; } }

Scythe Dependency Graph Construction G Delta Debugging candidate declaration set D semantic decoupling operators

Program Rewrite

property oracle O

P’

Language Agnostic Reducer (e.g. Perses)

Property Checker P’

minimized program P’’

(a)

Fig. 2: The high-level architecture of S CYTHE. 1 2 3 4 5 6 7 8 9 10 11

class Main { final boolean READY = (( A) null).check(null, () −> { String text = "x"; return text; }) || (( A) null).check(null, null); } interface Supplier<R> {R get(); } class A { Boolean check( A other, Supplier task) {return ,→ true; } } (b)

Fig. 1: An example of a Java program that crashes JDK 8. (a) The minimized program produced by P ERSES, a language-agnostic reducer; (b) The minimized program produced by P ERSES after the code is pre-processed by S CYTHE.

Challenge 1: program dependencies that block removal: Pruning a declaration usually makes the oracle reject the program, even when the declaration is irrelevant to the bug, because it is referenced at multiple sites. For example, pruning class Base alone makes the crash disappear, since Base still appears after extends (line 11) and its constructor is called (line 12). A reducer must therefore identify every dependency between a declaration and its uses, and different uses demand different edits. Removing the method label requires dropping or replacing its call. Removing a class used as the type of a field, such as Widget for active (line 2), may require removing the field and, in turn, every use of that field. Challenge 2: Syntax-guided search is prohibitively expensive: Existing reducers employ sophisticated search to find further reduction opportunities. V ULCAN [3] guarantees treeminimality, a stronger property than 1-minimality, through exhaustive, syntax-guided search that can discover that removing Base also requires removing its super call and the inheritance. However, this is very costly and still misses opportunities [4]: V ULCAN cannot reduce our example even after six hours. III. S CYTHE Overview: Figure 2 shows the high-level architecture of S CYTHE, which runs as a fast pre-processing step before the

class Main

contains

contains contains Main.READY Main.active type

class Widget

class Base

value

inherits contains type Widget.«init»()

contains

call

Base.«init»()

call

Main.label()

call call

contains

type

Widget.check()

type

interface Supplier<R> contains

Supplier.get()

Fig. 3: The dependency graph of the program of Figure 1a.

actual language-agnostic reducer. Its goal is not to produce a fully minimized program or to remove every redundant token, but to quickly remove bulk code (Challenge 2) and whole declarations that the downstream reducer would struggle to reason about (Challenge 1). S CYTHE takes a source file P and a property oracle O, and outputs a program P ′ for the downstream reducer. The two may alternate until the program stops shrinking, as each can expose new opportunities for the other. Internally, S CYTHE iterates four steps until a fixpoint. Step 1: dependency graph construction: S CYTHE parses the input program P into a graph that we call the typed dependency graph. Each node represents a declaration, such as a function, field, or class. Each edge records how one declaration uses another. The edge labels let S CYTHE pick the right way to break each dependency before removing a declaration (see Step 3). The graph (Figure 3) captures four kinds of relationships: (1) containment (Main contains Main.active), (2) inheritance (Widget inherits from Base), (3) type (Main.active has type Widget), and (4) value/call (Main.READY reads Main.active). Step 2: delta debugging: S CYTHE applies delta debugging [5] over the nodes of G, i.e., at the level of declarations. Rather than a single reduction list over all nodes, S CYTHE schedules a sequence of passes, each on a single declaration type, ordered from coarse to fine-grained (e.g., classes, then

TABLE I: S CYTHE’s semantic decoupling operators. Declaration d (Kind)

Use Site u (Kind)

Class

inherits type

R EMOVE(u) A DD C LASS(u, R EPLACE(u,

Function

call (result used) call (unused result)

R EPLACE u, D EFAULT(ret(d)) R EMOVE(u)

Any

value

R EPLACE u, D EFAULT(type(d))

Any

contains

R EMOVE(d)

Operator

TABLE II: Sample results: size in tokens (Tok), time in seconds (s), and bug type (Prop): U (unexpected error), CR (crash), M (miscompilation). S

A); A)

methods, then fields). Deleting a class discards all its nested code in one oracle call. Each pass yields a candidate set D ⊆ V (G), tested against the oracle (Step 4). The process guarantees 1-minimality at the level of declarations. Step 3: program rewrite: For each declaration in the candidate set D, S CYTHE removes the declaration node and applies a set of semantic-aware decoupling operators that detach it from its use sites. To decide which operators to apply, S CYTHE examines the incoming edges of the node (its uses), together with those of the declarations it contains. The kind of reference selects the operator for each use (Table I). For example, to remove class Base (Figure 1a, line 10), S CYTHE applies R EMOVE to its inherits edge from Widget, dropping the extends clause, and to the call of its constructor from Widget’s constructor, whose result is unused. With both edges gone, Base and its constructor are deleted (Figure 1b). Similarly, a type use of a removed class is rewritten to a placeA (A DD C LASS; R EPLACE). A value use, or a holder class call whose result is used as an expression, is replaced by the default value of the corresponding type (D EFAULT(type(d))). This is why the references to Widget and the field active collapse to (( A) null) in Figure 1b (lines 3, 6). Step 4: property checking: If the rewritten P ′ still satisfies the oracle O, the change is committed (feedback arrow in Figure 2); otherwise, it is rolled back. Faulty rewrites thus never reach the output, assuming, like any reducer, a deterministic oracle. A. Implementation, Usage, and Availability S CYTHE is implemented in ∼4,000 lines of Python. Parsing is delegated to tree-sitter [6]; adding a new language only requires mapping tree-sitter node types to S CYTHE’s declaration and edge kinds and instantiating the operators of Table I. S CYTHE relies on the picire [7] library for delta debugging, but could be easily configured to use any list reduction algorithm (e.g., probabilistic delta debugging [8]). Users pass the input program, the oracle, and, optionally, a wrapper for the downstream reducer: scythe --language java --source-file A.java \ --script oracle.sh --post-processor perses.sh

S CYTHE is open source (GPL-3.0) at https://github.com/ itiarom/scythe, with a Docker image and usage instructions; the artifact is at https://doi.org/10.5281/zenodo.23589196.

Tok

P s Tok

Benchmark

Prop

Init

C clang-31259 gcc-64990 gcc-61917 gcc-59903

M M CR CR

48,079 147,002 84,473 56,951

Java jdk11-10 jdk11-7 jdk8-24 jdk8-34

U U CR CR

5,298 3,158 4,691 3,377

83 80 131 143

98 55 73 44

657 382 608 591

Solidity smart17 smart7 smart13 smart4

U U U U

2,570 4,103 1,500 1,288

69 143 55 100

65 60 48 22

93 92 84 64

S+P s Tok

2,101 744 518 4,111 1,861 1,807 435 4,624 2,471 2,515 579 5,956 2,635 1,839 722 5,171

s

240 104 125 302

3,546 3,687 4,177 4,723

731 343 796 649

31 31 74 95

124 81 121 116

298 325 161 122

16 33 38 29

86 133 91 59

IV. P RELIMINARY E VALUATION We evaluate whether S CYTHE improves the (RQ1) quality and (RQ2) efficiency of language-agnostic reducers. Benchmarks: No public dataset spans C, Java, and Solidity, so we collect 73 programs from three sources. C (20 benchmarks): the P ERSES benchmarks [2], Csmith [9]-generated programs that trigger crashes and miscompilations in GCC and LLVM, widely used in prior work [2], [4], [10]. Java (34 benchmarks): we generate programs with H EPHAESTUS [11] against OpenJDK: 20 programs that javac (JDK 11) rejects with an unexpected compile-time error and 14 that crash javac (JDK 8). Solidity (19 benchmarks): smart contracts from the dataset of Mitropoulos et al. [12], each triggering a different warning or error in the Slither static analyzer [13]. Reducers: We pair S CYTHE with two state-of-the-art reducers: the grammar-based P ERSES [2] and L ATRA [4], which adds language-specific transformation templates and performs comparably to C-Reduce. We run L ATRA only on C, as it does not support Java or Solidity. We exclude C-Reduce [1]: it is C-specific, whereas S CYTHE is designed to boost languageagnostic reducers, so the two are complementary rather than competing. For each benchmark and reducer R, we run three pipelines: (1) S CYTHE alone (S), (2) R alone (P or L), and (3) S CYTHE followed by R (S+P or S+L). Results: Table II shows four benchmarks per language (all are in our artifact), and Figure 4 shows the distributions across all benchmarks. S CYTHE’s own runtime is small (14 minutes, 50 seconds, and 30 seconds on C, Java, and Solidity). S+P substantially reduces final program size by 71.7%, 59.5%, and 31.6% on average for C, Java, and Solidity, respectively. S+P accelerates reduction by 1.6×, 3×, and 1.6× on average for C, Java, and Solidity, respectively. On C, this saves 23 minutes per benchmark on average and up to 2.5 hours. Overall, S+P is never larger than P, strictly smaller on 70 of 73 benchmarks, and faster on 67. Beyond P ERSES: The benefits carry over to L ATRA: S+L is 2.4× faster than L on average (up to 7.3×), cutting total time from 19.0 to 11.4 hours. Although L ATRA already applies

Tokens

S (a) Tokens

S+P

L

context-sensitively, to open further opportunities downstream and avoid the L ATRA regressions.

S+L

1K

R EFERENCES

100 10 10K

Time (s)

P

C

Java

Solidity

C

Java with Perses

Solidity

C with Latra

(b) Time

1K 100 10

C

S+R vs. R Δ% tokens, mean Δ% tokens, median Speedup, mean Speedup, median

C −71.7% −74.0% 1.6× 1.3×

with Perses Java Solidity −59.5% −31.6% −61.2% −25.4% 3.0× 1.6× 2.4× 1.6×

with Latra C −10.6% −15.2% 2.4× 2.0×

Fig. 4: Reduction size (a) and time (b) of S CYTHE alone (S), a reducer R alone (P: P ERSES; L: L ATRA, hatched), and S CYTHE followed by R (S+R). language-specific transformations, S+L yields smaller programs than L in 13 cases and equal ones in one (15.2% smaller at the median, up to 61.8%). In six cases, the output grows by 3–86 tokens, as S CYTHE’s default values (Table I), e.g., 0xDEADBEEF for an int, can hinder L ATRA’s transformations; we plan to fix this in future work (Section VI). V. R ELATED W ORK The closest line of work is grammar-guided reduction over a syntactically valid parse tree. P ERSES [2] introduced the quotient representation that keeps every candidate parseable, PARDIS [14] prioritises subtrees by expected gain, and typebatched reduction [15] amortises oracle cost across simultaneous queries. All operate within a single parse tree, whereas S CYTHE runs one step before them, pruning whole declarations on a graph abstraction, and composes with any of them. The remaining reducers fall into two groups. Deltadebugging engines (ddmin [5], HDD [16], P ICIRE [7], P ROB DD [8]) improve the underlying search policy and are orthogonal to S CYTHE: any can replace its delta-debugging core. Language-specific reducers (C-R EDUCE [1], GTR [17], LPR [18]) encode per-language passes (hand-coded, learned, or LLM-suggested) and reach smaller results, but work in only one language. S CYTHE complements both families, and even improves L ATRA, which performs on par with C-Reduce. VI. C ONCLUSION AND F UTURE W ORK We presented S CYTHE, a semantic-aware front-end that makes language-agnostic reducers both faster and more effective, without modifying them. Paired with P ERSES, S CYTHE never produced a larger result across 73 benchmarks in three languages, halved the output in 50 of them, and cut total reduction time from 31.2 to 21.0 hours, lowering the compute and energy cost of debugging. Beyond this preliminary evaluation, we plan to select operators (Table I) and default values

[1] J. Regehr, Y. Chen, P. Cuoq, E. Eide, C. Ellison, and X. Yang, “Testcase reduction for C compiler bugs,” in Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM, 2012, pp. 335–346. [2] C. Sun, Y. Li, Q. Zhang, T. Gu, and Z. Su, “Perses: Syntax-guided program reduction,” in Proceedings of the 40th International Conference on Software Engineering. ACM, 2018, pp. 361–371. [3] H. Xu, Z. Wang, S. Hao, J. Li, W. Wang, and L. Zhang, “Pushing the Limit of 1-Minimality of Language-Agnostic Program Reduction,” in Proceedings of the ACM on Programming Languages, OOPSLA. ACM, 2023. [4] Z. Xu, Y. Wang, Y. Tian, M. Zhang, and C. Sun, “Latra: A templatebased language-agnostic transformation framework for effective program reduction,” in 2025 40th IEEE/ACM International Conference on Automated Software Engineering (ASE). IEEE, 2025, pp. 2274–2285. [5] A. Zeller and R. Hildebrandt, “Simplifying and isolating failure-inducing input,” IEEE Transactions on Software Engineering, vol. 28, no. 2, pp. 183–200, 2002. [6] “Introduction to Tree-Sitter,” https://tree-sitter.github.io/tree-sitter/, 2026, accessed online; June 24, 2026. [7] R. Hodován and A. Kiss, “Practical improvements to the minimizing delta debugging algorithm,” in Proceedings of the 11th International Joint Conference on Software Technologies (ICSOFT). SciTePress, 2016, pp. 241–248. [8] G. Wang, R. Shen, J. Chen, Y. Xiong, and L. Zhang, “Probabilistic delta debugging,” in Proceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE). ACM, 2021, pp. 881–892. [9] X. Yang, Y. Chen, E. Eide, and J. Regehr, “Finding and understanding bugs in C compilers,” in Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM, 2011, pp. 283–294. [10] Z. Xu, Y. Tian, M. Zhang, J. Zhang, P. Liu, Y. Jiang, and C. Sun, “T-Rec: Fine-grained language-agnostic program reduction guided by lexical syntax,” ACM Trans. Softw. Eng. Methodol., vol. 34, no. 2, Jan. 2025. [11] Hephaestus Compiler Project, “Hephaestus: A compiler testing framework,” https://github.com/hephaestus-compiler-project/hephaestus, accessed: 2026-06-12. [12] C. Mitropoulos, M. Kechagia, C. Maschas, S. Ioannidis, F. Sarro, and D. Mitropoulos, “Broken agreement: The evolution of Solidity error handling,” in Proceedings of the 18th ACM/IEEE International Symposium on Empirical Software Engineering and Measurement. ACM, 2024, pp. 257–268. [13] J. Feist, G. Grieco, and A. Groce, “Slither: A static analysis framework for smart contracts,” in 2019 IEEE/ACM 2nd International Workshop on Emerging Trends in Software Engineering for Blockchain (WETSEB). IEEE, 2019, pp. 8–15. [14] G. Gharachorlu and N. Sumner, “Pardis: Priority aware test case reduction,” in Proceedings of the 22nd International Conference on Fundamental Approaches to Software Engineering (FASE). Springer, 2019, pp. 409–426. [15] ——, “Type batched program reduction,” in Proceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA). ACM, 2023, pp. 727–739. [16] G. Misherghi and Z. Su, “HDD: Hierarchical delta debugging,” in Proceedings of the 28th International Conference on Software Engineering. ACM, 2006, pp. 142–151. [17] S. Herfert, J. Patra, and M. Pradel, “Automatically reducing treestructured test inputs,” in Proceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering (ASE). IEEE, 2017, pp. 861–871. [18] M. Zhang, Y. Tian, Z. Xu, Y. Dong, S. H. Tan, and C. Sun, “LPR: Large language models-aided program reduction,” in Proceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA). ACM, 2024, pp. 261–273.

Related documents

• ClarifyCodeBench: Evaluating LLMs on Clarifying Ambiguous Requirements for Code Generation#798985
• ClarifyCodeBench: Evaluating LLMs on Clarifying Ambiguous Requirements for Code Generation#797571
• MSLL: A Runtime Multi-Stack Parsing Approach for Interactive Grammar Development - A Lightweight Extension of LL-Style Recursive Descent#1013272
• An Empirical Study on the Potential of LLMs in Automated Software Refactoring#1037683
• The Imitation Game: When LLMs Learn to Reason Like Programs via Code-Centric Reasoning Data Synthesis#1110466