💻 computer science

State Machine Guided Multi-Relational Synthetic Data from Logs for Anomaly Detection

This paper proposes a framework that recovers a latent state machine from software logs to generate multi-relational synthetic data, which significantly enhances anomaly and bug detection performance by preserving structural, temporal, and process constraints that sequence-based methods overlook.

Original authors: Aja Khanal, Apurva Narayan

Published 2026-06-02

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Aja Khanal, Apurva Narayan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a massive software system as a giant, busy factory. Every time a machine starts, stops, or makes a sound, it writes a note in a giant, messy logbook. These notes are the "logs" the paper talks about.

The Problem: The Messy Logbook
Currently, when computer scientists try to find mistakes (anomalies) in these factories, they treat the logbook like a simple list of words. They look at the sequence of notes: "Machine A started," "Machine B hummed," "Machine C stopped."

The authors argue this is like trying to understand a complex play just by reading the list of words spoken, without knowing the plot, the characters, or the rules of the stage. In reality, these logs follow a hidden script (a State Machine). The factory doesn't just make random noises; it moves through specific "states" (like "Idle," "Working," "Error," "Recovery") and follows strict rules about what can happen next.

Existing methods miss this hidden script. They try to guess what's wrong by looking at the order of words, often missing the deeper structural reasons why a failure happened.

The Solution: LogSynthFSM (The Smart Factory Manager)
The paper introduces a new system called LogSynthFSM. Think of this as a team of specialized AI detectives working together to solve the mystery of the factory logs. Instead of one AI trying to do everything at once, they use a "multi-agent" approach, where each agent has a specific job:

The Translator (Execution Parsing Agent): First, this agent reads the messy, raw logbook and cleans it up. It turns chaotic sentences into neat, structured cards with clear labels (like "Time," "Event Type," "Details").
The Scriptwriter (State Discovery Agent): This agent looks at the cleaned cards and figures out the hidden script. It asks: "What are the different 'moods' or 'states' the factory goes through? What rules govern the transition from 'Working' to 'Broken'?" It builds a map of the factory's logic.
The Architect (Schema Induction Agent): Once the script is known, this agent designs a new filing system (a relational database). Instead of a single long list, it organizes the data into connected tables: one for the timeline, one for the events, one for the states, and one for the details. This ensures the data is organized logically, just like a real database.
The Storyteller (Relational Synthesis Agent): This is the magic part. The factory doesn't always have enough examples of rare problems (like a specific type of crash). To fix this, the Storyteller uses the script and the filing system to invent new, realistic stories. It doesn't just copy-paste old logs; it generates new scenarios that follow the rules of the script. Crucially, it focuses on creating more examples of those rare, tricky failures so the computer can learn to spot them.
The Quality Inspector (Consistency Evaluation Agent): Before the new stories are accepted, this agent checks them. "Did this new story follow the script? Is the timeline logical? Does it look like a real factory event?" If a story breaks the rules, it gets thrown out. This ensures the fake data is high-quality and trustworthy.

The Result: Better Safety Checks
The paper shows that when you use this new, structured, AI-generated data to train a computer to spot factory errors, it works much better than before.

Analogy: Imagine teaching a security guard to spot a thief. If you only show them 10 photos of thieves, they might miss a new type of thief. But if you have a smart system that understands the rules of how thieves move (the script), it can generate hundreds of new, realistic photos of different types of thieves (including rare ones) for the guard to study. The guard becomes much better at catching them.

Key Takeaways from the Paper:

Structure Matters: Logs aren't just random words; they follow a hidden state machine (a script).
Multi-Agent Team: Breaking the task into small, specialized AI roles works better than one big AI trying to do it all.
Smart Synthesis: The system generates new data that respects the rules of the system, making it useful for training anomaly detectors.
Real-World Proof: The authors tested this on real data from big systems (like Hadoop and OpenStack) and found it significantly improved the ability to detect bugs and rare failures compared to older methods.

In short, LogSynthFSM turns a messy pile of notes into a structured, rule-based storybook, uses that storybook to invent new training examples for rare problems, and helps computers become much better at spotting when something goes wrong in complex software systems.

Technical Summary: State Machine Guided Multi-Relational Synthetic Data from Logs for Anomaly Detection

Problem Formulation

Modern software systems generate massive volumes of unstructured execution logs that record behavior, failures, and component interactions. While these logs are central to anomaly detection, existing methods predominantly treat them as flat sequences of event templates. This approach overlooks the latent relational execution structure—the control flow, state transitions, and dependencies among parameters, resources, and components—that governs how executions evolve.

Current log synthesis and augmentation techniques often operate at the template or sequence level, failing to respect underlying execution semantics. Consequently, they frequently produce unrealistic or structurally invalid traces that do not generalize to complex failure modes. Furthermore, while Large Language Models (LLMs) show promise in understanding unstructured text, applying them in a single-pass manner for log synthesis is insufficient due to context window limitations, a lack of structural guarantees, and susceptibility to hallucination when generating complex execution traces. The core challenge addressed is the joint discovery of latent execution structure from raw logs and the use of that structure to guide the principled generation of multi-table relational synthetic data.

