PaperlayerView exact revision on arXiv

Source-linked AI summary

When Retrieval Fails Before It Begins: Structurally Indirect Prerequisite Eviction as a Retention Failure in Agentic Memory

Minkyu Song

arXiv:2608.20400v1cs.AIcs.CLcs.LG

TL;DR

Under a fixed budget, agentic memory can fail before retrieval when structurally necessary but weakly query-aligned prerequisites are evicted. The paper defines and benchmarks this retention-stage failure, then evaluates one-hop Dependency-aware Semantic Garbage Collection (DSGC), which substantially improves full-chain retention in the main suite while degrading in identified scaling regimes.

  • Problem

    Existing retrieval-centered approaches assume necessary evidence remains in the store, leaving insufficiently studied the earlier failure boundary where structurally indirect prerequisites are evicted.

  • Method

    The paper provides an operational definition, a deterministic benchmark with supplied dependency edges, trace diagnostics, and a one-hop graph-aware retention rule called DSGC.

  • Results

    Full-chain retention improves from 0.03 to 0.90 under the lexical encoder and from 0.23 to 1.00 under the sentence encoder with DSGC.

  • Takeaways & Limitations

    Retention can be studied as a structural reachability problem before retrieval, and one-hop dependency propagation mitigates the benchmarked eviction failure.

  • Takeaways & Limitations

    The synthetic benchmark uses supplied dependency edges and isolates retention from graph induction, multi-step planning, and tool use; scaling also exposes degradation for the lexical encoder.

Abstract

from arXiv · show

Agentic memory under a fixed budget involves two stages: retention and retrieval. Existing retrieval-centered paradigms implicitly assume necessary evidence survives eviction, but we challenge this by isolating a pre-retrieval failure mode: structurally indirect prerequisite eviction, in which upstream blocks weakly aligned with the query are discarded under budget pressure. We provide an operational definition of this failure, a reproducible deterministic benchmark, and per-seed trace diagnostics. Finally, we evaluate Dependency-aware Semantic Garbage Collection (DSGC), a one-hop graph-aware rule. In our main suite, DSGC improves full-chain retention from 0.03 to 0.90 under a lexical encoder and from 0.23 to 1.00 under a sentence encoder. Robustness checks then identify the budget and scaling regimes where the one-hop rule holds or degrades. Our released pipeline and failure postmortem support mechanistic analysis of retention before retrieval as a distinct failure boundary.

1. Introduction

The paper identifies a retention-stage failure that occurs before retrieval when weakly query-aligned prerequisites are evicted under a fixed memory budget. It defines this failure, builds a deterministic benchmark and trace diagnostics, and evaluates a one-hop graph-aware retention rule.

  • Agentic memory separates retention, which determines what survives eviction, from retrieval, which ranks surviving blocks for a query.
  • Similarity-based and recency-based heuristics can evict structurally required upstream blocks that are weakly aligned with the query, making downstream retrieval unable to recover them.
  • The paper operationalizes this retention failure, distinguishes it from retrieval, forgetting, and reasoning failures, and constructs a deterministic benchmark with fixed seeds and dependency-sensitive targets.
  • Per-seed trace diagnostics decompose failures into a displaced block, a displacing competitor, and a score margin.
  • The study evaluates DSGC, a one-hop graph-aware retention rule that protects prerequisites through structural reachability while leaving multi-step inference to downstream reasoning.

2. Operational Definition

The paper defines structurally indirect prerequisite eviction as a retention-stage failure: a necessary upstream block is less query-aligned than a dependent downstream block and is evicted while that downstream block remains retained. This failure occurs before retrieval and is distinct from retrieval, surface-forgetting, and reasoning failures.

  • Benchmark model: The benchmark models memory as atomic blocks with deterministic whitespace-word token costs and directed prerequisite edges supplied as ground truth.Edges define which block is an immediate prerequisite of another, separating retention evaluation from graph induction.
  • Retention and retrieval boundary: Under a query and budget, policies rank blocks and greedily retain them until adding the next block would exceed the budget; retrieval then operates only on the retained subset.The benchmark answer depends on joint retention of the generator-labeled chain(q) blocks.
  • Structural vulnerability: A block is structurally indirect when a necessary chain block has lower query similarity than a dependent downstream chain block.Indirectness belongs to the block–query–encoder tuple, not to a retention policy.
  • Eviction event: Retention-stage failure occurs when a policy excludes that prerequisite while retaining the more query-similar downstream block that depends on it.Once evicted from the active prompt-visible store, the prerequisite cannot be recovered by downstream ranking.
  • Scope of the failure: The definition excludes retrieval failure, surface forgetting, and reasoning failure, isolating disagreement between structural necessity and surface similarity at eviction.In retrieval failure the needed block remains retained; in reasoning failure the retained set is complete.
  • Worked example: The worked example shows similarity-only retention evicting c2, the low-overlap logical bridge, while DSGC preserves it through support propagated from c3.The chain links Alice’s assignment to bundle M, bundle M to clearance N, and clearance N to deletion permission.

