betaFeedback

WorksComputer Science

When Facts Change, Which Decisions Break? Dependency-Aware Context Graphs for Agents

Abstract

When an observed fact changes, an agent must identify and repair the decisions that depend on it while preserving unaffected outputs. We investigate the reliability-cost trade-off of field-level dependency graphs extracted from actual agent read traces. A controlled benchmark spans three executable workflow domains and four successive updates, with independent imperative and expression-based references. Across 120 workflows, two models and two repeated runs, we compare full recomputation, rolling summary memory, lexical retrieval, trace-extracted dependencies and verified dependency upper bounds. Trace-derived graphs reduce reviewed decisions and estimated total cost, but omitted alternative supports and missing repair context can reduce complete-plan correctness. Paired ablations isolate the effects of edge deletion, spurious edges, transitive propagation and context scope. An exploratory enhancement supplies the existing record ID/field directory during extraction without revealing unread values or reference edges. We evaluate this enhancement on 60 fresh workflows with two repeats per model. On this fresh set, the directory-aware graph matches observed full-context complete-plan correctness for gpt-6.1-sol (100%) with an estimated 4.0% total-cost reduction, but reaches only 84.8% versus 99.6% for gpt-6-luna. The results distinguish potential dependency impact from actual decision invalidity and show why selective repair must be evaluated with both executable correctness and full memory-processing cost. The evidence concerns explicit procedural workflows; broad real-world agent-memory generalization remains untested.

Introduction

Agent decisions can remain in memory after the facts supporting them change. A supplier selected under an earlier delivery estimate may become ineligible; downstream spend, approval, and reminder decisions can then become stale. Revising a fact alone is insufficient, while recomputing every output may incur unnecessary work. Explicit dependencies offer a way to select candidate decisions for review, but their usefulness depends on the completeness of the extracted support structure and the evidence available during repair.

We investigate this trade-off with a prototype context graph and a controlled executable workflow benchmark. The central question is not whether reverse reachability identifies graph descendants, but whether a graph extracted from an agent’s actual observations supplies enough information to maintain a correct plan across successive updates. An initially sufficient read trace need not describe every alternative that can become relevant later. This creates a mismatch between initial planning and future repair.

Our contribution is an empirical evaluation rather than a claim that dependency tracking or cascading invalidation is new. We provide: (i) sequential workflows with executable reference decisions, (ii) comparisons that include initial planning, memory construction, maintenance, and repair cost, (iii) paired dependency and context ablations, and (iv) fresh-workflow evaluation of a simple observable-directory enhancement. We report failures and limitations alongside successes.

The results do not support an unconditional replacement of full-context recomputation with extracted graph repair.

Related work

StateGraph explicitly models state dependencies, verifies counterfactual support, handles alternative support, and evaluates selective cascade revision and public-memory tasks [1]. PACMI studies provenance-aware cascading memory invalidation and repair [2]. These are directly overlapping mechanisms. We do not reproduce either system and cannot claim comparative superiority.

Impact Is Not Invalidation distinguishes a changed artifact’s impact from whether a stored claim actually becomes false, using executable claim ground truth [3]. Our candidate sets are likewise separated from decision correctness: reachability is a conservative review signal rather than proof of invalidity.

LongMemEval evaluates long-term interactive memory, including knowledge updates and temporal reasoning [4]; AMA-Bench studies long-horizon memory for agentic applications and causality-graph-based memory [5]. Our external LongMemEval check is evidence-only calibration, not full-history evaluation. The narrow framing here is the reliability and total cost of trace-derived field dependencies for executable workflow repair over repeated updates.

Problem and methods

Decisions, changes, and review candidates

Let FtF_t denote observable fact records after update tt, and let DD be a fixed set of requested decisions. An explicit policy specifies an executable reference yt∗=f(Ft)y_t^* = f(F_t), while method mm maintains output vector y^t(m)\hat{y}_t^{(m)}. A decision changes in the reference when

It∗={d∈D:yt,d∗≠yt−1,d∗}.I_t^* = \{d \in D : y_{t,d}^* \ne y_{t-1,d}^*\}.

