Enhancing Local and Global Structure in Compressed AI Agent Memory: The Two Maps of Memory Compression
> Paper: Enhancing Local and Global Structure in Compressed AI Agent Memory > arXiv: 2611.08341 | Author: Henry Han / Baylor University > Published: 2026-11-05
---
🗺️ The Two Maps Metaphor
Imagine moving from a city where you lived for five years. While packing, you only care about one thing: can the people closest to me live in the same neighborhood? Months later, you discover a problem. A dinner with a friend that used to take five minutes on foot now takes forty minutes by bus—not because the distance between you changed, but because you moved the hospital to the other side of town. You preserved who lives next to whom, but the overall shape of the city map was destroyed.
This is the core problem facing AI agent memory compression. Current methods only care about "nearest neighbors"—whether each memory's closest neighbors remain its closest neighbors after compression. Vendors proudly claim "our binary embeddings retain 97-98% retrieval accuracy." But they ignore a fact: agents don't just retrieve memories—they consolidate, delete, compare, and categorize them, and these operations depend not on "who is near whom" but on "what is far from what across the entire memory space."
🧠 The Agent Memory Problem
LLM agents—scheduling assistants, research automators—accumulate memories that can reach millions of entries, each stored as an embedding vector (a point in high-dimensional space). At million scale, storage becomes costly: hundreds to thousands of dimensions per vector, several bytes per dimension—potentially gigabytes per million memories.
Common compression methods:
- Truncation: keep only the first few dimensions (Matryoshka embeddings are designed for this)
- Scalar quantization: map each float dimension to an 8-bit integer
- Binary codes: turn each dimension into one bit (+1/-1)
- Product quantization (PQ): split vectors into subspaces, each represented by the nearest codeword in a small codebook
- Retrieval: find relevant memories given a query. Depends only on local structure.
- Consolidation: group memories by topic. Requires comparing each memory against all other memories—global distances.
- Deletion: e.g., "delete all memories about client X." Requires that client X's memories form a coherent cluster; compressed cross-contamination causes either data leakage or wrongful deletion.
- Mapping: e.g., "draw relationships between companies and industries." Requires global distance structure.
- No labels needed—critical for private agent memories with no "ground truth"
- Only the codebook is trained—drop-in replacement for any existing OPQ index, near-zero deployment cost
- Theoretical guarantee: Proposition 5 shows the far-end hinge has no first-order effect on reconstruction error—L and G can improve simultaneously
- Reconstruction only: G improved in 0 of 52 runs
- Near-end hinge only: average G gain of 0.0058—weak
- Far-end hinge only: G improved in 52 of 52 runs, average gain 0.0127
- Retrieval correlates with L (0.83-0.99), not significantly with G
- Consolidation and deletion correlate with G (0.55-0.93), not with L
- Mapping also correlates with G
- Han, H. (2026). Enhancing Local and Global Structure in Compressed AI Agent Memory. *arXiv:2611.08341*.
- Jégou, H., Douze, M., & Schmid, C. (2011). Product Quantization for Nearest Neighbor Search. *TPAMI*.
- Ge, T., et al. (2013). Optimized Product Quantization for Approximate Nearest Neighbor Search. *CVPR*.
- van der Maaten, L., & Hinton, G. (2008). Visualizing Data Using t-SNE. *JMLR*.
- Sarabadani, A., et al. (2024). Matryoshka Embedding and Truncation. *arXiv*.
- Han, H. (2024). Degree of Locality Preservation: A Measure for Embedding Quality. *Prior work*.
All are evaluated by neighbor retention (recall@10)—does each memory's nearest-neighbor list survive compression?
But real agent memory systems perform at least four kinds of operations:
A concrete scenario: an assistant tracking a VC manager's portfolio (2000 memories about company earnings calls, product launches, regulatory news). When asked to summarize all fintech memories by sub-topic (payments, lending, blockchain, insurtech), a compression that preserves only local structure may push a "blockchain payments" memory into the "traditional banking" cluster—producing a content error even though every memory's nearest neighbors are correct. Similarly, "delete all memories of company C" can leak entries compressed into company D's cluster.
This is why G is not a nice-to-have metric—it is the correctness floor for certain agent operations.
📉 The Blind Spot: Two Metrics
The author introduces two metrics:
Local fidelity L
L = ν_10, the chance-corrected locality profile at scale k=10: after compression, are each memory's 10 nearest neighbors still the same 10? Ranges from 0 (random) to 1 (perfect). Essentially a corrected recall@10—the industry standard.
Global fidelity G
G asks whether near/far relations are preserved at larger scales—e.g., within each memory's 30%-50% distance range. At k=N/2, G becomes a rank correlation over all distance orderings. It captures whether topics, companies, and time periods remain correctly separated.
The Surprising Finding: High L ≠ High G
On FinQA with 96-byte rescored binary codes: L = 0.97—near-perfect retrieval. But 10.1% of memories were moved to a different topic. Meanwhile PCA + 8-bit scalar quantization, with a much lower L = 0.77, moved only 1.7% of memories across topics.
High L guarantees an accurate contact list, not a correct city map. Across methods at equal byte budgets, L may differ by only a few points while G differs by up to 0.30—yet current evaluation ignores G entirely.
📐 The Mathematical Guarantee
Theorem 1 (Rank-Violation Bound): for any compression and scale k,
where N = n−1 and p̄_k is the cross-pair violation rate. A memory loses fidelity at scale k exactly when many cross pairs (a near point p and a far point q whose order flips after compression) are inverted.
The key insight is the coefficient N/√(k(N-k)): at k=10 it is ~√(N/10) (≈14 for 2000 memories), but in G's reading range (k/n between 30%-50%) it is only 2 to 2.18—an extremely tight bound. At far scales, cross-pair violations almost directly determine G.
Corollary 1 (hinge corollary): cross-pair violation rate is upper-bounded by a hinge loss: if the compressed distance gap Δz is pushed to at least a fraction η of the original gap Δx, violations drop. This penalizes compressing large original distance gaps into near-equality—the very mechanism that blurs topic boundaries.
Relative Distance Noise: A Single Predictor of G
Proposition 4: under normal approximation, cross-pair violations are fully determined by one ratio—relative distance noise:
ω = sd(e_j) / s_i
where e_j is the distance residual after compression and s_i the spread (standard deviation) of original distances. Small ω: distortions can't flip orderings because gaps are large relative to noise. Large ω: G collapses.
Across all 52 held-out runs, ω predicted cross-pair violation rates with correlation 0.979—near perfect. Normal approximation accuracy at k=0.4n and k=0.5n is within 0.10 and 0.06 standard deviations, versus 0.42 at k=10, confirming the far-scale regime where the theory applies. Predicting ν_k at k=0.4n via ω yields median error 0.005 (correlation 0.982).
A bonus finding: data entropy correlates with LAQ's gains—rank correlation 0.77-0.81 between data entropy and ω reduction, and 0.82-0.84 with G improvement (p ≤ 4×10⁻⁴) on retrieval-tuned encoders. LAQ helps most on information-dispersed, "complex" memories—precisely where global structure most needs protection.
🔧 LAQ: Locality-Aware Quantization
LAQ is, to the author's knowledge, the first quantizer trained with far-end rank order as the objective.
Starting Point: OPQ
LAQ starts from standard Optimized Product Quantization: PCA reduction, a learned rotation matrix R balancing subspace variances, then M subspaces each encoded by one of K=256 codewords—one byte per subspace. OPQ's codebook minimizes reconstruction error only.
The Change: A Far-End Hinge
LAQ keeps everything—same PCA basis, rotation, byte budget, search—and only changes the objective:
1. Reconstruction term: keep reconstruction error no worse than the OPQ starting point 2. Mid-scale hinge: penalize cross-pair violations at middle scales 3. Far-end hinge: penalize cross-pair violations at far scales—the key innovation
The Four-Step LAQ Recipe
1. Fit the OPQ starting point (PCA, rotation R, initial codebook C_0) on training memories 2. Compute far-end hinges at the OPQ starting point: sample cross pairs (near neighbor p, far neighbor q per anchor); incur hinge loss if Δz < η·Δx 3. Train the codebook with a straight-through estimator: forward pass uses hard assignment, backward pass treats gradients as soft 4. Monitor on a held-out set of L and G; stop when G stops improving
No labels, no queries, no human intervention. Key design properties:
📊 Experimental Evidence
Evaluated on FinQA (financial documents), LoCoMo (long conversation memory), and FinDER (external financial benchmark).
G Up Everywhere, L Essentially Unharmed
Across all 52 held-out runs, LAQ improved G; in 46 of 52, L also improved or stayed flat. G gains are highly significant (p = 8.5×10⁻⁴, sign test). On Amazon Titan V2, LAQ raised G by 0.032-0.038—two to five times the gains on retrieval-tuned encoders, likely because its OPQ starting point preserves the least far-end structure.
Ablation: The Far-End Hinge Is the Key
Exactly as Theorem 1 predicts.
Against Other Quantizers
On 12 runs of the Multi-Doc-2025 benchmark against six equal-size quantizers (scalar quantization, ITQ, RaBitQ, LSQ++, residual quantization, learned quantization): LAQ had the highest G in all 12. Retrieval quality (evidence recall@10) matched OPQ (p=0.84).
Scale
Training on one million memories takes 175 seconds—under three minutes—and is deterministic, reproducing identical codebooks bit-for-bit.
Why It Matters: Each End Governs Its Own Operations
Partial correlation analysis over 6 encoders and 2 agent memories confirms:
Optimizing only L—the industry standard—leaves consolidation, deletion, and mapping quality unprotected.
🤔 Reflections
The paper's contribution is moving a neglected evaluation dimension from measurement to optimization: LAQ is the first quantizer trained on G, with an objective derived from a proven bound (Theorem 1) rather than empirical heuristics. Practically, for agents using compressed vector indexes, LAQ offers a near-zero-cost upgrade—just swap the OPQ codebook.
Open questions:
1. What is the "right" value of G? L=0.97 may suffice for an agent that rarely reorganizes topics; one doing frequent bulk restructuring may need G>0.90. Operational thresholds need task-specific study. 2. LAQ doesn't fix embedding quality. It preserves geometry under compression; if the original embedding doesn't separate "apples" from "oranges," LAQ can't help. 3. Static training only. Real agent memories grow and shift domains; drifting distributions may require codebook retraining. Incremental LAQ is a natural extension. 4. G depends on memory scale n. G is read at relative scales of 30%-50%, so identical G values may mean different things for 1,000 vs. 1,000,000 memories. The paper estimates G via 2000-item subsampling; the mapping from G to topic preservation quality remains open.