NexMem: Efficient Multi-Granular Conversational Memory using N-ary Link Scoring

Long-term conversational memory methods must preserve specific facts and connect experiences across sessions. Many existing approaches support this through costly, iterative memory refinement steps. We propose NexMem, which jointly extracts memory records and their indexing metadata in a single pass, without subsequent iterative refinements. Typed n-ary links, called nexus points, organize each memory at two granularities: broad aboutness links capture topical context, while fine-grained event-fact links capture entity–phrase associations. Retrieval first scores conventional memory, entity, and phrase graph nodes against the query, then propagates relevance between nexus points using personalized PageRank within a bounded local neighborhood. Across three long-term conversational-memory benchmarks, NexMem achieves the highest average accuracy among evaluated methods on each benchmark, including a 28-percentage-point advantage over the strongest evaluated baseline on the benchmark with the longest histories. On the benchmark where we profile construction cost, NexMem requires half as many LLM calls as the next-lowest profiled memory system and generates 5-10x fewer construction output tokens than the two strongest memory baselines.