1 Introduction↩︎

Sophisticated cyber attacks, particularly Advanced Persistent Threats (APTs), pose an escalating threat to critical infrastructures. As adversaries frequently evade initial defenses to establish prolonged persistence within compromised networks, the ability to reconstruct a comprehensive attack scenario after anomaly detection becomes a critical forensic capability. To support such post-intrusion analysis, provenance graphs [1] have emerged as instrumental tools: by parsing kernel-level audit logs into a unified graph representation where nodes represent system entities and edges capture causal interactions, they transform discrete, fragmented log entries into a temporal graph with inherent causality, enabling systematic investigation. The central objective in this investigation is backward tracking: starting from a Point-of-Interest (POI) event flagged by an Intrusion Detection System (IDS), analysts trace backward along the provenance graph to reconstruct the adversarial operations and locate the attack entry points [2].

Prior research has advanced backward tracking through several strategies, including reachability analysis [3], [4], statistical anomaly detection [5], and semantic clustering [6]. Despite their contributions, existing approaches still encounter two critical challenges. First, they often rely on low-level features such as frequency, node degree, or structural connectivity to assess individual events, fundamentally lacking the capacity to capture the high-level adversarial intent behind system operations. This significant gap is particularly acute against living-off-the-land (LotL) techniques [7], where adversaries leverage legitimate system utilities to perform malicious actions, producing statistical and topological footprints indistinguishable from benign administrative activities. Second, their rigid, predefined traversal strategies fail to navigate the massive scale of provenance data efficiently. A single host can produce terabytes of logs daily, where attack-related events constitute less than 0.001of the total volume. Lacking intelligent pruning or heuristic strategies, these methods inevitably suffer “dependency explosion” at high-degree supernodes (e.g., system processes), resulting in degraded performance and excessive computational overhead.

The advent of Large Language Models (LLMs) [8] offers promising insights for addressing these challenges. Regarding event assessment, LLMs can transcend low-level features by reasoning over the latent malicious intent, enabling more nuanced and high-fidelity judgments. Regarding “dependency explosion”, LLM-based agents can simulate the specialized division of labor characteristic of human investigation teams to replace blind traversal with reasoning-driven, hypothesis-guided exploration.

Motivated by these insights, we propose Minos, a framework that formulates backward tracking as a multi-agent collaborative reasoning process. Minos addresses the two core challenges through a decomposed, two-tiered architecture. For individual event assessment, Minos introduces a structured reasoning framework explicitly designed to overcome three inherent limitations of generic LLMs: to counter context window constraints during prolonged tracking, a hierarchical context model employs a dual-grained design to maintain a condensed yet rich global tracking state; to eliminate knowledge cutoffs and hallucinations, a retrieval-augmented module with automated citation verification enhances the reasoning capability while anchoring each inference to traceable sources; and to mitigate the false positives induced by sycophancy bias, an adversarial deliberation mechanism (prosecutor–defense–judge) systematically extracts supporting evidence from both malicious and benign perspectives before yielding an objective event assessment through impartial arbitration. For end-to-end graph exploration, Minos partitions the complex investigation task into four specialized agent roles orchestrated by a finite state machine (FSM). The Planner agent serves as the hypothesis-driven commander, guiding the backward tracking through high-level semantic reasoning rather than rigid topological traversal. The Query agent acts as the data interface, employing a “count-first” protocol to securely retrieve system events while preventing “dependency explosion” at high-degree nodes. The Adversarial Assessment Group focuses on individual event assessment using the aforementioned adversarial deliberation. Finally, the Memory agent centralizes the tracking state, dynamically updating the evolving context to ensure logical coherence across the entire tracking lifecycle.

We evaluate Minos on 14 attack scenarios spanning five public datasets across three operating systems. Specifically, Minos achieves an average recall of 0.92 and precision of 0.64, representing a significant improvement over the baselines, while producing attack subgraphs that are 49% more compact. The multi-agent architecture also exhibits a decisive advantage over the single-agent baseline. Additionally, the ablation studies validate the effectiveness of each design component. Furthermore, the cross-model experiments reveal that the tracking performance can be optimized by tailoring the underlying LLM backbone to the specific cognitive demands of each agent role.

Our principal contributions are summarized as follows:

