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

• URL: http://arxiv.org/abs/2609.05911v1
• Date: Sat, 05 Sep 2026 06:09:06 GMT
• Title: Structurally Close, Temporally Distant: Measuring Security Exposure in Long-Horizon LLM Agents
• Abstract summary: We show that temporal remoteness can overstate security separation in stateful agents.<n>We introduce a provenance-aware execution graph linking agent events through deterministic state, identifier, and tool.<n>Execution structure reveals proximity hidden by step count and can support targeted intervention.
• Score: 1.1659383493623567
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Long-horizon LLM agents interact with untrusted content, persistent memory, external state, and sensitive tools. Existing analyses often characterize attacks by the number of execution steps between malicious input and a downstream action. We show that temporal remoteness can overstate security separation in stateful agents. We introduce a provenance-aware execution graph linking agent events through deterministic state, identifier, and tool provenance, and define \emph{influence distance} $\DI$ as the shortest structural path from an untrusted source to a sensitive action. We compare it with \emph{sequence distance} $\DT$, the shortest injection--sink path in the ordered trajectory. Since the influence graph contains every sequence edge, $\DI \leq \DT$; $\Gap=\DT-\DI$ measures the separation hidden by step count. Across 454 injection--sink pairs from 360 long-horizon AgentDojo trajectories over 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. On AgentDojo's banking suite, 33.8% of 231 pairs from 377 trajectories decouple through different provenance mechanisms. Among 274 OpenAI pairs, $\Gap$ does not independently predict attack success after controlling for $\DT$, attack family, and backend ($β_{\Gap}=0.066$, $p=.088$). At matched thresholds $k=2,3$, a deterministic $\DI$-based pre-execution gate blocks five attack sinks missed by a sequence-only gate with no additional benign blocking, although the paired gain is not significant ($p=.0625$). Execution structure therefore reveals proximity hidden by step count and can support targeted runtime intervention. We measure candidate influence pathways rather than causal attribution.

Related papers

• Facts Without Rules: Boundary Metadata Collapse in Multi-Agent LLM Handoffs [13.92589238677081]
  We show that summaries preferentially preserve operational facts while weakening the boundary metadata that governs how those facts may be used.<n> Boundary-marker and operational-fact survival are nearly uncorrelated at the handoff level on both GPT-5-mini and DeepSeek-R1-32B.
  arXiv  Detail & Related papers  (2026-08-29T03:38:35Z)
• Directional Contextual Representations for Dependency Relations: Why Cross-Direction Pairing Fails [22.49571926071395]
  We show that pairing a token's forward state against a emphcandidate's backward state (cross-direction'' pairing, $F_i$ vs. $B_j$) consistently emphunderperforms same-direction pairing, and the penalty emphgrows, not shrinks, with token distance, both paired-bootstrap significant.
  arXiv  Detail & Related papers  (2026-08-21T00:50:25Z)
• Long-Horizon State Tracking in LLMs: Executing MD5 through a Deep Sequence of Dependent Tool Calls [0.5097809301149342]
  Long-horizon tasks remain uncommon in large language model (LLM) evaluation.<n>We test whether an LLM can carry exact intermediate state across many tool calls at all.<n>Two ingredients decide success: keeping the model's own reasoning in its context each turn, and voting over a thinking-enabled worker to remove its modular-arithmetic slips.
  arXiv  Detail & Related papers  (2026-08-02T09:38:02Z)
• Safety, or Just Capability? A Validity Audit of Agent-Safety Benchmarks [10.839956062772792]
  Three agent-safety benchmarks rank the same 18 models differently.<n>R-Judge specificity against AgentHarm safety correlates $-0.64$ at $n=7$ and $+0.02$ at $n=18$, and a quarter of random size-7 subsets reach $|| geq 0.5$ around that near-zero value.<n>AgentHarm shows the strongest held-out association, $=+0.72$ with three-template jailbreak safety after controlling capability.
  arXiv  Detail & Related papers  (2026-07-30T03:45:10Z)
