This was almost certainly my fault, but as I look at the implementation of Sets.cartesianProduct, I think its contains method made the assumption that ImmutableSet.asList().indexOf was O(1), which is no longer the case for Android. It should probably get a specific contains implementation that actually is O(sets), not O(sets*setSize).