Primitive-based evolutionary AutoML discovers novel state-of-the-art ML components by searching over programs built from low-level building blocks. While very expressive, these spaces have sparsely distributed good performing candidates. This poses great challenges in efficient search. Performance predictors have proven successful in speeding up search in smaller and denser Neural Architecture Search (NAS) spaces, but they have not yet been tried on these larger primitive-based search spaces. Through a unified graph representation to encode a wide variety of ML components, we train a binary classifier online to predict which of two given candidates is better. We then present an adaptive mutation method that leverages the learned binary predictor and show how it improves local search. We empirically demonstrate our method speeds up end-to-end evolution across a set of diverse problems including a 3.7x speedup on the symbolic search for ML optimizers and a 4x speedup for RL loss functions.