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

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.