My models performs better with the arbitrary random feature. How can I interpret this?
It's a good sanity check, but the fact it fails means there must be a mistake somewhere:


Hypothesis 1: mistake in the interpretation of the results. Is the performance improvement significant? If not, it might simply be due to chance. That would mean that none of the models actually uses the random feature, one happens to be slightly better by chance. However the chances that this would happen with 6 distinct classifiers are very low ($1/2^6$ to be precise)
Hypothesis 2: mistake in the generation of the the random feature. If it actually contributes to the prediction, then there must be a regular pattern so it's not truly random. Manually inspect the models (especially the decision tree one, it's the easiest to interpret) to see what happens. Then try to reproduce the result with a different random sequence and observe the model again: if the model uses the random feature in the same way then it's not really random.
Hypothesis 3: mistake in the split between training and test set. We always underestimate how easy it is to make a stupid mistake, so my money is on this one ;) More seriously, the fact that the performance is better with the random feature points to this direction: assuming it's truly random and it has mostly distinct values, an overfit model could use it as an id for an instance that was seen in the training set. Try re-sampling and/or cross-validation.