Mining Beyond the Bools: Learning Data Transformations and Temporal Specifications

Sam Nicholas Kouteili, William Fishell, Christian Scaff, Mark Santolucito †, Ruzica Piskac · 2026

Read Mining Beyond the Bools: Learning Data Transformations and Temporal Specifications by Sam Nicholas Kouteili, William Fishell, Christian Scaff, Mark Santolucito †, Ruzica Piskac (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-2603-06710.txt.

Introduction

Sam Nicholas Kouteili and colleagues widen spec mining from bare true-false events to data-aware behavior. They first find candidate functions that cover the traces with syntax-guided synthesis. They then give a finite-prefix semantics for TSL_f, a temporal stream logic with first-order predicates and functional updates. That pairing unifies learning of data transforms and time-based specs. On Gymnasium ToyText tasks, mined specs beat passive learning baselines on sample use.

Catalog record

CREATORSam Nicholas Kouteili, William Fishell, Christian Scaff, Mark Santolucito †, Ruzica Piskac
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE70196
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.06710

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Mining Beyond the Bools: Learning Data Transformations and Temporal Specifications Sam Nicholas Kouteili, William Fishell, Christian Scaff, Mark Santolucito †, Ruzica Piskac Abstract Mining specifications from execution traces presents an automated way of capturing characteristic system behaviors. However, existing approaches are largely restricted to Boolean abstractions of events, limiting their ability to express data-aware properties. In this paper, we extend mining procedures to operate over richer datatypes. We first establish candidate functions in our domain that cover the set of traces by leveraging Syntax-Guided Synthesis (SyGuS) techniques. To capture these function applications temporally, we formalize the semantics of TSL f , a finite-prefix interpretation of Temporal Stream Logic (TSL) that extends LTL f with support for first-order predicates and functional updates. This allows us to unify a corresponding procedure for learning the data transformations and temporal specifications of a system. We demonstrate our approach synthesizing reactive programs from mined specifications on the OpenAI-Gymnasium ToyText environments, finding that our method is more robust and orders of magnitude more sample-efficient than passive learning baselines on generalized problem instances. 1 Introduction Specification mining is the process of deriving logical properties from demonstrations, discovering invariants that unify observations or discriminate positive and negative examples [ 3 , 34 , 36 ] . Manually crafting specifications is an error-prone process, with numerous examples where flawed specifications have led to serious software failures. For instance, faulty specifications in the Linux kernel have resulted in exploitable vulnerabilities [ 20 ] , while specification gaps have caused critical failures in large-scale cloud systems [ 37 ] . To reduce reliance on human intuition, specification mining automates learning directly from executions. Standard approaches to specification mining analyze execution traces, which capture system behavior over time. As a result, temporal logics are used as a natural formalism for expressing the specification. Linear Temporal Logic (LTL) [ 38 , 16 ] and its finite-prefix interpretation LTL f [ 19 ] have long been the standard for encoding temporal properties of systems, with applications in agent-based planning [ 5 , 2 ] and runtime verification [ 17 ] . Recent mining tools such as Scarlet [ 40 ] and Bolt [ 8 ] demonstrate the feasibility of mining LTL f specifications. Despite their adoption, LTL and LTL f are propositional formalisms, meaning that all events are encoded as Booleans. This results in multiple challenges. For example, to express properties that depend on variable evolutions (i.e. “move x to the cell above the nearest obstacle”), we can either hand-craft predicates and their interpretations (requiring manual intervention) or bit-blast the trace’s data (increasing formula size and potentially introducing spurious semantic relations). Temporal Stream Logic (TSL) [ 23 ] presents a more expressive alternative that addresses this. By separating control from data, TSL allows specifications to express properties not only about the temporal ordering of events, but also about the data transformations applied to variables defined over arbitrary types. In this paper, we demonstrate that a temporal logic equipped with data transformations offers an expressive formalism for capturing complex specifications. Because specification mining operates over finite traces, we introduce TSL f , a finite-prefix interpretation of TSL. TSL f improves on the expressivity of LTL f by natively capturing functional updates on variables over time. Our specification mining algorithm operates on sets of input traces whose variables may range over arbitrary types, not just Booleans. To infer a specification, we must first discover functions that change system variables over time, and the temporal relations among those variables. We use Syntax-Guided Synthesis (SyGuS) [ 1 ] for the automatic discovery of functions from input-output examples. To identify a set of functions that captures how variables evolve, our procedure synthesizes a function for every variable at every time step. We next iteratively prune this set until we find functions that minimally describe the data transformations over the entire trace. Finally, using the learned set of transformations, we lift our data traces to function application traces. Such traces are then amenable to standard mining algorithms such as Boolean Subset Cover [ 8 ] . We evaluate our approach on the OpenAI-Gymnasium ToyText suite [ 11 ] , a collection of environments in which agents must reason temporally to reach a goal state. Using only positive and negative traces, and without any domain-specific knowledge, action functions, or fine-grained reward signals, our method extracts specifications that fully capture the environment objectives. We validate these mined specifications by synthesizing reactive controllers and deploying them as game-playing agents, achieving perfect win rates on held-out configurations using only a small number ( \leq 20 ) of examples. Our approach significantly outperforms both symbolic and neural baselines, requiring an order of magnitude fewer examples while demonstrating better performance on generalized problems. Overall, this work enables the mining of more expressive temporal properties than prior approaches; more broadly, it presents a step toward a purely symbolic reinforcement learning (RL) paradigm, where an agent interacts with an environment, learns from mining generated traces, and refines itself through formal specification. In summary, our contributions are as follows: • We present a bottom-up synthesis algorithm that discovers function sets that cover full execution traces, with a greedy input-swapping strategy. • We introduce a specification mining framework over functions and datatypes using TSL f , a finite-trace semantics for Temporal Stream Logic. • We show on standard RL benchmarks that from mined specifications, we can synthesize reactive programs that are sample-efficient and generalizable. ⬇ { p : (0 , 0) , g : (3 , 3) , h0 : (1 , 1) , h1 : (0 , 3) , h2 : (3 , 2)} { p : (0 , 1) , g : (3 , 3) , h0 : (1 , 1) , h1 : (0 , 3) , h2 : (3 , 2)} { p : (0 , 2) , g : (3 , 3) , h0 : (1 , 1) , h1 : (0 , 3) , h2 : (3 , 2)} { p : (1 , 2) , g : (3 , 3) , h0 : (1 , 1) , h1 : (0 , 3) , h2 : (3 , 2)} { p : (2 , 2) , g : (3 , 3) , h0 : (1 , 1) , h1 : (0 , 3) , h2 : (3 , 2)} { p : (2 , 3) , g : (3 , 3) , h0 : (1 , 1) , h1 : (0 , 3) , h2 : (3 , 2)} { p : (3 , 3) , g : (3 , 3) , h0 : (1 , 1) , h1 : (0 , 3) , h2 : (3 , 2)} ⬇ { p : (0 , 0) , g : (3 , 3) , h0 : (1 , 1) , h1 : (0 , 3) , h2 : (3 , 2)} { p : (1 , 0) , g : (3 , 3) , h0 : (1 , 1) , h1 : (0 , 3) , h2 : (3 , 2)} { p : (2 , 0) , g : (3 , 3) , h0 : (1 , 1) , h1 : (0 , 3)

Read the complete text