LRUCache evicts the wrong entries

Done

/home/devdi/devswarm/evals/tasks/lru_cache_recency/repo · 2026-11-09 16:17:20 UTC · took 25.7s

Plan (done)
Code (done)
Test (done)
Review (done)
Finish (done)

Cost

$0.0029

Tests

Passed

Iterations

Re-plans

LLM calls

Prompt read from cache

79%

Usage by agent

Cost per agent

Tokens per agent

Cache read
Cache write
Input
Output

View as table

Agent	Cost	Cache read	Cache write	Input	Output
planner	$0.0008	5,630	881	8	1,196
coder	$0.0010	9,230	2,515	8	1,257
tester	$0.0011	11,190	3,370	8	1,067

Timeline

planner iteration 1 Finished 3 calls · 7,715 tokens · $0.0008 · 7.9s

Loading…
coder iteration 1 Finished 3 calls · 13.0K tokens · $0.0010 · 8.6s

Loading…
tester iteration 1 Finished 3 calls · 15.6K tokens · $0.0011 · 8.0s

Loading…

verify iteration 1 Passed 0.5s

.......                                                                  [100%]
7 passed in 0.02s

Final diff

diff --git a/lru.py b/lru.py
index 8f9595c..1cd7f0a 100644
--- a/lru.py
+++ b/lru.py
@@ -7,9 +7,16 @@ class LRUCache:
         self._data: OrderedDict = OrderedDict()
 
     def get(self, key):
-        return self._data.get(key)
+        if key not in self._data:
+            return None
+        self._data.move_to_end(key)
+        return self._data[key]
 
     def put(self, key, value) -> None:
+        if key in self._data:
+            self._data[key] = value
+            self._data.move_to_end(key)
+            return
         if len(self._data) >= self.capacity:
             self._data.popitem(last=False)
         self._data[key] = value
diff --git a/test_lru.py b/test_lru.py
index ee81494..02d9428 100644
--- a/test_lru.py
+++ b/test_lru.py
@@ -12,3 +12,49 @@ def test_evicts_when_full():
     cache.put("a", 1)
     cache.put("b", 2)
     assert cache.get("a") is None
+
+
+def test_get_refreshes_recency():
+    cache = LRUCache(2)
+    cache.put("a", 1)
+    cache.put("b", 2)
+    assert cache.get("a") == 1
+    cache.put("c", 3)
+    assert cache.get("b") is None
+    assert cache.get("a") == 1
+
+
+def test_update_refreshes_recency():
+    cache = LRUCache(2)
+    cache.put("a", 1)
+    cache.put("b", 2)
+    cache.put("a", 10)
+    cache.put("c", 3)
+    assert cache.get("b") is None
+    assert cache.get("a") == 10
+
+
+def test_update_does_not_evict():
+    cache = LRUCache(2)
+    cache.put("a", 1)
+    cache.put("b", 2)
+    cache.put("a", 5)
+    assert len(cache._data) == 2
+    assert cache.get("a") == 5
+    assert cache.get("b") == 2
+
+
+def test_get_missing_key_does_not_insert():
+    cache = LRUCache(2)
+    cache.put("a", 1)
+    assert cache.get("missing") is None
+    assert len(cache._data) == 1
+    assert list(cache._data) == ["a"]
+
+
+def test_update_at_capacity_one_keeps_entry():
+    cache = LRUCache(1)
+    cache.put("a", 1)
+    cache.put("a", 2)
+    assert len(cache._data) == 1
+    assert cache.get("a") == 2