First, you need to reflect what, in fact, is a CFT. The abstract answer is that
It's a set of correlation functions ⟨Oi(x)Oj(y)⋯Ok(z)⟩ which satisfy certain axioms, like the conformal covariance or the short distance behavior when x→y.
These multi-point functions can be encoded in the generating function, so the same set of axioms can be phrased as
It's a functional Γ[ϕi]=⟨exp∫∑iOi(x)ϕi(x)dnx⟩ which satisfies certain set of properties.
Now, consider a gravity theory in an asymptotically AdS spacetime, and consider its partition function given the boundary values of ϕi. It gives a functional
Zs(ϕi|∂(AdS)=ϕi)
This functional automatically satisfies the properties which a CFT generating function satisfies. Conformal covariance comes from the isometry of the AdS, for example. Therefore, abstractly, it is a CFT. (A duck is what quacks like a duck, as a saying goes.)
Now this line of argument does not say why Type IIB on AdS5× S5 gives N=4 SYM. For that you need string theory. But everything above this paragraph is just about axiomatics.
So, when there is a consistent theory of gravity on AdSd+1 other than string/M-theory, you still get CFTd.
This post has been migrated from (A51.SE)