> I know an algorithm BDS exists, which speeds up the authentication path generation, but how big is the speedup compared to the standard implementation?

I assume by "standard implementation", you mean one that regenerates the entire tree on each signature.

When BDS outputs an authentication path, it needs to compute $O(h)$ WOTS+ public keys (to get ready for the next authentication path); what this translates in practice for $h=20$ is 10 public keys per signature (actually, it alternates between 9 and 10 between successive signatures); this compares to 1,048,575 public keys for the "standard implementation"; because the cost of computing these public keys is the bulk of the work when generating an authentication path, we're looking at a factor of 100,000 speed up (!).

And, if BDS isn't fast enough for you, there are other algorithms, such as [Fractal][1] or one I have dubbed [BKN][2] (the authors didn't give it an official name) that require even less computation (possibly at the cost of increased storage for holding intermediate Merkle tree nodes).

> The keys still need to be generated in order to produce the XMSS leaves, thus even if one would save all leaves, it still takes a lot of time to compute all 2^h leaves. How can one speed up the leaves generation?

You are correct; fancy Merkle tree walking algorithms don't help during the initial key generation; here are some ideas that might give some speed-up (some of which are easier than others):

- Use an XMSS^MT parameter set instead; for example, XMSSMT-SHA2_20/2_256 also gives you 1+ million signatures, and it makes key generation much faster

- Are you using a SHAKE-based parameter set or a SHA-512 parameter set?  Consider switching to the equivalent SHA-256 parameter set - in my experience, SHA-256 is considerably faster in this context (at least on the CPUs I've tried them out on).

- If you know that you really only need (say) 100,000 signatures to be generated with this private key, consider generating only the first 100,000 WOTS+ public keys, and use arbitrary values for the public keys past that.  You wouldn't be able to sign with these arbitrary values - however if you're assumption about the number of signatures is correct, you will never need to.

- You can speed up the hash function using AVX instructions (or [SHA-NI instructions][4] in the case of SHA-256)

- You can build separate parts of the tree using different threads.

- You might consider using [LMS][3] rather than XMSS (LMS is several times faster for equivalent parameter sets)

[1]: http://markus-jakobsson.com/papers/jakobsson-ctrsa03.pdf
[2]: https://dl.acm.org/doi/10.1016/j.tcs.2006.11.029
[3]: https://datatracker.ietf.org/doc/rfc8554/
[4]: https://software.intel.com/content/www/us/en/develop/articles/intel-sha-extensions.html