• Which Defense Closes Which Threat? Attributing OWASP-LLM-Top-10 Coverage and Its Brittleness Under Paraphrasing [51.56484100374058]
  Production LLM applications stack several defense families -- refusal-phrase filters, tokenbudget controls, model allowlists, rate limits, tool-registry authentication -- yetBAS benchmarks report a single aggregate coverage number.<n>We add four-LLM-Top-10-aware agents to a 21-agent baseline scanner and target a lattice of four synthetic LLM endpoints.
  arXiv  Detail & Related papers  (2026-06-01T19:39:25Z)
• Block-Wise Differentiable Sinkhorn Attention: Tail-Refinement Gradients with a Gap-Aware Dustbin Bridge [0.0]
  We study long-context balanced optimal transport attention on TPU hardware through a stopped-base, fixed-depth tail-refinement surrogate.<n>We provide a local surrogate-bias bound, an a posteriori bias certificate, and a projective contraction certificate for strictly positive active blocks.<n>On synthetic masked problems, the optimized matches exact autodiff of the same centered surrogate to within $10-5$--$10-10$.
  arXiv  Detail & Related papers  (2026-04-28T19:01:11Z)
• Online Learning in MDPs with Partially Adversarial Transitions and Losses [42.59565593884281]
  We study reinforcement learning in MDPs whose transition function is at most steps but may behave adversarially at a fixed subset of $$ steps per episode.<n>We introduce emphconditioned occupancy measures, which remain stable across episodes even with adversarial transitions.<n>We characterize the regret of adversarial MDPs in the emphfully adversarial setting ($=H-1$) both for full-information and bandit feedback.
  arXiv  Detail & Related papers  (2026-02-10T07:13:11Z)
• SABER: Small Actions, Big Errors -- Safeguarding Mutating Steps in LLM Agents [52.20768003832476]
  We analyze execution traces on $$-Bench (Airline/Retail) and SWE-Bench Verified.<n>We formalize emphdecisive deviations, earliest action, level divergences that flip success to failure.<n>We introduce cm, a model-agnostic, gradient-free, test-time safeguard.
  arXiv  Detail & Related papers  (2025-11-26T01:28:22Z)
• Reinforcement Learning from Adversarial Preferences in Tabular MDPs [62.73758165845971]
  We introduce a new framework of episodic Markov decision processes (MDPs) with adversarial preferences.<n>Unlike standard episodic MDPs with adversarial losses, in PbMDPs the learner instead observes preferences between two candidate arms.<n>We develop algorithms that achieve a regret bound of order $T2/3$ under known transitions.
  arXiv  Detail & Related papers  (2025-07-15T20:19:32Z)
• Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
  We study the episodic reinforcement learning (RL) problem modeled by finite-horizon Markov Decision Processes (MDPs) with constraint on the number of batches. We design a computational efficient algorithm to achieve near-optimal regret of $tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot) hides logarithmic terms of $(S,A,H,K)$ in $K$ episodes. Our technical contribution are two-fold: 1) a near-optimal design scheme to explore
  arXiv  Detail & Related papers  (2022-10-15T09:22:22Z)
• Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policies [88.75843804630772]
  We design an algorithm that achieves an $Oleft(mathrmpoly(S,A,log K)sqrtKright)$ regret in contrast to existing bounds. Our result relies on a sequence of new structural lemmas establishing the approximation power, stability, and concentration property of stationary policies.
  arXiv  Detail & Related papers  (2022-03-24T08:14:12Z)
• Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
  We revisit offline reinforcement learning on episodic time-homogeneous Markov Decision Processes with $S$ states, $A$ actions and planning horizon $H$. We obtain the first set of nearly $H$-free sample complexity bounds for evaluation and planning using the empirical MDPs.
  arXiv  Detail & Related papers  (2021-03-25T18:52:17Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.