WitRepair: Certifiable Minimum Repair of Persistent Agent Memory via Retrieval Equivalence

Deleting a memory record that caused an agent failure can expose a replacement with the same effect. We study minimum-cardinality deletion over a declared actionable memory set, with a certificate excluding every smaller repair. We introduce WitRepair, which groups deletions by their ordered retrieved contexts. Under deterministic replay and deletion-stable rankings, each single-read class has a unique minimum representative; one replay labels the whole class. For read-only multi-turn agents, deletion and retention conditions across all reads characterize complete trace classes. We derive tight worst-case search bounds and a separate label count for certifying a given minimum repair. On ReAct–StrategyQA, the complete search policy certifies 93.33–97.44% of incidents across three models. An order-by-cache ablation attributes fresh-response differences to search order and execution savings to trace reuse. Across 12 controlled SQLite configurations, trace reuse reduces mean fresh executions from 42.42 to 9.58 under repair-first search and from 74.25 to 11.75 under direct search, relative to exact-candidate caching. Certificates establish minimum cardinality for the specified task, actionable set, and deterministic replay oracle.