We start by comparing all-pairs and all-pairs-max variants, each applied to either the entire set of species or to polytomies of a 50 % majority rule consensus (default), limiting our study to the 37-taxon and 45-taxon avian and mammalian datasets where Θ(n 4 k) methods could run. On both datasets, a surprising pattern emerges. Without the use of consensus, the error unexpectedly goes up with decreased ILS, a pattern that is more pronounced for all-pairs-max (Additional file 1: Figures S1 and S2). As discussed before, we attribute this pattern to difficulties of estimating long quartet lengths. When consensus is used within DISTIQUE, the accuracy improves with decreased ILS, as expected (Additional file 1: Figures S1 and S2). Depending on the level of ILS, the consensus tree is unresolved for 25 to 95 % of branches, leaving much to DISTIQUE to resolve. Overall, all-pairs methods has better accuracy than all-pairs-max, a result that we do not find surprising. Based on these results, hereafter, we only show results for DISTIQUE applied to a majority consensus, and we omit all-pairs-max.