The stale-output set for a particular method is instead

It(m)={d∈D:y^t−1,d(m)≠yt,d∗}.I_t^{(m)} = \{d \in D : \hat{y}_{t-1,d}^{(m)} \ne y_{t,d}^*\}.

These sets can differ because earlier model mistakes remain in the maintained plan. We retain those mistakes rather than replacing them with oracle values.

An edge d→sd \to s means decision dd depends on support ss, annotated with watched fields. Supports can be fact records or other decisions. A field-level update Δt\Delta_t first selects decisions whose support fields intersect the changed fields, then propagates conservatively through dependent decisions. The resulting candidate set CtC_t is not necessarily It∗I_t^* or It(m)I_t^{(m)}: a changed premise can leave an output unchanged, for example when an alternative support still suffices.

The prototype stores nodes and DEPENDS_ON edges in an in-memory SQLite GraphStore. Its existing review_plan function performs reverse traversal with field filtering. Graph edges and initial stored node values are built once; current facts enter the repair context externally. This experiment therefore does not evaluate temporal edge maintenance or bitemporal correction.

Initial agent and extraction

The initial agent receives policies and a record directory containing IDs and field names, but not values. It makes an actual read_records function call, receives the requested observable records, and returns a plan with brief public explanations. Each repair method shares that initial plan within a workflow/model/repetition trial.

The main extractor receives the policies, plan, and actual tool-read results. It is instructed to enumerate direct field dependencies, including alternatives that may become relevant after changes. It does not receive reference expressions or reference dependencies. Unknown IDs, invalid fields, self-supports, and malformed annotations are rejected by the harness. Extraction quality is measured against conservative static expression references, including alternative branches; these labels are not necessary-active-cause annotations.

Repair methods

Full context. Recompute all decisions using all current fact records and the prior plan.

Rolling summary. Create a working memory prompted to at most 1,200 characters, update it with each fact patch, and recompute all outputs from that memory. This is a prompted limit, not hard truncation.

Lexical retrieval. Use a fixed keyword-overlap rule to choose eight decisions and eight fact records. This is a lightweight lexical baseline, not an embedding retriever or a reproduction of a named memory system.

Extracted graph. Select graph candidates, retrieve their recursively required support fields and stored decision values, and ask the model to recompute the requested outputs together. Unselected outputs are retained.

Verified graph. Use reference dependency annotations with the same graph selection and repair machinery. This is a diagnostic upper bound with free oracle annotations, not a deployable method with measured annotation acquisition cost.

Missing information can produce null/unknown outputs, which count as incorrect. If the candidate set is empty, no repair call is made. There are no paid SDK retries, deterministic replacement answers, or hidden fallback methods.

Experimental design

Procedural workflows

The main set contains 120 workflows, 40 per domain: procurement, scheduling, and resource allocation. Procurement includes supplier eligibility, alternative suppliers, spend, approval, ownership, and dependent reminders. Scheduling includes job ordering, sequential start/finish calculations, deadlines, and downstream coordination. Resource allocation includes ordered demand allocation, remaining capacity, coverage, costs, and ownership.

Each workflow includes unrelated fact records and four independent noise decisions. Development and test families differ in numbers of alternatives, reminder chain length, or noise volume. There are only two test families per domain, so parameter instances should not be treated as broad structural diversity. These families are held out from harness development, not model pretraining.

Four successive patches introduce a relevant shock, changed eligibility or order, an irrelevant metadata update, and a reversal or late adjustment. Policies define one exact expected answer. The generator cross-checks separate imperative and expression-DAG evaluators at every snapshot. Both evaluators still share the generator and parameters; there is no independent human annotation audit.

Models, repetitions, and cost

Two OpenAI-compatible gateway identifiers were used: openai/gpt-6-luna and openai/gpt-6.1-sol, abbreviated Luna and Sol below. These identifiers and returned served identities are retained, but dated weight snapshots and public availability are not independently established. Responses use low reasoning effort, a 4,096-token output maximum for main study calls, no server-side storage, and disabled retries.