• We design an LLM-based reasoning framework for individual event assessment that addresses three inherent limitations of LLMs through hierarchical context model, retrieval-augmented reasoning, and adversarial deliberation.

• We architect a multi-agent collaborative system with four specialized agents orchestrated by an FSM, enabling efficient and interpretable backward tracking on massive provenance graphs.

• We conduct comprehensive experiments on 14 attack scenarios across 5 public datasets, demonstrating that Minos achieves significant improvements over state-of-the-art methods in both reconstruction fidelity and subgraph compactness.

2 Background and Problem Formulation↩︎

2.1 Provenance Graphs.↩︎

In cybersecurity, continuous system auditing is a fundamental capability for monitoring and defending computing infrastructures. To achieve this, modern operating systems are instrumented via kernel-level audit frameworks [9] to record fine-grained system calls (e.g., read, write). These recorded operations are then systematically modeled as a provenance graph—a directed acyclic graph \(G = (V, E)\) where nodes \(V\) represent system entities (e.g., processes, files) and edges \(E\) denote causal dependencies among them (e.g., process spawning, file accesses), as Fig. 1 shows. By unifying isolated system calls into a causal topology, provenance graphs transform raw audit logs into a structured behavioral history, effectively bridging the gap between discrete audit data and comprehensive security analysis [1].

2.2 Backward Tracking.↩︎

Modern security operations often leverage provenance-based IDS, which employ specific detection algorithms to identify suspicious behaviors and generate alerts. These alerts, termed POIs, represent localized anomalies whose broader context remains unknown. To uncover the full sequence of malicious activities, analysts perform backward tracking: starting from a POI event \(e_{\textit{poi}}\), they traverse the provenance graph backward to trace its causal dependencies. This process aims to reconstruct the complete attack scenario preceding the POI and locate the root cause [2].

Formally, given a provenance graph \(G = (V, E)\) and a POI event \(e_{\textit{poi}}\), backward tracking aims to recover an attack subgraph \(G^* \subseteq G\), which is defined as: \[\label{eq:subgraph} G^* = \{ e \in E \mid \mathcal{R}_{\textit{attack}}(e,\, e_{\textit{poi}}) \}.\tag{1}\] \(\mathcal{R}_{\textit{attack}}\) is a binary predicate indicating whether \(e\) is a causal ancestor of \(e_{\textit{poi}}\) and is relevant to the underlying attack campaign. The optimization objective is to minimize \(|G^*|\) to ensure compactness while maintaining completeness with respect to \(\mathcal{R}_{\textit{attack}}\).

Since the full scope of an attack is often manifested incrementally, the backward tracking task can be formulated as an iterative discovery process. At each step \(t\), an exploration policy \(\pi\) identifies a set of candidate events based on the current state: \[\label{eq:explore} \mathcal{E}_t = \pi(G,\, G^*_{t-1}).\tag{2}\] Subsequently, a decision function \(f\) evaluates the relevance of each candidate \(e \in \mathcal{E}_t\): \[\label{eq:decide} y_e = f(e,\, \mathcal{I}_t),\tag{3}\] where \(\mathcal{I}_t\) denotes the information that can be gathered to support the assessment of \(e\). The tracking process proceeds as follows: \[\label{eq:iterate} G^*_0 = \{e_{\textit{poi}}\};\quad G^*_t = G^*_{t-1} \cup \{e \in \mathcal{E}_t \mid f(e,\, \mathcal{I}_t) = 1\}.\tag{4}\]

2.3 Core Challenges.↩︎

According to Eq. 1 –4 , the fidelity of the recovered subgraph \(G^*\) is determined by the synergy between the exploration policy \(\pi\) and the decision function \(f\). In practice, however, both components face bottlenecks arising from the inherent complexity of provenance data and the stealthy nature of modern attacks.

C1. As illustrated in Fig. 1, events in provenance graphs often appear neutral when observed in isolation. For instance, a PowerShell process creating a scheduled task could equally represent a routine administrative operation or a malicious persistence mechanism. Existing approaches typically evaluate events by constructing \(\mathcal{I}_t\) from low-level features, like metadata, frequency or node degree [4], [5]. However, these features are increasingly ineffective against LotL techniques [7], since attackers hijack native OS binaries to mask their actions, generating causal patterns devoid of obvious structural anomalies.

