acceptodds
Under review as a conference paper at ICLR 2027

From Error Propagation to Recovery: Principles for Persistent Memory in Multi-Agent Systems

Abstract

Error propagation undermines reliable decision-making in large language model-based multi-agent systems (LLM-MAS). Existing work uses persistent memory to mitigate this problem, but **lacks a theoretical characterization of how memory enables recovery**. This leaves memory design without theoretical guidance on **what to remember** and **when to intervene**, potentially leading to unnecessary memory use and increased **token and storage costs**. To address this gap, we connect error propagation and recovery analysis, establishing the necessity of persistent memory in LLM-MAS under information loss and deriving principles for memory design. Specifically, we derive a closed-loop error propagation law coupling agent communication and environment feedback. We further analyze error recovery under information loss and show that persistent memory reduces the optimal error from random guessing to zero. Guided by this theoretical analysis, we develop , an in-task memory for efficient error recovery. Experiments across five benchmarks and three MAS frameworks demonstrate performance gains over in-task and cross-task memory baselines, with efficiency analyses showing reduced token usage and storage overhead.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Multi-agent Systems, Error Propogation, Agent Memory

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_w2iGOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies how errors propagate in LLM-based multi-agent systems and when persistent memory can enable recovery. It models the feedback loop between agent communication and environment interaction, establishes information-theoretic limits on recovery without new evidence, and constructs a task where minimal persistent memory enables exact recovery while memory-free interaction remains at chance. These results motivate RECOVER, an in-task memory mechanism that retains verified evidence for action preconditions and selectively injects it when it resolves an otherwise undetermined check. Experiments across five benchmarks and three multi-agent frameworks report the highest mean performance among the evaluated baselines, while injection-timing comparisons and efficiency analyses support improved token and storage efficiency.

Critical strengths
  1. Clear theoretical insight. The paper establishes when communication alone cannot recover lost information and how sufficient memory can restore correct decisions, providing a principled basis for memory design.
  2. Consistent practical benefits. RECOVER achieves the highest mean performance across all 15 benchmark–framework combinations, with timing and efficiency experiments supporting selective evidence injection.
Critical weaknesses
  1. The connection between the theory and RECOVER remains limited. Theorem 3 establishes separation through a construction that stores the already-computed target before erasing it from all transient inputs (Appendices B.2–B.4). This demonstrates the value of preserving information, but does not establish that RECOVER’s precondition-based representation is sufficient for general task recovery. Proposition 3 guarantees only local verdict correctness under strong evidence-validity and retrieval assumptions. Consequently, the theory provides motivation rather than a substantive guarantee for the proposed system.
  2. The experiments do not isolate the central mechanism. RECOVER combines structured evidence retention, precondition checking, selective injection, and an additional revision call (Appendix C.1). Although Figure 6 evaluates injection timing, the reported comparisons do not separate the contribution of precondition-based memory from structured state tracking or additional deliberation. This leaves uncertainty about whether the gains specifically validate the proposed memory-design principles.
Questions for authors
  1. Clarification: Beyond the constructed erasure task, what result or measurement connects the propagation analysis to RECOVER’s recovery benefits? In particular, how does correctness of the declared preconditions translate into recovery of the task-level target?
  2. Clarification: How are evidence extraction, invalidation, and precondition checking implemented and validated, particularly for semantic judgments in FEVER? What evidence shows that the assumptions underlying Proposition 3 hold sufficiently often in actual runs?
  3. Targeted validation: Can you provide a controlled comparison against compact factual memory with the same checking and revision budget, changing only the precondition-based retention or injection rule? This would help establish whether the proposed mechanism explains the gains.
6 comments

W1 & Q1.

Clarification: Beyond the constructed erasure task, what result or measurement connects the propagation analysis to RECOVER’s recovery benefits? In particular, how does correctness of the declared preconditions translate into recovery of the task-level target?

We thank the reviewer for this important question.

1. Empirical connection between error propagation and RECOVER's recovery benefits

Beyond the constructed erasure task, empirical analysis validates error propagation in MAS, while complementary experiments demonstrate RECOVER's improvements in task success and token efficiency.

  • Empirical validation of propagation analysis (Theorem 1). We connect the error propagation mechanisms characterized by Theorem 1 to RECOVER's recovery decisions and their measured benefits.
Propagation Analysis (Theorem 1)Empirical AnalysisTheory-to-Method ConnectionRECOVER's Recovery Benefits
Topology- and depth-dependent propagationAcross 64 ALFWorld configurations, propagation factors correlate with terminal drift at ρ = 0.9982/0.9988 (Fig. 5; Table 10).Recovering decisions using retained evidenceBenefits of recovery-oriented memory use: RECOVER achieves 91.54% accuracy, outperforming retrieval-based memory (77.61%) by 13.93 pp with 27.50% fewer tokens, and revision-based memory (73.88%) by 17.66 pp with 31.66% fewer tokens.
Error propagation to actions and statesAcross 864 ALFWorld decision records, terminal drift correlates with action and next-state discrepancies at ρ = 0.656/0.657, with 99.54% bound coverage (Fig. 3; Tables 7–8).Motivate when to intervene: Resolve undetermined preconditions before execution.Insertion ablation: Under identical Extract-based retention, Check-step insertion improves accuracy from 89.04% to 91.54% (+2.50 pp) over Every-step insertion, with 4.87% fewer tokens.
Persistent downstream effectsIn ScienceWorld, injected factual errors cause greater late-window trajectory divergence across all seven topologies (Fig. 4; Table 9).Motivate what to retain: Preserve decision-relevant evidence for subsequent decisions.Retention ablation: Under identical Check-step insertion, Extract-based retention improves accuracy from 79.85% to 91.54% (+11.69 pp) over Fact-based retention, with 25.10% fewer tokens.
  • Complementary theoretical support for recovery (Theorems 2–3).
