Retrieve, Reason, Recover: Evidence-Grounded ICD Clinical Coding under Long Tails and Missing Labels

Automated International Classification of Diseases (ICD) coding from clinical narratives faces three interrelated challenges; severe long-tail code distributions with sparse training examples, systematically incomplete labels from clinical undercoding, and a lack of interpretable evidence linking predictions to documentation. We propose HERA-ICD, a two-stage framework that reframes ICD coding as retrieval-augmented classification. Stage 1 performs hierarchical retrieval at document, code, and span granularities, enabling prototype-based few-shot and description-based zero-shot prediction for rare codes. In Stage 2, we construct per-instance graphs, whose topologies dynamically adapt to the retrieved evidence. A Graph Attention Network then reranks the candidates using document-specific reasoning. To handle missing labels, we integrate positive-unlabeled learning with graph-based label completion, propagating soft positives through the ICD hierarchy. We theoretically prove three key properties of our framework: the non-negative PU objective is unbiased and consistent, the generalization gap of the retrieval-then-rerank architecture is independent of vocabulary size, and prototype scoring generalizes from fewer than ten examples. Consequently, experiments on MIMIC-III and MIMIC-IV demonstrate consistent improvements over state-of-the-art methods, particularly on rare codes, while providing traceable evidence linking predictions to specific clinical spans.