C2. The massive scale of provenance data poses a significant challenge for efficient subgraph recovery [5]. While continuous monitoring easily yields terabyte-scale records daily per host, genuine adversarial events remain extremely sparse, generally falling below 0.001. To achieve \(\pi\), existing exploration strategies, such as connectivity-based traversals (e.g., BFS or DFS), frequently encounter high-degree system process nodes (e.g., svchost.exe or bash) that interact with thousands of entities. Expanding through these nodes causes the candidate set \(\mathcal{E}_t\) to grow exponentially, resulting in excessive computational overhead and the accumulation of irrelevant background events.

The rapid advancement of LLMs [8], [10] presents pivotal insights for addressing these challenges: Regarding C1, pre-trained on massive corpora, LLMs are equipped with semantic priors over operating-system primitives, command-line idioms, and adversarial techniques, which allows them to transcend low-level features and reason over the latent malicious intent underlying system events [11]–[13], yielding more accurate event assessment. For C2, LLM-based agents can plan, decompose, and coordinate sub-tasks through tool use [14], [15], allowing the exploration policy to mimic the iterative workflow of human SOC analysts and replace exhaustive topological traversal with reasoning-driven, on-demand queries. Building upon these two insights, we design the Minos system.

3 Individual Event Assessment↩︎

As discussed in Section 2, addressing the semantic ambiguity of individual events (C1) requires transcending low-level statistical features to perform intent-level reasoning. However, directly applying generic LLMs to construct the decision function \(f\) encounters three inherent limitations. First, LLM invocations are stateless; they cannot accumulate the evolving context throughout backward tracking, despite such historical state being essential for accurate intent reasoning. Second, due to knowledge cutoff and domain knowledge gaps, LLMs struggle to keep pace with the rapid evolution of adversarial techniques, leading to hallucinations [16]. Third, LLMs exhibit sycophancy bias [17], a tendency to over-accommodate implicit prompt assumptions, which manifests as systematic false positive escalations in security investigations. To overcome these limitations, we formulate the individual event assessment as a structured framework powered by three corresponding mechanisms. Fig. 2 illustrates the complete workflow.

3.1 Hierarchical Context Representation.↩︎

To address the stateless nature of LLM invocations, a sustainable mechanism for maintaining the tracking state is required. Given the protracted timeframes and immense data volumes of APT campaigns, linearly concatenating raw historical events to the prompt rapidly surpasses context window constraints [18]. Accordingly, we propose a hierarchical context model that dynamically abstracts confirmed malicious events into two complementary dimensions: a fine-grained semantic narrative and a coarse-grained tactical sequence.

The fine-grained context serves as an evolving narrative summary of confirmed attack-related events, preserving critical forensic artifacts (e.g., abnormal command lines or file paths) to reconstruct the attack scenario and anchor localized causal reasoning. However, since cyberattacks unfold as phased campaigns, accurately interpreting event intent also requires global tactical awareness. Therefore, we introduce a coarse-grained context that maps known malicious events to the MITRE ATT&CK framework [19], forming a sequential tactical chain (e.g., [Initial Access - Execution - Persistence]). By monitoring the logical completeness of the attack lifecycle, this sequence enables the system to recognize campaign boundaries, acting as a global constraint against localized reasoning. We select MITRE ATT&CK as the mapping target because recent studies have demonstrated that LLMs possess a strong inherent capability to align system events with its standardized taxonomy.

Both levels are dynamically updated as new malicious events are encountered. The fine-grained context employs LLM-driven incremental summarization, emulating a memory decay strategy [20] that preserves immediate details while compressing distant history. The coarse-grained sequence is updated by prompting the LLM to infer appropriate MITRE mappings via a prompt-engineering mechanism established in prior work. Prompt templates for both mechanisms are detailed in the Appendix 9.

3.2 Retrieval-Augmented Reasoning with Citation Verification.↩︎

