Since star identification algorithms most likely yield multiple matching candidates, validation algorithms are required for star trackers. Traditional validation is performed in an iteratively cascaded way by incrementally introducing new star points for help, costing plenty of inefficient lookups and complex combinations, but leading to nondeterministic results only. Focusing on this problem, this paper considers a novel validation idea that the attitude estimate perturbation caused by bounded measuring noises should be bounded as well. As a result, a two-step validation algorithm is proposed following a noniterative deterministic structure. Theoretical analyses and simulation examples are both given to demonstrate the algorithm.