Memory Compression for AI Agents: Reducing a 1M-Entry Knowledge Graph to 50K Entries

A Comprehensive Survey of Algorithms and Trade-offs (2024-2026)

---

1. Problem Framing

Compressing a 1M-node knowledge graph to 50K nodes represents a 20:1 reduction ratio. This sits in the well-explored range of graph reduction research (2x-40x), but the challenge is unique for AI agent memory because:

• Semantic fidelity matters more than structural fidelity (unlike GNN training)
• The graph is heterogeneous (entities, relations, attributes, temporal metadata)
• Compression must be incremental (agents accumulate knowledge over time)
• Retrieval quality is the ultimate metric, not spectral or cut preservation

The field has matured significantly in 2024-2026, converging on a multi-stage pipeline: entity resolution, community-based hierarchical abstraction, importance-weighted pruning, and information-theoretic validation.

---

2. Graph Summarization Algorithms

2.1 Graph Sparsification (Edge Reduction)

Sparsification removes edges while preserving graph properties. Applicable as a first-pass step before node-level compression.

Key algorithms (from the IJCAI 2024 survey by Hashemi et al.):

Algorithm	Preserves	Complexity	Mechanism
Spectral Sparsifiers (TRS)	Eigenvalues of Laplacian	O(m log^3 n)	Effective-resistance sampling; reweights retained edges
Spanners	Pairwise distances (stretch t)	O(n^{1+1/t}) edges	Greedy: adds edge only if it improves shortest paths
WIS (Razin 2023)	Node classification accuracy	O(m)	Walk-index scoring; removes low-importance edges
SparRL (Wickman 2022)	Task-specific performance	Learned	RL agent learns which edges to prune

Trade-off for KG compression: Sparsification alone cannot achieve 20:1 node reduction. It reduces edge count (often 2-10x) while keeping all nodes. It is best used as a preprocessing step to simplify the graph before node-level methods.

2.2 Graph Coarsening (Node Merging)

Coarsening merges nodes into super-nodes, directly reducing the node count. This is the most natural fit for 1M-to-50K reduction.

Key algorithms:

Algorithm	Strategy	Preserved Property	Applicable Scale
Local Variation (LV) (Loukas 2019)	Greedy pairwise contraction	Top-k eigenvalues (spectral guarantee)	Medium (100K)
Heavy Edge Matching	Merge endpoints of heaviest edges	Partitioning quality	Large (1M+)
Kron Reduction	Schur complement of Laplacian	Effective resistance	Medium
SNAP/k-SNAP (Tian 2008)	Attribute-based node grouping	Attribute homogeneity	Large (heterogeneous graphs)
GraSS (LeFevre & Terzi 2010)	Pairwise merging minimizing reconstruction error	Adjacency reconstruction	Medium
FGC (Kumar 2023)	Joint optimization of assignment + attributes	Structure + attributes	Medium
GOREN (Cai 2021)	GNN-learned edge weights in coarse graph	Laplacian spectrum	Medium

For KG compression specifically, SNAP/k-SNAP is highly relevant because knowledge graphs are heterogeneous (typed nodes and edges). SNAP groups nodes sharing attribute patterns into summary nodes with controlled resolution, directly producing a compressed representation. k-SNAP allows tuning the number of output groups, making it straightforward to target exactly 50K super-nodes.

Topology-aware coarsening (NeurIPS 2024) extends these methods for continual learning settings where the graph evolves over time, which matches the agent memory use case.

2.3 Graph Condensation (Synthetic Graph Generation)

Condensation synthesizes a small graph whose GNN training performance matches the original. Less directly applicable to KG memory but provides useful compression ratios as baselines.

State-of-the-art methods (2024-2025):

Method	Approach	Key Innovation
GCond (Jin 2022)	Gradient matching	Nested optimization; strong accuracy
DosCond (Jin 2022)	One-step gradient matching	10x faster than GCond
Bonsai (ICLR 2025)	Gradient-free; distribution matching	Architecture-independent; works with GAT, GCN, GraphSage
DisCo (Xiao 2024)	Disentangled node/edge condensation	10x faster than SotA; scales to 100M+ nodes
GEOM (Zhang 2024)	Lossless condensation	Zero performance loss on benchmarks
GCSR (KDD 2024)	Self-expressive structure reconstruction	Interpretable condensed structure

