🤖 machine learning

Promoting Simple Agents: Ensemble Methods for Event-Log Prediction

This paper demonstrates that lightweight n-gram models, particularly when enhanced by a proposed "promotion" ensemble algorithm that dynamically selects between active models, achieve accuracy comparable to or better than neural architectures for event-log prediction while offering superior stability and significantly lower computational costs.

Original authors: Benedikt Bollig, Matthias Függer, Thomas Nowak, Paul Zeinaty

Published 2026-04-24

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Benedikt Bollig, Matthias Függer, Thomas Nowak, Paul Zeinaty

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 you are trying to predict what a busy hospital will do next. Will the patient go to surgery? Will they be discharged? Or will they need a new test?

The hospital generates a massive, continuous stream of notes (an "event log"). Your job is to look at the history of a specific patient and guess their very next step. This is the challenge of Event-Log Prediction.

For a long time, experts have tried to solve this using two main approaches:

The "Super-Brain" (Neural Networks): These are complex AI models like LSTMs and Transformers. They are like genius detectives who can read thousands of pages of history to find subtle patterns. They are powerful but slow, hungry for computer power, and sometimes get confused if they look at too much or too little history.
The "Simple Note-Taker" (n-grams): These are lightweight models that just look at the last few steps. If a patient usually goes "Check-up → Blood Test → X-Ray," the note-taker just remembers that pattern. They are fast and cheap but can get stuck if the pattern is too long or complex.

The Problem: The "Window" Dilemma

Both methods have a tricky setting called the Window Size.

Imagine looking through a window at a parade.
If the window is too small, you miss the context (you see a clown but don't know it's a circus).
If the window is too big, you get overwhelmed by the whole parade, and the "Super-Brain" gets confused trying to focus on the right part.
Finding the perfect window size is like trying to guess the exact right amount of salt for a soup without tasting it first. It's a gamble.

The Solution: A Team of Simple Agents

The authors of this paper asked: What if we didn't rely on one genius detective or one simple note-taker, but instead used a team of simple agents working together?

They tested two ways to do this:

1. The "All-Hands-On-Deck" Approach (Classic Ensemble)

Imagine hiring a whole committee of note-takers, each looking through a window of a different size (one looks at the last 3 steps, another at 5, another at 10, etc.). They all shout out their predictions, and you take a vote.

Pros: Very accurate.
Cons: It's expensive. You have to run all those agents at the same time, which eats up a lot of memory and slows things down. It's like hiring 50 people to answer one phone call.