ProposedTheoretical ContributionTheory-to-Method Connection
Theorem 2Establishes that endogenous interaction cannot recover information lost from transient inputs.Inject memory when a precondition is undetermined, but retained evidence can resolve it (Eq. 5). Insertt=1[Check(Pt,Et)=⊥∧Check(Pt,Et∪Mt)≠⊥]\mathrm{Insert}_t = \mathbf{1}[\mathrm{Check}(P_t, E_t) = \bot \land \mathrm{Check}(P_t, E_t \cup M_t) \neq \bot]. Only the relevant missing facts are injected.
Theorem 3Establishes the necessity and sufficiency of persistent memory for exact recovery in a constructed distributed task.Retain valid evidence beyond transient context, preserving information needed for subsequent recovery (Eq. 4). Mt+1=Update(Mt,ExtractPre(at,ot+1))M_{t+1} = \mathrm{Update}(M_t, \mathrm{ExtractPre}(a_t, o_{t+1})).

The overall recovery comparison further supports the practical value of the theory-guided design. With Extract-based retention and Check-step insertion, RECOVER improves task accuracy from 77.61% with retrieval-based memory to 91.54% (+13.93 pp) while using 27.50% fewer tokens. It also outperforms revision-based recovery by 17.66 pp with 31.66% fewer tokens.

W1 & Q1. (continued)

2. Precondition correctness translate into task-level target recovery

Controlled experiments demonstrate that RECOVER translates correct precondition judgments into reduced errors during task execution and improved final task success.

  • Recovery of task-level target errors. We quantify RECOVER's recovery benefits by measuring the reduction in per-step error rates during subsequent task execution with precondition-based memory insertion compared to fact-based memory insertion.
MethodError Reduction ↓Task Accuracy ↑
Fact-based Memory5.12 pp79.85%
RECOVER (precondition-based)28.36 pp91.54%
  • Precondition-oriented memory and task-level recovery. We further compare different memory designs under identical Check-step insertion settings:
MethodMemory TypeACC ↑Tokens/Task ↓
Revision-basedFact-based70.90%57,654
Precondition-based73.88%56,197
Retrieval-basedFact-based75.37%54,594
Precondition-based77.61%52,975
RECOVERFact-based79.85%51,276
RECOVER (Ours)Precondition-based91.54%38,406

Precondition-based RECOVER memory achieves the highest task accuracy and lowest token consumption, improving accuracy by up to 20.65 percentage points while reducing tokens per task by 33.39% compared with fact-based revision.

Overall, these results demonstrate that correct precondition recovery reduces errors during task execution and supports task-level target recovery, improving end-to-end task success and token efficiency.

Q2.

Clarification: How are evidence extraction, invalidation, and precondition checking implemented and validated, particularly for semantic judgments in FEVER? What evidence shows that the assumptions underlying Proposition 3 hold sufficiently often in actual runs?

We thank the reviewer for this important question. Independent assessments validate the reliability of RECOVER's evidence extraction and precondition checking. Controlled experiments further support the practical applicability of Proposition 3's assumptions in task-level recovery. The implementation details and experimental evidence are presented below.

1. Implementation of evidence extraction and precondition checking

Extract/Check Implementation. Both components use straightforward implementations without specialized architectures or additional training.

ComponentImplementationExample
ExtractUses fixed regular-expression templates tailored to each environment's action grammar and observation format. Extracts action arguments and observed state values while preserving source spans.FEVER: Given claim (q): “Global warming threatens food security.” and agent responded action “finish support the claim,” extracts Claim[q], Finish[Support], and Support[Claim].
CheckEvaluates preconditions using fixed action schemas. Reuses benchmark regular-expression templates for PDDL-like environments (e.g., ALFWorld) and direct field lookup/value comparison for structured conditions. For textual conditions (primarily FEVER), uses a frozen DeBERTa-v3-base-mnli entailment model.FEVER: Map entailment → true, contradiction → false, and neutral → unknown.

2. Empirical validation of Proposition 3's assumptions

  • Independent correctness assessment. We independently evaluated sampled Extract and Check outputs using GPT-6/Astra-based assessments:
Independent EvaluatorExtract Accuracy ↑Check Accuracy ↑
GPT-6/Astra92.68%100.00%
DeepSeek-V4-Flash90.91%96.10%

These results provide independent empirical support for the correctness of evidence extraction and precondition checking, two key operations underlying Proposition 3.

  • Sensitivity to Extract/Check errors and assumption violations. Precondition-based retention consistently outperforms fact-based retention under imperfect Extract/Check conditions, supporting the robustness of RECOVER's recovery mechanism.

