Beyond Confidence Thresholding: Mitigating Cache Corruption in Test-Time OOD Detection

Out-of-distribution (OOD) detection aims to identify test samples deviating from in-distribution (ID) data. Recent test-time adaptation methods tackle this challenge by dynamically updating visual caches to retrieve negative labels that delineate the ID decision boundary. However, these methods implicitly assume balanced test streams and suffer catastrophic performance degradation under realistic, ID-dominated streaming deployments in challenging Near-OOD scenarios. In this work, we reveal that this failure stems from an inherent objective misalignment between margin-driven negative label retrieval and confidence-based cache updates. By projecting high-dimensional representations onto a scalar confidence metric, existing cache updates discard local neighborhood geometry, mistakenly purging informative boundary negatives in favor of coarse, uninformative concepts. To resolve this dilemma, we propose a graph-driven training-free framework that replaces heuristic scalar thresholding with a mutual $k$-NN bipartite graph constructed between visual embeddings and textual concepts, introducing a topological connectivity gate to govern cache admission via geometric proximity. By preserving the cross-modal manifold structure, our approach reliably mines informative negative labels that are acutely sensitive to the fine-grained boundary between ID and Near-OOD data. Extensive evaluations on challenging Near-OOD benchmarks demonstrate that our framework effectively prevents boundary collapse, outperforming state-of-the-art baselines by up to 10% AUROC under severe streaming imbalances while remaining highly competitive in balanced settings.