Each workflow/model pair has two independent runs. The main study therefore contains 480 initial agent trajectories and 480×5×4=9,600480 \times5 \times4 = 9{,}600 method-update evaluations. The initial tool-use and plan-generation calls are shared within a trial but included in each method’s hypothetical standalone cost. Costs use runtime gateway prices: Luna input/output $0.10/$0.50 per million tokens and Sol $2.00/$10.00 per million tokens. Cached-input discounts are ignored. These are rate-based estimates, not provider invoices.

For a deployed method, total trajectory cost is

Km=Kinitial+Kmemory,m+∑t=14(Kmaintenance,m,t+Krepair,m,t).K_m = K_{\mathrm{initial}} + K_{\mathrm{memory},m} + \sum_{t=1}^{4}\left(K_{\mathrm{maintenance},m,t} + K_{\mathrm{repair},m,t}\right).

Graph extraction and summary generation are included rather than amortized away. The four-update horizon does not establish a universal long-run break-even point.

Endpoints and uncertainty

The primary endpoint is complete-plan correctness after each update:

Am=1N∑i=1N1RT∑r=1R∑t=1T1[y^i,r,t(m)=yi,t∗],R=2, T=4.A_m = \frac{1}{N}\sum_{i=1}^{N}\frac{1}{RT}\sum_{r=1}^{R}\sum_{t=1}^{T}\mathbf{1}\left[\hat{y}^{(m)}_{i,r,t}=y^*_{i,t}\right], \qquad R=2,\ T=4.

A single stale, missing, or unknown output makes a plan incorrect. We also report decision accuracy, initial correctness, edge precision/recall, selected outputs, changed-set coverage, tokens, and total estimated cost.

For paired accuracy differences, steps and repetitions are averaged inside a workflow, then 5,000 workflow-cluster bootstrap samples are drawn within domains. Intervals are descriptive 95% intervals; repetitions and steps are not independent samples. We do not make a multiple-comparison-adjusted familywise significance claim. When every sampled workflow succeeds, bootstrap intervals can be degenerate and do not imply zero population error.

Results

Main comparison

Table 1 reports the main comparison. Extracted graphs review substantially fewer outputs, but this reduction is accompanied by lower complete-plan correctness. The verified-graph diagnostic separates annotation limitations from the repair model’s ability to use a correct support structure.

ModelMethodAccuracy (%)95% CIReviewedTotal cost ($)
gpt-6-lunaFull context99.4[98.8, 99.9]14.670.001601
gpt-6-lunaRolling summary61.1[55.8, 66.4]14.670.002410
gpt-6-lunaLexical retrieval24.8[22.0, 27.7]8.000.001167
gpt-6-lunaExtracted graph87.6[84.1, 90.9]5.820.001553
gpt-6-lunaVerified graph98.0[96.5, 99.4]6.080.000923
gpt-6.1-solFull context100.0[100.0, 100.0]14.670.027286
gpt-6.1-solRolling summary99.6[98.8, 100.0]14.670.047122
gpt-6.1-solLexical retrieval24.3[21.5, 27.2]8.000.021335
gpt-6.1-solExtracted graph73.3[72.0, 74.6]5.430.024503
gpt-6.1-solVerified graph100.0[100.0, 100.0]6.080.015416

Table 1. Main study: 120 workflow clusters, two repeats per model, four updates. Reviewed is mean selected outputs per update. Cost includes initial planning, memory construction and maintenance, and repair. Verified annotations are free oracle inputs.

For gpt-6-luna, extracted graph accuracy differs from full context by -11.8 percentage points (paired 95% CI [-15.3, -8.4]), with estimated total cost 3.0% lower. This is not a quality-equivalent saving.

For gpt-6.1-sol, extracted graph accuracy differs from full context by -26.7 percentage points (paired 95% CI [-28.0, -25.4]), with estimated total cost 10.2% lower. This is not a quality-equivalent saving.

Complete-plan correctness in the main study

Figure 1. Complete-plan correctness in the main study. Error bars are workflow-cluster bootstrap intervals.

Mean cumulative estimated cost

Figure 2. Mean cumulative estimated cost, including initial agent calls and extraction or summary construction at update zero. Savings should be interpreted jointly with accuracy.

