Deleted file before saving it

If Keynote behaves like Pages when you exit the application without triggering autosave by initially saving the document, then the application cleans up all temporary content associated with that session and there is nothing to back up or recover.

In order for you to delete a Keynote presentation, it would have needed to be manually saved once so that it appears in your filesystem. If that is the case, then it would be on a Time Machine backup, or in your unemptied Trash. Otherwise, it is gone.

Do you have a backup?

When I perform a search through the entire /Users/username/Library folder for any filename (*.key), nothing is found while I have a new Keynote document open, but not initially saved.