While the hierarchical context captures the evolving state, accurately interpreting event intent requires mitigating the domain knowledge gap and hallucinations. We introduce a Retrieval-Augmented Generation (RAG) module [21] built upon a multi-source knowledge base aggregating: (1) Cyber Threat Intelligence (CTI) reports, providing insights into the latest adversarial techniques to circumvent knowledge cutoff; (2) the MITRE ATT&CK TTPs matrix [19], offering technique descriptions and execution examples to facilitate intent inference; and (3) system log schemas, standardizing heterogeneous audit fields. As cybersecurity analysis integrates both high-level attack semantics and exact technical IoCs (e.g., IP addresses or file hashes), we implement a hybrid retrieval strategy fusing dense vector similarities and sparse BM25 scores equally to retrieve the top-3 most relevant fragments.

Moreover, to ensure the generated intent analysis is highly traceable, we enforce a strict citation protocol. The LLM must explicitly cite the factual provenance of its outputs: label [CTI] for retrieved threat reports, label [MITRE] for tactical references, and label [KNOWN] for model’s intrinsic knowledge. A deterministic algorithm validates these citations by cross-referencing [CTI] against the retrieved source list and verifying [MITRE] identifiers via regular expressions. Unmatched claims are flagged as [SUSPECT], yielding a quantified credibility summary that anchors the assessment to grounded evidence.

3.3 Adversarial Reasoning for Intent Verification.↩︎

Despite leveraging enriched context and retrieved knowledge, a single LLM for intent assessment frequently exhibits sycophancy bias [17], misclassifying benign events as malicious and causing excessive false positives. To mitigate this, we propose an adversarial reasoning framework [22] featuring three specialized agents: a prosecutor, a defense attorney, and a judge.

In the initial phase, the prosecutor and defense agents independently analyze the target event under opposing assumptions—malicious and benign intent, respectively. Both agents exhaustively extract supporting evidence from the hierarchical context, retrieved knowledge, and intrinsic knowledge, providing formal citations for every claim. The verification algorithm then parses these citations to generate a credibility summary, flagging unverified claims.

In the adjudication phase, the judge agent receives the opposing arguments together with their credibility summaries as input, and sequentially evaluates causal dependencies, evidence grounding, and action consistency to render a final verdict substantiated by transparent reasoning. This adversarial architecture necessitates a comprehensive assessment of benign alternatives, thereby significantly alleviating sycophancy bias. Prompt templates for these three agents are detailed in the Appendix 9.

4 Multi-Agent Collaborative Backward Tracking↩︎

While the mechanisms introduced in Section 3 establish a solid foundation for evaluating a single event, constructing an end-to-end backward tracking system requires the effective implementation of the exploration policy \(\pi\) defined in Section 2. Specifically, the system must navigate the massive and complex topology of the provenance graph strategically to reconstruct the attack scenario without suffering from dependency explosion.

Rather than relying on blind traversal, Minos employs a dynamic exploration strategy that explicitly determines the subsequent investigatory paths based on the current state. Minos achieves this through a multi-agent collaborative framework that emulates the functional specialization of human Security Operations Centers (SOCs). Fig. 3 illustrates this system architecture.

4.1 Role Specialization and Agent Design.↩︎

Drawing inspiration from specialized human labor division, Minos partitions the investigation responsibilities across discrete task units fundamental to the backward tracking process. Particularly, the system proposes four specialized agents, whose roles are codified in Table 1.

The Planner Agent serves as the decision-making core governing the exploration policy \(\pi\). It receives all current investigation state as input, including the POI event, hierarchical context, and action history, and outputs explicit instructions for the subsequent step. Since Minos iteratively queries the graph database to fetch candidates for evaluation, the Planner’s output is formalized as a structured query instruction (e.g., query the process that connected to the specific IP). As human analysts do not blindly scan logs but actively seek evidence based on their understanding of the attack progress, the Planner similarly performs a hypothesis-driven reasoning strategy rather than executing topological traversals like BFS. The Planner leverages the current context to explicitly propose hypotheses regarding the attacker’s next steps. To implement this, the Planner adopts a progressive three-tier strategy: (1) an initial backward expansion centered on the POI to establish a local footprint; (2) an edge-first exploration focusing on low-degree frontier nodes to broaden the subgraph efficiently; and (3) a continuous constraint that anchors hypotheses to the tactical lifecycle (e.g., if data exfiltration is confirmed, the Planner hypothesizes prior credential access activities). This design ensures that the search space is semantically constrained by the attack logic rather than relying solely on topological connectivity. The prompt template for the Planner agent is provided in the Appendix.