2. The "Promotion Algorithm" (The Paper's Innovation)

This is the star of the show. Instead of hiring a whole committee, you hire two agents:

Agent A: A simple note-taker with a small window (looking at the last few steps).
Agent B: A slightly smarter note-taker with a bigger window (looking at more history).

How it works:

You let Agent A do the predicting because it's fast and cheap.
You quietly watch Agent B in the background.
If Agent B starts getting the answers right more often than Agent A for a few steps in a row (say, 20 times), you promote Agent B to be the main predictor.
If Agent B starts making mistakes, you don't fire it; you just keep it in reserve. If a third, even bigger agent is available, you might promote that one instead.

The Analogy:
Think of it like a relay race where the baton is passed based on performance. You don't need 10 runners sprinting at once. You just have one runner going, and a coach watching a second runner. If the second runner starts running faster, the coach yells, "Switch!" and the second runner takes over.

What Did They Find?

Simple is often enough: The simple "note-takers" (n-grams) were surprisingly good. They matched the accuracy of the complex "Super-Brains" (Neural Networks) in many cases.
Stability: The complex AI models sometimes crashed or got confused when the "window size" was wrong. The simple agents were much more stable.
The Winner: The Promotion Algorithm was the best of both worlds. It was almost as accurate as the complex AI, but it was much faster and used much less computer power because it only ever ran two simple agents at a time.

Why Does This Matter?

In the real world, we need predictions to happen instantly (like predicting a server crash before it happens or a patient's deterioration in real-time).

Running a giant, complex AI model is like using a supercomputer to check the weather; it works, but it's overkill and slow.
The Promotion Algorithm is like a smart, lightweight weather app that updates itself based on who is currently doing the best job. It's fast, efficient, and reliable.

In short: You don't always need a giant brain to solve a problem. Sometimes, a small team of simple workers, who know when to step up and take charge, is the most efficient solution.

1. Problem Statement

The paper addresses the challenge of next-activity prediction in streaming event logs, a core task in process mining. Modern information systems generate continuous, time-ordered logs of discrete activities (e.g., hospital patient treatments, server operations). The goal is to predict the next activity in a specific process instance (case) based on its history.

Key Challenges Identified:

Resource Intensity: State-of-the-art deep learning models (LSTMs, Transformers) often require significant computational resources and memory, making them less suitable for real-time, high-throughput streaming applications.
Window Size Sensitivity: Streaming models often rely on sliding windows to limit context. However, selecting the optimal window size is difficult. Too small a window misses long-term dependencies; too large a window leads to data sparsity (for statistical models) or computational degradation (for attention-based models).
Instability: Neural models, particularly Transformers, have been observed to exhibit unstable performance patterns when window sizes vary, sometimes suffering sudden accuracy drops.
Ensemble Overhead: While ensemble methods (combining multiple models) can improve robustness, traditional approaches like soft voting require running many agents in parallel, increasing latency and memory consumption.

2. Methodology

The authors propose a comparative study of lightweight automata-based models against complex neural architectures, culminating in a novel ensemble strategy.

A. Baseline Models

n-grams: Represented as Probabilistic Deterministic Finite Automata (PDFAs). They rely on the frequency of the last $n-1$ activities (history) to predict the next activity. They are computationally cheap and inherently suited for streaming.
LSTM (Long Short-Term Memory): A recurrent neural network capable of capturing long-term dependencies via memory cells.
Transformer: An attention-based architecture. In streaming settings, the authors utilize sliding windows to truncate input sequences to manage computational costs, employing Rotary Positional Embeddings (RoPE).

B. The Novelty: The Promotion Algorithm

To overcome the trade-off between the robustness of ensembles and the overhead of running multiple agents, the authors propose the Promotion Algorithm.

Mechanism: Instead of running all agents in parallel (like soft voting), this algorithm maintains only two active models at any given time during inference:
1. A current active model ( $M_i$ ) with a smaller window size.
2. A candidate model ( $M_{i+1}$ ) with a larger window size.
Logic: Both models predict the next activity. The system tracks the accuracy of both. If the larger-window model ( $M_{i+1}$ ) outperforms the current model for a consecutive threshold of $\tau$ predictions, it is "promoted" to become the new active model.
Advantages: This dynamic selection reduces memory footprint and latency significantly compared to full ensembles while adapting to the optimal context size for the current data stream.

C. Experimental Setup

Synthetic Datasets: Designed to test specific properties like counting, periodicity, and discrimination (e.g., $AAABBB$, $xx\bar{x}$ ). These include deterministic and randomized patterns to test generalization.
Real-World Datasets: Five standard process mining datasets (Sepsis, BPI 2012, 2013, 2017, 2018) ranging from ~15k to ~2.5M events.
Metrics: Prediction accuracy, average prediction time ( $\Delta t_{pred}$ ), and training time ( $\Delta t_{train}$ ).

3. Key Contributions

Empirical Analysis of Window Sizes: The study demonstrates that while LSTMs and Transformers generally achieve high accuracy, they are highly sensitive to window size. Transformers, in particular, show performance degradation as window sizes increase beyond a certain point due to attention mechanism limitations. In contrast, n-grams provide stable accuracy over a broad range of window sizes.
The Promotion Algorithm: A novel, low-overhead ensemble method that dynamically switches between two agents. It achieves the robustness of an ensemble without the parallel execution cost of traditional voting schemes.
Efficiency vs. Accuracy Trade-off: The paper establishes that simple n-gram ensembles can match or exceed the accuracy of non-windowed neural models while requiring substantially fewer computational resources.

4. Results

Synthetic Data Findings

Stability: n-grams maintained stable accuracy across a wide range of window sizes.
Neural Instability: Transformers showed significant accuracy drops when window sizes exceeded specific thresholds (e.g., >16 for the $AAABBB$ pattern). LSTMs were more stable but still showed occasional drops.
Ensemble Performance: The Promotion Algorithm matched or exceeded the accuracy of individual models. For complex randomized patterns, it outperformed the 5-gram baseline and approached the accuracy of windowed LSTMs/Transformers.
Latency: The Promotion algorithm had a prediction time ( $\sim 26 \mu s$ ) comparable to a single n-gram and significantly faster than windowed LSTMs ( $\sim 932 \mu s$ ) or Transformers ( $\sim 2647 \mu s$ ).

Real-World Data Findings

Accuracy: On real-world datasets, LSTMs generally achieved the highest raw accuracy. However, the Promotion Algorithm and Soft Voting ensembles of n-grams achieved comparable or slightly better accuracy than the best single n-gram, and in some cases (like BPI 2018), surpassed the windowed neural models.
Efficiency: The Promotion algorithm was the most efficient ensemble method, with a prediction time of $62 \mu s$ on the Sepsis dataset, compared to $1106 \mu s$ for windowed LSTMs.
Training: Training times for n-gram based methods were orders of magnitude faster than neural networks (e.g., $10 \mu s$ vs. $3370 \mu s$ per activity).

5. Significance and Conclusion

The paper challenges the assumption that complex deep learning architectures are always necessary for event-log prediction. It demonstrates that:

Simplicity is Effective: Lightweight automata (n-grams) are highly competitive with neural networks, offering stable performance and superior computational efficiency.
Dynamic Adaptation: The Promotion Algorithm offers a practical solution for streaming environments where the optimal context size is unknown or changes over time. It provides the robustness of an ensemble with the latency of a single agent.
Practical Application: For real-time process monitoring (e.g., healthcare, infrastructure), the proposed method enables high-accuracy prediction with lower hardware requirements, making it feasible for deployment in resource-constrained or high-throughput environments.

Future Work: The authors suggest extending the algorithm to include "demotion" mechanisms to handle concept drift (where process behavior changes over time) and automating the selection of n-gram sets and the promotion threshold $\tau$ .