To enable statistical static timing analysis, for each cell in a digital library, a timing model that considers variations must be characterized. In this paper, we propose a dynamic method to accurately and efficiently characterize a cell's delay and output slew as a function of random mismatch variations. Based on a tight error bound for characterization using partial devices, our method sequentially performs simulations based on decreasing importance of devices and stops when the error requirement is met. Results on an industrial 32nm library demonstrate that the proposed method achieves significantly better accuracy-efficiency trade-off compared to other partial finite differencing approaches. © 2012 ACM.