Systems and techniques for evaluating assertions during circuit verification are described. During operation, m semantically equivalent assertions can be identified, wherein each of the m semantically equivalent assertions is evaluated using n logical expressions. Next, a set of vectors based on the m semantically equivalent assertions can be determined, wherein each vector element corresponds to a logical expression that is used for evaluating one of the m semantically equivalent assertions. The m semantically equivalent assertions can then be evaluated, in parallel, using the set of vectors.