DisCo is particularly relevant: it achieves 10x speedup over prior methods and successfully scales to graphs with 100M+ nodes, making it viable for 1M-node KGs. Its disentangled approach (separate node and edge condensation) is conceptually aligned with KG structure where entities and relations have independent semantics.

---

3. Community Detection for Knowledge Pruning

Community detection is the backbone of hierarchical KG compression, pioneered at scale by Microsoft’s GraphRAG (2024).

3.1 The Leiden Algorithm

The Leiden algorithm (Traag et al., 2019) is the current standard for hierarchical community detection in KG compression:

• Complexity: O(L * |E|) where L is iteration count; effectively near-linear
• Guarantee: All discovered communities are guaranteed connected (unlike Louvain, which can produce disconnected communities)
• Hierarchy: Recursively merges communities into super-nodes, optimizing modularity at each level
• Parallelism: Fast Leiden (ACM 2024) provides shared-memory parallelization for large-scale graphs

3.2 Microsoft GraphRAG Pipeline (2024)

The seminal application of community detection to KG compression. The pipeline:

1. Extract entity-relation triples from source documents via LLM
2. Build a knowledge graph from extracted triples
3. Run Leiden to discover hierarchical community structure
4. Summarize each community using an LLM, producing a compressed textual representation
5. Index summaries at multiple hierarchy levels (root, intermediate, leaf)

Compression results: Up to 97% fewer tokens for root-level summaries compared to source documents. The hierarchical structure allows trading off compression vs. detail by selecting the summary level.

Key insight for 1M-to-50K: If the Leiden algorithm produces ~50K communities at an intermediate hierarchy level, each community summary becomes one node in the compressed graph. Inter-community edges are preserved as summary-level relations.

3.3 LightRAG (EMNLP 2025)

LightRAG achieves comparable accuracy to GraphRAG with 10x token reduction through:

• Dual-level indexing: Low-level entity-relation pairs + high-level thematic structures
• Deduplication function: Identifies and merges identical entities/relations across text segments, reducing graph size before community detection
• Knowledge units as first-class citizens: Relations are directly indexed (not inferred at query time)

3.4 Community-Based Compression Algorithm

Combining these approaches, a practical pipeline for 1M-to-50K compression:

Algorithm: Community-Hierarchical KG Compression Input: KG with N=1M nodes, target T=50K Output: Compressed KG with T nodes 1. ENTITY RESOLUTION - Embedding-based blocking (cosine similarity > threshold) - Merge duplicate entities (typically 10-30% reduction) - Result: ~700K-900K unique nodes 2. EDGE SPARSIFICATION - Compute edge importance (walk-index or effective resistance) - Remove bottom 50% edges by importance - Preserves connectivity; reduces computation for step 3 3. HIERARCHICAL COMMUNITY DETECTION - Run Leiden with resolution parameter tuned to yield ~T communities - Produces hierarchy: Level 0 (leaves) -> Level K (root) - Select level L where |communities| ≈ T 4. COMMUNITY SUMMARIZATION - For each community: generate summary node (entity types, key relations, representative facts) - Preserve inter-community edges as summary relations - Weight edges by number of cross-community connections 5. IMPORTANCE-WEIGHTED RETENTION - Within each community, retain top-k critical nodes based on PageRank, degree centrality, or semantic importance - Allocate retention budget proportional to community importance

---

4. Hierarchical Abstraction

4.1 Multi-Resolution Memory (2024-2026 Agent Architectures)

Several agent memory systems implement hierarchical abstraction natively:

HippoRAG (NeurIPS 2024): Neurobiologically inspired, uses LLM for entity extraction + Personalized PageRank for retrieval. Constructs a hippocampal index where entities connect to passages. Achieves 20% improvement on multi-hop QA while being 10-30x cheaper and 6-13x faster than iterative retrieval.

MAGMA (January 2026): Multi-graph architecture with four orthogonal views:
- Temporal graph: Strict chronological ordering
- Causal graph: Logical entailment inferred during consolidation
- Semantic graph: Conceptual similarity connections
- Entity graph: Object permanence across timeline segments

