diff --git a/src/avalanche/test/voterecord_tests.cpp b/src/avalanche/test/voterecord_tests.cpp
--- a/src/avalanche/test/voterecord_tests.cpp
+++ b/src/avalanche/test/voterecord_tests.cpp
@@ -20,10 +20,11 @@
 
 BOOST_FIXTURE_TEST_SUITE(voterecord_tests, TestingSetup)
 
-#define REGISTER_VOTE_AND_CHECK(vr, vote, state, finalized, confidence)        \
+#define REGISTER_VOTE_AND_CHECK(vr, vote, state, finalized, stale, confidence) \
     vr.registerVote(nextNodeId(nodeid), vote);                                 \
     BOOST_CHECK_EQUAL(vr.isAccepted(), state);                                 \
     BOOST_CHECK_EQUAL(vr.hasFinalized(), finalized);                           \
+    BOOST_CHECK_EQUAL(vr.isStale(), stale);                                    \
     BOOST_CHECK_EQUAL(vr.getConfidence(), confidence);
 
 BOOST_AUTO_TEST_CASE(vote_record) {
@@ -33,6 +34,7 @@
     // Check initial state.
     BOOST_CHECK_EQUAL(vraccepted.isAccepted(), true);
     BOOST_CHECK_EQUAL(vraccepted.hasFinalized(), false);
+    BOOST_CHECK_EQUAL(vraccepted.isStale(), false);
     BOOST_CHECK_EQUAL(vraccepted.getConfidence(), 0);
 
     VoteRecord vr(false);
@@ -40,68 +42,71 @@
     // Check initial state.
     BOOST_CHECK_EQUAL(vr.isAccepted(), false);
     BOOST_CHECK_EQUAL(vr.hasFinalized(), false);
+    BOOST_CHECK_EQUAL(vr.isStale(), false);
     BOOST_CHECK_EQUAL(vr.getConfidence(), 0);
 
     // We need to register 6 positive votes before we start counting.
     for (int i = 0; i < 6; i++) {
-        REGISTER_VOTE_AND_CHECK(vr, 0, false, false, 0);
+        REGISTER_VOTE_AND_CHECK(vr, 0, false, false, false, 0);
     }
 
     // Next vote will flip state, and confidence will increase as long as we
     // vote yes.
-    REGISTER_VOTE_AND_CHECK(vr, 0, true, false, 0);
+    REGISTER_VOTE_AND_CHECK(vr, 0, true, false, false, 0);
 
     // A single neutral vote do not change anything.
-    REGISTER_VOTE_AND_CHECK(vr, -1, true, false, 1);
+    REGISTER_VOTE_AND_CHECK(vr, -1, true, false, false, 1);
     for (int i = 2; i < 8; i++) {
-        REGISTER_VOTE_AND_CHECK(vr, 0, true, false, i);
+        REGISTER_VOTE_AND_CHECK(vr, 0, true, false, false, i);
     }
 
     // Two neutral votes will stall progress.
-    REGISTER_VOTE_AND_CHECK(vr, -1, true, false, 7);
-    REGISTER_VOTE_AND_CHECK(vr, -1, true, false, 7);
+    REGISTER_VOTE_AND_CHECK(vr, -1, true, false, false, 7);
+    REGISTER_VOTE_AND_CHECK(vr, -1, true, false, false, 7);
     for (int i = 2; i < 8; i++) {
-        REGISTER_VOTE_AND_CHECK(vr, 0, true, false, 7);
+        REGISTER_VOTE_AND_CHECK(vr, 0, true, false, false, 7);
     }
 
     // Now confidence will increase as long as we vote yes.
     for (int i = 8; i < AVALANCHE_FINALIZATION_SCORE; i++) {
-        REGISTER_VOTE_AND_CHECK(vr, 0, true, false, i);
+        REGISTER_VOTE_AND_CHECK(vr, 0, true, false, false, i);
     }
 
     // The next vote will finalize the decision.
-    REGISTER_VOTE_AND_CHECK(vr, 1, true, true, AVALANCHE_FINALIZATION_SCORE);
+    REGISTER_VOTE_AND_CHECK(vr, 1, true, true, false,
+                            AVALANCHE_FINALIZATION_SCORE);
 
     // Now that we have two no votes, confidence stop increasing.
     for (int i = 0; i < 5; i++) {
-        REGISTER_VOTE_AND_CHECK(vr, 1, true, true,
+        REGISTER_VOTE_AND_CHECK(vr, 1, true, true, false,
                                 AVALANCHE_FINALIZATION_SCORE);
     }
 
     // Next vote will flip state, and confidence will increase as long as we
     // vote no.
-    REGISTER_VOTE_AND_CHECK(vr, 1, false, false, 0);
+    REGISTER_VOTE_AND_CHECK(vr, 1, false, false, false, 0);
 
     // A single neutral vote do not change anything.
-    REGISTER_VOTE_AND_CHECK(vr, -1, false, false, 1);
+    REGISTER_VOTE_AND_CHECK(vr, -1, false, false, false, 1);
     for (int i = 2; i < 8; i++) {
-        REGISTER_VOTE_AND_CHECK(vr, 1, false, false, i);
+        REGISTER_VOTE_AND_CHECK(vr, 1, false, false, false, i);
     }
 
     // Two neutral votes will stall progress.
-    REGISTER_VOTE_AND_CHECK(vr, -1, false, false, 7);
-    REGISTER_VOTE_AND_CHECK(vr, -1, false, false, 7);
+    REGISTER_VOTE_AND_CHECK(vr, -1, false, false, false, 7);
+    REGISTER_VOTE_AND_CHECK(vr, -1, false, false, false, 7);
     for (int i = 2; i < 8; i++) {
-        REGISTER_VOTE_AND_CHECK(vr, 1, false, false, 7);
+        REGISTER_VOTE_AND_CHECK(vr, 1, false, false, false, 7);
     }
 
     // Now confidence will increase as long as we vote no.
     for (int i = 8; i < AVALANCHE_FINALIZATION_SCORE; i++) {
-        REGISTER_VOTE_AND_CHECK(vr, 1, false, false, i);
+        REGISTER_VOTE_AND_CHECK(vr, 1, false, false, false, i);
     }
 
     // The next vote will finalize the decision.
-    REGISTER_VOTE_AND_CHECK(vr, 0, false, true, AVALANCHE_FINALIZATION_SCORE);
+    REGISTER_VOTE_AND_CHECK(vr, 0, false, true, false,
+                            AVALANCHE_FINALIZATION_SCORE);
 
     // Check that inflight accounting work as expected.
     VoteRecord vrinflight(false);
@@ -127,6 +132,58 @@
     }
 }
 
