  For relational structures A, B of the same signature, the Promise Constraint
Satisfaction Problem PCSP(A,B) asks whether a given input structure maps
homomorphically to A or does not even map to B. We are promised that the input
satisfies exactly one of these two cases.
  If there exists a structure C with homomorphisms $A\to C\to B$, then
PCSP(A,B) reduces naturally to CSP(C). To the best of our knowledge all known
tractable PCSPs reduce to tractable CSPs in this way. However Barto showed that
some PCSPs over finite structures A, B require solving CSPs over infinite C.
  We show that even when such a reduction to finite C is possible, this
structure may become arbitrarily large. For every integer $n>1$ and every prime
p we give A, B of size n with a single relation of arity $n^p$ such that
PCSP(A, B) reduces via a chain of homomorphisms $ A\to C\to B$ to a tractable
CSP over some C of size p but not over any smaller structure. In a second
family of examples, for every prime $p\geq 7$ we construct A, B of size $p-1$
with a single ternary relation such that PCSP(A, B) reduces via $A\to C\to B$
to a tractable CSP over some C of size p but not over any smaller structure. In
contrast we show that if A, B are graphs and PCSP(A,B) reduces to tractable
CSP(C) for some finite digraph C, then already A or B has a tractable CSP. This
extends results and answers a question of Deng et al.
