ReHoPER: Receding-Horizon Planning for Enhanced Reasoning
ReHoPER is a zero-shot, inference-only reasoning method that improves LLM compositional reasoning by formulating it as receding-horizon planning. At each step, it generates a short horizon of candidate intermediate questions, answers one, updates its history, and replans across multiple stochastic paths before aggregating by majority vote. The paper reports consistent gains over self-consistency on MuSR, MoreHopQA, and a new controlled benchmark iLLC, with the largest improvements on the hardest compositional tasks. While the method is task-agnostic, its accuracy gains come at a significant inference-time cost.
ReHoPER is a well-executed inference-time method that meaningfully improves compositional reasoning without task-specific prompts or labeled data. The gains are strongest on hard benchmarks and hold across diverse model families and prompting prefixes. However, the method is expensive—often several times slower than simple self-consistency—and the comparison conflates architectural novelty with a particular allocation of inference budget. The authors also slightly mischaracterize Tree-of-Thoughts as requiring labeled data, which weakens the framing that ReHoPER uniquely removes oracle dependence.
The receding-horizon formulation is intuitive and crisply evaluated. Planning ablations in Table 2 show that full ReHoPER outperforms both the no-replanning and no-look-ahead variants, and Appendix E confirms that the candidate-selection rule successfully prevents within-path redundancy. The new iLLC benchmark provides a useful controlled diagnostic, and the aggregation analysis demonstrates that combining predictions across steps and paths improves reliability. As reported in Section 5.1, "On average (bottom-right block), ReHoPER improves accuracy by 5.8pp for IO, 8.4pp for CoT, and 6.4pp for PS."
The primary limitation is compute cost. On Llama 3.1 70B and iLLC L2-6, ReHoPER takes 11:15 versus only 2:37 for SC61 and 9:04 for SC181 (Table 4); on easier near-ceiling tasks the gains are marginal or negative, so the method trades substantial latency for accuracy that is unevenly distributed. The framing of prior work is also partially misleading: the authors write that Tree-of-Thoughts "often depend on labeled data (e.g., solved examples for learning or retrieving strategies) or a manually crafted reasoning structure" (Section 1), yet the original ToT framework relies on zero-shot LM self-evaluation and generic search heuristics without labeled demonstrations. This mischaracterization weakens the claim that ReHoPER uniquely removes the need for oracle data. Additionally, matching 61 total candidates conceals a structural difference—ReHoPER's predictions are correlated along paths, whereas SC samples are i.i.d.—so a like-for-like comparison should arguably include search baselines run with equivalent forward-pass budgets.
The evidence broadly supports the core claim that adaptive intermediate questioning helps compositional reasoning. On iLLC L2-6, ReHoPER yields "14.3pp for IO, 25.4pp for CoT, and 20.9pp for PS" over SC (Section 5.1), and the macro-averaged gains remain positive across benchmark families. However, the authors fairly note that "tasks that are either more straightforward or closer to ceiling (e.g., iLLC L1-{w} variants) show only modest gains and occasionally small regressions, suggesting limited headroom for further improvement through additional planning" (Section 5.1). Comparisons to Least-to-Most and Self-Refine (Table 3) favor ReHoPER on harder L2 variants, but these baselines were not designed for zero-shot use here—LtM requires few-shot exemplars and SR was run without task-specific feedback prompts—so the comparison is informative but not strictly controlled.
Reproduction is feasible but computationally demanding. The authors specify exact checkpoints, quantization configs, and vLLM deployment in Appendix K, publish code and the iLLC generator, and provide full prompts in Appendix L. The reproducibility statement notes that "Section 3.2 specifies the ReHoPER planning, rollout, termination, and answer-aggregation procedure." Independent replication will still require substantial GPU hours: eight models, three prefixes, six paths, and up to ten steps per path. A critical efficiency detail is that "For efficiency, we batch the three prefix-specific conversations in a single inference request for all methods" (Section 5.6); omitting this would make runtime reproduction inconsistent.
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 iLLC, a new controlled benchmark for compositional reasoning, ReHoPER outperforms strong baselines, with the largest gains in the most compositional settings. Our implementation and the iLLC generator are publicly available to support future work.
Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.
No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.