Deduplicate and Evict Agent Memories
Problem Statement
An agent that writes to memory after every turn accumulates near-duplicates: "User prefers dark mode.", "user prefers dark mode", "User prefers dark mode!". Left alone this becomes the "vector-DB soup" failure mode - retrieval returns three copies of the same fact and burns the context window on redundancy.
Build the consolidation pass that runs before memory is written back.
Background
Consolidation is two stages:
Stage 1 - deduplicate by normalised key. Two memories collide when their normalised text is identical. Normalisation is: lowercase, strip leading/trailing whitespace, remove the characters ., ,, !, ?, ;, :, ' and ", then collapse every run of whitespace to a single space. Within a collision group keep exactly one record - the newest (largest timestamp); ties go to the higher importance; still tied, the lexicographically smallest id.
Stage 2 - evict to capacity. Rank the survivors by importance descending, then timestamp descending, then id ascending, and keep the first capacity.
Note the ordering matters: dedup first, so that three copies of a low-value fact cannot crowd out a distinct high-value one.
Your Task
Implement:
def consolidate_memories(memories, capacity):
- memories: list of dicts {"id": str, "text": str, "timestamp": int, "importance": int}.
- capacity: maximum number of memories to retain.
Return the retained memory dicts in the Stage 2 ranking order (highest priority first).
Input/Output Format
Returns list[dict] - the original dict objects, at most capacity of them, ordered by (-importance, -timestamp, id).
Sample
mem = [
{"id": "m1", "text": "User prefers dark mode.", "timestamp": 10, "importance": 3},
{"id": "m2", "text": " user prefers DARK mode ", "timestamp": 20, "importance": 1},
{"id": "m3", "text": "Deploys on Fridays", "timestamp": 5, "importance": 5},
]
print([m["id"] for m in consolidate_memories(mem, 5)])
# ['m3', 'm2']
m1 and m2 normalise to the same key user prefers dark mode; m2 is newer so it survives - even though m1 has higher importance.
Example:
mem = [{'id':'m1','text':'User prefers dark mode.','timestamp':10,'importance':3},{'id':'m2','text':' user prefers DARK mode ','timestamp':20,'importance':1},{'id':'m3','text':'Deploys on Fridays','timestamp':5,'importance':5}]
print([m['id'] for m in consolidate_memories(mem, 5)])['m3', 'm2']
m1 and m2 both normalise to 'user prefers dark mode', so only the newer m2 (timestamp 20) survives dedup. m3 is a distinct key. Ranking the two survivors by importance descending puts m3 (importance 5) ahead of m2 (importance 1); capacity 5 keeps both.
Constraints:
0 <= len(memories) <= 2000,capacity >= 0timestampandimportanceare ints;importanceis in1..5- Normalisation: lowercase -> strip -> remove
.,!?;:'"-> collapse whitespace runs to one space - Dedup keeps the newest record first, then higher importance, then smallest id
- Eviction ranks by
(-importance, -timestamp, id)and keeps the firstcapacity - Never build the output by iterating a set - the order must be fully determined
1. Background Knowledge
Memory Consolidation in AI agents is the process of refining raw, noisy memory traces into a structured, high-signal knowledge base. Agents often generate redundant or near-identical memories during interaction (e.g., "I like coffee" vs. "I LIKE coffee!"). Without consolidation, the vector database becomes cluttered with duplicates, leading to inefficient retrieval and wasted context window space. This problem models a critical preprocessing step: deduplication followed by capacity-based eviction.
The core concept here is normalization. To detect duplicates, we must transform text into a canonical form. This involves lowercasing, stripping punctuation, and collapsing whitespace. Two memories are considered duplicates if their normalized texts are identical. This is a classic hashing or grouping problem where we map raw data to a key.
The second phase is ranking and selection. After deduplication, we have a set of unique memories. We must retain only the top K memories based on a multi-criteria sort: importance (descending), timestamp (descending), and id (ascending). This ensures that high-value, recent memories are preserved while older, less important ones are evicted. The order of operations is crucial: deduplication must happen before eviction to prevent low-value duplicates from occupying slots meant for distinct, high-value memories.
2. Algorithm Approach
The problem can be decomposed into two distinct algorithmic stages:
- Grouping and Selection (Deduplication):
- Iterate through all memories.
- Compute a normalized key for each memory's text.
- Group memories by this key.
- For each group, select the single "best" memory based on the tie-breaking rules: highest timestamp, then highest importance, then lexicographically smallest id.
- Sorting and Truncation (Eviction):
- Take the list of survivors from Stage 1.
- Sort them according to the global ranking criteria: importance descending, timestamp descending, id ascending.
- Slice the sorted list to keep only the first capacity elements.
This approach leverages hash maps (dictionaries) for efficient grouping (O(1) average insertion) and comparison-based sorting for the final ranking (O(NlogN)).
3. Step-by-Step Strategy
- Define a Normalization Function:
- Create a helper function normalize(text) that:
- Converts text to lowercase.
- Strips leading/trailing whitespace.
- Removes specific punctuation characters: ., ,, !, ?, ;, :, ', ".
- Collapses multiple whitespace characters into a single space.
- Returns the cleaned string.
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.