When Do Cheap Evaluations Preserve the Best Composed Program?

Cheap evaluations are useful for searching over composed programs only when they identify candidates that remain strong after their continuations are optimized. We study this question for a finite library of first decisions. A least-squares decomposition separates each composed-value gap into a component aligned with the cheap ranking and a constrained continuation residual. The relative size of these components gives a one-sided condition for preserving the cheap winner and a sharp boundary beyond which a pairwise ordering cannot reverse. The same geometry extends to programs with multiple legs and yields certificates for retaining a small candidate set. Guided by this analysis, we evaluate an adaptive rule that reads continuations until the remaining candidates cannot challenge the incumbent, and a promotion rule that carries candidates through weak early fidelities. In simulated control archives, the geometric certificates agree with observed orderings and adaptive reads recover the best composed choice at reduced evaluation cost. On public multi-fidelity optimization benchmarks, the promotion rule improves final-fidelity regret against standard budget-matched schedules.