8th Annual Conference on Robot LearningWhile unmanned aerial vehicles (UAVs) are proven beneficial in search and rescue (SAR) missions, real-world scalability remains challenging due to limited high-level decision-making capabilities and rarely addressed human-in-the-loop command and communications. Recent LLM-modulo planning frameworks combine the broad knowledge of LLMs with domain-specific reasoning for more robust planning, yet adapting them for online SAR planning requires further changes to scale while preserving real-time performance. We introduce Say-REAPEx, an LLM-modulo online planning framework that discards irrelevant or low-feasibility actions using domain knowledge to shrink the planning space, and leverages online heuristic search to reduce uncertainty in future rewards. In validation tests based on realistic SAR missions, Say-REAPEx is 70% more efficient than existing frameworks while achieving comparable or better success rates.