To ensure a fair comparison, both methods use identical Extract implementations and RECOVER's Check-step insertion rule. We introduce controlled errors by randomly dropping Extract outputs or flipping Check verdicts, and compare the resulting accuracy degradation across different memory strategies.

SettingFact-based memory ACC ↑RECOVER ACC ↑Gain (pp) ↑
Original Extract/Check78.36%91.54%+13.18
Extract-drop-10%75.87%91.04%+15.17
Extract-drop-20%70.40%90.05%+19.65
Check-flip-10%73.38%85.32%+11.94
Check-flip-20%69.90%82.84%+12.94

Overall, the independent correctness assessments and sensitivity analysis provide empirical support for evidence extraction and precondition checking mechanisms, and demonstrate the sufficiency of Proposition 3’s assumptions for effective recovery in actual runs.

Reviewer_NBbhOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

this work analyzes error propagation through multi-agent communication and environment feedback, then asks whether further communication can recover information lost from transient context. a constructed task shows how persistent memory can preserve otherwise unrecoverable target information. RECOVER builds on this motivation by storing valid, source-backed facts and injecting them when they resolve an unknown action precondition. Experiments cover five benchmarks and three multi-agent frameworks, reporting task success, insertion-timing comparisons, and token and storage costs.

Critical strengths
  1. Section 5 makes a useful distinction between reducing error and recovering information. Even a contracting communication process need not restore discarded evidence. This explains why additional interaction rounds may not substitute for memory. 2. RECOVER has broad empirical coverage, achieving the highest mean in all 15 benchmark–framework combinations in Table 1. Figure 6 already compares fixed insertion schedules, and Figure 8 reports costs. These results make maintaining valid facts and using memory selectively a worthwhile system design.
Critical weaknesses
  1. I am not yet clear about which algorithmic choices follow from the theory. In Theorem 3's construction, the target U has already been aggregated at t0, and persistent state stores U directly. This establishes the need to preserve information, but does not provide a procedure for constructing minimal sufficient memory in general tasks. Proposition 3 further assumes correct evidence judgments, sufficient witnesses, and successful retrieval; its guarantee concerns the precondition verdict. The appendix states these limits, but the connection from the propagation bounds to RECOVER's stored content or insertion rule remains unclear.

  2. The main experiments do not sufficiently separate memory from checking and revision. the existing timing ablation does not control these differences. It is therefore difficult to determine how much of the improvement comes from the memory mechanism itself, especially on FEVER/HotpotQA, where checking involves entailment or relations.

Questions for authors
  1. Which retention or insertion decisions depend directly on Theorems 1–3, beyond the general motivation to preserve sufficient information? Please explain how Proposition 3's guarantee relates to the final task success measured in the experiments.

  2. With the same fact representation, checker, and extra revision-call budget, how much does RECOVER improve over simple retrieval or revision alone? Please also specify how Extract/Check are implemented and whether their errors have been independently assessed. This comparison would be most likely to change my recommendation.

4 comments

W1 & Q1.

Which retention or insertion decisions depend directly on Theorems 1–3, beyond the general motivation to preserve sufficient information? Please explain how Proposition 3's guarantee relates to the final task success measured in the experiments.

We thank the reviewer for this important question. Theorems 1–3 directly inform RECOVER's memory retention and insertion decisions. Proposition 3 guarantees correct local precondition recovery under its stated assumptions. Their connections to the implemented mechanisms and final task success are detailed below.

1. Direct connections between theoretical results and RECOVER's retention and insertion decisions

ProposedTheoretical contributionCorresponding method operationSupporting experimental results
Theorem 1Bounds error propagation through MAS communication topology, depth, and task horizon.Check and revise proposed actions (a~t\tilde{a}_t) before execution to prevent errors from entering the environment feedback loop (Appendix C.1).(i) Topology propagation: 64 ALFWorld configurations, ρ=0.9982/0.9988\rho = 0.9982/0.9988 (Fig. 5; Table 10). (ii) Action–state propagation: 864 decision records, ρ=0.656/0.657\rho = 0.656/0.657, with 99.54% bound coverage (Fig. 3; Tables 7–8). (iii) Downstream effects: Persistent trajectory divergence across 7 ScienceWorld topologies (Fig. 4; Table 9).
Theorem 2Establishes that endogenous interaction cannot recover information lost from transient inputs.Inject memory when a precondition is undetermined, but retained evidence can resolve it (Eq. 5). $\mathrm{Insert}_t = \mathbf{1}[\mathrm{Check}(P_t,E_t)=\bot $ $ \land \mathrm{Check}(P_t,E_t \cup M_t) \neq \bot]$. Only the relevant missing facts are injected.(i) Controlled insertion ablation: +5.56 pp performance, with 7.6% fewer tokens (Fig. 6).
Theorem 3Establishes the necessity and sufficiency of persistent memory for exact recovery in a constructed distributed task.Retain valid evidence beyond transient context, preserving information needed for subsequent recovery (Eq. 4). Mt+1=Update(Mt,M_{t+1} = \mathrm{Update}(M_t, ExtractPre(at,ot+1))\mathrm{Extract_{Pre}}(a_t,o_{t+1})).(i) Execution-level recovery: 28.36 pp per-step error reduction with precondition-based memory versus 5.12 pp with fact-based memory, relative to no memory insertion. (ii) Recorded-run validation: Evidence retained at step 9 resolves an undetermined precondition at step 16 (Table 2).
Proposition 1Characterizes exact recoverability through the distinguishability of histories requiring different answers.Retain decision-relevant precondition evidence and its supporting observations through ExtractPre\mathrm{Extract_{Pre}}.(i) Controlled retention ablation: +11.69 pp ACC, with 25.10% fewer tokens, compared with fact-based retention. (ii) Cross-method validation: +2.99 pp for Revision and +2.24 pp for Retrieval under identical Check-step insertion.

