FastPERT: Towards Fast Microservice Application Latency Prediction via Structural Inductive Bias over PERT Networks

Da Sun Handason Tam, Huanle Xu, Yang Liu, Siyue Xie, Wing Cheong LauAAAI 2025 · DOI

Abstract

Modern cloud-native applications rely on complex microservice interactions, making end-to-end latency prediction critical for proactive resource scaling. FastPERT addresses the limitations of existing models—which are either too simple to capture dependencies or too computationally heavy for real-time use—by leveraging the structural properties of microservice execution traces. Modeled as PERT networks, these traces allow FastPERT to achieve high accuracy with extreme efficiency, running entirely on standard CPUs.

The Challenge of Microservice Latency Prediction

In cloud-native architectures, a single user request triggers a cascade of internal calls across dozens of microservices. Predicting the total "end-to-end latency" of these chains is essential for maintaining service level agreements (SLAs). However, engineers face a "Goldilocks" problem: simple models like Gradient Boosted Trees (GBTs) often fail to capture complex service dependencies, while accurate Graph Neural Networks (GNNs) require expensive GPU resources and are too slow for real-time production environments. FastPERT aims to bridge this gap by being both accurate and lightweight.

Methodology: Leveraging Structural Inductive Bias

FastPERT bridges the gap between speed and accuracy through a two-stage workflow grounded in the "structural inductive bias" of Directed Acyclic Graphs (DAGs).

1. Trace-PERT Graph Representation

The system first models execution traces as Trace-PERT Graphs. As shown in Figure 2, individual service calls and their dependencies are mapped from a linear trace into a DAG structure that represents the concurrent and sequential nature of the request execution.

Mapping execution traces to Trace-PERT Graphs.

2. Node-level Estimation and Path-Averaging

The prediction process involves two main steps:

  • Node-level Delay Estimation: FastPERT predicts the delay of each individual task (node) using a shared GBT model. This keeps the model lightweight and efficient.
  • Path-Averaging Aggregation: To calculate total latency, FastPERT uses a unique aggregation method. Instead of identifying a single "critical path" (the longest path), which can be sensitive to measurement noise, FastPERT calculates the average latency across all possible paths from the start to the end of the trace.
The FastPERT workflow: node-wise latency prediction followed by path-averaging aggregation.

This averaging acts as a built-in ensemble, making the system robust to noise in individual service measurements. Mathematically, this is achieved using a precomputed reachability matrix, allowing the average to be calculated via a single, fast vector operation rather than an exponential path search.

Experimental Evaluation

FastPERT was evaluated using two massive real-world datasets from Alibaba: Ali-2021 (20 million traces) and Ali-2022 (detailed runtime metrics for 1,084 API calls).

Key Results

  • Speed: FastPERT processed 1.5 million traces in under 10 seconds on a standard CPU. In contrast, the state-of-the-art PERT-GNN required over 10 minutes on an Nvidia RTX 3090 GPU. Training time was similarly reduced from 11 hours to just 7 minutes.
  • Accuracy: On the Ali-2022 dataset, FastPERT achieved a Mean Absolute Percentage Error (MAPE) of 11.36%, outperforming both PERT-GNN (12.84%) and standard GBTs (17.29%).

Discussion and Insights

The success of FastPERT highlights that complex GNNs may not be necessary when the underlying system rules—such as the DAG structure of microservice traces—are already known. By treating these structures as a "cheat code" or inductive bias, the authors moved the computational workload from GPUs to CPUs without sacrificing performance.

Limitations and Future Work

Currently, FastPERT focuses on predicting average expected latency. Future work aims to address tail latency (e.g., p99 lag), which is critical for high-stakes systems where rare, slow requests can significantly impact user experience. Additionally, the model currently relies on the frequency of observed graph structures to handle cases where the exact trace graph isn't known in advance.

Summary updated

BibTeX
@inproceedings{tam2025fastpert,
  author = {Da Sun Handason Tam and Huanle Xu and Yang Liu and Siyue Xie and Wing Cheong Lau},
  title = {{FastPERT: Towards Fast Microservice Application Latency Prediction via Structural Inductive Bias over PERT Networks}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i19.34291},
}

Loading related content...

Figure