diff --git a/src/main/java/com/googlesource/gerrit/modules/cache/chroniclemap/AutoAdjustCaches.java b/src/main/java/com/googlesource/gerrit/modules/cache/chroniclemap/AutoAdjustCaches.java
index a07d8c4..a6ccb01 100644
--- a/src/main/java/com/googlesource/gerrit/modules/cache/chroniclemap/AutoAdjustCaches.java
+++ b/src/main/java/com/googlesource/gerrit/modules/cache/chroniclemap/AutoAdjustCaches.java
@@ -15,6 +15,7 @@
 
 import static com.googlesource.gerrit.modules.cache.chroniclemap.ChronicleMapCacheFactory.getCacheDir;
 
+import com.google.common.annotations.VisibleForTesting;
 import com.google.common.cache.Cache;
 import com.google.common.flogger.FluentLogger;
 import com.google.gerrit.common.Nullable;
@@ -185,29 +186,31 @@
       String cacheName,
       ConcurrentMap<KeyWrapper<Object>, TimedValue<Object>> store,
       ProgressMonitor progressMonitor) {
-    long kAvg = 0;
-    long vAvg = 0;
+    long kTotal = 0;
+    long vTotal = 0;
 
-    if (store.isEmpty()) return ImmutablePair.of(kAvg, vAvg);
+    if (store.isEmpty()) return ImmutablePair.of(kTotal, vTotal);
 
     progressMonitor.beginTask(
         String.format("[%s] calculate average key/value size", cacheName), store.size());
 
-    int i = 1;
     for (Map.Entry<KeyWrapper<Object>, TimedValue<Object>> entry : store.entrySet()) {
-      kAvg = kAvg + (serializedKeyLength(cacheName, entry.getKey()) - kAvg) / i;
-      vAvg = vAvg + (serializedValueLength(cacheName, entry.getValue()) - vAvg) / i;
+      kTotal += serializedKeyLength(cacheName, entry.getKey());
+      vTotal += serializedValueLength(cacheName, entry.getValue());
       progressMonitor.update(1);
     }
     progressMonitor.endTask();
-    return ImmutablePair.of(kAvg, vAvg);
+    long numCacheEntries = store.entrySet().size();
+    return ImmutablePair.of(kTotal / numCacheEntries, vTotal / numCacheEntries);
   }
 
-  private static int serializedKeyLength(String cacheName, KeyWrapper<Object> keyWrapper) {
+  @VisibleForTesting
+  static int serializedKeyLength(String cacheName, KeyWrapper<Object> keyWrapper) {
     return CacheSerializers.getKeySerializer(cacheName).serialize(keyWrapper.getValue()).length;
   }
 
-  private static int serializedValueLength(String cacheName, TimedValue<Object> timedValue) {
+  @VisibleForTesting
+  static int serializedValueLength(String cacheName, TimedValue<Object> timedValue) {
     return CacheSerializers.getValueSerializer(cacheName).serialize(timedValue.getValue()).length;
   }
 
diff --git a/src/test/java/com/googlesource/gerrit/modules/cache/chroniclemap/AutoAdjustCachesIT.java b/src/test/java/com/googlesource/gerrit/modules/cache/chroniclemap/AutoAdjustCachesIT.java
index 5e4fe22..21e62b1 100644
--- a/src/test/java/com/googlesource/gerrit/modules/cache/chroniclemap/AutoAdjustCachesIT.java
+++ b/src/test/java/com/googlesource/gerrit/modules/cache/chroniclemap/AutoAdjustCachesIT.java
@@ -17,6 +17,8 @@
 import static com.google.common.truth.Truth.assertThat;
 import static com.googlesource.gerrit.modules.cache.chroniclemap.AutoAdjustCaches.MAX_ENTRIES_MULTIPLIER;
 import static com.googlesource.gerrit.modules.cache.chroniclemap.AutoAdjustCaches.PERCENTAGE_SIZE_INCREASE_THRESHOLD;
+import static com.googlesource.gerrit.modules.cache.chroniclemap.AutoAdjustCaches.serializedKeyLength;
+import static com.googlesource.gerrit.modules.cache.chroniclemap.AutoAdjustCaches.serializedValueLength;
 import static com.googlesource.gerrit.modules.cache.chroniclemap.AutoAdjustCachesCommand.CONFIG_HEADER;
 import static com.googlesource.gerrit.modules.cache.chroniclemap.AutoAdjustCachesCommand.TUNED_INFIX;
 import static com.googlesource.gerrit.modules.cache.chroniclemap.ChronicleMapCacheConfig.Defaults.maxBloatFactorFor;
@@ -134,13 +136,20 @@
   @Test
   @GerritConfig(name = "cache.test_cache.maxEntries", value = "10")
   @GerritConfig(name = "cache.test_cache.maxBloatFactor", value = "1")
-  public void shouldIncreaseCacheSizeWhenIsGettingFull() throws Exception {
+  public void shouldCorrectlyIncreaseCacheSizeWhenIsGettingFull() throws Exception {
     ChronicleMapCacheImpl<String, String> chronicleMapCache =
         (ChronicleMapCacheImpl<String, String>) testCache;
 
+    long elemsAdded = 0;
+    long totalKeySize = 0;
+    long totalValueSize = 0;
     while (chronicleMapCache.percentageUsedAutoResizes() < PERCENTAGE_SIZE_INCREASE_THRESHOLD) {
-      String aString = UUID.randomUUID().toString();
-      testCache.put(aString, aString);
+      String key = UUID.randomUUID() + "someExtraValue";
+      String value = UUID.randomUUID().toString();
+      elemsAdded += 1;
+      totalKeySize += serializedKeyLength(TEST_CACHE_NAME, new KeyWrapper<>(key));
+      totalValueSize += serializedValueLength(TEST_CACHE_NAME, new TimedValue<>(value));
+      testCache.put(key, value);
     }
 
     String tuneResult = adminSshSession.exec(SSH_CMD + " " + TEST_CACHE_NAME);
@@ -150,6 +159,10 @@
     assertThat(tunedConfig.getSubsections("cache")).contains(TEST_CACHE_NAME);
     assertThat(tunedConfig.getLong("cache", TEST_CACHE_NAME, "maxEntries", 0))
         .isEqualTo(chronicleMapCache.getConfig().getMaxEntries() * MAX_ENTRIES_MULTIPLIER);
+    assertThat(tunedConfig.getLong("cache", TEST_CACHE_NAME, "avgKeySize", 0))
+        .isEqualTo(totalKeySize / elemsAdded);
+    assertThat(tunedConfig.getLong("cache", TEST_CACHE_NAME, "avgValueSize", 0))
+        .isEqualTo(totalValueSize / elemsAdded);
   }
 
   @Test