2. Connection between Proposition 3 and final task success

Proposition 3 theoretically guarantees correct local precondition recovery, and controlled experiments further demonstrate that these recovery mechanisms improve end-to-end task success. We conduct additional experiments to evaluate the effects of theory-guided memory retention and insertion on final task success:

RetentionInsertionACC ↑
Fact-basedCheck step79.85%
Precondition-basedEvery step89.04%
RECOVER (Precondition-based)Check91.54%

Under identical check-step insertion, precondition-based retention improves task accuracy by 11.69 percentage points over fact-based retention. With the same precondition-based retention, targeted check-step insertion further improves accuracy by 2.50 percentage points over every-step insertion.

Overall, Proposition 3 establishes the correctness of local precondition recovery. And the empirical results demonstrate that theoretically motivated retention and insertion decisions translate into measurable improvements in final task success in MAS.

W 2 & Q 2.

With the same fact representation, checker, and extra revision-call budget, how much does RECOVER improve over simple retrieval or revision alone? Please also specify how Extract/Check are implemented and whether their errors have been independently assessed. This comparison would be most likely to change my recommendation.

We thank the reviewer for pointing this question. Under matched configurations, RECOVER improves task accuracy by 13.93 and 17.66 percentage points over simple retrieval and revision, respectively, while reducing token consumption. We further clarify the implementation and independent assessment of Extract/Check, and provide controlled experiments to validate the effectiveness of memory-based error recovery.

1. Comparison with simple retrieval and revision

We conducted comprehensive comparisons across different memory retention and injection strategies to isolate the contribution of persistent-memory-based error recovery. Under matched Extract-based retention and check-step injection settings, RECOVER improves task accuracy by 13.93 and 17.66 percentage points over simple retrieval and revision, respectively, while reducing token consumption by 27.5% and 31.7%.

MethodRetentionInjectionACC ↑Tokens/Task ↓
RevisionFact-basedEvery Step66.4179%127,090.11
Fact-basedCheck step70.8955%57,654.05
ExtractEvery Step67.9104%113,740.66
ExtractCheck step73.8806%56,196.66
RetrievalFact-basedEvery Step68.6567%71,676.47
Fact-basedCheck step75.3731%54,594.35
ExtractEvery Step70.1493%73,145.73
ExtractCheck step77.6119%52,974.98
RECOVERExtractEvery Step89.044740,373.447
RECOVERFact-basedCheck79.8507%51,276.35
RECOVER (Ours)ExtractCheck91.542%38,405.709

The results consistently demonstrate RECOVER's advantages in both task success and token efficiency. Under identical Extract-based retention and check-step injection settings, RECOVER substantially outperforms both retrieval and revision. Furthermore, precondition-based retention improves RECOVER's accuracy by 11.69 percentage points over fact-based retention, while check-step injection provides an additional 2.50 percentage point improvement over every-step injection.

W2 & Q2 (continued)

2. Extract/Check implementation and evaluation

Extract and Check use straightforward engineering implementations without specialized architectures or sophisticated optimization. RECOVER's improvements stem from its core contribution of error recovery through persistent memory, rather than reliance on perfectly accurate Extract/Check components. This can be supported by following independent correctness assessments and controlled error injection experiments.

  • Independent assessment. We independently evaluated sampled Extract/Check outputs using external LLM evaluators, obtaining the following accuracy results:
Independent EvaluatorExtract Accuracy ↑Check Accuracy ↑
GPT-6 Astra92.68%100.00%
DeepSeek-V4-Flash90.91%96.10%
  • Sensitivity of Extract/Check to assumption violations. To further assess whether RECOVER's improvements depend on Extract/Check correctness, we deliberately introduced errors by dropping 10% or 20% of Extract outputs or flipping 10% or 20% of Check verdicts on ALFWorld.
SettingRetrieval-based ACC ↑RECOVER ACC ↑Gain (pp) ↑
Original Extract/Check75.37%91.54%+16.17
Extract-drop-10%73.88%91.04%+17.16
Extract-drop-20%70.40%90.05%+19.65
Check-flip-10%69.90%85.32%+15.42
Check-flip-20%67.16%82.84%+15.68

RECOVER consistently outperforms retrieval-based memory across all tested Extract/Check error conditions, maintaining accuracy gains of 15.42 - 19.65 percentage points. These results support the robustness of RECOVER's recovery mechanism under imperfect Extract/Check components.

  • Implementation details. Extract and Check use straightforward engineering implementations without specialized architectures or additional training.

    • Extract uses fixed regular-expression templates tailored to each environment's action grammar and observation format. It parses action arguments and observed state values while preserving their source spans. For FEVER and HotpotQA, it retains task-input text, source identifiers, and agent actions. For example, given the FEVER claim (qq) ] Global warming threatens food security. and the agent response finish support the claim, Extract produces Claim[q], Finish[Support], and Support[Claim]. These records capture the input and action semantics, without independently verifying the claim.

    • Check evaluates preconditions using fixed action schemas. For PDDL-like environments such as ALFWorld, it reuses existing regular-expression checking templates provided by the dataset. Structured conditions are evaluated through direct field comparisons. For textual conditions, primarily in FEVER, evaluations are handled by a frozen DeBERTa-v3-base-mnli model, mapping entailment, contradiction, and neutral to true, false, and unknown, respectively.

