IIRC Restic keeps indexes of data it uploads to configured backends. I think it caches that index locally, but it can also download it from the remote backend to compare.