Become a MacRumors Supporter for $50/year with no ads, ability to filter front page stories, and private forums.
The data is stored locally, but due to the nature of how tvOS handles storage it will automatically clear things out if/when it thinks your Apple TV is running low on space. The Cloud Backup guide has more info on this.
I know, but this has never happend for me (I don't have any big apps on the device). But I guess it's possible that the TVOS 26 update was unusually large.
 
Register on MacRumors! This sidebar will go away, and you'll see fewer ads.