diff --git a/src/avalanche.h b/src/avalanche.h
--- a/src/avalanche.h
+++ b/src/avalanche.h
@@ -169,9 +169,9 @@
 
     bool addBlockToReconciliate(const CBlockIndex *pindex);
     bool isAccepted(const CBlockIndex *pindex) const;
-    bool hasFinalized(const CBlockIndex *pindex) const;
 
-    bool registerVotes(const AvalancheResponse &response);
+    bool registerVotes(const AvalancheResponse &response,
+                       std::vector<uint256> &finalized);
 
     bool startEventLoop(CScheduler &scheduler);
     bool stopEventLoop();
diff --git a/src/avalanche.cpp b/src/avalanche.cpp
--- a/src/avalanche.cpp
+++ b/src/avalanche.cpp
@@ -34,21 +34,22 @@
     return false;
 }
 
-bool AvalancheProcessor::hasFinalized(const CBlockIndex *pindex) const {
-    if (auto vr = GetRecord(vote_records, pindex)) {
-        return vr->hasFinalized();
-    }
-
-    return false;
-}
-
-bool AvalancheProcessor::registerVotes(const AvalancheResponse &response) {
+bool AvalancheProcessor::registerVotes(const AvalancheResponse &response,
+                                       std::vector<uint256> &finalized) {
     const std::vector<AvalancheVote> &votes = response.GetVotes();
 
     // Register votes.
     auto w = vote_records.getWriteView();
     for (auto &v : votes) {
-        w[v.GetHash()].registerVote(v.IsValid());
+        auto &r = w[v.GetHash()];
+        r.registerVote(v.IsValid());
+        if (r.hasFinalized()) {
+            finalized.push_back(v.GetHash());
+        }
+    }
+
+    for (auto &h : finalized) {
+        w->erase(h);
     }
 
     return true;
diff --git a/src/test/avalanche_tests.cpp b/src/test/avalanche_tests.cpp
--- a/src/test/avalanche_tests.cpp
+++ b/src/test/avalanche_tests.cpp
@@ -77,6 +77,8 @@
     AvalancheProcessor p;
     CBlockIndex index;
 
+    std::vector<uint256> finalized;
+
     // Make sure the block has a hash.
     static const uint256 blockHash(uint256S(
         "abcdef0000000000000000000000000000000000000000000000000000000001"));
@@ -84,7 +86,6 @@
 
     // Querying for random block returns false.
     BOOST_CHECK(!p.isAccepted(&index));
-    BOOST_CHECK(!p.hasFinalized(&index));
 
     // Add a new block. Check it is added to the polls.
     BOOST_CHECK(p.addBlockToReconciliate(&index));
@@ -95,21 +96,20 @@
 
     // Newly added blocks are also considered rejected.
     BOOST_CHECK(!p.isAccepted(&index));
-    BOOST_CHECK(!p.hasFinalized(&index));
 
     // Let's vote for this block a few times.
     AvalancheResponse resp{{AvalancheVote(blockHash, 0)}};
     for (int i = 0; i < 5; i++) {
-        p.registerVotes(resp);
+        p.registerVotes(resp, finalized);
         BOOST_CHECK(!p.isAccepted(&index));
-        BOOST_CHECK(!p.hasFinalized(&index));
+        BOOST_CHECK_EQUAL(finalized.size(), 0);
     }
 
     // Now it is accepeted, but we can vote for it numerous times.
     for (int i = 0; i < AVALANCHE_FINALIZATION_SCORE; i++) {
-        p.registerVotes(resp);
+        p.registerVotes(resp, finalized);
         BOOST_CHECK(p.isAccepted(&index));
-        BOOST_CHECK(!p.hasFinalized(&index));
+        BOOST_CHECK_EQUAL(finalized.size(), 0);
     }
 
     // As long as it is not finalized, we poll.
@@ -119,27 +119,35 @@
     BOOST_CHECK(invs[0].hash == blockHash);
 
     // Now finalize the decision.
-    resp = {{AvalancheVote(blockHash, 1)}};
-    p.registerVotes(resp);
-    BOOST_CHECK(p.isAccepted(&index));
-    BOOST_CHECK(p.hasFinalized(&index));
+    p.registerVotes(resp, finalized);
+    BOOST_CHECK_EQUAL(finalized.size(), 1);
+    BOOST_CHECK(finalized[0] == blockHash);
+    finalized = {};
 
     // Once the decision is finalized, there is no poll for it.
     invs = AvalancheTest::getInvsForNextPoll(p);
     BOOST_CHECK_EQUAL(invs.size(), 0);
 
     // Now let's undo this and finalize rejection.
-    for (int i = 0; i < 5; i++) {
-        p.registerVotes(resp);
-        BOOST_CHECK(p.isAccepted(&index));
-        BOOST_CHECK(p.hasFinalized(&index));
+    BOOST_CHECK(p.addBlockToReconciliate(&index));
+    invs = AvalancheTest::getInvsForNextPoll(p);
+    BOOST_CHECK_EQUAL(invs.size(), 1);
+    BOOST_CHECK_EQUAL(invs[0].type, MSG_BLOCK);
+    BOOST_CHECK(invs[0].hash == blockHash);
+
+    // Only 3 here as we don't need to flip state.
+    resp = {{AvalancheVote(blockHash, 1)}};
+    for (int i = 0; i < 3; i++) {
+        p.registerVotes(resp, finalized);
+        BOOST_CHECK(!p.isAccepted(&index));
+        BOOST_CHECK_EQUAL(finalized.size(), 0);
     }
 
     // Now it is rejected, but we can vote for it numerous times.
     for (int i = 0; i < AVALANCHE_FINALIZATION_SCORE; i++) {
-        p.registerVotes(resp);
+        p.registerVotes(resp, finalized);
         BOOST_CHECK(!p.isAccepted(&index));
-        BOOST_CHECK(!p.hasFinalized(&index));
+        BOOST_CHECK_EQUAL(finalized.size(), 0);
     }
 
     // As long as it is not finalized, we poll.
@@ -149,18 +157,20 @@
     BOOST_CHECK(invs[0].hash == blockHash);
 
     // Now finalize the decision.
-    p.registerVotes(resp);
+    p.registerVotes(resp, finalized);
     BOOST_CHECK(!p.isAccepted(&index));
-    BOOST_CHECK(p.hasFinalized(&index));
+    BOOST_CHECK_EQUAL(finalized.size(), 1);
+    BOOST_CHECK(finalized[0] == blockHash);
+    finalized = {};
 
     // Once the decision is finalized, there is no poll for it.
     invs = AvalancheTest::getInvsForNextPoll(p);
     BOOST_CHECK_EQUAL(invs.size(), 0);
 
     // Adding the block twice does nothing.
+    BOOST_CHECK(p.addBlockToReconciliate(&index));
     BOOST_CHECK(!p.addBlockToReconciliate(&index));
     BOOST_CHECK(!p.isAccepted(&index));
-    BOOST_CHECK(p.hasFinalized(&index));
 }
 
 BOOST_AUTO_TEST_CASE(event_loop) {