3. Method: One-Hop Dependency Propagation

DSGC is a minimal one-hop graph-aware retention rule that propagates survival support from relevant downstream blocks to their necessary prerequisites. The method is evaluated against similarity-only and ranking-equivalent no-graph controls using deterministic scoring and greedy budget selection.

  • Rule design: DSGC propagates survival support from highly relevant downstream blocks to structurally necessary prerequisites without learned components, multi-hop diffusion, or per-step reranking.The one-hop restriction makes the effect of dependency propagation directly testable.
  • Propagation boundary: The mechanism elevates a prerequisite’s retention score through πi while limiting inference to one hop; vulnerabilities beyond that radius remain residual failures.The downstream reasoner retains responsibility for multi-step inference.
  • Hyperparameter setting: The main suite uses λπ = 1.0, giving one unit of downstream relevance one unit of propagated prerequisite support.The study also reports a sweep around this equal-weight base case.
  • Ablation design: Similarity-only and no-graph DSGC are ranking-equivalent controls, while their comparison with DSGC isolates the structural propagation term.No-graph DSGC sets λπ = 0; the complete DSGC uses λπ = 1.0.
  • Scoring and selection: The scoring pipeline encodes the query and blocks, computes normalized relevance, propagates support one hop, combines scores, and greedily selects blocks under budget.Selection proceeds in descending combined score until the additive token budget is exhausted.
  • Complexity: For N blocks of embedding dimension d and |E| edges, scoring costs O(Nd), propagation O(|E|), and selection O(N log N).These costs characterize the retention rule itself.
  • Evaluation assumption: The benchmark supplies dependency edges directly, so the experiment measures retention improvement from graph-aware propagation independently of graph induction.This supports a mechanistic test of how much a minimal rule helps when dependencies are available.
  • Encoders: The evaluation compares a 256-dimensional lexical encoder with a 384-dimensional normalized dense sentence encoder to test whether the failure persists beyond surface overlap.The lexical encoder stresses overlap vulnerabilities, while the dense encoder tests the same retention-stage failure under stronger semantic embeddings.

4. Reproducible Trigger

The benchmark contrasts retrieval-friendly controls with target scenarios where structurally necessary chain blocks diverge from query similarity. Fixed templates, seeds, budgets, and encoders make this divergence reproducible and auditable.

  • Regime design: The trigger compares a control regime, where chain blocks are query-aligned, with targets containing structurally indirect prerequisites.This tests whether propagation helps specifically when structural necessity and query similarity diverge.
  • Scenario construction: Each scenario contains 20 blocks, including necessary chain blocks, honeypot distractors, and filler noise.Honeypots share decisive query vocabulary without completing the reasoning chain, while fillers contain neither the answer relation nor that vocabulary.
  • Fixed protocol: The main suite fixes M = 2.0, 15 seeds per condition, two encoders, three policies, four templates, and medium-strength honeypots.M = 2.0 preserves chain capacity while maintaining competition at the budget cutoff.
  • Target contrast: Role Target c1 retains residual lexical support, whereas Profile Target c1 has only shallow identifier overlap and is more vulnerable under budget pressure.Both targets share the same one-hop rescue of c2 from c3; their divergence occurs at c1.
  • Target architecture: The target architecture uses a three-block chain in which c2 is one hop from query-facing c3 and c1 lies two hops away.This is the minimum configuration isolating the structural failure without confounding recency effects.
  • Evaluation: Full Chain Retention measures whether every generator-labeled chain block survives eviction, with means and standard deviations over 15 seeds.Deterministic template answer accuracy is also recorded but is nearly a consequence of full-chain retention in this suite.

5. Main Results

The controls saturate because their required chains are query-aligned, while target results expose the failure of similarity-only retention and the benefit of one-hop dependency propagation. The remaining weakness is concentrated in the lexical Profile Target.

  • Controls: 1.00 full-chain retention is achieved by all three methods in the control regime.Query-aligned chain blocks make similarity-based retention sufficient, and DSGC does not degrade the controls.
  • Target results: 0.03 full-chain retention is achieved by both baselines in the lexical target regime, versus 0.90 with DSGC.This result exposes the vulnerability of indirect prerequisites under budget pressure.
  • Target results: 0.23 full-chain retention is achieved by the similarity baselines under the sentence encoder, versus 1.00 with DSGC.The same improvement pattern holds with denser semantic embeddings.
  • Ablation: Similarity-only and no-graph DSGC have exactly equal rankings because λπ = 0 yields I_i = r_i.The controlled comparison attributes ranking differences to the one-hop dependency propagation term.
  • Residual boundary: 0.80 retention remains for DSGC on the lexical Profile Target, while the sentence encoder reaches 1.00.The lexical Profile Target is the only setting where DSGC still fails on some seeds.

6. Trace Diagnostics