Initial plans are correct in 98.8% of Luna trials and 100% of Sol trials. Initial decision accuracy is 99.9% and 100%, respectively. Main extraction precision/recall is 99.9%/94.9% for Luna and 100%/82.4% for Sol. Relevant-record read coverage is 99.9% and 92.6%. Different read strategies produce different extraction evidence; these figures are not a controlled ranking of extraction capability independent of trace coverage.

Dependency robustness

On the first 30 main workflows per model, repetition zero, paired ablations remove field triples with a fixed SHA256 threshold at nominal 30%, suppress transitive traversal, or add spurious dependencies. Table 2 shows large failures under missing edges and direct-only review.

ModelMethodAccuracy (%)Reviewed
gpt-6-lunaExtracted graph88.35.87
gpt-6-lunaMissing 30%0.03.62
gpt-6-lunaActive spurious90.09.53
gpt-6-lunaDirect only9.22.15
gpt-6.1-solExtracted graph70.85.42
gpt-6.1-solMissing 30%0.03.23
gpt-6.1-solActive spurious71.79.08
gpt-6.1-solDirect only9.22.10

Table 2. Paired robustness subset: 30 workflow clusters per model, repetition zero.

The active spurious arm connects every output to the metadata field changed at update three, increasing unnecessary review. An initial implementation instead watched an unchanged contact-description field; that run is preserved as an inactive control, excluded from the active stress results. Its paid calls remain in project accounting. This correction affects the stress arm, not the frozen main comparison.

Exploratory diagnosis

Failure inspection revealed omitted alternative support and missing repair context. A procurement trace can establish that supplier A is initially eligible without reading suppliers B and C. Later, A may become ineligible; a graph that records only A can lack the fields needed to choose an alternative. A resource-allocation graph can omit the decision selecting which service’s demand applies, leaving an allocation stale after order reversal.

Two exploratory arms use the same 30-workflow subset and initial plans. The first retains extracted-graph selection but supplies all current facts during repair. The second adds the complete record ID/field directory to the extraction input without revealing unread values or reference edges. Table 3 reports both. These comparisons were motivated by preliminary main errors, and are not preregistered primary comparisons. Separate model calls introduce sampling variation.

ModelMethodAccuracy (%)Total cost ($)
gpt-6-lunaSelected outputs, full facts89.20.001753
gpt-6.1-solSelected outputs, full facts100.00.027857
gpt-6-lunaDirectory-aware graph85.00.001575
gpt-6.1-solDirectory-aware graph100.00.026020

Table 3. Exploratory context and extraction diagnostics on the paired subset.

Fresh-workflow confirmation

After the exploratory diagnosis, the directory addition was frozen and evaluated on 60 additional workflows, generator indices 120–179, disjoint from the main set. There are 20 workflows per domain and two repeats per model, giving 240 initial trajectories and 1,920 method-update evaluations. These workflows share the original procedural generator, so this is fresh-instance confirmation rather than broad out-of-distribution validation.

ModelMethodAccuracy (%)95% CIReviewedTotal cost ($)
gpt-6-lunaFull context99.6[99.0, 100.0]14.670.001600
gpt-6-lunaDirectory-aware graph84.8[79.4, 90.0]5.880.001577
gpt-6.1-solFull context100.0[100.0, 100.0]14.670.027295
gpt-6.1-solDirectory-aware graph100.0[100.0, 100.0]6.080.026193

Table 4. Fresh confirmation. The graph treatment receives the observable record directory during extraction.

For Sol, directory-aware graph repair matches observed full-context complete-plan correctness at 100%, with estimated total cost 0.960 times full context (4.0% lower). For Luna, accuracy is 84.8% versus 99.6%, a paired difference of −14.8 percentage points (95% CI [−20.2, −9.4]), with cost 0.986 times full context. Thus the simple enhancement does not uniformly preserve correctness or deliver substantial quality-equivalent savings across models.

The all-success Sol intervals are degenerate. Even zero failing clusters among 60 independent workflows permits about a 4.9% failure probability under a one-sided 95% zero-event bound. We do not claim broad noninferiority or zero error.

