# STLGT: A Scalable Trace-Based Linear Graph Transformer for Tail Latency Prediction in Microservices

arXiv: https://arxiv.org/abs/2604.26422 · HTML: https://mlsanity.com/paper/2604.26422/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 49 references that are in the map.
- First posted on arXiv 29 Apr 2026.

## Builds on (most cited first, 17 of 17)

- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [SGFormer: Simplifying and Empowering Transformers for Large-Graph Representations](https://mlsanity.com/paper/2306.10759/) (2023)
- [An Attention Free Transformer](https://mlsanity.com/paper/2105.14103/) (2021)
- [FIRM: An Intelligent Fine-Grained Resource Management Framework for SLO-Oriented Microservices](https://mlsanity.com/paper/2008.08509/) (2020)
- [RCAEval: A Benchmark for Root Cause Analysis of Microservice Systems with Telemetry Data](https://mlsanity.com/paper/2412.17015/) (2024)
- [CausalRCA: Causal Inference based Precise Fine-grained Root Cause Localization for Microservice Applications](https://mlsanity.com/paper/2209.02500/) (2022)
- [A Survey and Taxonomy of Self-Aware and Self-Adaptive Cloud Autoscaling Systems](https://mlsanity.com/paper/1609.03590/) (2016)
- [A Survey of DevOps Concepts and Challenges](https://mlsanity.com/paper/1909.05409/) (2019)
- [Autothrottle: A Practical Bi-Level Approach to Resource Management for SLO-Targeted Microservices](https://mlsanity.com/paper/2212.12180/) (2022)
- [Surprisingly Strong Performance Prediction with Neural Graph Features](https://mlsanity.com/paper/2404.16551/) (2024)
- [AHPA: Adaptive Horizontal Pod Autoscaling Systems on Alibaba Cloud Container Service for Kubernetes](https://mlsanity.com/paper/2303.03640/) (2023)
- [DeepScaler: Holistic Autoscaling for Microservices Based on Spatiotemporal GNN with Adaptive Graph Learning](https://mlsanity.com/paper/2309.00859/) (2023)
- [Cloud-Native Computing: A Survey from the Perspective of Services](https://mlsanity.com/paper/2306.14402/) (2023)
- [Graph-PHPA: Graph-based Proactive Horizontal Pod Autoscaling for Microservices using LSTM-GNN](https://mlsanity.com/paper/2209.02551/) (2022)
- [PBScaler: A Bottleneck-aware Autoscaling Framework for Microservice-based Applications](https://mlsanity.com/paper/2303.14620/) (2023)
- [HarmonyBatch: Batching multi-SLO DNN Inference with Heterogeneous Serverless Functions](https://mlsanity.com/paper/2405.05633/) (2024)

## Abstract (arXiv)

Accurate end-to-end tail-latency forecasting is critical for proactive SLO management in microservice systems. However, modeling long-range dependency propagation and non-stationary, bursty workloads while maintaining inference efficiency at scale remains challenging. We present STLGT (Scalable Trace-based Linear Graph Transformer), a per-API predictor that encodes traces as span graphs for multi-step p95 tail-latency forecasting. STLGT uses a structure-aware linear graph Transformer to propagate cross-service dependencies with inference time linear in span graph size, and a decoupled temporal module to capture workload dynamics. Across a personalized education microservice application, DeathStarBench, and Alibaba traces, STLGT improves forecasting accuracy over PERT-GNN by 8.5% MAPE on average and achieves up to 12x faster CPU inference at N=32, matching the maximum span graph size after preprocessing the Alibaba traces. Ablation studies further demonstrate the effectiveness of each component, especially under bursty traffic.