In high-level scene interpretation, it is useful to exploit the evolving probabilistic context for stepwise interpretation decisions. We present a new approach based on a general probabilistic framework and beam search for exploring alternative interpretations. As probabilistic scene models, we propose Bayesian Compositional Hierarchies (BCHs) which provide object-centered representations of compositional hierarchies and efficient evidence-based updates. It is shown that a BCH can be used to represent the evolving context during stepwise scene interpretation and can be combined with low-level image analysis to provide dynamic priors for object classification, improving classification and interpretation. Experimental results are presented illustrating the feasibility of the approach for the interpretation of facade images.