MAGMA’s dual-stream processing is particularly relevant:
- Fast path (synaptic ingestion): Non-blocking event segmentation, vector indexing, temporal backbone updates
- Slow path (structural consolidation): Asynchronous LLM-based inference of causal and entity links

Result: 95%+ token reduction (0.7K-4.2K tokens per query vs. 100K+ for full context), with 45.5% higher reasoning accuracy on long-context benchmarks.

A-Mem (NeurIPS 2025): Zettelkasten-inspired self-organizing memory. Each memory is an atomic note with keywords, tags, embeddings, and dynamic links. When new memories arrive, the system:
1. Constructs a structured note
2. Analyzes historical memories for relevant connections
3. Establishes links where semantic similarity exists
4. Triggers updates to existing memories’ representations

Result: 85-93% reduction in memory operation tokens, sub-10 microsecond retrieval latency for 1M notes.

4.2 MemOS: Memory Operating System (2025-2026)

MemOS introduces a three-tier memory hierarchy directly analogous to memory compression:

Memory Type	Representation	Compression Level	Use Case
Plaintext Memory	Raw text/structured data	None (highest fidelity)	Recent interactions
Activation Memory	Neural activations/embeddings	Medium (dimensionality reduction)	Working memory
Parameter Memory	Model weight updates	Maximum (absorbed into parameters)	Long-term knowledge

The MemCube abstraction enables transitions between levels: plaintext can be compressed into activation memory, and frequently accessed patterns can be further consolidated into parameter memory. This mirrors the 1M-to-50K problem: most entries transition to higher-compression representations, with only the most critical retained in full fidelity.

4.3 Hierarchical Abstraction Algorithm

Algorithm: Multi-Level Abstraction for KG Compression Input: KG nodes with metadata (frequency, recency, connectivity) Output: Three-tier compressed KG TIER 1 — FULL FIDELITY (5K nodes, 10% of budget) - Criteria: High PageRank AND recent access AND high query frequency - Full entity triples, attributes, provenance TIER 2 — COMMUNITY SUMMARIES (35K nodes, 70% of budget) - Leiden communities at intermediate resolution - Each summary: entity type distribution, key relations, representative facts, aggregate statistics - Inter-community edges with weights TIER 3 — ABSTRACT CONCEPTS (10K nodes, 20% of budget) - Root-level Leiden communities - Topic-level summaries (domain, theme, key actors) - Coarsest navigation structure

---

5. Information-Theoretic Approaches

5.1 Rate-Distortion Framework

Rate-distortion theory provides the theoretical foundation for optimal KG compression. The formalization (explored in recent work using Gromov-Wasserstein optimal transport):

• Rate R: Number of bits to represent the compressed graph (proportional to node count)
• Distortion D: Semantic distance between queries answered by original vs. compressed KG
• Goal: Minimize R subject to D < threshold, or minimize D subject to R = log(50K)

The distortion metric for KGs is typically semantic similarity preservation: how well the compressed graph maintains answer quality for downstream retrieval tasks.

5.2 Minimum Description Length (MDL)

MDL formalizes Occam’s razor for graph compression: the best compressed graph minimizes L(model) + L(data|model), where:
- L(model) = cost of describing the compressed graph structure
- L(data|model) = cost of describing the deviations from the compressed version

For KGs, this translates to: find the 50K-node summary that requires the fewest additional bits to reconstruct the original graph’s answers. Practical implementations use two-part MDL codes where the model is the community structure and the data given model is the within-community variation.

5.3 Information Bottleneck Method

The information bottleneck (Tishby et al.) provides a principled framework:

Minimize: I(G_original; G_compressed) - β * I(G_compressed; Answers)

Where:
- I(G_original; G_compressed) = mutual information between original and compressed (the “rate”)
- I(G_compressed; Answers) = mutual information between compressed graph and query answers (the “relevance”)
- β = Lagrange multiplier controlling the compression-relevance trade-off

At β → infinity, the compressed graph preserves all answer-relevant information. As β decreases, more aggressive compression is allowed.

5.4 Entropy-Based Importance Scoring

Mnemosyne (2025) implements a practical entropy-based approach for node importance:

Hybrid scoring function:

