fast inference in random forests?

Try randomly sampling trees from the forest (with replacement) and taking a majority vote of the sampled trees. If p is the fraction of all trees that vote "yes", and p' is the fraction of sampled trees that vote "yes", then |p - p'| <= e with probability 1-delta, provided you sample at least (1/e^2) log (1/delta) trees. Note that this number of samples is independent of the number of trees in the forest.

Bucila et al's approach is effective, largely because it allows you to generate a huge set of training data that allows the training of a replica model for the random forest.

There is a simpler method, however, that can produce reasonable compression more easily. Simply go through some data from a held-out training set and simply keep the trees that have higher mutual information relative to your target variable. If you don't have additional training data, you unlabeled data and use mutual information relative to your original model. Many of the trees in the random forest are simply emulating a random number generator and can be eliminated with no important loss of information.

If you have doubts about the efficacy of sampling trees from the ensemble, see Hernandez-Lobato et al. 2009. They give a clearer presentation of the computation for the binary classification case in Soto et al. 2010.

I suspect that the confidence bounds in the above papers will be tighter than the Chernoff bound Umar gives above, but that is just my intuition. Certainly the Chernoff bound will be easier to compute.

What you seem to be after is described in this paper: Bucila et al, Model Compression. It's also unfortunately approximate, but you don't necessarily want an exact method here, or you'd be tied to the performance of the ensemble in the worst case.