Methodology: LogSynthFSM

The authors propose LogSynthFSM, a coordinated multi-agent LLM framework designed to discover latent execution structures and generate multi-relational synthetic data. The system decomposes the synthesis task into specialized agents operating in a closed-loop pipeline:

Execution Parsing Agent: Converts raw, unstructured logs into structured event representations ( $e_i = (t_i, \theta_i, \tau_i)$ ), extracting templates, parameters, and timestamps. This acts as a compression operator to reduce lexical noise and mitigate LLM context limitations.
State Discovery Agent: Infers a latent Finite State Machine (FSM) ( $F = (S, A, \delta)$ ) from the structured event sequences. It groups events into states such that the resulting sequence satisfies a Markov property, balancing expressiveness and identifiability to recover the control flow governing the system.
Schema Induction Agent: Transforms the inferred FSM into an explicit multi-table relational schema ( $R$ ). This schema includes tables for traces, events, states, transitions, and parameters, connected by primary and foreign key constraints. This factorization separates control flow from state-conditional attributes, ensuring structural faithfulness.
Relational Synthesis Agent: Generates synthetic relational data by sampling valid state paths from the inferred FSM and synthesizing event/parameter records conditioned on state-specific distributions. This agent amplifies rare but valid execution behaviors while strictly adhering to the structural and temporal constraints of the FSM.
Consistency Evaluation Agent: Assesses the generated data across three dimensions:
- Structural Consistency: Verifies schema constraints (keys, ordering, valid transitions).
- Process Consistency: Ensures executions correspond to legal FSM traversals.
- Distributional Consistency: Compares attribute distributions against real data to detect drift.
  This agent provides feedback to guide iterative refinement, filtering out invalid or hallucinated outputs.

The framework operates as an iterative loop where the Consistency Evaluation Agent validates batches of synthetic data against the inferred FSM and schema, ensuring that only structurally valid and distributionally realistic data is retained for downstream use.

Key Contributions

Latent Structure Discovery: The paper demonstrates that execution logs implicitly encode a relational database governed by a latent state machine, which can be recovered directly from raw logs without prior knowledge of the system's architecture.
Multi-Agent Framework: It introduces a novel multi-agent architecture that decomposes the complex task of log synthesis into verifiable stages (parsing, state discovery, schema induction, synthesis, and evaluation), overcoming the limitations of single-pass LLM generation.
Relational Synthetic Data: Unlike sequence-based augmentation, LogSynthFSM generates multi-table relational data that preserves global process semantics, temporal ordering, and cross-entity dependencies.
Constraint-Aware Generation: By using the recovered FSM as a generative prior, the framework ensures that synthetic data adheres to strict execution constraints, preventing the creation of semantically incoherent traces.

Experimental Results

The framework was evaluated on four real-world system log datasets (BGL, Thunderbird, Hadoop, OpenStack) using a Graph Neural Network (GNN) for downstream anomaly detection.

Anomaly Detection Performance: LogSynthFSM achieved a PR-AUC of 0.742, outperforming the strongest LLM-based baseline (GraphMaster at 0.701) and classical augmentation methods.
Rare Event Detection: The method significantly improved the detection of rare behaviors, increasing the Rare PR-AUC from 0.438 (GraphMaster) to 0.511.
Structural Fidelity:
- Transition Validity Rate (TVR): 0.985, indicating that 98.5% of synthetic transitions were valid according to the inferred FSM.
- Distributional Similarity: The $k$ -gram path Jensen–Shannon divergence was reduced to 0.091 (compared to 0.137 for GraphMaster), showing closer alignment with real execution dynamics.
- Distinguishability: The Classifier Two-Sample Test (C2ST) AUC was 0.503 (near the ideal 0.50), suggesting synthetic traces are difficult to distinguish from real ones.
Ablation Studies: Removing the State Discovery Agent caused the most severe degradation (Rare PR-AUC dropped to 0.341), confirming that explicit state modeling is essential. Removing the Consistency Evaluation Agent also reduced PR-AUC (to 0.703) and increased C2ST AUC (to 0.567), highlighting the necessity of closed-loop validation.
Efficiency: The system runs effectively on consumer-grade hardware (single RTX 4080 SUPER) with runtimes of 41–52 minutes, demonstrating that specialized infrastructure is not required.

Significance and Claims

The paper claims that execution logs implicitly encode a relational database governed by a latent state machine. Recovering this structure enables principled synthetic data generation that is both robust and interpretable.

The authors emphasize that the performance gains are not merely due to the use of larger language models or increased data volume. Instead, the improvements stem from the architectural integration of execution parsing, state discovery, schema induction, and constraint-aware relational synthesis within a closed-loop multi-agent framework. This approach ensures structural correctness and distributional realism, addressing the fundamental limitation of existing methods that ignore the relational and process-level structure of software executions. The work suggests a promising direction for generating execution-aware synthetic data to improve anomaly detection in complex, distributed software systems.