The key computational challenge is that the marginal prob-
z∈Z p(y | x, z) p(z | x) involves a sum-
mation over all documents z in the knowledge corpus Z.
We approximate this by instead summing over the top k
documents with highest probability under p(z | x)—this is
reasonable if most documents have near zero probability.
Even with this approximation, we still need an efﬁcient way
to ﬁnd the top k documents. Note that the ordering of doc-
uments under p(z | x) is the same as under the relevance
score f (x, z) = Embedinput(x)(cid:62)Embeddoc(z), which is an
inner product. Thus, we can employ Maximum Inner Prod-
uct Search (MIPS) algorithms to ﬁnd the approximate top k
documents, using running time and storage space that scale
sub-linearly with the number of documents (Ram & Gray,
2012; Shrivastava & Li, 2014; Shen et al., 2015).
To employ MIPS, we must pre-compute Embeddoc(z) for
every z ∈ Z and construct an efﬁcient search index over
REALM