Resolving the seismic velocity heterogeneity in the lowermost mantle is essential for understanding the chemical and dynamical processes operating in the boundary layer between the core and the mantle. Several regions of the lowermost mantle appear to have abrupt increases in shear velocity several hundred kilometers above the core-mantle boundary, at the top of the D'' layer. This structure is revealed by seismic wave energy refracted by the velocity increase, resulting in an extra arrival (Scd) in teleseismic S wavetrains at distances from 65¿ to 95¿. Anomalies in differential travel times of the extra arrival relative to direct S (which turns at shallower depths in the midmantle) or ScS (which reflects from the core-mantle boundary below the velocity increase) provide probes of the velocity heterogeneity in the lowermost mantle with better vertical resolution than provided by conventional ScS-S measurements. We explore the spatial patterns in Scd-S, ScS-Scd, and ScS-S differential time residuals for paths through the lower mantle beneath Alaska, Eurasia, and India (all being regions with coherent Scd phases) to place constraints on the strength and scale lengths of shear velocity heterogeneity and/or variable topography of the lower mantle discontinuity in these regions. The observed patterns are poorly predicted by existing global tomographic models. Significant small-scale heterogeneity, with lateral length scales of 200--500 km or less, exists even within regions that display a relatively uniform D'' discontinuity structure over scale lengths of 1500--2000 km. The strongest travel time variations are associated with structure above the D'' region, in contrast to common assumptions. Rapid lateral fluctuations in ScS-Scd differential times suggest that the anomalies accumulate within a relatively thin zone, less than the overall thickness of D''. Correlations among the differential time anomalies indicate that Scd variations, ranging over about 4 s, are more pronounced than ScS variations and that the travel time fluctuations accumulate near the top of D'' due to shear velocity heterogeneity of ¿4% within a 50 km thick region and/or discontinuity topography of ¿50 km, with scale lengths of 200--500 km. It appears that the upper portion of D'' is much more heterogeneous than the deeper region. Heterogeneity within the layer appears to be decoupled from that at the top of the layer or in the overlying mantle.¿ 1997 American Geophysical Union