Recognizing that strategic planning and the generation of query languages (e.g., Cypher) are cognitively distinct operations, Minos decouples these functionalities. A dedicated Query Agent is designed to receive the Planner’s natural language instructions and translate them into executable query code. This separation insulates the planning framework from the database infrastructure, allowing seamless migration across different storage engines by simply reconfiguring the Query Agent. Furthermore, this architectural decoupling enables the deployment of specialized LLMs optimized specifically for code generation to power the Query Agent, thereby enhancing the fidelity of query translation. The Query Agent incorporates two pivotal self-feedback mechanisms. The first is the “count-first” protocol, engineered to mitigate the data explosion. Considering that high-degree nodes in provenance graphs may connect to tens of thousands of events, executing naive queries directly would return an immense volume of candidates, incurring significant computational overhead on irrelevant background noise. Therefore, before fetching any data, the Query Agent executes a counting probe to quantify the candidate volume \(n\). If \(n\) exceeds a predefined threshold \(\theta_{\max}\), it triggers a backpressure feedback signal, compelling the Planner to generate more stringent query instructions (e.g., by imposing tighter temporal windows). This self-optimization rigorously ensures the safety and efficiency of the query phase. A potential risk of this protocol is that attack-relevant events in high-degree neighborhoods may be filtered out when the Planner narrows the candidate set. However, since refinements are guided by the current investigation context rather than blind down-sampling, such omissions are unlikely in practice, making the protocol a favorable efficiency-coverage trade-off. The second mechanism is syntactic self-correction. To address the instability of LLM-based code generation, Minos routes any database execution errors back to the Query Agent to trigger an iterative repair process. Queries that fail to execute within a specified retry limit are bypassed to prevent infinite loops.

The Memory Agent is primarily responsible for the maintenance and synchronous update of the hierarchical context introduced in Section 3, serving as the foundational state for the tracking process. The Adversarial Assessment Group, which is composed of the Prosecutor, Defense Attorney, and Judge agents, executes the intent reasoning mechanisms to function as the de facto arbiter for any event assessment.

The orchestration of these specialized agents manifests the principle of task-oriented division of labor. By integrating hypothesis-driven exploration with intent-aware assessment, this framework systematically mitigates the dependency explosion of provenance graph (Challenge C2) while effectively resolving the semantic ambiguity of individual events (Challenge C1).

4.2 Automated Backward Tracking Orchestration.↩︎

These specialized agents collaborate through a FSM control loop to autonomously execute backward tracking. In each iteration, the Planner proposes a hypothesis, the Query Agent fetches candidate events under the “count-first” protocol, and the Adversarial Group adjudicates the intent of these events. Crucially, once an event is confirmed as attack-related, it triggers the Memory Agent to execute a context update, synchronously recalibrating both the fine-grained narrative and the coarse-grained tactical sequence to inform the next planning iteration.

This iterative cycle is rigorously governed by multi-dimensional termination conditions designed to balance investigation completeness with operation safety. The orchestration loop terminates immediately if any of the following criteria are met: (1) logical completeness: the Planner autonomously infers via the coarse-grained context that the tactical chain has converged upon the root intrusion vector (e.g., the [Initial Access] stage), rendering further backward traversal redundant; (2) exploration sufficiency: the size of the attack-related subgraph remains stagnant for a predefined number of consecutive rounds (\(N_{\text{stag}}\)), indicating the exhaustion of valid causal paths; or (3) system safety: an upper-bound on the total number of iterations (\(N_{\max}\)) is reached, effectively preventing infinite loops.

4.3 State Persistence and Explainability.↩︎

A fundamental requirement for automated security systems is decision transparency. Minos achieves this by persistently serializing the comprehensive investigation state into structured audit logs at each FSM iteration. These persistent records encapsulate the holistic inferential lineage: the Planner’s strategic hypotheses, the specific CTI and MITRE fragments retrieved, and the multi-agent debate transcripts underlying every intent inference.