Overall, these evaluations demonstrate that RECOVER's task-success improvements stem from its theory-guided recovery of information loss caused by error propagation in MAS. These improvements are not driven by perfectly accurate or sophisticated Extract/Check components.

We sincerely thank the reviewer for the insightful and constructive feedback, which has helped us strengthen our work.

We will incorporate these additional experiments and clarify the corresponding evaluation protocols in the revised manuscript. Detailed implementation information for the additional rebuttal experiments, including revision and retrieval baseline configurations, ablation studies, and illustrative examples of evidence extraction and precondition checking, has been added to our anonymous GitHub repository to facilitate reproducibility.

We hope these additional experimental results and clarifications adequately address the reviewer's concerns and encourage the reviewer to reconsider the rating.

Reviewer_YHpbOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies error propagation in LLM multi-agent systems (MAS) and argues for persistent memory. It first derives a closed-loop error propagation law (Theorem 1) that couples agent-to-agent communication within a step with action–environment feedback across steps, bounding error growth through the communication topology, the communication depth, and the task horizon. It then gives a Fano-type lower bound for memory-free interaction (Theorem 2) and a constructed distributed task where memory-free interaction stays at random-guessing error while a persistent memory with R states reaches zero error (Theorem 3).

Guided by this, it proposes RECOVER, an in-task memory that stores observation-verified precondition facts and injects them only when a proposed action's preconditions cannot be decided from the current context. On five benchmarks and three MAS frameworks with Qwen3-14B, RECOVER has the highest mean in all 15 combinations and reports lower token use and storage than cross-task memories.

Critical strengths

S1. An important and hard problem. Error analysis in a MAS is much more complex than in a single agent, whose trajectory is one time-ordered sequence: in a MAS, errors pass between agents within a step and through the environment across steps. The paper tackles this problem directly, couples both loops in one bound (Theorem 1), and tests the propagation factors with controlled error injection (Figs. 3–5).

S2. Open-source code. The code is released in an anonymous repository (p. 1 footnote; L1965). For replicability, a public codebase is a good sign.

S3. Many and thorough experimental results, reported in full and well organized. Table 1 covers every pair of five benchmarks and three MAS frameworks against eight memory baselines (in-task and cross-task, single-agent and multi-agent) and a no-memory reference. App. E.3 repeats the full grid with Qwen3-8B and Qwen3-32B (Tables 13–14). Results are not cherry-picked and reported fully -- the paper also reports cases where memory falls below raw history (L428–431), and App. C.2 adds five worked traces, one per benchmark.

Critical weaknesses

W1. Generalizability is limited: every backbone is from the Qwen3 family.

  • The main paper results use only Qwen3-14B (L417). App. E.3 adds Qwen3-8B and Qwen3-32B (Tables 13–14, Fig. 7), which partly covers model scale, but no other open or API model family is tested.
  • Tables 13–14 also report no standard deviation, and several baselines collapse there, e.g., with Qwen3-8B raw history scores 8.955% on ALFWorld against 67.164% for RECOVER, and with Qwen3-32B ACON scores 16.224% against 57.192% for raw history on ScienceWorld (AutoGen).

W2. The analysis stays high level.

  • The paper shows that memory helps, but not exactly which MAS errors it reduces or how. App. C.2 gives five worked traces of how RECOVER writes and injects facts, which helps, but they show the rule, not its effect: no baseline is shown on the same task, and there is no breakdown of which error types memory fixes. All propagation experiments (Figs. 3–5) run with memory disabled (L1512), so no experiment shows RECOVER reducing propagated error. The only design ablation is injection timing (Fig. 6); nothing varies what is stored, e.g., precondition facts versus full history at the same trigger. Would be good to provide with more example-wise qualitative analysis.

W3. Why memory, and not verification?

  • To stop error propagation, self-verification, reviewer, verifier, or judge agents come to mind first, and MAS work already adds inspector and challenger agents for this purpose [1].
  • The paper neither discusses nor compares with such methods; Reflexion is cited only as a memory method (L51–52). RECOVER itself checks action preconditions and makes an extra revision call when memory resolves a check (App. C.1), so part of its gain may come from verification rather than from memory. No ablation runs the same check and revision without stored memory.

W4. RECOVER is not positioned well against closely related MAS memory and shared-workspace designs.

  • Shared workspace: MAS designs where agents read and write a shared workspace or blackboard [2] are not discussed. A MetaGPT memory variant is evaluated as a baseline, but how RECOVER differs conceptually from a shared pool is not stated.
  • In-task MAS memory: the claim that in-task memory beats cross-task memory at lower cost misses Intrinsic Memory Agents [3], an in-task MAS memory evaluated with the same G-Memory protocol on ALFWorld and FEVER. It is neither cited nor compared, and the in-task baselines here (HiAgent, ACON) are single-agent methods.

