Recent theoretical investigations suggest that the rate of river incision into bedrock depends nonlinearly on sediment supply, challenging the common assumption that incision rate is simply proportional to stream power. Our measurements from laboratory abrasion mills support the hypothesis that sediment promotes erosion at low supply rates by providing tools for abrasion, but inhibits erosion at high supply rates by burying underlying bedrock beneath transient deposits. Maximum erosion rates occur at a critical level of coarse-grained sediment supply where the bedrock is only partially exposed. Fine-grained sediments provide poor abrasive tools for lowering bedrock river beds because they tend to travel in suspension. Experiments also reveal that rock resistance to fluvial erosion scales with the square of rock tensile strength. Our results suggest that spatial and temporal variations in the extent of bedrock exposure provide incising rivers with a previously unrecognized degree of freedom in adjusting to changes in rock uplift rate and climate. Furthermore, we conclude that the grain size distribution of sediment supplied by hillslopes to the channel network is a fundamental control on bedrock channel gradients and topographic relief.