Because your search history can be stored, and that stored history can get synced if you use the Sync feature. That's kinda the point behind the Sync feature.
Sync is end-to-end encrypted. Even if they want to introduce ToS, it should be only for Sync feature, not the whole software. Also why Sync suddenly requires ToS after two decades?