A three-dimensional memory device includes alternating stacks of insulating layers and electrically conductive layers located over a semiconductor material layer, and memory stack structures extending through one of the alternating stacks. Laterally-undulating backside trenches are present between alternating stacks, and include a laterally alternating sequence of straight trench segments and bulging trench segments. Cavity-containing dielectric fill structures and contact via structures are present in the laterally-undulating backside trenches. The contact via structures are located within the bulging trench segments. The contact via structures are self-aligned to sidewalls of the alternating stacks. Additional contact via structures may vertically extend through a dielectric alternating stack of a subset of the insulating layers and dielectric spacer layers laterally adjoining one of the alternating stacks.