Inductive First-Order Formula Synthesis by ASP: A Case Study in Invariant Inference
Ziyi Yang George Pîrlea Ilya Sergey · 2026
Read Inductive First-Order Formula Synthesis by ASP: A Case Study in Invariant Inference by Ziyi Yang George Pîrlea Ilya Sergey (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-03854.txt.
Introduction
Ziyi Yang, George Pîrlea, and Ilya Sergey present a framework for building first-order logic formulas from examples, aimed at inferring invariants of transition systems. Invariants are the safety facts a spread-out system must never break, and finding them on its own is a long-standing bottleneck in checking. The authors first study and sort current methods for encoding formula building inside answer set programming.
From that survey they propose orthogonal slices, a technique that splits the search space into handy chunks and enables two forms of step-wise pruning of candidates. Built into their FORCE framework, the mix greatly speeds up a state-of-the-art algorithm for spread-out system invariant inference. The framework also makes it easier to compose varied inference approaches, opening new tweaks for checking the protocols behind cloud infrastructure.
Catalog record
| CREATOR | Ziyi Yang George Pîrlea Ilya Sergey |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 51 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-03854
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Inductive First-Order Formula Synthesis by ASP: A Case Study in Invariant Inference Thanks: We thank Andrew Cropper, Roland Kaminski, and Jianan Yao for providing help on Popper , Clingo , and DuoAI , respectively. We are also grateful to Roland Yap for his feedback on a draft of this paper. This work was partially supported by a Singapore Ministry of Education (MoE) Tier 3 grant “Automated Program Repair” MOE-MOET32021-0001 and by Amazon Research Award “Scaling Automated Verification of Distributed Protocols with Specification Transformation and Synthesis”. Affiliation: National University of Singapore, Singapore Ziyi Yang George Pîrlea Ilya Sergey Abstract We present a framework for synthesising formulas in first-order logic (FOL) from examples, which unifies and advances state-of-the-art approaches for inference of transition system invariants. To do so, we study and categorise the existing methodologies, encoding techniques in their formula synthesis via answer set programming (ASP). Based on the derived categorisation, we propose orthogonal slices , a new technique for formula enumeration that partitions the search space into manageable chunks, enabling two approaches for incremental candidate pruning. Using a combination of existing techniques for first-order (FO) invariant synthesis and the orthogonal slices implemented in our framework FORCE , we significantly accelerate a state-of-the-art algorithm for distributed system invariant inference. We also show that our approach facilitates composition of different invariant inference frameworks, allowing for novel optimisations. 1 Introduction First-Order Logic (FOL) has been used with great success as a foundational tool for modelling and verifying complex systems. Its applications span various domains, ranging from hardware design [ 6 ] to software verification [ 22 ] . These successes are largely attributed to the development of advanced frameworks that allow for automated verification and synthesis, often supported by high-performance provers such as Z3 [ 20 ] and cvc5 [ 2 ] . To achieve fully automated verification of a complex system in FOL, it is often necessary to synthesise formulas capturing the invariants ( i.e. , the properties always hold) of the system being verified. Despite the undecidable nature of this task, many recent efforts have made substantial progress to infer inductive invariants of complex distributed systems ( e.g. , Lamport’s Paxos consensus protocol [ 17 ] ) by synthesising FO formulas from examples: sampled traces of a protocol or counter-examples to induction. The resulting approaches are implemented by a plethora of distinct frameworks [ 28 , 9 ] , and a systematic study of their inter-connections is still missing. This raises important questions: are the existing synthesis methods fundamentally non-overlapping? Could techniques developed for one approach be adapted to benefit others? Addressing these questions would not only deepen our understanding of the underlying methodologies but also enable the development of superior tools for formula synthesis, potentially improving scalability of automated verification tools across various domains. In this paper, we present a unified framework for synthesising bounded first-order formulas from examples—first-order structures that the formulas satisfy. Our framework is designed to encode and combine diverse synthesis techniques, enabling seamless integration with different high-level algorithms for invariant inference. To achieve this, we have conducted a detailed study of nine recent approaches for invariant inference of distributed systems (DS), each of which offered a different take on inductive synthesis of FO formulas. We summarise our study in two main observations w.r.t. inductive synthesis of FO formulas, hinting an opportunity for improvement in the state of the art: O1 Existing techniques fall within a small number of distinct classes, in terms of how they treat their inputs and results, e.g. , how examples are used and how formulas are constructed. We give a uniform categorisation of these approaches. O2 Whilst a wide variety of synthesis techniques exists, the vast majority fall into one of two categories, exploiting the properties of the first-order theories they employ: “redundancy elimination” and “incremental pruning”. To make a unified framework that captures O1 , we use Answer Set Programming (ASP) [ 18 ] , to encode the enumeration-based FO formula synthesis (as constraint solving) and the customisations and techniques of the synthesis (as knowledges representation). To improve on the existing techniques, we exploit O2 by proposing the idea of orthogonal slices (also implemented by ASP) of the FO search space: a new approach to efficiently prune candidate formulas during the inductive synthesis. The key idea of orthogonal slices is to partition the search space into ordered slices, where the synthesis of former slices can be used to prune the latter slices using either satisfied or unsatisfied formulas. The practical benefits of the unified framework, FORCE ( F irst- O rder synthesiser via o R thogonal sli CE s), are demonstrated by improving two state-of-the-art DS invariant synthesisers, DuoAI [ 28 ] and Flyvy [ 9 ] , without any conceptual modifications to their high-level algorithms . Our results show that our framework is sufficiently expressive and extensible to encode and compose existing formula synthesis techniques, advancing the state of the art in DS invariant synthesis. 2 Overview We start with a primer on inductive synthesis of FO formulas—a common subroutine in existing invariant inference frameworks for distributed systems (DS). Then we summarise nine notable existing approaches for DS invariant inference (with the earliest dated 2019), concluding with a brief description of our ASP-based framework to capture various aspects of the synthesis and its particular instance, orthogonal slices. 2.1 Problem Definition First-Order Language. In this work, we focus on system properties that are expressible in a first-order, many-sorted logic with equality, following the common textbook definitions. A signature \Sigma=\langle C,R,F,S\rangle consists of: a set of constant symbols C , a set of relation symbols (predicates) R , a set of function symbols F , and a set of sorts S for the variables, constants, and function symbols. In the rest of this paper we assume all signatures to be finite , i.e. , the sets C , R , F , and S are finite. Logic terms are defined recursively. A term is either a constant c\in C , a variable x , or a function symbol f\in F applied to other terms ( e.g. , f(x_{1},x_{2}) ). Logic atoms are the basic formulas formed by applying relation symbols from R or equality to terms of appropriate sorts; and a literal is an atom or its negation ( i.e. , \neg p(x) ). Formulas are constructed by closing literals under logical connectives ( i.e. , conjunction \land and disjunction \lor ) and quantification (universal \forall and existential \exists ). It is well-known that any FO formula can be transformed into an equivalent formula in prenex normal form , where all quantifiers are placed at the beginning. In this structure, the prefix includes the quantifiers, and the matrix consists of the remaining Boolean components. For example, the formula \forall x:s_{1}\,\exists y:s_{2}.~p(x,y)\lor(\neg q(x)\land r(y)) is in prenex normal form, with prefix \forall x:s_{1}\,\exists y:s_{2} and matrix p(x,y)\lor(\neg q(x)\land r(y)) . Definition 1 (First-Order Synthesis Problem) Given a set of formulas \Omega_{0} over signature \Sigma and a set of FO structures \sigma=\{M_{1},\dots,M_{k}\} , where each M_{i} is a model over \Sigma , find a set of formulas \Phi=\{\phi_{1},\ldots,\phi_{n}\}\subseteq\Omega_{0} s.t. \forall\phi\in\Phi : \displaystyle\text{1. }\forall M\in\sigma.M\models\phi,\quad \displaystyle\textsf{(satisfies all input FO structures)}, \displaystyle\text{2. }\text{FreeVars}(\phi)=\emptyset,\quad \displaystyle\textsf{(closed formula)}, \displaystyle\text{3. }\exists