This comprehensive persistence mechanism transcends the black-box nature of typical backward tracking systems, establishing a verifiable and accountable digital evidence chain. Consequently, security experts can conduct high-fidelity auditing of the reasoning trajectory for every node incorporated into the attack subgraph. Moreover, this interpretable trail enables analysts to pinpoint investigation failures, trace systematic misjudgments back to discrete reasoning discrepancies, and leverage these insights to fine-tune Minos’s strategies, prompt designs, and orchestration logic.

5 Experiments↩︎

In this section, we present a systematic evaluation of Minos to investigate its reasoning performance and efficiency as a multi-agent collaborative framework for provenance-based backward tracking. Our evaluation is guided by three primary research questions:

• RQ1: How effective is Minos compared to state-of-the-art approaches?

• RQ2: How do different LLM backbones affect the performance of each specialized agent?

• RQ3: How do individual components contribute to the performance of Minos?

5.1 Implementation.↩︎

Experimental Setup. Minos is implemented in Python 3.10 using LangGraph, employing Neo4j as the graph database backend. The Query Agent is powered by GPT-5.2-Codex [23], while the remaining agents utilize GPT-5.2 [24] as the core reasoning engine unless otherwise specified. The inference temperature of the Query Agent is set to \(0\) for deterministic code generation, whereas the other agents use the provider’s default temperature setting to preserve their reasoning diversity. Text embeddings are generated via text-embedding-3-large (3072 dimensions). We set \(\alpha{=}0.7\), top-\(K{=}3\), \(\theta_{\max}{=}50\), \(N_{\text{stag}}{=}20\), and \(N_{\max}{=}75\). To simulate an initial security alert, we select the chronologically final malicious event in the ground truth as the POI event.

Datasets and Baselines. We evaluate our system on advanced provenance datasets: (1) the DARPA Transparent Computing (TC) datasets [25], including Cadets, Trace, and Theia scenarios, which contain real-world APT scenarios interleaved with massive background noise; (2) the Aurora dataset [26], which is generated by an automated attack emulation engine that synthesizes stealthy attack chains by drawing on the curated catalog of living-off-the-land binaries and scripts maintained by the LOLBAS project [27]; and (3) the OpTC dataset [28], which represents enterprise-level APT campaigns. These three datasets provide a total of 14 attack scenarios, whose detailed descriptions are available in Table 5 in the Appendix.

We compare Minos against three baselines representing distinct analytical mechanisms: (1) NoDoze [5], a frequency-based statistical framework that assigns anomaly scores based on the historical frequency of system events, aiming to identify rare, suspicious activities from the pervasive background noise inherent in provenance logs. (2) DepImpact [4], a learning-based analytical system that extracts shallow event features and employs a Latent Dirichlet Allocation (LDA) model to score discrete system activities. It identifies critical attack paths by back-propagating threat scores from the POI, essentially formulating the investigation as a task of quantifying and propagating causal impact. (3) a Single-Agent baseline, which encapsulates the full suite of investigative capabilities within an independent GPT-5.2 instance. This agent operates via a standard ReAct [14] prompting loop and is granted access to the identical database query and knowledge retrieval toolset as Minos. This baseline serves as a controlled ablation to validate the architectural superiority of our multi-agent collaborative framework.

We evaluate effectiveness using edge-level recall and precision, along with the final output subgraph size (\(|G|\)). For efficiency, we measure the end-to-end backward tracking time and total LLM token consumption.

5.2 RQ1: Overall Effectiveness.↩︎

Table 2 summarizes the performance of all systems across 14 attack scenarios. Generally, Minos achieves superior recall and precision while producing significantly more compact attack subgraphs than all baselines.

2.5pt

Specifically, in complex scenarios involving massive background system activities, such as the OpTC and Theia datasets, existing systems suffer severely from “dependency explosion”. NoDoze and DepImpact exhibit notably low precision, retaining hundreds of irrelevant edges due to their inability to distinguish between structurally reachable benign events and genuinely adversarial operations. In contrast, Minos maintains consistently high precision by leveraging intent reasoning to filter semantically irrelevant events, demonstrating its robustness in noisy environments. In datasets with more distinctive attack patterns, such as Aurora, all systems achieve relatively high recall, reflecting the attack sequences’ alignment with standard tracking assumptions. However, the baselines still generate larger subgraphs due to their misclassification of benign administrative events. Minos produces the smallest and highest-fidelity attack subgraphs, attributed to the Aurora attacks’ strict adherence to the MITRE ATT&CK tactical order [19], which enables the coarse-grained context to terminate unnecessary exploration paths efficiently. On the Cadets dataset, a notable exception is Cadets Case 2, where recall drops to 0.75. Our analysis reveals this is caused by a specific technique that maps to multiple MITRE tactical stages, leading the system to prematurely terminate backward tracking before full coverage.

