Abstract: Coevolution offers an adaptive evaluation method for problems where performance can be measured using tests. How to ensure the reliability and efficiency of evaluation is a central challenge in coevolution research. Recent studies have shown that within coevolutionary problem domains［0］, there exist a set of implicit dimensions that can structure the evolution information of problem domains, on which the performance of each individual can be accurately evaluated. Therefore, by means of dimension information of problems, reliable evaluation can in principle be provided using only a possible small subset of all tests. Based on the above studies, the characteristic outcome relationships between individuals possessed by dimension structures are first analyzed, and then an online dimension extraction approach based on the characteristic outcome relationships is proposed. Furthermore, a coevolutionary algorithm integrated with the dimension extraction approach is designed. The algorithm synchronously extracts the dimensions of the problem during execution and utilizes this information to provide accurate evaluation for individuals, and to guide selection and reservation so as to guarantee monotonic progress. Experimental results on abstract test problems demonstrate the feasibility of the proposed algorithm, and show that it outperforms other existing similar algorithms in both performance and accuracy of dimension extraction.