The lower bound for the tests are too tight and any slight improvement in the timing can result in a test failure.
For example, these tests were failing due to the improvements from the MR 3718