What you're describing is more in spirit with the intent of a lockfile and worth exploring by package managers. But I do think a heuristic could be conceived fo

What you're describing is more in spirit with the intent of a lockfile and worth exploring by package managers. But I do think a heuristic could be conceived for the lockfile-was-rebuilt situation: If a single top-level dependency declared with ^ or ~ was present in the lockfile when the existing resolution was still valid. Ideally the onus is on the package manager to provide metadata in the lockfile for the strategies it took when generating.