diff --git a/src/avalanche.h b/src/avalanche.h
--- a/src/avalanche.h
+++ b/src/avalanche.h
@@ -358,7 +358,7 @@
 private:
     void runEventLoop();
     void clearTimedoutRequests();
-    std::vector<CInv> getInvsForNextPoll(bool forPoll = true) const;
+    std::vector<CInv> getInvsForNextPoll(bool forPoll = true);
     NodeId getSuitableNodeToQuery();
 
     friend struct AvalancheTest;
diff --git a/src/avalanche.cpp b/src/avalanche.cpp
--- a/src/avalanche.cpp
+++ b/src/avalanche.cpp
@@ -367,22 +367,26 @@
     return eventLoop.stopEventLoop();
 }
 
-std::vector<CInv> AvalancheProcessor::getInvsForNextPoll(bool forPoll) const {
+std::vector<CInv> AvalancheProcessor::getInvsForNextPoll(bool forPoll) {
     std::vector<CInv> invs;
 
-    auto r = vote_records.getReadView();
-    for (const std::pair<const CBlockIndex *const, VoteRecord> &p :
-         reverse_iterate(r)) {
-        const CBlockIndex *pindex = p.first;
-
-        {
-            LOCK(cs_main);
+    // First remove all blocks that are not worth polling.
+    {
+        LOCK(cs_main);
+        auto w = vote_records.getWriteView();
+        for (auto it = w->begin(); it != w->end();) {
+            const CBlockIndex *pindex = it->first;
             if (!IsWorthPolling(pindex)) {
-                // Obviously do not poll if the block is not worth polling.
-                continue;
+                w->erase(it++);
+            } else {
+                ++it;
             }
         }
+    }
 
+    auto r = vote_records.getReadView();
+    for (const std::pair<const CBlockIndex *const, VoteRecord> &p :
+         reverse_iterate(r)) {
         // Check if we can run poll.
         const bool shouldPoll =
             forPoll ? p.second.registerPoll() : p.second.shouldPoll();
@@ -391,7 +395,7 @@
         }
 
         // We don't have a decision, we need more votes.
-        invs.emplace_back(MSG_BLOCK, pindex->GetBlockHash());
+        invs.emplace_back(MSG_BLOCK, p.first->GetBlockHash());
         if (invs.size() >= AVALANCHE_MAX_ELEMENT_POLL) {
             // Make sure we do not produce more invs than specified by the
             // protocol.
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
@@ -15,7 +15,7 @@
 struct AvalancheTest {
     static void runEventLoop(AvalancheProcessor &p) { p.runEventLoop(); }
 
-    static std::vector<CInv> getInvsForNextPoll(const AvalancheProcessor &p) {
+    static std::vector<CInv> getInvsForNextPoll(AvalancheProcessor &p) {
         return p.getInvsForNextPoll(false);
     }