It could have been simply some data put in the keychain. That persists through app deletion.
I’ve had a few apps I’ve redownloaded months later, the only one from the developer, and my auth state was preserved.
I keep hearing that the Keychain data should be deleted, but my iCloud Keychain is filled with long-dead data
I have a specific debug setting to wipe the keychain.
Sign in with Apple also generates a persistent ID with each app. That could be used to fingerprint the user, but not the device.
After some iOS release though, every app started doing "new phone, who dis" regardless of the restoration strategy, so I stopped wasting my time.
At one point, google authenticator started marking its entries as "this device only". I don't know if they've backed off on that since then.