The "Small Model Property" lemma says that if a monadic formula $\phi$ (i.e. over a monadic signature - contains only constants and (monadic) unary predicates) with $k$ unary predicates is satisfiable, then it is satisfiable in a structure with at most $2^k$ elements.
Also - the satisfiability problem for monadic signature is decided (follows from the lemma above).
So, is it true that if a signature contains only constans and binary predicates, then any satisfiable formula $\phi$ over this signature with $k$ binary predicates is satisfiable in a structure with at most $4^k$ elements? - It came to my mind because the $2^k$ "comes from" going all over the possible definitions of the predicate - it is unary so only $2$ options available. In the other case - there are $4$ options so it may be also true (and therefore to any signature with $n$-nary predicates would correspond $n^k$).