The Single-Agent baseline further highlights the limitations of independent LLM-based backward tracking, achieving only 0.40 average recall and 0.15 precision with 120 edges per subgraph. Analysis reveals two failure modes: (1) on the large-scale Trace dataset, the single context window saturates rapidly, causing premature termination; (2) on Cadets and Theia, the absence of adversarial cross-validation allows initial misjudgments to propagate along causal chains, inflating subgraphs to 130–200 edges with precision as low as 0.06–0.10. These results validate the architectural design of Minos: multi-agent separation prevents context overflow, while adversarial assessment improves the accuracy of reasoning.

Fig. 4 further reports the backward tracking overhead. NoDoze and DepImpact, as non-LLM statistical methods, complete tracking within seconds, whereas both LLM-based systems require substantially longer due to iterative inference latency. Minos achieves an average backward tracking time of 1,290 seconds, moderately faster than the Single-Agent baseline, while consuming significantly fewer tokens. The token efficiency gain stems directly from Minos’s architecture: the “count-first” protocol prevents wasteful queries on high-degree nodes, and the adversarial assessment reduces the exploration on the wrong branches. Notably, on the Trace dataset, Minos requires more time (1,758s) than the Single-Agent (558s), but this is because the Single-Agent terminates prematurely due to context overflow rather than completing a thorough investigation. While the LLM-based approaches incur approximately two orders of magnitude higher latency than traditional methods, the backward tracking time remains practical for real-world security operations, where manual analysis typically requires hours to days per incident.

5.3 RQ2: Impact of LLM Backbone Selection.↩︎

A key advantage of the multi-agent architecture is enabling each agent to leverage a backbone best suited to its task characteristics. Since the Query Agent performs structured code generation whereas the remaining agents perform semantic intent reasoning, these two roles impose divergent requirements on the underlying LLM. Therefore, we conduct controlled experiments across two groups and the results are shown in Table 3: Group A varies the Query Agent’s LLM backbone while keeping the reasoning agents at GPT-5.2 [24], and Group B varies the remaining agents’ LLM backbone while maintaining the Query Agent at GPT-5.2-Codex [23].

In Group A, the smaller Qwen3-Coder-30B [29] struggles to generate valid Cypher at a high rate, causing excessive retries. Scaling to 480B partially mitigates this deficiency, yet queries still exhibit semantic imprecision under complex conditions. DeepSeek-R1 [30] narrows the performance gap but slightly increases token consumption due to the thinking mode. GPT-5.2-Codex, which synthesizes reasoning capability with dedicated code optimization, achieves the best overall balance. These results confirm that both parameter scale and code-specific optimization are critical.

In Group B, the 122B-parameter Qwen3.5 [31] lacks sufficient reasoning depth, yielding only 0.33 precision. DeepSeek-V3 [32], despite the lowest token cost, reaches only 0.48 precision without thinking mode. By contrast, reasoning-enhanced models (DeepSeek-R1 and Qwen-Max) substantially improve precision to 0.55 and 0.62, respectively. GPT-5.2 ultimately demonstrates superior efficacy across all effectiveness metrics, confirming that deep thinking capability is the decisive factor for backward tracking.

Overall, these results reveal clear selection criteria for each agent role: the Query Agent benefits most from code-generation optimized backbones, while the other agents demand models with deep thinking capabilities. In both cases, sufficient parameter scale serves as a necessary prerequisite for reliable performance.

5.4 RQ3: Ablation Study.↩︎

To evaluate the individual contribution of each design component, we conduct a systematic ablation study by selectively disabling one mechanism at a time. Table 4 presents the performance metrics averaged across all 14 scenarios.