W5. The theoretical contribution is smaller than claimed.

  • The paper claims the first theoretical characterization of the coupled error propagation law (L71–72, L111–112), but topology-based analyses of error propagation in LLM-MAS exist. Xie et al. [4] derive an amplification threshold on an operator of the same form as Definition 2 (M_G = dI + gA_G).
  • The paper cites [4] for the macro-level loop in which joint actions change environment states that feed back into communication (L106–108), but [4] models only message-level adoption, without environment state or feedback.
  • Theorems 2–3 are close to results that memory-free interaction cannot recover hidden or lost information [5, 6], which are not cited. Theorem 3 also holds by construction: the memory stores the target itself, and the perturbation erases it from every context (App. B.2–B.3).
  • RECOVER does not use the propagation factors of Theorem 1 (topology, depth, horizon), so the link from theory to method is loose.

References

[1] Huang et al., On the Resilience of LLM-Based Multi-Agent Collaboration with Faulty Agents, arXiv:2408.00989

[2] Han et al., Exploring Advanced LLM Multi-Agent Systems Based on Blackboard Architecture, arXiv:2507.01701

[3] Yuen et al., Intrinsic Memory Agents: Heterogeneous Multi-Agent LLM Systems through Structured Contextual Memory, arXiv:2508.08997

[4] Xie et al., From Spark to Fire: Modeling and Mitigating Error Cascades in LLM-Based Multi-Agent Collaboration, arXiv:2603.04474

[5] Baldelli et al., LLMs Can't Play Hangman: On the Necessity of a Private Working Memory for Language Agents, arXiv:2601.06973

[6] Choi et al., Debate or Vote: Which Yields Better Decisions in Multi-Agent Large Language Models?, arXiv:2508.17536

Questions for authors
  1. Each experiment is run only twice. MAS runs are noisier than single-agent runs, so please report 3–5 runs with confidence intervals. With two runs, RECOVER's mean minus one standard deviation overlaps the strongest baseline's mean plus one standard deviation in 12 of the 15 cells of Table 1.
  2. Can RECOVER generalize and scale up? The main text does not state how many agents each framework uses, and the theory experiments use at most 8 agents and 100 steps. Does RECOVER stay efficient and still stop error propagation with many agents (e.g., 100), or on long-horizon tasks with many facts to remember and verify, such as SWE marathon-style or BrowseComp-style tasks?
  3. Sec. 7.2 reports relative gains of 1.45%–7.31% over the strongest baseline (L424, L1979), but from Table 1 the smallest relative gain is 2.22% (AutoGen, ALFWorld: 91.542 vs. 89.552). How was 1.45% computed? Also, L413 lists a memory-augmented MacNet variant as a baseline, but Table 1 has no such row.
7 comments

W1.Generalizability is limited: every backbone is from the Qwen3 family.

We thank the reviewer for this important concern. Additional experiments on two non-Qwen3 backbone families, Llama-3.1-8B-Instruct and Gemma-3-12B-it, demonstrate that RECOVER consistently improves task success and token efficiency across different model families.

We conducted additional experiments on AutoGen-ALFWorld, evaluating all 134 tasks with each backbone under the same experimental protocol.

BackboneNo In-Task Memory ACC ↑RECOVER ACC ↑Gain (pp) ↑Token Savings ↑
Llama-3.1-8B-Instruct3.73%9.70%+5.975.81%
Gemma-3-12B-it69.40%79.85%+10.4520.26%

RECOVER consistently improves task performance across 5 LLM backbones from three model families, 3 MAS frameworks, and 5 task domains, demonstrating its effectiveness across diverse experimental settings. Furthermore, RECOVER operates on task observations, action preconditions, and retained evidence without backbone-specific training or parameter modifications, supporting its generalizability and applicability across different backbone architectures.



W2. The analysis stays high-level.

We thank the reviewer for this constructive suggestion. Additional controlled experiments directly demonstrate that RECOVER reduces errors during task execution and that its theory-guided memory retention and insertion decisions improve task success.

  • Recovery of task-level target errors. To solve this concern, we additionaly conduct a experiment to hows RECOVER reducing propagated error. We quantify RECOVER's recovery benefits by measuring the reduction in per-step error rates during subsequent task execution with RECOVER memory compared to fact-based memory insertion.
MethodError Reduction ↓Task Accuracy ↑
Fact-based Memory5.12 pp79.85%
RECOVER (precondition-based)28.36 pp91.54%
  • Controlled recovery experiments. We evaluated the individual contributions of retention and insertion.
MethodRetentionInsertionACC ↑Tokens/Task ↓
ExtractEvery Step89.044740,373.447
Fact-basedCheck79.8507%51,276.35
RECOVER (Ours)ExtractCheck91.542%38,405.709
  • Connection to propagation analysis. The original propagation experiments (Figs. 3-5) intentionally operate without memory to isolate communication-driven error propagation. The additional execution-level experiments of RECOVER and controlled ablations evaluate RECOVER's recovery interventions along this identified propagation pathway.

Together, these results connect the theoretical propagation analysis to RECOVER's measurable benefits in execution reliability, task success, and token efficiency.