Fresh-workflow confirmation of directory-aware extraction

Figure 3. Fresh-workflow confirmation of directory-aware extraction. The enhancement is model-dependent within this benchmark.

Supplementary checks

LongMemEval evidence-only calibration

We select 20 knowledge-update and 20 temporal-reasoning questions from the official cleaned LongMemEval oracle evidence-only file, ordered by SHA256(question ID), excluding abstention questions. Both models answer from the supplied dated evidence or a question-independent summary prompted to at most 4,000 characters. Reference answers and answer-session IDs are hidden during answering.

A Sol judge applies criteria adapted from the official evaluator, accepting equivalent updated answers and temporal off-by-one duration errors. There is no human judge calibration. Table 5 reports these results as a separate answering/compression check. They are not full-history retrieval results, not leaderboard-comparable, and not evidence that graph repair generalizes to natural conversation.

ModelTypeFull evidence (%)Compressed evidence (%)
gpt-6-lunaknowledge-update95.080.0
gpt-6-lunatemporal-reasoning75.050.0
gpt-6.1-solknowledge-update100.090.0
gpt-6.1-soltemporal-reasoning100.090.0

Table 5. External evidence-only calibration, 20 questions per type and model. Scores are model-judged.

Graph versus flat-list cost

We measure 20 queries at each of 100, 1,000, and 10,000 nodes, with the same seven-decision affected chain. The prototype is compared with flat scans and rebuilt adjacency, including edge loading and index construction on every query. All return identical candidate sets. At 10,000 nodes, median query times are 23.55, 19.96, and 19.54 ms, respectively. The prototype loads all 8,750 edges despite the small affected set. Thus this implementation does not demonstrate an inherent speed advantage over equivalent flat dependencies. Persistent reverse indexing is a possible engineering improvement, not a measured result here. The microbenchmark uses local in-memory SQLite under concurrent model activity, not production storage latency.

Discussion and limitations

The main failure mechanism is a distinction between sufficient evidence for an initial decision and sufficient support coverage for future repair. Reverse reachability cannot recover edges or alternative facts that extraction omitted. Correct initial plans can therefore coexist with incomplete repair graphs. A record directory is a simple way to expose possible alternatives without leaking future values, but its benefit is not uniform across the tested models.

Total cost changes the efficiency conclusion. The Sol enhancement matches observed correctness on fresh instances, but saves only about 4% over four updates after paying for initial planning and extraction. Low-cost review calls alone would suggest a stronger saving than the full pipeline supports. Conversely, oracle annotations substantially reduce estimated cost in the diagnostic bound, but their acquisition cost is excluded.

The dataset has explicit rules, modest contexts, one exact answer per output, four updates, and few procedural families. Imperative and expression references agree on generated states, but share a generator and have no independent human audit. The initial agent performs a record-reading action rather than rich long-horizon execution. The lexical baseline is weak and fixed, summaries have prompted limits, and close temporal/dependency methods are not reproduced. Static edge labels include possible alternative supports, not active causal necessity. Graph maintenance, action execution, partial observability recovery through new tool reads, and multiple acceptable repairs are not evaluated.

Model aliases and gateway prices are retained, but public dated weight snapshots are not established. Summed call durations under concurrency are not user-facing end-to-end latency. Workflow bootstrap intervals measure variation within this generator, not across organizations or task families. Multiple exploratory comparisons are disclosed without a broad adjusted significance claim. Real workflow traces, human annotation, stronger retrieval, close-baseline reproduction, and additional policy families are needed before broad agent-memory claims.

Reproducibility and AI assistance

The experiment retains exact prompts, public responses, tool observations, response IDs, served model identifiers, token usage, rates, elapsed times, source hashes, dataset hashes, and internally frozen protocols. Successful checkpoints are resumable without rebilling. No external preregistration is claimed. Across prior pilots, development, main, robustness, confirmation, and judge calls, the project completed 16,558 requests with no pending or uncertain calls. Rate-based usage is estimated at $34.93; conservative admission accounting with a 25% margin is $43.66. Fifty targeted transport, budget, dependency, and workflow tests pass. No public code-repository availability is claimed in this version.

