Structurally Close, Temporally Distant: Measuring Security Exposure in Long-Horizon LLM Agents

Long-horizon LLM agents interact with untrusted content, persistent memory, external state, and sensitive tools. Existing analyses commonly characterize an attack by the number of execution steps separating malicious input from a downstream action. We show that temporal remoteness can substantially overstate security separation in stateful agents. We introduce a provenance-aware execution graph that connects agent events through deterministic state, identifier, and tool provenance, and define \emph{influence distance} $\DI$ as the shortest structural path between an untrusted source and a sensitive action. We compare it against \emph{sequence distance} $\DT$, the shortest injection--sink path in the ordered trajectory. Because the influence graph contains every edge of the sequence graph, $\DI \leq \DT$; the gap $\Gap = \DT - \DI$ quantifies how much the step-count view overstates separation. Across 454 injection--sink pairs from 360 long-horizon AgentDojo trajectories on OpenAI's \texttt{gpt-4o-mini} and \texttt{gpt-4o} and Claude's Haiku 4.5 and Sonnet 4.6, $\Gap > 0$ for 96.9\% of pairs, with a median gap of 9 hops; 91.0\% remain decoupled after removing the largest provenance-only edge class. In a cross-domain evaluation on AgentDojo's banking suite, 33.8\% of 231 pairs from 377 trajectories decouple through different provenance mechanisms. Among the 274 pairs from \texttt{gpt-4o-mini} and \texttt{gpt-4o}, $\Gap$ does not independently predict attack success after controlling for $\DT$, attack family, and backend ($\beta_{\Gap}=0.066$, $p=.088$). At matched thresholds $k=2$ and $k=3$, a deterministic $\DI$-based pre-execution gate blocks five attack sinks missed by the sequence-only gate, with no additional benign blocking under either graph variant, though this paired gain is not significant at the 5\% level ($p=.0625$). Execution structure can therefore reveal proximity that step count hides, supporting more targeted runtime intervention. Hence, in this study, we measure candidate influence pathways rather than causal attribution.