W3. Why memory, and not verification?

We thank the reviewer for this important concern. Our theoretical results establish why persistent memory is necessary when verification cannot recover missing information, and controlled experiments demonstrate RECOVER's additional benefits beyond verification and revision.

1. Theoretical Justification: Why Memory Is Necessary Beyond Verification

Theorems 2–3 establish the necessity of persistent memory for recovering lost information.

Theorem 2 establishes the information limit of verification alone. When transient context (XDX_D) is insufficient to determine the target (YDY_D), and endogenous interaction introduces no additional target information, all such protocols remain subject to the Bayes-error lower bound (err⁡(YD∣XD)\operatorname{err}(Y_D\mid X_D)), regardless of communication depth. This includes additional self-verification, reviewer, or judge calls operating under the same information constraint.

Theorem 3 establishes the recovery benefit of persistent memory. In the constructed distributed task, memory-free endogenous interaction has optimal error (1−1/R1-1/R) after erasure, regardless of communication depth. In contrast, an (RR)-state persistent memory enables zero-error recovery, and (RR) states are also necessary.

Together, these theorems establish that verification alone cannot overcome the information loss under the stated assumptions, while persistent memory enables recovery by preserving otherwise unavailable evidence.

2. Empirical Validation: Benefits Beyond Verification and Revision

Controlled comparisons demonstrate that RECOVER's evidence recovery mechanism improves task success beyond additional checking and revision under matched budgets.

All methods use the same additional revision-call budget, with precondition-based retention and Check-step insertion held fixed. The self-verification baseline also retains historical memory.

MethodACC ↑Tokens/Task ↓
Self-verification73.88%56,197
Retrieval-based77.61%52,975
RECOVER (Ours)91.54%38,406

RECOVER outperforms self-verification recovery by 17.66 percentage points with 31.66% fewer tokens, and retrieval-based memory by 13.93 percentage points with 27.50% fewer tokens. These results demonstrate the additional benefits of RECOVER's structured evidence recovery under matched verification budgets.

Overall, these theoretical and empirical results establish the importance of persistent memory beyond verification alone. RECOVER's primary contribution is a theory-guided recovery mechanism that restores missing evidence to support correct precondition judgments, reducing execution errors and improving end-to-end task success.

W4. RECOVER is not positioned well against closely related MAS memory and shared-workspace designs.

We thank the reviewer for highlighting these related approaches. Our evaluation covers diverse MAS memory methods, and RECOVER's distinct contribution is a theory-guided memory framework specifically designed to recover from information loss caused by error propagation in MAS.

1. Baseline comparison with related MAS memory methods

Our evaluation builds on the G-Memory protocol and extends it with additional in-task memory methods, comparing against eight memory baselines and raw history across five benchmarks and three MAS frameworks (15 combinations).

CategoryMethods
MAS and shared-workspaceG-Memory [1], MetaGPT[2], ChatDev[3]
In-task memoryHiAgent[4], ACON[5]
Cross-task memoryVoyager[6], MemoryBank[7], Generative Agents[8]

MetaGPT employs a shared message pool, while G-Memory (NeurIPS 2025) organizes collaborative experience through hierarchical memory graphs. Thus, shared-workspace and collaborative memory mechanisms are already represented in our comparisons. Furthermore, we incorporate HiAgent (ACL 2025) and ACON (ICML 2026), evaluating these in-task memory and context-management methods within the same MAS frameworks.

We recognize Intrinsic Memory Agents [9] (arXiv) as a relevant in-task MAS memory approach. RECOVER's advantage in design lies in its explicit recoverability criterion and corresponding theoretical guarantees, beyond organizing role-aligned contextual memory. We will additionally include a direct comparison with this method.

2. Memory designed for MAS recovery

Our primary contribution is the theoretical characterization of error propagation and recoverability in MAS, which provides a principled foundation for recovery-oriented memory design.

Theoretical ResultsContribution to RECOVER
Theorem 1Characterizes error propagation through communication, actions, and environment feedback, motivating recovery before execution.
Theorems 2–3Establish information limits without persistent memory and its necessity for recovering lost information under the stated conditions.
Propositions 1 and 3Guide what evidence to retain and when to restore it for correct local precondition recovery.

RECOVER operationalizes these theoretical findings through simple precondition-based retention and targeted Check-step insertion, explicitly designed to recover MAS decisions from information loss caused by error propagation. Controlled ablations validate these theory-guided design choices:

Memory RetentionInjection RuleACCToken per task
Self-verificationFact-basedEvery Step66.4179%127,090.11
Fact-basedCheck step70.8955%57,654.05
Precondition-basedEvery Step67.9104%113,740.66
Precondition-basedCheck step73.8806%56,196.66
RetrievalFact-basedEvery Step68.6567%71,676.47
Fact-basedCheck step75.3731%54,594.35
Precondition-basedEvery Step70.1493%73,145.73
Precondition-basedCheck step77.6119%52,974.98
RECOVERPrecondition-basedEvery Step89.044740373.447
RECOVERFact-basedCheck79.8507%51,276.35
RECOVER (Ours)Precondition-basedCheck91.542%38,405.709

These controlled comparisons isolate the contributions of RECOVER's theory-guided memory retention and insertion mechanisms.

