I'm afraid you are right. I remember that some time ago, I have also been very surprised when finding out that each Ajax request, even when not navigating to another page, was triggering a rebuild of the component tree. I didn't use page scoped beans at that time, but a rebuild of the component tree also implies that the page scoped beans need to be recreated, because the page scope is stored in the root of the component tree (UIView).

I always use conversations that correspond one-to-one with pages. So I start the conversation when the page is loaded (in a page action) and I stop it when navigating to another page. In that case, the rebuild of the component tree has no effect on the beans that I need on the page.

Another thing you could look at, if you use RichFaces, is self rendered regions. See this link. If a region is marked with selfRendered set to true, the AJAX request will use the existent component tree, instead of rebuilding it based on the xhtml file. There are some nasty side effects you should take care of when using self rendered regions (mentioned in the documentation), so it has to be used with care. But not building a new component tree for each request will improve performance.

But first I'd advise you to have a look at variable resolving. Your profiling result is very recognizable to me. Looking up variables in stateful contexts can indeed be very expensive. Especially when you're trying to resolve variables, that cannot be found or that resolve to null. For example, if you have an EL expression #{bean.property}, a whole chain of resolvers will try to find something that is named 'bean'. That costs a lot of time, especially in situations where bean is non-existent or resolves to null. The best way to tackle this problem, is to add your own (temporary) resolver to the end of the chain. Your resolver will be able to detect the 'resolver misses'. Here's the resolver you could use for that:

public class MyELResolver extends ELResolver {

     @SuppressWarnings("unchecked")
     @Override
     public Class getCommonPropertyType(ELContext context, Object base) {
          return null;
     }

     @SuppressWarnings("unchecked")
     @Override
     public Iterator getFeatureDescriptors(ELContext context, Object base) {
          return null;
     }

     @SuppressWarnings("unchecked")
     @Override
     public Class getType(ELContext context, Object base, Object property) {
          return null;
     }

     @Override
     public Object getValue(ELContext context, Object base, Object property) {
          if (base == null) {
               System.out.println("Didn't find property " + property);
          }
          return null;
     }

     @Override
     public boolean isReadOnly(ELContext context, Object base, Object property) {
          return base != null
                    && (JSF.DATA_MODEL.isInstance(base)
                              || (base instanceof Collection<?>) || (base instanceof Map<?, ?>));
     }

     @Override
     public void setValue(ELContext context, Object base, Object property,
               Object value) {
     }

}

You can activate the resolver in your faces-config.xml:

  <application>
       <el-resolver>com.mycompany.myapp.MyELResolver</el-resolver>
  </application>

If you've found the cases where the resolver 'falls through the chain', resulting in a null value, you can try to change your xhtml so that the resolver will always find the variable. You can read more about this in the article of Dan Allen (section 'Resolving variables efficiently'):

Speed up your Data-Driven JSF/Seam Application by Two Orders of Magnitude

It's a very well-written article, indispensable if you're experiencing performance problems in a Seam/JSF application.