  Nearest neighbor machine translation augments the Autoregressive
Translation~(AT) with $k$-nearest-neighbor retrieval, by comparing the
similarity between the token-level context representations of the target tokens
in the query and the datastore. However, the token-level representation may
introduce noise when translating ambiguous words, or fail to provide accurate
retrieval results when the representation generated by the model contains
indistinguishable context information, e.g., Non-Autoregressive
Translation~(NAT) models. In this paper, we propose a novel $n$-gram nearest
neighbor retrieval method that is model agnostic and applicable to both AT and
NAT models. Specifically, we concatenate the adjacent $n$-gram hidden
representations as the key, while the tuple of corresponding target tokens is
the value. In inference, we propose tailored decoding algorithms for AT and NAT
models respectively. We demonstrate that the proposed method consistently
outperforms the token-level method on both AT and NAT models as well on general
as on domain adaptation translation tasks. On domain adaptation, the proposed
method brings $1.03$ and $2.76$ improvements regarding the average BLEU score
on AT and NAT models respectively.
