The man page for GNU find describes -execdir in part thusly:

Like -exec, but the specified command is run from the subdirectory containing the matched file, which is not normally the directory in which you started find.

So there is no real subtlety involved. -exec invokes the command from the directory that you run find from (and thus needs to provide the path either relative to that directory or absolute from the root), and -execdir invokes the command from the directory containing the file and thus doesn't need to provide the full path, so does not.

To get the behavior you are after, you should use -exec rather than -execdir.

If you didn't need the confirmation, you could have used -delete instead. For large number of files that is also likely to be more efficient as it avoids having to invoke rm time and time again.

The man page for GNU find describes -execdir in part thusly:

Like -exec, but the specified command is run from the subdirectory containing the matched file, which is not normally the directory in which you started find.

So there is no real subtlety involved. -exec invokes the command from the directory that you run find from (and thus needs to provide the path either relative to that directory or absolute from the root), and -execdir invokes the command from the directory containing the file and thus doesn't need to provide the full path, so does not.

To get the behavior you are after, you should use -exec rather than -execdir.

You can demonstrate this behavior by replacing your rm invocation with for example echo to simply print the list of parameters (in this case, the file name). Or use -print which does that without needing to invoke an external command. (Note: -print is also the default action if none is given.)

If you didn't need the confirmation, you could have used -delete instead. For large number of files that is also likely to be more efficient as it avoids having to invoke rm time and time again.