In the introspective computing model, on-chip resources are divided into those used for computing and those used for introspection. The introspective processor or processors may perform sophisticated online observation and analysis of the computation and use the extracted information to improve performance, reliability, or other system properties. This paper considers the possibility of online construction of graphical models representing program behavior and the use of such models to perform better branch prediction. The particular graphical model that we employ is that of decision trees. We explore the space of decision tree models, consider the feasibility of implementation of the introspective processor, then present the performance of this model on the SPEC2000 benchmark suite.