ReHoPER: Receding-Horizon Planning for Enhanced Reasoning

We propose ReHoPER, an inference-only, zero-shot method that improves large language models’ reasoning by generating and answering intermediate questions along multiple paths before the final answer. It iteratively plans a horizon of candidate intermediate questions, selects one to answer, and replans from the updated history. ReHoPER is task-agnostic, using the same generic instructions across datasets and models without labeled data or task-specific prompt design. Across multiple datasets, including a new controlled benchmark for compositional reasoning, ReHoPER outperforms strong baselines, with the largest gains in the most compositional settings. We will release our implementation and the iLLC generator to support future work.