CS Paper Radar

Augmenting Rewrite Rule Sets via Knuth-Bendix Completion

Michael Schifferer, Marcel Ullrich, Sebastian Hack

cs.PL ·submitted 2026-10-01 07:42 UTC · v1

Abstract

Equality Saturation (EqSat) is a powerful technique for program optimization, systematically exploring the search space of candidate programs to overcome the phase ordering problem. However, the feasibility and performance of EqSat rely heavily on the specific rewrite rules used to derive equivalent programs. These rule sets are typically handcrafted, requiring extensive domain expertise and carrying the risk of missing valuable transformations. In this work, we evaluate Knuth-Bendix Completion (KBC) as a method for automatically generating and augmenting rewrite rules for EqSat. Our experiments show faster optimization as well as reaching better terms with previously missed optimizations.

Closest papers

Nearest neighbours by meaning across the whole index.

Equality saturation theory exploration à la carte

cs.PL ·2026-09-13 ·Anjali Pal, Brett Saiki, Ryan Tjoa, Cynthia Richey, Amy Zhu +4 more
publishedhighly cited similarity 0.72
Abstract · 43 pages, 9 figures, Extended version of the OOPSLA 2023 paper, submitted to the Journal of Functional Programming. v2: corrected the accent…

Rewrite rules are critical in equality saturation, an increasingly popular technique in optimizing compilers, synthesizers, and verifiers. Unfortunately, developing high-quality rulesets is difficult and error-prone. Recent work to automatically infer rewrite rules does not scale to large terms or grammars. Users struggle to guide inference and incrementally construct rulesets because existing rule inference tools are monolithic and opaque. As a result, most equality saturation users still manually develop and maintain rulesets. This paper proposes Enumo, a new domain-specific language for programmable theory exploration. Enumo provides a small set of core operators that enable users to strategically guide rule inference and incrementally build rulesets. Short Enumo programs easily replicate results from state-of-the-art tools like Ruler, but Enumo programs can also scale to infer deeper rules from larger grammars than prior approaches. Enumo's composable operators even facilitate developing new strategies for ruleset inference. We introduce a new fast-forwarding strategy which does not require evaluating terms in the target language, and thus supports domains that were out of scope for prior work. Enumo is also easy to extend: two new operators suffice to incorporate large language models into rule inference, where they complement guided search. We evaluate Enumo and fast-forwarding across a variety of domains. Compared to state-of-the-art techniques, Enumo can synthesize better rulesets over a diverse set of domains, in some cases matching the effects of manually developed rulesets in systems driven by equality saturation.

0.55

Extending Higher-Order Critical Pairs

cs.LO ·2026-10-28 ·Johannes Niederhauser, Aart Middeldorp
similarity 0.62
Abstract

Confluence is a fundamental property of computation which implies that the nondeterminism of a system does not affect its outcomes. A key concept of confluence research in rewriting theory is the notion of critical pairs which captures the potential local sources of non-confluence. In this paper, we lift the definition of higher-order critical pairs to a more expressive class of higher-order rewrite systems. Thereby, we facilitate confluence analysis of rewrite systems which can express complex one-step computations as well as program transformations from functional programming.

0.19

Symbolic Execution of Constrained Horn Clauses

cs.LO cs.PL ·2026-10-02 ·Johannes Weiser, Zafer Esen, Philipp Rümmer
similarity 0.61
Abstract · 34 pages, 8 figures

Constrained Horn clauses (CHCs) are a fragment of first-order logic widely used as an intermediate language for verification. We study constrained resolution as a calculus for reasoning about the satisfiability of sets of CHCs. Constrained resolution forms a simple alternative to model checking algorithms such as CEGAR and IC3 and is here shown to exhibit complementary features. We show that, when CHCs encode programs, forward symbolic execution corresponds to positive unit hyper-resolution, and backward symbolic execution to SLD resolution, which are special cases of constrained resolution. We formalize forward and backward reasoning for linear and non-linear CHCs and transition systems, prove refutational completeness under fair strategies, and develop subsumption criteria for pruning redundant derivations. We moreover show that backward resolution with subsumption generalizes $k$-induction to non-linear CHCs, and that forward constrained resolution is related to the problem of constructing proofs in incorrectness logic. Lastly, we provide an experimental evaluation in the Eldarica CHC solver on benchmarks from CHC-COMP.

0.19

Metamorphic Testing for Floating-Point Performance Issues in SMT Solvers

cs.PL ·2026-09-17 ·Rosa Abbasi, Eva Darulova
similarity 0.61
Abstract · extended version with appendix of SEFM 2026 paper

