On a printout and even inside the vault itself. You only need the key the first time you unlock the vault on a device. After that the key can be encrypted locally with just the master password or kept in the TPM (or the platform's equivalent).
To lose your passwords, you have to lose literally every device you have LastPass on and your printout and any E2EE backups of the key (e.g. to iCloud.)
