Dead reckoning drift and acoustic positioning
With GPS off the table entirely, underwater vehicles fall back on dead reckoning as a baseline: starting from a known position and integrating velocity and heading measurements over time to estimate where the vehicle has moved to. This is the same core idea as wheel odometry on a land robot, but underwater it's typically driven by a combination of a doppler velocity log, which measures speed relative to the seafloor using acoustic pulses, and an inertial measurement unit tracking orientation and acceleration. As with any dead reckoning approach, small measurement errors don't cancel out, they accumulate, so the estimated position drifts further from the true position the longer the vehicle travels without an external correction. Underwater, this drift problem is worse than on land because there's no equivalent of an occasional GPS ping to reset the error, so it just keeps growing unchecked for as long as the vehicle stays submerged.
To bound that drift, underwater operations use acoustic positioning systems, with ultra-short baseline, or USBL, being one of the most common. A USBL system works by having a transceiver, often mounted on a surface ship, send an acoustic signal to a transponder on the underwater vehicle and measure both the time delay and the angle at which the return signal arrives. From that timing and angle, the system can compute the vehicle's range and bearing relative to the ship, giving a position fix without needing satellites. This isn't free of tradeoffs either: acoustic positioning accuracy degrades with range and depth, and it depends on a surface reference point being present and within acoustic reach, so it works well for ROVs tied to a surface ship but is less directly useful for a long-range AUV operating far from any surface vessel.