Seems like it would be more computationally expensive to tokenize letters instead of words. You would get more granularity (spelling errors in the training data suddenly matter a lot more.) But now you have increased the number of tokens that need selected by 5 or 6 times on average. So sure, they can get around having to completely retrain the models but wouldn't this increase operating costs ultimately?

I believe so. They do not mention a change in model architecture which reduce the compute for these byte-level models. So it would be expected that compute costs of token generation increase proportionally with the average increase of tokens with respect to current subword tokenization. I have just read the paper here and they seem to combat the increase compute cost with their efficent self-attention method, I do not see a mention of this here, so I only assume that the internal model architecture remains the same, and thus it is expected that the larger context length and time to generate a token will be the main issues.