We report the results of a sensitive K-band survey of Herbig Ae/Be disk sizes using the 85-m baseline Keck Interferometer. Targets were chosen to span the maximum range of stellar properties to probe the disk size dependence on luminosity and effective temperature. For most targets, the measured near-infrared sizes (ranging from 0.2 to 4 AU) support a simple disk model possessing a central optically-thin (dust-free) cavity, ringed by hot dust emitting at the expected sublimation temperatures (T_sub~1000-1500K). Furthermore, we find a tight correlation of disk size with source luminosity R propto L^(1/2) for Ae and late Be systems (valid over more than 2 decades in luminosity), confirming earlier suggestions based on lower-quality data. Interestingly, the inferred dust-free inner cavities of the highest luminosity sources (Herbig B0-B3 stars) are under-sized compared to predictions of the optically-thin cavity model, likely due to optically-thick gas within the inner AU.