Permutation testing for machine learning: permute entire set or only training set? Ojala and Garriga (2010) [Journal of Machine Learning Research 11 (2010) 1833-1863] mention two permutation tests for machine learning: test one for assessing whether a classifier has learned anything better than random guessing. As far as I understand, the idea is to permute class labels and perform machine learning k number of times and compare with original model performance to derive a p value.
The question is a simple one: if I am using cross-validation, should I permute the entire data set before diving into training/test (per fold) OR should I permute the cross-validation training data only (within each fold) and leave the test data untouched. (As far as I understand, one would permute the class labels for the entire data and then perform cross-validation).

At prediction time, you have the $(y_i, \hat y_i)$ pairs of the actual labels and the predictions. Notice that the result would be the same if you permuted the actual labels $y_i$'s and if you permuted the predictions $\hat y_i$'s, since permuting them breaks the pairing. So such a permutation test would create the null distribution in the scenario where the predictions were made at random but the distribution of the predictions is fixed.
But notice what does the paper say:

A significant classifier for Test 1 rejects the null hypothesis that
the features and the labels are independent, i.e., that there is no
difference between the classes. If the original data contains
dependency between data points and labels, then: (1) a significant
classifier $f$ will use such information to achieve a good
classification accuracy, resulting into a small $p$-value; (2) if the
classifier $f$ is not significant with Test 1, $f$ was not able to use
the existing dependency between data and labels in the original data.
Finally, if the original data did not contain any real dependency
between data points and labels, then all classifiers would have a high
$p$-value and the null hypothesis would never be rejected.
Applying randomizations on the original data is therefore a powerful
way to understand how the different classifiers use the structure
implicit in the data, if such structure exists. [...]

It mentions "different classifiers" using the structure of the data. If you permuted whole data it is a different question that is answered. A model trained on data with permuted labels learns to find spurious correlations. Having a small train error in such a case tells you how much is it prone to overfit. There is another difference when permuting only the labels and comparing them to predictions. In the first case, you are looking at the distribution of predictions from a single model. In the second case, you look at the distribution of predictions from different "null" models. Only the second case tells you how does the classifier learns the structure of the data.
Finally, correct me if I'm wrong, but the paper does not seem to say anything about the train and test data. They seem to be describing training the classifier on a dataset $D$ and comparing the performance to the permuted datasets $D'$, but those are the training errors.
