Using Learned Execution Graphs for API Anomaly Detection

Identifying Anomalies via Execution Graphs

Traditional monitoring often masks issues by averaging latency across entire endpoints, which hides skipped processing steps or localized node failures. The approach uses short-lived execution graphs—Directed Acyclic Graphs (DAGs) representing the middleware steps of a single request—to compare actual execution against a learned baseline. By modeling each request as a DAG, the system identifies structural deviations, such as a missing or injected node, which standard health checks fail to capture.

Detecting and Categorizing Drift

To distinguish between transient anomalies and systemic drift, the system employs per-node baselines and KL divergence rather than global thresholds. Drift is categorized into three types:

• Structural Drift: Occurs when nodes are added or removed from the execution path, requiring an update to the baseline to avoid false positives.
• Volume Drift: Occurs when increased request load causes specific services to exceed latency thresholds, necessitating scaling or asynchronous processing adjustments.
• Covariate Drift: Occurs when the distribution of request types changes, such as an increase in international traffic requiring different currency conversion steps, which requires re-baselining based on client-specific criteria.

Implementation and Tuning

Telemetry data is ingested via OpenTelemetry and processed through a pipeline that separates hot-path decisions from more accurate, slower reconciliation. To minimize false alarms and improve accuracy, the system incorporates tail-based sampling and handles cold starts by creating endpoint-specific baselines rather than generic ones. When a deviation is detected, the system localizes the issue to the specific node, reducing root cause analysis time from hours to under 30 seconds. Before full automation, the system validates proposed fixes by rolling them out to a small percentage of nodes (5% to 10%) to monitor for risk.