diff --git a/tests/ovn-northd.at b/tests/ovn-northd.at
index 9f2f15abca8f..b7c916874a2f 100644
--- a/tests/ovn-northd.at
+++ b/tests/ovn-northd.at
@@ -9493,50 +9493,67 @@ sim_add hv1
 as hv1
 ovs-vsctl add-br br-phys
 ovn_attach n1 br-phys 192.168.0.11
-ovs-vsctl add-port br-int lsp0-0 -- set interface lsp0-0 external_ids:iface-id=lsp0-0
-ovs-vsctl add-port br-int lsp0-1 -- set interface lsp0-1 external_ids:iface-id=lsp0-1
-ovs-vsctl add-port br-int lsp0-2 -- set interface lsp0-2 external_ids:iface-id=lsp0-2
 
-check ovn-nbctl --wait=hv ls-add ls0
-
-check as northd ovn-appctl -t NORTHD_TYPE inc-engine/clear-stats
-check ovn-nbctl --wait=hv lsp-add ls0 lsp0-0 -- lsp-set-addresses lsp0-0 "unknown"
-OVS_WAIT_UNTIL([test `as northd ovn-appctl -t NORTHD_TYPE inc-engine/show-stats northd recompute` = 5])
-OVS_WAIT_UNTIL([test `as northd ovn-appctl -t NORTHD_TYPE inc-engine/show-stats lflow recompute` = 5])
-
-check as northd ovn-appctl -t NORTHD_TYPE inc-engine/clear-stats
-check ovn-nbctl --wait=hv lsp-add ls0 lsp0-1 -- lsp-set-addresses lsp0-1 "aa:aa:aa:00:00:01 192.168.0.11"
-AT_CHECK([as northd ovn-appctl -t NORTHD_TYPE inc-engine/show-stats northd recompute], [0], [0
-])
-AT_CHECK([as northd ovn-appctl -t NORTHD_TYPE inc-engine/show-stats lflow recompute], [0], [0
-])
-
-check as northd ovn-appctl -t NORTHD_TYPE inc-engine/clear-stats
-check ovn-nbctl --wait=hv lsp-add ls0 lsp0-2 -- lsp-set-addresses lsp0-2 "aa:aa:aa:00:00:02 192.168.0.12"
-AT_CHECK([as northd ovn-appctl -t NORTHD_TYPE inc-engine/show-stats northd recompute], [0], [0
-])
-AT_CHECK([as northd ovn-appctl -t NORTHD_TYPE inc-engine/show-stats lflow recompute], [0], [0
-])
-
-check as northd ovn-appctl -t NORTHD_TYPE inc-engine/clear-stats
-check ovn-nbctl --wait=hv lsp-del lsp0-1
-AT_CHECK([as northd ovn-appctl -t NORTHD_TYPE inc-engine/show-stats northd recompute], [0], [0
-])
-AT_CHECK([as northd ovn-appctl -t NORTHD_TYPE inc-engine/show-stats lflow recompute], [0], [1
-])
+fail_count=0
+check_recompute_counter() {
+    northd_recomp=$(as northd ovn-appctl -t NORTHD_TYPE inc-engine/show-stats northd recompute)
+    if test x$northd_recomp != x$1; then
+        fail_count=$(($fail_count + 1))
+        echo check northd recompute failed: expected $1, got $northd_recomp
+        return 1
+    fi
+    lflow_recomp=$(as northd ovn-appctl -t NORTHD_TYPE inc-engine/show-stats lflow recompute)
+    if test x$lflow_recomp != x$2; then
+        fail_count=$(($fail_count + 1))
+        echo check lflow recompute failed: expected $2, got $lflow_recomp
+        return 1
+    fi
+    return 0
+}
 
-check as northd ovn-appctl -t NORTHD_TYPE inc-engine/clear-stats
-check ovn-nbctl --wait=hv lsp-set-addresses lsp0-2 "aa:aa:aa:00:00:88 192.168.0.88"
-AT_CHECK([as northd ovn-appctl -t NORTHD_TYPE inc-engine/show-stats northd recompute], [0], [0
-])
-AT_CHECK([as northd ovn-appctl -t NORTHD_TYPE inc-engine/show-stats lflow recompute], [0], [1
-])
+# Depending on order of responses from NB and SB, the number of recompute may
+# be different. This test case only verifies the best case scenario, which
+# should have the expected recompute count at least 70% of the time.
+for i in $(seq 10); do
+    check ovn-nbctl --wait=hv ls-add ls$i
+
+    check as northd ovn-appctl -t NORTHD_TYPE inc-engine/clear-stats
+    check ovn-nbctl --wait=hv lsp-add ls$i lsp${i}-0 -- lsp-set-addresses lsp${i}-0 "unknown"
+    ovs-vsctl add-port br-int lsp${i}-0 -- set interface lsp${i}-0 external_ids:iface-id=lsp${i}-0
+    wait_for_ports_up
+    check ovn-nbctl --wait=hv sync
+    check_recompute_counter 5 5 || break
+
+    check as northd ovn-appctl -t NORTHD_TYPE inc-engine/clear-stats
+    check ovn-nbctl --wait=hv lsp-add ls$i lsp${i}-1 -- lsp-set-addresses lsp${i}-1 "aa:aa:aa:00:00:01 192.168.0.11"
+    ovs-vsctl add-port br-int lsp${i}-1 -- set interface lsp${i}-1 external_ids:iface-id=lsp${i}-1
+    wait_for_ports_up
+    check ovn-nbctl --wait=hv sync
+    check_recompute_counter 0 0 || break
+
+    check as northd ovn-appctl -t NORTHD_TYPE inc-engine/clear-stats
+    check ovn-nbctl --wait=hv lsp-add ls$i lsp${i}-2 -- lsp-set-addresses lsp${i}-2 "aa:aa:aa:00:00:02 192.168.0.12"
+    ovs-vsctl add-port br-int lsp${i}-2 -- set interface lsp${i}-2 external_ids:iface-id=lsp${i}-2
+    wait_for_ports_up
+    check ovn-nbctl --wait=hv sync
+    check_recompute_counter 0 0 || break
+
+    check as northd ovn-appctl -t NORTHD_TYPE inc-engine/clear-stats
+    check ovn-nbctl --wait=hv lsp-del lsp${i}-1
+    check_recompute_counter 0 1 || break
+
+    check as northd ovn-appctl -t NORTHD_TYPE inc-engine/clear-stats
+    check ovn-nbctl --wait=hv lsp-set-addresses lsp${i}-2 "aa:aa:aa:00:00:88 192.168.0.88"
+    check_recompute_counter 0 1 || break
+
+    # No change, no recompute
+    check as northd ovn-appctl -t NORTHD_TYPE inc-engine/clear-stats
+    check ovn-nbctl --wait=sb sync
+    check_recompute_counter 0 0 || break
 
-# No change, no recompute
-check as northd ovn-appctl -t NORTHD_TYPE inc-engine/clear-stats
-check ovn-nbctl --wait=sb sync
-AT_CHECK([as northd ovn-appctl -t NORTHD_TYPE inc-engine/show-stats northd recompute], [0], [0
-])
+done
+echo Test failed $fail_count in 10.
+AT_CHECK([test $fail_count -le 3])
 
 OVN_CLEANUP([hv1])
 AT_CLEANUP