Among the architectural components, the two context layers exhibit complementary degradation patterns that substantiate the design rationale in Section 3. Removing the coarse-grained context results in the most severe degradation: recall rises to 0.94, but precision plummets to 0.28 with the subgraph inflating to 98 edges, as the system loses the tactical boundary constraints and drifts into unbounded exploration. Conversely, removing the fine-grained context restricts each assessment to local topology, causing recall to decline to 0.72 with a smaller subgraph of 28 edges, since the system can no longer traverse long-range causal chains without the support of evolving narrative memory. The precision rise reflects an expected trade-off rather than an improvement: deprived of long-range narrative, the Adversarial Group falls back on stricter local evidence and discards ambiguous mid-chain events, sacrificing a sizeable fraction of genuine cross-stage causal edges. Disabling the adversarial reasoning reduces precision from 0.64 to 0.51 (subgraph: 35 \(\rightarrow\) 52 edges), validating its role as the primary safeguard against sycophancy-induced false positives. Removing the “count-first” protocol incurs a substantial token overhead (164K \(\rightarrow\) 248K) alongside precision degradation to 0.48, as the Query Agent fetches massive candidate sets from high-degree nodes, wasting resources and introducing downstream noise.

Regarding the knowledge components, removing the MITRE ATT&CK knowledge base causes the most substantial decline, as it provides the structured tactical references that anchor coarse-grained context updates. CTI reports contribute moderately, providing complementary intelligence for novel adversarial techniques that exceed the LLM’s intrinsic knowledge. Finally, log schema removal produces a marginal impact, suggesting the LLM’s capability to partially compensate for common audit formats.

6 Related Work↩︎

6.1 Provenance-Based Attack Investigation.↩︎

Extensive research has explored provenance-based backward tracking to uncover attack context. Early efforts reconstruct causal footprints via reachability analysis [3], while subsequent work mitigates dependency explosion through dependency weighting [4] or graph compression [33]. In parallel, statistical approaches model behavioral distributions to detect frequency anomalies [5], and semantic clustering abstracts low-level interactions into higher-level behaviors [6]. Despite these topological and statistical insights, such approaches remain constrained by rigid features, making it difficult to infer high-level adversarial intents.

6.2 LLMs for Cybersecurity.↩︎

The cognitive capabilities of LLMs have motivated their application in security analysis. Initial paradigms utilize LLMs as auxiliary reasoning modules to interpret suspicious events [12], often incorporating RAG for factual grounding [11]. To overcome context limits and hallucinations in single-model setups, emerging studies explore multi-agent systems that automate forensic tasks [13]. However, existing systems are generally built as static workflows, limiting the utilization of LLMs’ inherent reasoning capabilities.

7 Discussion and Conclusion↩︎

7.1 Limitations and Future Work.↩︎

Despite its promising capabilities, Minos presents opportunities for further refinement. First, to address data privacy constraints regarding sensitive audit logs, future work will explore localized deployment via model fine-tuning and knowledge distillation, empowering smaller open-source models for local execution and eliminating data exfiltration risks. Second, to reduce reliance on POI event quality, we aim to develop a multi-POI joint tracking mechanism for parallel exploration and cross-validation, complemented by a credibility self-assessment module to dynamically adjust strategies when processing low-confidence inputs.

7.2 Conclusion.↩︎

In this paper, we presented Minos, a multi-agent framework that reformulates provenance-based backward tracking as an LLM-driven reasoning process. Addressing semantic ambiguity and dependency explosion, Minos synergizes micro-level assessment (integrating hierarchical context, RAG, and adversarial deliberation) with macro-level orchestration of four specialized agents for hypothesis-driven exploration. Evaluations across 14 scenarios demonstrate that Minos achieves superior reconstruction fidelity and subgraph compactness, providing a foundation for next-generation automated cyber-investigation.

8 Evaluation Dataset Details↩︎

Table 5 provides comprehensive statistics for the 14 evaluation scenarios detailed in Section 5, spanning five public provenance datasets of varying scale and complexity.

9 Structured Prompt Details↩︎

Fig. 5 presents the three prompt templates that govern the adversarial reasoning framework described in Section 3.

Fig. 6 shows the prompt templates used by the Memory Agent to maintain the hierarchical context introduced in Section 3.

Fig. 7 illustrates the prompt template used by the Planner Agent to facilitate hypothesis-guided graph exploration, as introduced in Section 4.

References↩︎