When Facts Change, Which Decisions Break? Dependency-Aware Context Graphs for Agents
Organizations: Scale AI
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.
Figures & tables
| Model | Method | Accuracy (%) | 95% CI | Reviewed | Total cost ($) |
|---|---|---|---|---|---|
| gpt-6-luna | Full context | 99.4 | [98.8, 99.9] | 14.67 | 0.001601 |
| gpt-6-luna | Rolling summary | 61.1 | [55.8, 66.4] | 14.67 | 0.002410 |
| gpt-6-luna | Lexical retrieval | 24.8 | [22.0, 27.7] | 8.00 | 0.001167 |
| gpt-6-luna | Extracted graph | 87.6 | [84.1, 90.9] | 5.82 | 0.001553 |
| gpt-6-luna | Verified graph | 98.0 | [96.5, 99.4] | 6.08 | 0.000923 |
| gpt-6.1-sol | Full context | 100.0 | [100.0, 100.0] | 14.67 | 0.027286 |
| Model | Method | Accuracy (%) | Reviewed |
|---|---|---|---|
| gpt-6-luna | Extracted graph | 88.3 | 5.87 |
| gpt-6-luna | Missing 30% | 0.0 | 3.62 |
| gpt-6-luna | Active spurious | 90.0 | 9.53 |
| gpt-6-luna | Direct only | 9.2 | 2.15 |
| gpt-6.1-sol | Extracted graph | 70.8 | 5.42 |
| gpt-6.1-sol | Missing 30% | 0.0 | 3.23 |
| Model | Method | Accuracy (%) | Total cost ($) |
|---|---|---|---|
| gpt-6-luna | Selected outputs, full facts | 89.2 | 0.001753 |
| gpt-6.1-sol | Selected outputs, full facts | 100.0 | 0.027857 |
| gpt-6-luna | Directory-aware graph | 85.0 | 0.001575 |
| gpt-6.1-sol | Directory-aware graph | 100.0 | 0.026020 |
| Model | Method | Accuracy (%) | 95% CI | Reviewed | Total cost ($) |
|---|---|---|---|---|---|
| gpt-6-luna | Full context | 99.6 | [99.0, 100.0] | 14.67 | 0.001600 |
| gpt-6-luna | Directory-aware graph | 84.8 | [79.4, 90.0] | 5.88 | 0.001577 |
| gpt-6.1-sol | Full context | 100.0 | [100.0, 100.0] | 14.67 | 0.027295 |
| gpt-6.1-sol | Directory-aware graph | 100.0 | [100.0, 100.0] | 6.08 | 0.026193 |
| Model | Type | Full evidence (%) | Compressed evidence (%) |
|---|---|---|---|
| gpt-6-luna | knowledge-update | 95.0 | 80.0 |
| gpt-6-luna | temporal-reasoning | 75.0 | 50.0 |
| gpt-6.1-sol | knowledge-update | 100.0 | 90.0 |
| gpt-6.1-sol | temporal-reasoning | 100.0 | 90.0 |
AI Agent Reliability
AI agent reliability studies whether tool-using systems act correctly, consistently, safely, and recoverably across changing tasks and environments.
See all 364 papers