Trace diagnostics show that residual lexical Profile failures match the predicted one-hop boundary: DSGC preserves the rescued pair but can evict the older prerequisite at a narrow cutoff margin.

  • One-hop boundary: In all three failing lexical Profile Target instances, c2 and c3 occupy the top two ranks while c1 falls to rank 6 or 10.The traces preserve the immediate prerequisite rescued from c3 but not the two-hop prerequisite.
  • Residual behavior: The remaining 12 seeds retain c1 because it has sufficient residual lexical support to clear the budget cutoff.This makes the residual failure marginal rather than systematic.
  • Displacement anatomy: c1 is displaced by a non-chain competitor in every failure, including honeypot h1 or fillers f9 and f3.The displaced block is exclusively c1, the multi-hop prerequisite.
  • Displacement anatomy: Margins below 0.05 indicate marginal budget-cutoff displacements rather than wholesale ranking collapses.Seed 8 shows that ordinary filler blocks, not only adversarial honeypots, can cross the cutoff.
  • Next test: A k ≥2 propagation variant is proposed as a falsifiable test that could recover these three seeds without degrading controls and Role Target.The narrow margins motivate bounded neighborhood expansions as a potentially lightweight extension.

7. Robustness and Failure Boundaries

Robustness checks show that DSGC remains effective across tested propagation weights and is most useful under intermediate budget pressure, but its one-hop rule degrades as sparse-encoder context scales.

  • Hyperparameter stability (λπ): Across λπ ∈{0.5, 1.0, 2.0}, structural gains remain positive, with Role Target saturation under the lexical encoder and perfect retention under the sentence encoder.The Profile Target improves monotonically across the tested propagation weights.
  • Budget pressure dynamics: At M = 2.0, DSGC retains the structurally necessary chain while similarity-only retention does not.This intermediate budget is the main separation regime between the policies.
  • Budget pressure dynamics: At M = 1.0, both policies struggle because the budget cannot comfortably include the full reasoning chain alongside competitive distractors.
  • Budget pressure dynamics: At M = 5.0, the performance gap narrows because the larger budget passively retains nearly the entire context store.
  • Budget pressure dynamics: The similarity-only Role Target curve is not strictly monotonic, so larger budgets do not automatically repair misranked prerequisites when distractors remain near the cutoff.
  • Baseline comparison: At M = 2.0, the sliding-window baseline retains the full chain in only 0.07 of lexical-encoder runs across all four templates.It fails even on elementary control scenarios, making recency insufficient for preserving logical prerequisite chains in this benchmark.
  • Context scaling and negative results: With 50 blocks, DSGC remains at 1.00 under the dense sentence encoder, while sparse lexical retention falls to 0.73 on Role Target and 0.33 on Profile Target.At 20 blocks, the corresponding sparse-encoder values are 1.00 and 0.80.

8. Discussion

The discussion frames structurally indirect prerequisite eviction as a reproducible retention-stage failure and identifies both the operating boundary of one-hop propagation and its systems and graph-quality trade-offs.

  • What this establishes: Structurally indirect prerequisite eviction is reproducible across seeds, visible in per-seed traces, and mitigated by one-hop dependency propagation.Control saturation indicates targeted gains, while residual failures mark a beyond-one-hop boundary.
  • Boundaries and negative results: The synthetic benchmark isolates retention from graph induction, multi-step planning, and tool use by supplying dependency edges.
  • Boundaries and negative results: The 50-block lexical result marks where the current one-hop rule breaks, identifying a concrete failure boundary rather than implying universal robustness.
  • Error modes under imperfect graphs: Missing prerequisite edges remove propagation support, whereas spurious edges can elevate unrelated blocks and displace true chain blocks at the budget cutoff.This asymmetry favors high-precision graph induction.
  • End-to-end answer evaluation: End-to-end LLM evaluation tests whether a model uses a complete retained chain correctly, whereas retention is the primary metric for whether the chain survives eviction.
  • The multi-hop extension: A k-hop extension could address residual failures but raises propagation cost to O(k|E|) and may require damping or normalization to manage score diffusion.Multi-hop variants must balance structural depth against production latency budgets.
  • Systems profile: For sparse graphs, one-hop DSGC has total cost O(Nd + |E| + N log N), avoiding an O(N^2) all-pairs interaction pattern.The rule combines dense query–block scoring, sparse propagation, and budgeted top-k selection.

9. Conclusion

The paper isolates structurally indirect prerequisite eviction as a retention-stage failure and evaluates DSGC as a one-hop structural mitigation. It frames retention as keeping reasoning chains live before retrieval begins.

  • The study isolates eviction of structurally indirect prerequisites as a retention-stage failure preceding retrieval.It distinguishes this boundary from downstream retrieval failure and other forms of forgetting.
  • DSGC applies a one-hop graph-aware rule to protect prerequisites via declared structural dependencies.This makes retention a structural reachability problem when dependency edges are supplied.
  • The released artifact includes the protocol, postmortem, calibration, main suite, robustness pack, and a reproduce.sh entrypoint.
Loading 2608.20400v1…