Should I use the cross validation score or the test score to evaluate a machine learning model? Let's say I want to compare two machine learning models (A and B) on a classification problem. I split my data into train (80%) and test set (20%). Then I perform 4-fold cross-validation on the training set (so every time my validation set has 20% of the data).
The average over the folds cross validation accuracy I get is: 
model A - 80%
model B - 90%
Finally, I test the models on the test set and get the accuracies:
model A - 90%
model B - 80%
Which model would you choose? 
The test result is more representative of the generalization ability of the model because it has never been used during the training process. However the cross-validation result is more representative because it represents the performance of the system on the 80% of the data instead of just the 20% of the training set. Moreover, if I change the split of my sets, the different test accuracies I get have a high variance but the average cross validation accuracy is more stable.
 A: First of all, if the cross validation results are actually not used to decide anything (no parameter tuning, no selection, nothing) then you don't gain anything by the test set you describe:


*

*your splitting in to training/test is subject to the same difficulties as you subsequent splitting of the training set into the surrogate training and cross validation surrogate test sets. Any data leakage (e.g. due to confounders you did not account for) happens to both.  

*in addition, as you say, the 20 % test yset is smaller. Whether this is a problem or not depends largely on the absolute number of cases you have. If 20 % of your data are sufficient to yield test results with a suitable precision for your application at hand, then you are fine. 



That being said, selecting a model is part of the training of the final model. Thus, the selected model needs to undergo independent validation. 
In your case, this means: select according to your cross validation, e.g. model B (although you may want to look into more sophisticated selection rules that take instability into account). Then do an independent test of the selected model. That result is your validation (or better: verification) result for the final model. Here: 80 %.
However, you can use an additional outer cross validation for that, avoiding the difficulty of having only few test cases for the final verification. 
A: 
However the cross-validation result is more representative because it represents the performance of the system on the 80% of the data instead of just the 20% of the training set.

This is not the whole picture. Yes, the cross-validation error uses unseen ("out-of-bag") data. However, note that you are using the CV error in fitting your model and tuning (hyper-)parameters. And then the final model you are working with has seen these "unseen" data.
Cross-validation is part of model training. CV errors are not indicative of out-of-sample performance.
This would argue for using model A, which performs better out-of-sample. However...
Note that now you are using your test set in selecting a model. Thus, for your final model, the test set is not unseen any more!
Another thought experiment: assume you are fitting a huge amount of models to your data (maybe some of these models add random noise to your predictions?) and assess all of these models on your test set. Then one model will perform best on the test set. But if you then choose this model as your final model, its good performance on the test set may be due to chance alone. You may have overfit to the test set.
Conclusion: test set performance is only then a guide to true out-of-sample performance if it is not used in selecting, tuning or "improving just a little bit" your final model.

Moreover, if I change the split of my sets, the different test accuracies I get have a high variance but the average cross validation accuracy is more stable.

High variance in test set performance is a red flag. It does seem like you are overfitting. You may simply have too little data for your model, and beyond some point, even cross-validation may not save you. Consider regularizing your model, or constraining it in some other way (e.g., using the one standard error rule).
Also, accuracy is not a good evaluation measure.
A: What you are doing is creating test data at 20% of your total data set. However, the main purpose of Cross Validation Testing is to evaluate your models on different random samples loosing minimum information.
It is also important to consider how you cross validate and create your test data, whether you stratify sample the data or straight split. I suggest using stratified sampling in both CV and test for the data to more representative.
The information you present on the accuracy on two different models leads to conclusion that model A can be improved by using more data, it is seems to have underfitted and your model B has overfitted to your train data. These maybe due to the nature of the algorithms you have used, the features in your model, the regularisation you may have used or the sampling/splitting method you have used in the splits. 
