acceptodds
Under review as a conference paper at ICLR 2027

Commutative Merge Does Not Ensure Order-Invariant Agent Memory

Abstract

An associative, commutative, and idempotent merge guarantees order-independent combination of fixed artifacts. In language-model memory, however, the artifacts are generated from batches of observations, and arrival order can change those batches. We test the gap between these two operations. In a controlled 4B study, all 300 world–arm cells produce multiple states under free arrival schedules; the same 300 cells produce a single state when extracted sub-batches are held fixed and only their processing order changes. The control localizes variability before fixed-artifact merging; the relative contributions of changed context and generation remain unresolved. A deterministic counterexample explains why merge algebra alone is insufficient, and canonical replacement gives agreement under fixed extraction outputs without requiring event-wise decomposition. We then measure what agreement establishes about utility. Historical design effects vary across scales and substrates. With atoms fixed, grouping and latest-value cues have positive interactions of 12.87 and 11.11 percentage points under two instructions, both surviving six-test Holm correction under the stated sign-flip reference assumption. In a 12-world online comparison, per-event extraction agrees across the evaluated arrival orders at 23.86% of canonical trie's summed request time, while trie's question-level gains and losses are mixed. Order-invariant merging leaves the production of its inputs outside its guarantee; answer quality and construction cost remain separate empirical outcomes.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Agent memory, extraction, order invariance, temporal readout, reproducibility, inference cost

Reviews

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

The paper studies how arrival order can change extraction batches and produce different agent memories, even when merging is commutative. The paper proposes canonical replacement to form batches consistently and replace outdated outputs, with agreement conditional on repeatable extraction.

Critical strengths

Making agent memory consistent across different arrival orders is a research problem with some practical value.

Critical weaknesses
  1. The significance of the problem is underdeveloped. Changing the inputs to an extractor can change its outputs. This observation is straightforward, and the paper provides limited evidence of how often it causes meaningful failures in existing memory systems.

  2. The advantage of canonical replacement is unclear. Its guarantee still depends on repeatable extraction or shared outputs. Hash-based batches can group unrelated observations, and their benefit for memory quality is weakly demonstrated. In the small online study, canonical trie takes 4.19 times the request time of per-event extraction for a 2.74-point accuracy gain, with mixed results across questions.

  3. The writing is repetitive and difficult to follow. The paper repeatedly explains what its results do not establish, while the main contribution remains diffuse. Similar terminology for different renderers, partitions, and construction policies also makes the pipeline unnecessarily confusing.

  4. The experimental narrative is fragmented. Shared-artifact replay, fixed-atom readout, and fresh online construction test different questions, but the paper does not clearly explain how their findings fit together. In particular, the controlled readout experiment evaluates a presentation scheme that is not used in the online construction study, leaving its connection to canonical replacement unclear.

  5. The distinction between consistency and usefulness offers limited insight. Consistent memory does not necessarily produce better answers, since accuracy also depends on extraction quality, retrieval, presentation, and reader behavior. Mixed accuracy results are therefore unsurprising. The paper provides limited explanation of when enforcing consistency improves task performance or when contextual extraction is worth its additional cost.

Questions for authors

No questions for the authors.

1 comment
AuthorsOpenReview ↗

Response to Reviewer ndZn

Thank you. We take your points in order.

W1 (significance). We agree that "different extractor inputs give different outputs" is straightforward, and the revision keeps it only as the diagnosis (contribution (a), §3). It adds a measurement of how often this changes answers in an existing library, Mem0 2.2.1 driven by a local 4-bit Qwen3-8B, on all 10 LoCoMo conversations (§4).

  • With deterministic decoding (an exploratory regime), same-order ingestions are byte-identical. Yet batch-boundary changes flip 20.4% of answers, redelivering one turn per session 16.9%, and a session arriving last 11.1%, each in 10 of 10 conversations.
  • At default sampling, same-order re-ingestion already flips 17.5%. Batch-boundary changes add 2.2–4.6 points, and redelivery and late arrival add nothing measurable above that floor.

Most of the questions that flip already flip between default re-ingestions, so the deterministic rates show fragility, not an arrival-specific excess (§8). Because mean accuracy barely moves, §8 argues that flip rates should be reported next to accuracy.

W2 (value of canonical replacement; repeatable extraction). Our new results agree with your concern about the construction. Hash-keyed batches answer 0.292 of correction questions, against 0.875 for one joint call, and retain 0.312 of the corrections bound to their subject, against 1.000 (§5; Table 18 in App. K.1). In the re-run cost study, the trie shows no measurable accuracy gain over per-event extraction (+0.8 points [−4.7, 6.3]) at 4.11× the extraction tokens (§6). The paper now presents canonical replacement only as the sufficient condition when joint context is needed (Proposition 2, §3.1). It states that a grouping key aligned with the dependency is untested.

You also note that the guarantee depends on repeatable extraction. The revision measures this directly. Extraction outputs were not repeatable by default in batched HuggingFace inference or in llama.cpp with prompt caching (§4, §6). A deterministic configuration made same-order Mem0 ingestions byte-identical in all 10 conversations, and a rebuilt stack reproduced the saved fingerprints of 21 of 21 earlier runs. Repeatability is achievable but must be configured, and §8 says so.

W3–W4 (writing; how the experiments fit). Limitations are collected in the Scope paragraphs of §8. Table 1 gives each experiment one question and marks the exploratory ones, and §8 opens with a paragraph on how the four studies fit. The readout factorial moved to App. F. The online construction study uses one common readout for every construction (§6).

W5 (consistency vs usefulness). We agree that consistency does not imply better answers. §5 quantifies what identity obtained by per-event extraction loses and what joint extraction recovers. For Mem0 we have only one indication of the cost of identity, and it is weak: one conversation (81 questions), no interval, and two factors changed at once. There, context-free one-turn extraction answered 0.395 of questions, against 0.506 with the default context (§4; App. K.3).

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

The paper studies how arrival order and batching affect the memory extracted by an LLM. It shows that order-independent merging alone does not ensure identical final memories, and proposes fixed grouping and replacement rules to obtain consistency under fixed extraction outputs. Experiments on synthetic and adapted factual datasets measure memory consistency, answer accuracy, and construction cost.

Critical strengths
  1. The experiment with fixed facts provides a useful control for studying how memory presentation affects answers. Including per-event extraction as a simple baseline also helps assess whether contextual extraction justifies its additional cost.

  2. The authors do not oversell their methods or hide unfavorable outcomes; they openly report that semantic normalization hurts accuracy on revision-derived data, that their proposed Canonical Trie costs over 4x the request time of simple per-event extraction for only a ~2.7% accuracy bump (with gains and losses canceling out 8-to-8 on supersession questions), and transparently log their interrupted runs and truncation failures.

Critical weaknesses
  1. The need for order-invariant agent memory is not well motivated. Why must different arrival orders produce identical memories, rather than preserve the same relevant information and support correct answers?

  2. The most critical concern is that memory construction depends heavily on the prompts and agent harness. Systems may retain complete source information while organizing it at different levels of granularity. The experiments cover the authors’ prototype memory designs and small factual datasets, leaving it unclear whether the observed order sensitivity is a significant problem beyond these setups.

  3. There are lots of studies and systems of agent memory, but the paper does not discuss them and explore and prove its "claims" on these systems and more powerful models, e.g. GPT series models.

  4. The paper writing is hard to understand and reads like an internal debugging log. The text immediately throws around undefined internal jargon ("world-arm cells," "substrates," "SEMA-FLAT," "supersession probe") without properly defining the task setup or showing a single concrete example of what an observation stream or extracted memory atom actually looks like. Please rewrite your paper.

  5. The narrative is completely fragmented. While the title and intro focus on commutative merges and arrival-order invariance, Section 2.1 turns into debugging a retrieval-window truncation bug in semantic normalization, and Section 4 switches to a prompt-formatting ablation (slot grouping vs. latest cues) with fixed memory atoms.

  6. There are too many incomplete and crashed experiments. For example, the online comparison in Section 5 is limited to just 12 tiny worlds because a larger run was interrupted mid-execution with length failures, which is admitted by the authors.

Questions for authors

See the above weaknesses。

2 comments
AuthorsOpenReview ↗

Response to Reviewer x9Zv

Thank you. We agree with the presentation criticism and have rewritten the paper around one measured example (Figure 1) and four questions (Table 1).

W1 (why identical memories). §1 now separates snapshot identity from answer stability, and the paper measures both. Identity is needed only where memory states are compared or replayed (retries, replica synchronisation, per-question reproducibility); where memory is used only through answers, answer stability is enough. Your distinction between identity and information also shows up in the data. In Mem0 with deterministic decoding, the gold answer's tokens disappear from the memory for only 6.1%, 4.4% and 2.5% of questions (batch-boundary change, redelivery, late session), against 20.4%, 16.9% and 11.1% answer flips. By this token-containment proxy, most flips come from changed wording, retrieval or reading rather than from answer tokens missing from the store (§4). In the controlled study (§5), identity obtained by per-event extraction does lose facts: it retains none of the corrections bound to their subject and answers 0.021 of correction questions, against all corrections retained and 0.875 answered for one joint extraction call (Table 4; App. K.1).

W2–W3 (beyond our prototypes; other systems and models).

  • The revision adds Mem0 2.2.1, running with its own extraction, deduplication and retrieval code, on all 10 LoCoMo conversations (§4). The harness only writes session dates into the message text and pins the prompt's date; the context-channel ablation also blanks prompt sections (App. K.3).
  • At default sampling, same-order re-ingestion flips 17.5% [16.9, 18.1] of answers, against 0.73% for the reader alone.
  • With deterministic decoding (an exploratory regime), same-order ingestions are byte-identical, while batch-boundary changes, redelivery and a late session flip 20.4%, 16.9% and 11.1% (10 of 10 conversations each).
  • You were right that the harness matters. With the server's prompt cache on, even temperature-0 ingestions diverged. We report this as a dependence on the serving stack (§4).
  • The Mem0 runs use a local 4-bit Qwen3-8B on llama.cpp; the dependency study and the online re-run use HuggingFace transformers, and the submitted runs used vLLM. Mem0's default model (gpt-5-mini) and other GPT-class models were not run, and §8 states this limit.

W4–W5 (jargon, fragmentation; a concrete example). For the concrete example you asked for, Figure 1 quotes two observations from a measured scenario, and §2 quotes one evidence line and the memory atom extracted from it, taken from the request records of the submitted online run. Internal names are replaced in the main text, with a mapping in App. A. The design-dependence matrix is in App. C, the readout factorial in App. F, and the semantic-normalization mechanism in App. J.3. The main text keeps only pointers to them.

W6 (incomplete runs). The interrupted larger online run is documented in the audit appendix (App. J). During the discussion period we re-ran the online comparison on the same 12 scenarios as an exploratory reconstruction (App. K.2); it does not confirm the submitted trie gain, and we report that. The deterministic Mem0 study now covers all 10 conversations. We also report a loss: the raw per-run files of the default-sampling Mem0 runs and of the earlier 2 × 2 runs were lost when the workspace was wiped. Those results come from saved derived tables, and the deterministic runs used a rebuilt stack that first reproduced the saved fingerprints (memory count, accuracy, mean F1, judge accuracy) of 21 of 21 earlier runs (App. K.3). The context-channel ablation covers three conversations, and the context-free control one. Table 1 marks the exploratory studies, and §8 lists what was not run.

Thanks for adding the Mem0 experiment. It addresses my concern that the original results were limited to the authors’ prototypes. The effect of arrival order is still only clear in one deterministic setup, and the rerun did not confirm the trie’s accuracy gain. I’ve raised my score to 2.

Reviewer_8yYyOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

Agents often maintain memory over long-running sessions where information arrives incrementally. This paper asks whether the resulting memory remains the same across different observation arrival orders. It shows that associative, commutative, and idempotent merging alone is insufficient: arrival order can change extraction batches and therefore the artifacts being merged. The paper proposes selecting extraction contexts from the observed event set and replacing outdated artifacts as that set grows. Independent per-event extraction provides a simple order-invariant baseline under fixed-extractor assumptions. The contextual approaches aim to preserve joint extraction across observations while retaining invariance. A capacity-bounded digest trie limits logical extraction work per insertion. The experiments examine memory-state agreement, answer accuracy, and cost. They show that agreement across arrival orders does not necessarily yield better answers or lower cost.

Critical strengths
  • A clear diagnosis of the merge problem. ACI merging guarantees agreement for fixed inputs, as in state-based CRDTs [A] and deterministic memory merge [B]. The paper shows why this guarantee does not extend to extraction from arrival-dependent batches.

References

  • [A] Efficient State-based CRDTs by Delta-Mutation, Arxiv 2014
  • [B] StateFuse: Deterministic Conflict-Preserving Memory for Multi-Agent Systems, Arxiv 2026
Critical weaknesses
  • Key terminology is explained too late. World-arm cell is used before Table 1 defines it as a scenario-method pair within a model run. The 30-cell design instead counts five design contrasts across three model sizes and two data sources. These different counting units should be explained at first use.
  • The merge framework needs clearer explanation. The main text describes ACI properties and gives a set union example, but leaves the join semilattice formalization to Appendix A. The merge operation, its laws, and their connection to the formal results should be explained earlier.
  • The practical need for snapshot invariance is not established. The introduction motivates order invariance through delayed observations, retries, and checkpoint recovery. However, it does not convincingly establish when identical memory snapshots are operationally necessary or worth the additional cost. ACI provides convergence for fixed inputs, not semantic correctness of independently generated artifacts.
  • The formal contribution appears limited. The authors describe the partition condition as an elementary join-preservation result, rather than a new CRDT theorem. Such a result can still be useful, but the paper needs to establish what substantial new insight or design guidance follows from it.
  • The proposed remedy combines standard ideas. Canonical inputs, replacement of outdated outputs, and bounded hash-based partitioning provide a concrete construction. However, its novelty and practical importance relative to simple independent extraction remain insufficiently established.
  • The empirical payoff is weak. The trie achieves 38.89% accuracy, compared with 36.15% for independent extraction, at 4.19 times the summed request time. These world-equal averages show little practical gain for the additional complexity. The contextual-memory evaluation on native long histories also remains unfinished.
  • The reader-side analysis needs stronger positioning against prior work. Chain-of-Agents [A] already compares natural, reversed, and random processing orders. Chow-Liu Ordering [B] constructs an evidence-processing order for sequential memory updates. Neither is cited. These works do not subsume the extraction-invariance result, but they limit the novelty of the broader observation that processing order affects answer quality.

References

  • [A] Chain of Agents: Large Language Models Collaborating on Long-Context Tasks, NeurIPS 2024
  • [B] Chow-Liu Ordering for Long-Context Reasoning in Chain-of-Agents, ICLR 2026
Questions for authors
  1. Why study ACI?: Could you clarify why ACI merging is an important design choice for agent memory, identify existing systems whose guarantees motivate this analysis, and demonstrate a practical consequence of arrival-dependent extraction? In particular, is the paper correcting an existing pipeline-level invariance claim, or proposing a stronger requirement than those systems intended to provide?
  2. Practical motivation: In which agent applications is identical memory across arrival orders necessary, beyond reproducible execution? What concrete failure does snapshot invariance prevent?
  3. Value over independent extraction: When does joint extraction context preserve useful information that per-event extraction misses? Can you demonstrate this with controlled cross-batch dependencies and directly check which required facts each method retains?
  4. Accuracy/cost trade-off: Given the small accuracy gain and substantially higher request time, when should a practitioner choose the canonical trie over independent extraction? Can you compare them under matched cost or quality budgets?
  5. Contribution beyond existing ideas: What is the principal new insight beyond the elementary join-preservation condition and the combination of canonical inputs, replacement, and hash-based partitioning? How does the reader-side analysis relate to Chain-of-Agents and Chow-Liu Ordering?
  6. Presentation: Could you define merge algebra, world–arm cell, and 30-cell design at first use, and provide an overview separating the formal guarantees, replay checks, fresh inference, and answer-quality experiments?
1 comment
AuthorsOpenReview ↗

Response to Reviewer 8yYy

Thank you for the detailed questions. We answer them in order.

Q1/Q2 and W3 (why ACI; which failure). We are not correcting an invariance claim made by a deployed system; §1 states that we do not claim any system promises snapshot identity. We study the property itself. Mem0 2.2.1's memory-text store grows by a union of extracted texts, but its extraction context depends on what arrived before (§4).

  • With deterministic decoding (an exploratory regime; Mem0 driven by a local 4-bit Qwen3-8B), same-order ingestions are byte-identical in all 10 LoCoMo conversations. Yet batch-boundary changes flip 20.4% of answers, redelivering one turn per session 16.9%, and a session arriving last 11.1% (each in 10 of 10 conversations).
  • At Mem0's default sampling, same-order re-ingestion already flips 17.5%. Batch-boundary changes add 2.2–4.6 points, while redelivery and late arrival add nothing measurable above that floor.

We have not shown an application-level failure. What we measured is that individual answers change under batch-boundary changes, redelivery of one turn per session and late arrival, while the benchmark score does not reveal it. Most of the questions that flip already flip between default re-ingestions, so these rates show fragility, not an arrival-specific excess (§8).

Q3 (what joint context preserves). This is now §5 (Table 4, with fact-level retention in App. K.1). In controlled scenarios with cross-observation dependencies (16 scenarios; Qwen3-8B shown), per-event extraction answers 0.021 of correction questions and retains none of the corrections bound to their subject; one joint extraction call answers 0.875 and retains all of them (Table 4; Table 18 in App. K.1). Per-event extraction buys identity by losing context-dependent facts.

Q4 and W6 (trie vs per-event; matched cost; native histories).

  • We re-ran the online comparison as a leaf-capacity sweep (§6, Figure 3c). The trie differs from per-event extraction by +0.8 points [−4.7, 6.3] (16 questions improved, 12 worsened) at 4.11× the extraction tokens.
  • The planned matched-budget arms were not run, and the paper says so.
  • The submission's +2.74-point gain was not statistically resolved (p = 0.49) and the re-run does not confirm it, so there is currently no accuracy-based reason to choose the trie.
  • The hash-keyed trie answers 0.292 of correction questions and retains 0.312 of the corrections bound to their subject, because hashing groups dependent observations only by chance. A dependency-aligned grouping key is untested; time-sorted rebatching (0.729 on corrections) is the closest tested proxy, and it gives identity only if every shifted batch is re-extracted (§8, App. B).

You also noted that the evaluation on native long histories was unfinished. It remains unfinished: App. G reports the partial raw-retrieval baseline and App. J.5 the construction failures. The revised main text no longer draws on it. The Mem0 study on full-length LoCoMo conversations (§4) measures a library on long conversations; it does not evaluate our constructions there.

Q5 and W4–W5 (contribution). We agree that the join-preservation condition is classical. The paper now presents it that way: Proposition 1 is stated informally in §2 and Proposition 2 in §3.1; both are stated formally and proved in App. B. The contribution we claim is the measurement: where order sensitivity enters a memory pipeline, how often it changes answers in an open-source library, and what restoring identity costs. Chain-of-Agents and Chow–Liu Ordering study the order in which a reader consumes evidence. Our question is the order in which memory is written. §7 now cites both and draws this distinction.

Q6, W1–W2 (presentation). §2 defines the merge and its laws, scenario, design and (scenario, design) pair before the experiments (§3–§6). Table 1 separates the replay check, the library measurement, the dependency study and the cost study.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response and summary of revisions

We thank the three reviewers for careful reviews. All three found the submission difficult to follow, and we agree. It used internal vocabulary before defining it, gave no concrete example, did not say why order-invariant memory matters, and did not show that the problem arises in a system people use. These are faults of the paper. We have uploaded a substantially revised PDF and list the changes below, so that reviewers can judge how much of it to consider. Table 1 marks the exploratory studies, whose scope or analysis was set after earlier results were known.

Presentation.

  • §1 opens with a measured example (Figure 1). An erratum names only the memo it corrects. In this scenario, when memo and erratum are extracted in the same call, the correction is bound and the answer is right; when they fall in different calls, it is not.
  • §2 defines the units, the merge and its laws before the experiments (§3–§6); a flip is defined in the §4 protocol. Internal labels are replaced in the main text; Appendix A maps old names to new ones.
  • Table 1 maps each question to its experiment. Limitations are collected in the Scope paragraphs of §8. Execution and analysis irregularities are in a labelled audit appendix (App. J) and, for the Mem0 study, in App. K.3, kept complete.

Motivation. §1 separates snapshot identity, which idempotent retries, replica synchronisation and reproducible evaluation need, from the weaker requirement that answers stay the same. The paper measures both.

New evidence.

  1. An open-source memory library (§4, Table 3, Figure 2). Mem0 2.2.1 runs with its own extraction, deduplication and retrieval code, here driven by a local 4-bit Qwen3-8B, on all 10 LoCoMo conversations (1,540 questions).
    • Default sampling. Same-order re-ingestion already changes the correctness of 17.5% [16.9, 18.1] of answers, against 0.73% when only the reader is re-run. Batch-boundary changes add 2.2–4.6 points (Table 3). Redelivery and late arrival add nothing measurable above that floor.
    • Deterministic decoding (exploratory: set up after the default-sampling results). Same-order ingestions are byte-identical in all 10 conversations. Yet batch-boundary changes flip 20.4% [18.5, 22.4] of answers, redelivering one turn per session 16.9% [15.5, 18.5], and a session arriving last 11.1% [8.8, 13.4]. Each is positive in 10 of 10 conversations.
    • Fragile answers. These flips concentrate on fragile questions: 68–77% of the questions flipped under deterministic decoding are among the 38.7% of questions that already flip between default re-ingestions. Arrival-neutral noise flips a similar share (sampling: 17.5%), so these rates show fragility, not an arrival-specific excess. Mean accuracy hardly moves, so the benchmark score hides the change.
  2. What joint context buys (§5, Table 4). We ran 16 controlled scenarios on Qwen3-4B and Qwen3-8B; positional batching used 15 arrival paths. Qwen3-8B accuracy on correction questions, where the erratum names only an earlier memo:
    • per-event extraction: 0.021;
    • one joint extraction call: 0.875;
    • a hash-keyed contextual construction: 0.292;
    • a time-sorted raw log read whole: 0.917.
  3. Cost (§6). A re-run of the online comparison gives the canonical trie +0.8 points [−4.7, 6.3] over per-event extraction at 4.11× the extraction tokens. The submission's +2.74-point gain was not statistically resolved (19 questions improved, 14 worsened; p = 0.49), and the re-run, on a different engine and prompts, does not confirm it. The paper no longer claims the gain. The planned matched-budget arms were not run.

Supplement. The revised supplement adds a discussion_period/ folder with the Mem0 scripts, result tables and the 110 deterministic per-run records, the dependency study and the leaf-capacity re-run. The per-run files of the default-sampling runs and of the earlier 2 × 2 runs were lost; those results come from saved derived tables (App. K.3). The recorded atom example in §2 comes from the submitted online-run request records.

Related work (§7). We added reader-side processing-order work (Chain-of-Agents; Chow–Liu Ordering), distinguished from the write-side question we study. We also added Mem0, MemGPT/Letta, A-Mem, LangMem, LoCoMo and Generative Agents.

A request. This revision is large, and we do not assume that reviewers can read all of it. If time allows only one thing, we would be most grateful for a short note on what you would change first.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.