Large Language Models (LLMs) have demonstrated strong capabilities in interpreting lengthy, complex legal and policy language. However, their reliability can be undermined by hallucinations and inconsistencies, particularly when analyzing subjective and nuanced documents. This challenge is especially critical in contexts such as medical coverage policy review, where accurate interpretation is essential. Although prior work has employed LLMs for such reasoning tasks using tailored prompts, the need to invoke the model for every decision introduces significant inference costs, posing a barrier to scalable deployment. In this paper, we address these challenges by minimizing the number of LLM inferences required. We introduce a novel methodology that combines a coverage-aware retriever with symbolic rule-based reasoning. By extracting governing policy language and encoding coverage policies as facts and rules, our system produces interpretable rationales for decisions while reducing the need for frequent LLM calls. Notably, our approach achieves a 44% reduction in inference cost alongside a 4.5% improvement in F1 score, demonstrating both efficiency and effectiveness.