oarse-grained　response　selection　is　a　fundamental　and　essential　subsystem　for　the　widely　used　retrievalbased　chatbots,　aiming　to　recall　a　coarse-grained　candidate　set　from　a　large-scale　dataset.　The　dense　retrievaltechnique　has　recently　been　proven　very　effective　in　building　such　a　subsystem.　However,　dialogue　denseretrieval　models　face　two　problems　in　real　scenarios:　(1)　the　multi-turn　dialogue　history　is　re-computed　ineach　turn,　leading　to　inefficient　inference;　(2)　the　index　storage　of　the　offline　index　is　enormous,　significantlyincreasing　the　deployment　cost.　To　address　these　problems,　we　propose　an　efficient　coarse-grained　responseselection　subsystem　consisting　of　two　novel　methods.　Specifically,　to　address　the　first　problem,　we　proposethe　Hierarchical　Dense　Retrieval.　It　caches　rich　multi-vector　representations　of　the　dialogue　history　and　onlyencodes　the　latest　user’s　utterance,　leading　to　better　inference　efficiency.　Then,　to　address　the　second　problem,we　design　the　Deep　Semantic　Hashing　to　reduce　the　index　storage　while　effectively　saving　its　recall　accuracynotably.　Extensive　experimental　results　prove　the　advantages　of　the　two　proposed　methods　over　previousworks.　Specifically,　with　the　limited　performance　loss,　our　proposed　coarse-grained　response　selection　modelachieves　over　5x　FLOPs　speedup　and　over　192x　storage　compression　ratio.　Moreover,　our　source　codes　havebeen　publicly　released.　©　2023　Association　for　Computing　Machinery.　All　rights　reserved.