SMT solvers are essential in various domains, including program verification and synthesis. Although their correctness and performance have been extensively studied, performance testing for the floating-point theory remains limited, particularly for real-world queries. We propose a metamorphic testing approach that uses semantics-preserving rewrite rules, focusing on floating-point special values and peep-hole optimizations, to uncover meaningful performance issues in SMT solvers' handling of floating-point formulas. Using real-world test inputs, our approach is able to identify for every solver tested SMT queries for which solving time increases when the queries are simplified; we see slowdowns of up to 33.4x for Z3, 5.6x for MathSAT, 4.5x for cvc5, and 1.8x for Bitwuzla. We further observe that the approach is less successful when using input files that were randomly generated from a grammar.

0.32

MetaphIR: Corpus-Scale Applicability Analysis for LLVM Peephole Optimizations

cs.PL cs.SE ·2026-11-17 ·Hongxu Xu, Xintong Zhou, Chunhao Liao, Chengnian Sun
similarity 0.61
Abstract

Peephole optimizations replace short source instruction sequences with more efficient equivalents, typically guarded by preconditions such as requiring a constant operand to be a power of two. Since every new rewrite adds maintenance burden and compile-time cost, compiler developers need to know how often real-world programs both match the source pattern and satisfy its preconditions before committing to an implementation. Existing workflows fall short: structural search over an intermediate representation (IR) corpus of 4.8 million functions ignores preconditions and therefore overcounts, whereas implementing the rewrite and recompiling the corpus yields exact counts only after paying the engineering cost, with each run of the corpus's on-demand recompilation pipeline taking a median of 47 minutes. This delay is especially limiting when generalizing a rewrite, as developers often iterate over multiple variants to trade off coverage against complexity. We introduce MetaphIR, a system pairing a domain-specific language for expressing LLVM peephole optimizations with an indexed search engine over large IR corpora. Using a syntax modeled on LLVM's C++ matchers, MetaphIR patterns augment LLVM IR with holes and Boolean preconditions over matched values. To answer queries at interactive speed, MetaphIR builds compact per-function summaries ahead of time and uses abstract interpretation over those summaries to soundly filter out functions that cannot satisfy a query's constraints. Across twenty recent peephole optimizations from LLVM's InstCombine pass, MetaphIR recovers the exact set of functions where each rewrite applies in isolation, achieving 100% precision and recall. Queries complete in a median of 1.27 seconds---a 22x speedup over a full corpus scan---enabling developers to quickly gauge an optimization's reach and generality prior to implementation.

0.13

An Applicative Multiset Path Order (Extended Version)

cs.LO ·2026-10-02 ·Nao Hirokawa, Teppei Saito, Teppei Tanaka, Wataru Yachi
similarity 0.58
Abstract

We present a variant of the multiset path order for untyped applicative term rewriting. Compared to existing work, our variant incorporates two distinctive features, dubbed arity assignment and reification, to overcome difficulties in handling partial and variable application.

0.30

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

cs.SE ·2026-11-04 ·Ioanna Moraiti, Charalambos Mitropoulos, Artem Anchikov, Sotirios Ioannidis, Dimitris Mitropoulos +1 more
similarity 0.58
Abstract

Automated program reduction shrinks a program into a smaller one that preserves a property of interest. Language-agnostic 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 SCYTHE, a fast, semantic-aware pre-processing step that runs in front of any grammar-based reducer without modifying it. SCYTHE encodes the program as a typed declaration dependency graph and applies 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 SCYTHE with PERSES never yields a larger result than PERSES 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$\times$ faster (up to 7.4$\times$). SCYTHE also boosts LATRA, a reducer that, unlike the purely syntactic PERSES, also applies language-specific transformations: the combination produces programs 10.6% smaller (up to 61.8%) and is 2.4$\times$ faster on average. Video: https://youtu.be/uEq_YYU0zZw

0.26

Symbolic Synthesis with Token-Level LLM Guidance

cs.PL ·2026-11-08 ·Derek Egolf, Stavros Tripakis
similarity 0.56
Abstract

We propose a synergistic combination of classical program synthesis techniques and contemporary large language models (LLMs) to solve the problem of recursive program synthesis from first-order logic specifications. Our approach leverages the strengths of both paradigms: we use LLMs as a source of statistical bias to guide the search for a correct program. At the same time we use techniques from classical synthesis to short-circuit on semantically incorrect prefixes and to avoid sampling semantically equivalent responses. The statistical bias is derived from the next-token distribution of an LLM, which is highly context-dependent. We operate with the understanding that (1) there is some class of synthesis instances that can be discharged by small models and symbolic tools, and (2) every other instance can be decomposed into these instances. Therefore, our intention is to expand the reach of small, open-weight LLMs and symbolic synthesis techniques, not to compete with proprietary frontier models on every possible instance. These are different tools for different jobs. In our experimental evaluation, we find that our method solves more benchmarks than either small LLMs or classical synthesis techniques alone. Our method solves 30/32 benchmarks using only a Qwen2.5 model with 32 billion parameters. Qwen2.5 solves 0 benchmarks on its own, and only solves a few additional benchmarks when combined with traditional constrained decoding techniques.

0.25