AI tools assisted software implementation, experiment orchestration, analysis, and manuscript drafting. The human author is responsible for the final manuscript and submission. AI-generated annotations are not described as independently human-verified. Generated workflow data contain fictional entities; this study does not involve real procurement, scheduling, or allocation decisions about people.

Conclusion

Trace-derived context graphs reduce review work but can fail when unvisited alternatives or selection-dependent fields are omitted. Directory-aware extraction recovers observed full-context correctness for one tested model on fresh procedural workflows, with a modest total-cost saving, while the other model remains less reliable. Selective repair should therefore be assessed using executable plan correctness, dependency coverage, and full memory-processing cost together. These results support a narrow empirical account of when selective repair fails and succeeds, rather than an unconditional graph-memory advantage.

Observable prompts and reference separation

The initial request provides policies and a record_directory, and requires a read_records tool call. The returned records are followed by a request for every decision, value, and brief public explanation; insufficient observations allow null values. Extraction requests direct field-level dependencies and possible alternative supports. The main extraction input has policies, the initial plan, and actual read results. The directory-aware condition adds record IDs and field names, without unread values.

Repair requests say: recompute all requested decisions under the latest facts; return exactly the requested IDs; old values may be stale; compute requested dependent decisions together; return null if required information is absent. Inputs contain requested IDs, corresponding policies, latest retrieved context, prior decisions, and the current patch. Reference expression trees, reference outputs, and reference dependency labels are evaluator-only. The verified-graph diagnostic is the explicit exception for edge-based selection and retrieval, not for model answer generation.

Frozen artifact identifiers

Main generator SHA256: 11fb0caa00ea591a304b846241488bc72d808da685588e095d29bdfc6ac10753.

Main runner SHA256: 6699d13f88e7a02417ab8e8ae4166a49c52ac20139f2e41d6e3105164b4b225c.

Fresh confirmation dataset SHA256: 29657cc1f394e58db186dee679d8d6531ed29709414c8df44787f1c0bcb540fe.

Full trace archives are retained by the author; publishing a portable reproduction package is future work because gateway access and exact dated model snapshots are not public prerequisites established here.

References

  1. [1]Yiqi Wang, Tongyuan Zhao, Jiaqi Zhang, Yiqun Duan, Zhangkai Wu, Mingkai Zheng, and Taotao Cai. A State Change Is Local, Its Consequences Are Not: Dependency-Aware State Revision for Long-Term Agent Memory. arXiv:2611.02912, 2026. https://arxiv.org/abs/2611.02912.
  2. [2]Yiqi Wang, Jiaqi Liu, Jiaqi Zhang, Zhangkai Wu, Yiqun Duan, Mingkai Zheng, and Taotao Cai. PACMI: Provenance-Aware Cascading Memory Invalidation for Long-Term LLM Agents. arXiv:2610.05732, 2026. https://arxiv.org/abs/2610.05732.
  3. [3]Atul Anand. Impact Is Not Invalidation: Ask About the Claim, Not the Diff. arXiv:2609.25130, 2026. https://arxiv.org/abs/2609.25130.
  4. [4]Di Wu, Hongwei Wang, Wenhao Yu, Yuwei Zhang, Kai-Wei Chang, and Dong Yu. LongMemEval: Benchmarking Chat Assistants on Long-Term Interactive Memory. arXiv:2410.10813, 2024; revised 2025. https://arxiv.org/abs/2410.10813.
  5. [5]Yujie Zhao, Boqin Yuan, Junbo Huang, Haocheng Yuan, Zhongming Yu, Haozhou Xu, Lanxiang Hu, Abhilash Shankaramppeta, Zimeng Huang, Wentao Ni, Yuandong Tian, and Jishen Zhao. AMA-Bench: Evaluating Long-Horizon Memory for Agentic Applications. arXiv:2602.22769, 2026. https://arxiv.org/abs/2602.22769.

Paper details

vlnc:W_zxnscpe7
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC0-1.0
Usage

views · 2

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents