acceptodds
Under review as a conference paper at ICLR 2027

CoGMem: Communication-Budgeted Collaborative Graph Retrieval for Agent-Private Memory

Abstract

Multi-agent LLM systems are rapidly shifting from a single model to fleets of agents, where each agent maintains a private, graph-indexed long-term memory over a temporal knowledge corpus. When a question spans several agents, no single agent holds the complete answer and the team must retrieve it jointly, raising the problem of distributed multi-agent memory retrieval: producing a globally accurate answer without moving raw data off its partition and within a hard per-query communication budget. Existing paradigms each fail on one category: independent agents are trapped in information islands, centralized pooling violates partition privacy, and full communication wastes bandwidth. In this paper, we propose CoGMem (Collaborative Graph Memory), a collaborative graph neural network framework in which each agent encodes its private heterogeneous graph partition with a per-edge-type message-passing encoder. The encoder's confidence and relevance signals directly drive the communication protocol: a complementarity-aware gate and a budgeted top-K gossip decide what to send and how much. A multi-round negotiation extension (CoGMem-n, n for negotiation) then spends the remaining budget on measured information gaps via need-vector-triggered, ∆/cost-greedy follow-ups. Unlike prior work that treats retrieval and communication as separate layers, CoGMem couples the two end-to-end. On two knowledge-augmented memory benchmarks, CoGMem-n matches the High Communication ceiling's hit@1 at 38% of its bytes on Episodic Memory and exceeds every lexical and system-like distributed baseline by over 30 pp hit@1 (p<0.001). Causal ablations confirm that the learned GNN stack is load-bearing; on GTSQA, negotiation rescues hit@1 from 0 to 0.266 on the 20.9% hardest queries, delineating both the capability and the boundary of budgeted collaborative retrieval.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
communication, graph memory, large language model, multi-agent

Reviews

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

This paper proposes CoGMem, a framework for communication-budgeted retrieval across agent-private graph memories. It combines heterogeneous GNN retrieval, complementarity-aware gossip, self-vote-protected fusion, and gap-triggered multi-round negotiation. Experiments on GTSQA and Episodic Memory show strong improvements over lexical and system-like baselines. Notably, CoGMem-n matches high-communication hit@1 using only 38% of the bytes on Episodic Memory, although hit@10 decreases substantially.

Critical strengths
  1. Important problem and clear insight. Communication-efficient retrieval across private agent memories is a meaningful problem. Using retrieval relevance and information complementarity to guide communication is an intuitive and potentially useful idea.

  2. Strong empirical evidence for the learned retriever. The GNN ablations show substantial performance degradation when learned components are removed. The paper also reports accuracy–communication trade-offs and negative findings transparently.

Critical weaknesses
  1. Unclear communication assumptions and accounting. The complementarity gate requires knowing whether a candidate exists in the receiver's private graph, relying on cross-partition SAME_AS alignment. How this information is obtained without additional communication or shared knowledge is insufficiently explained. Moreover, Algorithm 1 describes receiver-specific pairwise exchanges, while the communication bound and byte accounting scale linearly with the number of agents. This directly affects the validity of the central communication-efficiency claim.

  2. Insufficient evidence for the proposed communication policy's independent contribution. Single-round CoGMem essentially matches High Communication at nearly identical byte costs. CoGMem-n preserves hit@1 with fewer bytes but substantially reduces hit@10, while removing targeted follow-ups leaves hit@1 unchanged. A simple budget-matched top-K truncation baseline using the same GNN and fusion is needed to establish whether complementarity-aware gossip and negotiation provide benefits beyond a strong retriever with candidate truncation.

Questions for authors
  1. How are receiver-specific inventories and SAME_AS bridges established and accessed? Does the reported byte accounting include all required cross-agent communication, particularly receiver-specific messages?

  2. How does CoGMem-n compare against simple relevance-based top-K truncation under the same byte budget, using the identical GNN encoder and fusion mechanism? This comparison would help establish the independent value of the proposed communication policy.

Reviewer_dAf7OpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper proposes a communication-budget-aware multi-agent memory framework consisting of four components: local GNN-based retrieval, budgeted gossip, cross-agent fusion, and negotiation. Experiments conducted on two benchmarks using two LLMs demonstrate the effectiveness of the proposed approach.

Critical strengths

The paper reports the mean and variance of experimental results across three random seeds, providing a more reliable assessment of the proposed method's performance.