s_hybrid(n; θ) = θ_1 * s_connectivity(n) + θ_2 * s_boost(n) + θ_3 * s_recency(n) + θ_4 * s_entropy(n) where Σ θ_i = 1

Components:
- Connectivity: Normalized degree in the memory graph
- Boost: Count of reinforced edges (redundancy = importance signal)
- Recency: Exponential decay with λ=28-day half-life, reverse-sigmoid with 5% floor (memories never fully forgotten)
- Entropy/Information Density: Penalizes generic but well-connected nodes; rewards informationally dense nodes

Temporal decay formula: Uses effective age that accounts for boost events:

e_eff = t - t_init - Δ_boost(t)

where Δ_boost is a sigmoid function that “rewinds” age when a memory is reinforced.

5.5 MemoryBank: Ebbinghaus Forgetting Curves

MemoryBank (Zhong et al.) implements biologically-inspired forgetting:

• Memory strength decays following the Ebbinghaus curve: R(t) = e^{-t/S} where S is stability
• Each retrieval event reinforces the memory (increases S)
• Memories falling below a salience threshold are pruned
• This naturally implements a compression schedule: frequently-accessed memories persist, rarely-accessed ones decay

---

6. Integrated Pipeline: 1M to 50K

Synthesizing all four research threads, the optimal pipeline is:

Phase 1: Entity Resolution and Deduplication (1M -> ~750K)

• Algorithm: Embedding-based blocking + semantic similarity matching
• Scale guidance: For 1M entities, use DBSCAN or graph-based blocking (Zingg/splink frameworks)
• Expected reduction: 15-30% (LLM-extracted KGs contain substantial duplication)
• Complexity: O(n log n) with blocking

Phase 2: Edge Sparsification (~750K nodes, edges reduced 50-80%)

• Algorithm: Walk-index sparsification (WIS) or effective-resistance sampling
• Purpose: Reduces computation cost of Phase 3; removes noisy/low-confidence edges
• Preserves: Connectivity, shortest paths within factor of 2

Phase 3: Community Detection and Hierarchical Summarization (~750K -> 50K)

• Algorithm: Leiden with resolution parameter tuned for ~50K communities
• Summarization: LLM generates per-community summaries (key entities, relations, facts)
• Hierarchy: Retain 2-3 levels for multi-resolution retrieval
• Complexity: O(L * |E|), near-linear

Phase 4: Importance-Weighted Budget Allocation

• Within each community, allocate representation budget using hybrid scoring:
• PageRank centrality (structural importance)
• Recency with exponential decay (temporal relevance)
• Access frequency with boost (usage-driven)
• Entropy-based information density (avoid generic nodes)
• High-importance communities get more detailed summaries
• Low-importance communities get abstract one-line summaries

Phase 5: Incremental Maintenance

• New entries undergo fast-path ingestion (A-Mem / MAGMA style)
• Periodic slow-path consolidation re-runs community detection on changed subgraphs
• Ebbinghaus-style forgetting curves prune decayed entries
• Budget rebalancing ensures total stays at ~50K

---

7. Trade-off Analysis

Approach	Compression Ratio	Semantic Fidelity	Computational Cost	Incremental Update	Best For
Edge Sparsification Only	1:1 nodes, 2-10x edges	High	Low O(m log n)	Easy	Preprocessing
Coarsening (Heavy Edge Matching)	Up to 50:1	Medium	Low O(m)	Moderate	Homogeneous graphs
Coarsening (Spectral LV)	Up to 20:1	High (spectral)	High O(n^2)	Hard	Small-medium graphs
Leiden Communities + LLM Summary	Arbitrary (tunable)	High	Medium + LLM cost	Moderate	Heterogeneous KGs
Graph Condensation (DisCo)	Up to 100:1	Task-specific	High (training)	Hard	GNN-backed retrieval
Hybrid (Entity Resolution + Leiden + Importance Pruning)	20:1 achievable	Highest	Medium total	Moderate	Agent memory (recommended)

Critical trade-offs at 20:1 compression:

1. Semantic fidelity vs. compression: Community summarization preserves thematic structure but loses specific facts. Mitigation: retain full triples for top-5K highest-importance entities.