+BOOST_AUTO_TEST_CASE(stale_vote) {
+    NodeId nodeid = -1;
+    // Setup a record that is inconclusive so far
+    VoteRecord vr(false);
+    for (uint32_t i = 0; i < AVALANCHE_VOTE_STALE_THRESHOLD / 8; i++) {
+        // Vote randomly, but such that there's always enough neutral votes to
+        // not gain confidence.
+        for (auto j = 0; j < 5; j++) {
+            REGISTER_VOTE_AND_CHECK(vr, InsecureRand32(), false, false, false,
+                                    0);
+        }
+        REGISTER_VOTE_AND_CHECK(vr, -1, false, false, false, 0);
+        REGISTER_VOTE_AND_CHECK(vr, -1, false, false, false, 0);
+        REGISTER_VOTE_AND_CHECK(vr, -1, false, false, false, 0);
+    }
+
+    // Vote record becomes stale after too many rounds of inconclusive voting
+    REGISTER_VOTE_AND_CHECK(vr, -1, false, false, true, 0);
+}
+
+BOOST_AUTO_TEST_CASE(stale_vote_after_confidence_flip) {
+    NodeId nodeid = -1;
+    auto voteCount = 0;
+    // Setup a record that is inconclusive so far
+    VoteRecord vr(false);
+    for (uint32_t i = 0; i < AVALANCHE_VOTE_STALE_THRESHOLD - 6; i++) {
+        REGISTER_VOTE_AND_CHECK(vr, -1, false, false, false, 0);
+        voteCount++;
+    }
+
+    // Vote to encourage confidence to increase
+    for (auto i = 0; i < 6; i++) {
+        REGISTER_VOTE_AND_CHECK(vr, 1, false, false, false, 0);
+        voteCount++;
+    }
+
+    // We reached the vote count threshold, but the record will not be stale
+    // until confidence resets
+    BOOST_CHECK_EQUAL(voteCount, AVALANCHE_VOTE_STALE_THRESHOLD);
+
+    // Increase confidence
+    REGISTER_VOTE_AND_CHECK(vr, 1, false, false, false, 1);
+
+    // Vote to encourage confidence to reset
+    for (auto i = 0; i < 6; i++) {
+        REGISTER_VOTE_AND_CHECK(vr, 0, false, false, false, 2);
+    }
+
+    // Vote becomes stale once the confidence resets
+    REGISTER_VOTE_AND_CHECK(vr, 0, true, false, true, 0);
+}
+
 BOOST_AUTO_TEST_CASE(duplicate_votes) {
     VoteRecord vr(true);
     NodeId nodeid = -1;
diff --git a/src/avalanche/voterecord.h b/src/avalanche/voterecord.h
--- a/src/avalanche/voterecord.h
+++ b/src/avalanche/voterecord.h
@@ -16,6 +16,11 @@
  */
 static constexpr int AVALANCHE_FINALIZATION_SCORE = 128;
 
+/**
+ * Number of votes before a record may be considered as stale.
+ */
+static constexpr uint32_t AVALANCHE_VOTE_STALE_THRESHOLD = 1024;
+
 /**
  * How many inflight requests can exist for one item.
  */
@@ -70,6 +75,11 @@
         return getConfidence() >= AVALANCHE_FINALIZATION_SCORE;
     }
 
+    bool isStale() const {
+        return successfulVotes > AVALANCHE_VOTE_STALE_THRESHOLD &&
+               getConfidence() == 0;
+    }
+
     /**
      * Register a new vote for an item and update confidence accordingly.
      * Returns true if the acceptance or finalization state changed.