Various innovations in media encoding are presented herein. In particular, the innovations can reduce the computational complexity of encoding by selectively skipping certain evaluation stages during encoding. For example, based on analysis of decisions made earlier in encoding or based on analysis of media to be encoded, an encoder can selectively skip evaluation of certain coding tools (such as residual coding or rate-distortion-optimized quantization), skip evaluation of certain values for parameters or settings (such as candidate unit sizes or transform sizes, or candidate partition patterns for motion compensation), and/or skip evaluation of certain coding modes (such as frequency transform skip mode) that are not expected to improve rate-distortion performance during encoding.