Critical weaknesses
  1. Poor presentation and methodological clarity. The paper is difficult to follow, particularly in the methodology section. Several implementation-specific hyperparameter values are embedded directly into the method description, making it difficult to distinguish the general methodological framework from its particular experimental configuration. The authors should provide a more abstract and systematic description of the proposed approach.

  2. Insufficient evaluation to isolate the contributions of individual components. The current experimental design does not adequately establish the necessity or effectiveness of the proposed components. For example, on EpBench, an important missing baseline is a GNN-only retriever without inter-agent communication. Such a comparison would help determine whether the observed improvements stem from the GNN-based retrieval mechanism or the proposed communication framework.

  3. Insufficient justification for the trade-off between retrieval effectiveness and communication cost. The paper does not adequately justify whether the reduction in communication cost is worth the observed degradation in Hit@10. A more comprehensive cost-effectiveness analysis is needed to establish the practical benefits of this trade-off.

Questions for authors
  1. Is inter-agent communication a meaningful computational bottleneck in the target scenarios? Given that LLM autoregressive generation can dominate the overall computational cost of multi-agent systems, it is unclear whether reducing communication overhead translates into meaningful end-to-end efficiency improvements. Could the authors provide a breakdown of the computational costs associated with LLM inference, retrieval, and inter-agent communication?

  2. Could the authors provide a more comprehensive end-to-end evaluation? In particular, reporting end-to-end task performance, latency, and computational cost under different communication budgets would help establish whether the proposed framework offers practical benefits beyond reducing communication overhead.

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

The paper studies distributed retrieval over agent-private graph memories under a per-query communication budget. CoGMem uses frozen text embeddings and a contrastively trained, query-conditioned heterogeneous GNN to rank local candidates. Agents exchange compact summaries and selected candidate identifiers through a complementarity gate and a budgeted gossip mechanism. CoGMem-n adds need-vector-driven gap assessment, targeted BFS follow-ups, and a marginal-utility-per-byte selection heuristic. The evaluation covers GTSQA with 1,622 test questions and Episodic Memory with 407 questions, primarily using three agents and reporting three-seed averages. Under the reported accounting, CoGMem-n matches High Communication’s Episodic hit@1 of 0.419 while reducing average communication from 13,740 to 5,267 bytes/query. This operating point trades away broader retrieval quality: hit@10 falls from 0.846 to 0.649 and MRR from 0.559 to 0.511. The paper also presents component ablations, partition and budget sensitivity analyses, and claimed guarantees for communication complexity, negotiation quality, and top-1 preservation.

Critical strengths
  1. The research problem is practically relevant, and the paper presents a concrete trade-off between communication cost and accuracy.

  2. The ablation studies are informative, support the role of the graph retriever in this setting, and candidly report failure cases.

Critical weaknesses

I believe the authors may need to further improve the experimental setup and supplement the current experiments. For example, adding the following experiments might better support the paper's central claims:

  1. The substantial improvements over BM25 and various "-like" system proxy implementations conflate differences in learned retrieval, training supervision, fusion methods, and communication overhead. These comparisons demonstrate the performance of the complete system under the authors' experimental setup, but they do not isolate the contribution of the new communication strategy.

  2. The authors do not appear to have compared single-round CoGMem and High Communication on the same subset. Therefore, it seems difficult to establish the gains attributable specifically to the negotiation mechanism.

Questions for authors

I appreciate the authors' work. It would be helpful if the authors could clarify the following questions.

  1. What are the actual communication topology, message recipients, serialized payload fields, and global budget-reservation mechanism? Could the authors reconcile Equation (1), Theorem 4.1, Algorithm 1, the candidate-count limit, and the 13,737-byte figure in Table 2, and report the maximum per-query communication volume and any budget violations? Where does fusion take place? How can the zero-communication Partition BM25, as described in the caption of Table 1, fuse the same local lists as All-Peer BM25?

  2. With the encoder, candidate generation procedure, and fusion mechanism held fixed, how do fixed top-k truncation, generic follow-ups, and need-directed follow-ups compare under the same total byte budget? On the same hard subset defined by the global GNN, what are the paired results for single-round CoGMem, CoGMem-n, and the no-BFS control?

  3. What exactly is being ranked? For questions requiring multiple answer entities or multiple edges, how exactly are hit@k and MRR computed? How does this metric definition explain the case in Figure 1 where an agent retrieves one of the three correct protagonists but still has hit@1 = 0? Please also clarify the specific definitions of the training, validation, and test splits, negative sampling, model fitting, and the coverage function.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.