Ad Exchange demand will usually bring a small uplift over adSense only when replaced like for like. The exception I see is on high CTR adsense units (ad exchange pays per impression so it's hard to compete with adsense if its picking up lots of clicks). I'd bet you'd see greater uplift from re-assessing your Criteo set-up. It's very easy for to have someone like Criteo passing back to adsense in a way that costs you more revenue than it makes. In fact, I'd say at least 75% of the sites I work who have this set up and suppressing their own revenue. (happy to PM you a link about this, but don't want to post it in case it breaks the self-promotion rules)

Moving to GAM makes most sense if you are introducing additional demand. Which, with 4-5 million visitors a day you absolutely should be doing.

[oops - double post]

It's 4-5 milion visitors/month :)

4-5 million a day would be nice though wouldn't it ! :) Sorry - I did mean per month. Our rule of thumb is that a million PV/month from tier 1 geos is about the threshold for making the transition to header or header + exchange worthwhile.