2. Recency bias vs. long-term knowledge: Forgetting curves naturally prune old knowledge. Mitigation: protect foundational facts from decay (mark as “crystallized” with infinite stability).

3. Incremental cost vs. quality: Full re-clustering is expensive but produces better communities than local updates. Mitigation: periodic full re-clustering (e.g., every 10K new entries) with incremental updates in between.

4. LLM cost for summarization: Summarizing 50K communities requires substantial LLM calls. Mitigation: use small models (Haiku-class) for summarization; only use large models for high-importance communities.

5. Information loss detection: No compression is lossless. Mitigation: maintain a “compression log” that records which original triples were absorbed into each summary, enabling on-demand decompression.

---

8. Key References and Resources

Surveys:
- A Comprehensive Survey on Graph Reduction: Sparsification, Coarsening, and Condensation (IJCAI 2024)
- Knowledge Distillation on Graphs: A Survey (ACM Computing Surveys 2025)
- Memory in the Age of AI Agents: A Survey (2025)
- Awesome Memory for Agents (Tsinghua C3I)
- Awesome Graph Reduction (IJCAI 2024)

Agent Memory Systems:
- MAGMA: Multi-Graph Agentic Memory Architecture (January 2026) – 95% token reduction, 45.5% higher reasoning accuracy
- A-Mem: Agentic Memory for LLM Agents (NeurIPS 2025) – Zettelkasten-inspired, 85-93% token reduction, sub-10μs retrieval at 1M scale
- HippoRAG: Neurobiologically Inspired Long-Term Memory (NeurIPS 2024) – PPR-based retrieval, 10-30x cheaper than iterative methods
- MemOS: A Memory OS for AI Systems (July 2025) – Three-tier memory hierarchy with MemCube abstraction
- Mem0: Production-Ready AI Agents with Scalable Long-Term Memory (2025) – Graph-enhanced memory with 26% accuracy boost

Graph RAG and Community Summarization:
- Microsoft GraphRAG: From Local to Global (2024) – Leiden-based hierarchical summarization, 97% token reduction at root level
- LightRAG: Simple and Fast RAG (EMNLP 2025) – 10x token reduction vs. GraphRAG
- Awesome GraphRAG

Memory Pruning and Forgetting:
- Mnemosyne: Unsupervised Long-Term Memory Architecture (2025) – Hybrid scoring with connectivity, frequency, recency, entropy
- MemoryBank: Enhancing LLMs with Long-Term Memory – Ebbinghaus forgetting curves
- ICLR 2026 MemAgents Workshop – Coordinated forgetting protocols

Graph Algorithms:
- From Louvain to Leiden – Guaranteed connected communities, O(L|E|) complexity
- Bonsai: Gradient-free Graph Condensation (ICLR 2025)
- DisCo: Disentangled Condensation for Large-scale Graphs (2024) – Scales to 100M+ nodes
- DynTKG: Dynamic Subgraph Pruning for Temporal KGs (2025)

Information-Theoretic:
- Rate-Distortion Guided Knowledge Graph Construction (2025) – Gromov-Wasserstein optimal transport for KG compression
- GraphMERT: Efficient Distillation of Reliable Knowledge Graphs (2025)

---

9. Summary of Recommendations

For a production system compressing 1M KG entries to 50K:

1. Use the hybrid pipeline (entity resolution + Leiden communities + importance-weighted retention). No single algorithm achieves 20:1 on heterogeneous KGs without unacceptable quality loss.

2. Adopt Leiden for community detection over Louvain. The connected-community guarantee prevents pathological summaries.

3. Implement three-tier retention (full fidelity for critical 5K, community summaries for 35K, abstract concepts for 10K). This mirrors both MemOS’s architecture and human memory consolidation.

4. Use Mnemosyne-style hybrid scoring for importance: connectivity + recency + frequency + information density. The entropy component is essential for avoiding the “hub bias” where well-connected but generic nodes crowd out informative ones.

5. Plan for incremental maintenance using MAGMA’s dual-stream approach: fast-path ingestion for real-time updates, slow-path consolidation for periodic re-clustering.

6. Budget LLM costs carefully: Community summarization at 50K scale requires ~50K LLM calls. Use small models for most summaries, reserving large models for the top ~500 highest-importance communities.