A memory die including a three-dimensional array of memory elements and a logic die including a peripheral circuitry that support operation of the three-dimensional array of memory elements can be bonded by die-to-die bonding to provide a bonded assembly. External bonding pads for the bonded assembly can be provided by forming recess regions through the memory die or through the logic die to physically expose metal interconnect structures within interconnect-level dielectric layers. The external bonding pads can include, or can be formed upon, a physically exposed subset of the metal interconnect structures. Alternatively or additionally, laterally-insulated external connection via structures can be formed through the bonded assembly to multiple levels of the metal interconnect structures. Further, through-dielectric external connection via structures extending through a stepped dielectric material portion of the memory die can be physically exposed, and external bonding pads can be formed thereupon.