Controlled AblationAccuracy Gain ↑Token Reduction ↓
Precondition-based vs. Fact-based retention+11.69 pp25.10%
Check-step vs. Every-step insertion+2.50 pp4.87%

These results demonstrate that the memory framework derived from our theoretical analysis improves task success and token efficiency through recovery-oriented evidence retention and insertion. Overall, our primary contribution lies in the theoretical understanding of error propagation and recoverability in MAS.

[1] G-Memory: Tracing Hierarchical Memory for Multi-Agent Systems, NeurIPS 2025.

[2] MetaGPT: Meta Programming for A Multi-Agent Collaborative Framework, ICLR 2024.

[3] ChatDev: Communicative Agents for Software Development, ACL 2024.

[4] HiAgent: Hierarchical Working Memory Management for Solving Long-Horizon Agent Tasks with Large Language Model, ACL 2025.

[5] ACON: Optimizing Context Compression for Long-horizon LLM Agents, ICML 2026.

[6] Voyager: An Open-Ended Embodied Agent with Large Language Models, TMLR 2024.

[7] MemoryBank: Enhancing Large Language Models with Long-Term Memory, AAAI 2024.

[8] Generative Agents: Interactive Simulacra of Human Behavior, UIST 2023.

[9] Intrinsic Memory Agents: Heterogeneous Multi-Agent LLM Systems through Structured Contextual Memory, arXiv

Comments on the paper

1 comment

Dear Area Chairs and Program Chairs,

Thank you for overseeing the review of our paper.

Our main contribution is a theoretical framework for decision recoverability in multi-agent systems (MAS), connecting micro–macro error propagation, information-theoretic recovery limits, and persistent memory requirements. We appreciate the reviewers’ comments and note that noreviewer‾\underline{\mathbf{no \\ reviewer}} has raised a correctness concern regarding our stated theorems. Motivated by derived theorems, we proposed an in-task memory framework for MAS, RECOVER, that retains memory only within each task. It outperforms both in-task and cross-task memory baselines, achieving higher accuracy with lower token cost.

Below, we clarify the theoretical contributions:

Theorem 1 and Proposition 2: Micro–macro closed-loop error propagation

  • Theoretical contribution. We establish a topology-aware propagation bound that couples micro-level semantic drift across agents with macro-level action discrepancies and environment feedback. The unified recursion explicitly characterizes how communication topology, interaction depth, and task horizon govern the propagation envelope. A Perron-aligned construction establishes attainability of the communication spectral growth rate within the comparison class.
  • Empirical validation. Figures 3-5 support micro–macro coupling and temporal error persistence. Empirical results also support the predicted communication factors across 64 graph–depth configurations. The calibrated action-to-state bound achieves 99.54% held-out coverage.

Theorem 2: Information-theoretic limits of endogenous recovery

  • Theoretical contribution. We formulate recovery as a statistical decision problem over a finite target set and establish a protocol-independent Bayes-error floor. The theorem shows that additional endogenous communication cannot reduce propagation-induced task error below the Bayes-error floor. Data processing and Fano’s inequality quantify an information barrier that additional communication and computation alone cannot overcome.
  • Empirical validation. Controlled perturbations (Fig. 4) show that extended interaction does not reliably eliminate the effects of an injected error across 7 MAS topologies. Benchmark comparisons: Across all 5 benchmarks, 3 MAS frameworks, and 5 LLM backbones, RECOVER consistently outperforms baselines that rely on endogenous communication over full interaction histories.

Theorem 3: Zero-error recovery with persistent memory in a distributed task

  • Theoretical contribution. We establish an exact recoverability separation on a distributed task with (RR) equiprobable targets: after complete transient information loss, endogenous interaction has random guessing error (1−1/R1-1/R). Matching achievability and lower bounds establish the necessity and sufficiency of persistent memory for exact recovery in MAS.
  • Empirical validation. Experiments across 5 benchmarks and 3 MAS frameworks support the effectiveness of recovery-guided memory. In the comparison with other memory methods, RECOVER achieves the largest reduction in per-step task errors and higher task accuracy.

During the rebuttal, we addressed the reviewers’ following main comments:

  • Connections between Theorem and RECOVER: theoretical results motivate RECOVER's design. Specifically, Theorems 1–3 motivate the need for the necessity of error recovery and persistent memory in MAS. The precondition-based recoverability criterion established in Proposition 3 guides what evidence RECOVER retains and when it injects memory.
  • Detail implementation and Empirical validation of RECOVER components: Both components use straightforward implementations without specialized architectures or additional training. Provided empirical support for the robustness of RECOVER's recovery mechanism under imperfect components’ outputs.
  • Empirical support for RECOVER's theoretically motivated design:
    • What to retain: Precondition-based evidence retention improves accuracy by 11.69 pp while reducing token usage by 25.10%.
    • When to inject: Selective memory injection improves accuracy by 2.50 pp while reducing token usage by 4.87%.
  • Comparison with retrieval and revision method: Across 12 different settings, the results consistently demonstrate RECOVER's advantages in both task success and token efficiency. Theoretically motivated components, What to retain and When to inject, consistently improve accuracy across retrieval and revision settings.

We have revised the manuscript and added implementation details and results of the additional rebuttal experiments to our anonymous GitHub repository.

Best regards,

The authors of paper 30882

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.