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).

There are few things to unpack here. The goal of permutation testing is to get a null distribution for your test statistic by permuting labels and repeating your procedure many times.
Your test statistic is e.g., average accuracy, and your procedure is CV. So you should permute the labels (all labels, because all labels go into the procedure) and then split the data into folds and run CV.
If you permute only the training set, then you are not getting valid null, because you don't have randomness in your outcome labels. If you permute data only in the test set, this will not be valid because it would not take into account the dependence between CV folds, which is the whole reason for doing permutation testing and not just some binomial test.
There are few caveats.
If you perform CV split randomly, then you can also simply permute the data first and then continue CV.
If your CV split is done so that each fold has the same proportion of labels from each class or that the folds are balanced based on the same other variables, then you have to permute so that this is also the case in your permutations. Usually, an easy way to do it is to permute first and then create your balanced splits.
If you don't have random folds, but they are already given, e.g., each fold is data from different cities, or different hospitals, or different measuring devices, then you have to permute within these folds so that labels from the same hospital will not get permuted with labels from a different hospital.
You might have other so-called "exchangeability blocks" that are not based on folds, e.g., you have different hospitals, but you don't split your data by hospital, then you should permute your data within these blocks, but not necessarily within folds.
