It is actually stored in the device. A new database is downloaded from time to time

It's not every song, the model is built from a list of N (100k?) most popular songs. If you pick something a bit obscure it won't work. The model is updated on occasion and pushed in bulk to pixel devices.

I've tried putting my phone in airplane mode and the feature still works. You can easily try that yourself.

That says the analysis is done locally. It does not say nothing goes to the cloud.