Spotify consistently feels like it's playing local media, it's crazy.
Unless you're using Spotify connect to a system that supports it, or playing a song for the very first time you're more than likely to be playing from local media. Spotify downloads a local copy to your phone even when streaming and it stays there indefinitely. When you download an album for off-line listening and delete it later, it doesn't actually get deleted either, just hidden. Its how Spotify reduce the demand on their bandwidth. Storing as much as possible on our local devices. If you're using and android device you should have the option of clear cache but on an iPhone the only way of deleting the downloaded media is to delete the App and reinstall it.
I'm not talking about playing cached songs, I mean searching for random keywords then clicking a random song in the list of results. There's no way that's cached.
Also, the Android version absolutely deletes songs when the cache is full. Otherwise it would fill it every device which uses Spotify. Also you can delete the cache in spotify options. I just checked.
On my phone it's using 4GB, which is hardly unreasonable.