PaperlayerView exact revision on arXiv

Source-linked AI summary

ReHoPER: Receding-Horizon Planning for Enhanced Reasoning

Saeed Ahmadnia, Cornelia Caragea

arXiv:2610.00940v1cs.CLcs.AIcs.LG

TL;DR

Compositional reasoning remains difficult for language models, while oracle-free prompting methods often use linear reasoning or fixed plans. ReHoPER adaptively plans and answers intermediate questions across multiple paths at inference time; it improves over strong baselines in most settings, with the largest gains on harder compositional tasks.

  • Problem

    Even state-of-the-art models struggle to integrate multiple pieces of evidence and handle long-range dependencies, while oracle-free prompting methods mostly follow linear reasoning patterns.

    Source: §1 · pp. 1–2

  • Method

    ReHoPER uses generic instructions at inference time to plan candidate intermediate questions, answer one, replan from the updated history, and aggregate predictions across multiple paths.

    Source: §1 · p. 2

  • Results

    ReHoPER improves over Self-Consistency and other strong baselines in most settings, with the largest gains on harder compositional tasks; overall averages are 62.3–66.3% for ReHoPER versus 56.1–59.9% for Self-Consistency.

    Source: §5.1 · p. 7, §6 · pp. 9–10

  • Takeaways & Limitations

    The controlled iLLC benchmark helps expose how performance changes with compositional difficulty, and the largest reported gains occur on harder compositional tasks.

    Source: §5.1 · p. 6, §6 · p. 10

    The method uses only the task test example and does not rely on task-specific instructions, labeled examples, or additional unlabeled data.

    Source: §3.1 · p. 3

Abstract

from arXiv · show

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.

1 Introduction

ReHoPER addresses the gap between oracle-free, task-agnostic prompting and richer reasoning plans by adaptively generating and answering intermediate questions. It evaluates this inference-only method across datasets and models, alongside a new controlled compositional benchmark.

1 Introduction

  • Multi-step and compositional benchmarks show that even state-of-the-art models struggle to integrate multiple pieces of evidence and handle long-range dependencies.Existing inference-time approaches can depend on labeled data or manually crafted task-specific reasoning structures.Source: §1 · pp. 1–2
  • ReHoPER generates and answers intermediate questions for each instance, using the same generic instructions across tasks, models, and answer-format prefixes without task-specific labeled data or demonstrations.It combines predictions from multiple paths before making a final prediction.Source: §1 · p. 2
  • ReHoPER alternates planning and execution: it answers the first unresolved question from a generated list, updates the reasoning state, and replans.Replanning can revise, refine, or discard previously proposed questions.Source: §1 · p. 2
  • The paper introduces iLLC, a controlled diagnostic benchmark for compositional execution, and provides its data generator and the ReHoPER implementation publicly.The study also compares against strong baselines and analyzes design choices and reasoning trajectories.Source: §1 · p. 2

2 Related work

Prior prompting methods range from linear reasoning and fixed decompositions to search and iterative self-feedback. ReHoPER combines lightweight planning with adaptive question selection across multiple reasoning paths.

2 Related work

  • Zero-shot Chain-of-Thought elicits step-by-step reasoning but does not require a complete outline, while Plan-and-Solve explicitly separates planning from execution.The paper identifies missing steps and omission errors as limitations of zero-shot Chain-of-Thought.Source: §2 · p. 2
  • Self-Ask and Least-to-Most use curated exemplars or predefined templates and execute an upfront decomposition in a single pass.Self-Discover removes manual design but commits to a fixed plan before solving.Source: §2 · p. 2
  • ReHoPER uses generic instructions to generate intermediate questions, selects one from a short plan, and updates the plan after the answer so later questions reflect new information.It gathers predictions across multiple paths and aggregates them.Source: §2 · pp. 2–3
  • ReHoPER connects to receding-horizon control, but uses the model’s predictions of the goal question as an implicit evaluation signal rather than an externally defined reward function.Self-consistency, tree search, and self-feedback methods instead use independent trajectory sampling, explicit search, or iterative revision.Source: §2 · p. 3

3 Methodology

ReHoPER is an inference-only method that uses multiple stochastic paths and repeatedly plans candidate intermediate questions, answers one, and replans from the updated history. Its predictions are aggregated across paths and steps.

3.2 ReHoPER

  • ReHoPER runs multiple stochastic paths, each organized as intermediate question-answer pairs generated through receding-horizon planning.At each step, it looks ahead to form candidate questions, executes one, and replans from the updated history.Source: §3 · p. 3, §3.2 · pp. 3–4

3.1 Problem statement

  • The task setting is to predict a label from an optional context and goal question using an instruction-tuned model, without task-specific instructions, labeled examples, or extra unlabeled data.The objective is to match the ground-truth label.Source: §3.1 · p. 3

3.2 ReHoPER

  • Each path begins with a goal-question prediction, then repeatedly plans candidate questions, selects the first unanswered candidate, answers it, updates the history, and predicts again.A path ends when no valid unanswered candidate remains or the user-defined step cap is reached.Source: §3.2 · p. 4
  • The final prediction is the most frequent value among predictions from the initial step and all path steps, with ties broken alphabetically.Because the initial history is identical across paths, its prediction is counted at most once.Source: §3.2 · p. 4

4 Experimental setup

The experiments cover natural-language reasoning benchmarks and controlled compositional execution, with diverse instruction-tuned models. ReHoPER is compared with matched-prefix Self-Consistency and other prompting baselines under a fixed path and step budget.

4.1 Datasets and tasks

  • MuSR tests long-context narrative reasoning, MoreHopQA tests multi-hop evidence aggregation, and iLLC tests controlled compositional execution.iLLC varies the character position extracted from each word and the number of words, allowing difficulty to be adjusted without external knowledge.Source: §4.1 · pp. 4–5

4.2 Language models

  • The evaluation includes instruction-tuned dense models from Llama, Gemma, Phi, and Mistral, and sparse Mixture-of-Experts models including gpt-oss and Qwen3.Quantized AWQ or GPTQ variants are used when needed for larger models; Qwen3 is evaluated with and without thinking enabled.Source: §4.2 · p. 5

4.3 Baselines and setup details

  • The core baseline is Self-Consistency with 61 sampled completions under each of IO, CoT, and PS prefixes; additional references include Self-Discover and, on iLLC, Least-to-Most, CoT, and Self-Refine.ReHoPER uses six paths and a maximum depth of ten steps, producing up to 61 candidate answers for majority voting.Source: §4.3 · p. 5
  • Planning ablations remove either replanning or look-ahead while retaining the full method’s answering, history-update, prediction, and aggregation procedures.The ablations are evaluated on MuSR MM, MoreHopQA, and iLLC L2-4.Source: §4.3 · p. 6

5 Results and discussion

ReHoPER improves on Self-Consistency across prompting styles, with the strongest gains in harder compositional settings. Ablations and compute comparisons favor adaptive planning, while the value of adding paths versus deeper steps varies by task.

5.1 ReHoPER results

  • 5.8pp (IO), 8.4pp (CoT), and 6.4pp (PS) are average gains over SC; ReHoPER averages 62.3–66.3%, versus SC’s 56.1–59.9% and SD’s 43.4%.Gains are reported across models, datasets, and prefixes; ReHoPER tends to be strongest and most reliable with PS.Source: §5.1 · pp. 6–7
  • 14.3pp (IO), 25.4pp (CoT), and 20.9pp (PS) are ReHoPER’s gains on iLLC L2-6, while straightforward or near-ceiling variants show smaller gains and occasional regressions.Across iLLC, performance generally declines from L1 to L2 and as the number of words increases; ReHoPER performs best relative to baselines in harder settings.Source: §5.1 · pp. 6–7

5.2 Effect of replanning and look-ahead

  • 1.9pp (IO), 2.7pp (CoT), and 2.5pp (PS) are ReHoPER’s overall gains over the stronger planning ablation, with larger advantages on iLLC L2-4.The no-look-ahead ablation also exceeds the no-replanning ablation on overall averages; individual configurations can favor an ablation.Source: §5.2 · p. 7, Table 2 · p. 7

5.3 Effect of answer aggregation

  • Cumulative voting typically finishes above latest-prediction voting, while voting across paths generally improves as paths are added.Latest predictions and their mean correctness tend to rise as more intermediate questions are answered; path-local voting varies across trajectories.Source: §5.3 · p. 8, Figure 2 · p. 8

5.4 Paths vs. steps

  • ReHoPER beats SC in most configurations, but the value of steps versus paths is task-dependent: added paths help iLLC early, while deeper steps continue improving afterward.Both methods show diminishing returns beyond some iteration budget; some ReHoPER paths terminate early, reducing the new candidates contributed by later steps.Source: §5.4 · pp. 8–9, Figure 3 · p. 8

5.5 Comparison with Least-to-Most and Self-Refine

  • ReHoPER performs best overall against LtM, its few-shot CoT baseline, and Self-Refine, particularly on the more compositional L2 variants.Self-Refine improves over LtM in several cases but does not match ReHoPER; the comparison uses instruction-only feedback and refinement prompts for SR.Source: Table 3 · p. 8, §5.5 · p. 9

5.6 Compute–accuracy tradeoffs

  • Increasing SC’s sampling budget from 61 to 181 yields limited gains, while ReHoPER’s accuracy gains are larger on L2 than L1 and SC181 often takes longer.The authors attribute ReHoPER’s advantage to allocating compute to planning and intermediate reasoning rather than simply using more forward passes.Source: §5.6 · p. 9, Table 4 · p. 9

6 Conclusion and future work

ReHoPER improves over Self-Consistency and other strong baselines in most settings, with its largest gains on harder compositional tasks. The conclusion highlights iLLC’s diagnostic role, while the accompanying statements disclose AI use and point to public implementation resources.

6 Conclusion and future work

  • ReHoPER improves over Self-Consistency and other strong baselines in most settings, with the largest gains on harder compositional tasks.The controlled iLLC benchmark helps expose performance changes with compositional difficulty; future work could adapt compute budgets when paths terminate early.Source: §6 · pp. 9–10

AI use statement

  • The authors used generative AI to seek related work, polish the manuscript, and assist with implementation and debugging, and reviewed the changes.They state that the authors take responsibility for the final manuscript, code, and results.Source: AI use statement · p. 10

Reproducibility statement

  • The ReHoPER implementation and iLLC generator are publicly available through repositories linked in the abstract.The reproducibility statement also points to appendices documenting prompts, dataset processing, deployment details, hyperparameters, and repeated-run results.Source: Reproducibility statement · p. 10

A Macro-aggregated results

Equal-weight macro-aggregation shows ReHoPER ahead of Self-Consistency across answer formats and benchmark families, with especially large iLLC gains. Aggregation analyses find cumulative voting effective across both intermediate steps and stochastic paths; the additional PS analysis compares allocating candidate predictions to steps versus paths.

A Macro-aggregated results

  • Under equal-weight family aggregation, ReHoPER exceeds SC by 3.9pp for IO, 6.6pp for CoT, and 4.8pp for PS, with especially large gains on iLLC.Gains span MuSR, MoreHopQA, and iLLC; equal weighting means families with more subsets do not receive more weight.Source: A Macro-aggregated results · p. 14, Table 5 · p. 14

B Answer aggregation across intermediate reasoning steps

C Answer aggregation across stochastic reasoning paths

D Additional paths vs. steps results

  • The PS analysis compares accuracy as the step cap rises across six fixed paths with accuracy as path count rises at a ten-step cap, using majority-vote candidate predictions.The maximum candidate counts are upper bounds because some paths terminate early.Source: D Additional paths vs. steps results · p. 23, Figure 12 · p. 25

E Intermediate question statistics

ReHoPER’s intermediate-question statistics show that its selection mechanism avoids within-path repetition while generated-question volume and cross-path diversity vary by dataset and planning configuration. Replanning frequently changes trajectories, and the selected temperature and path/step budget perform competitively across iLLC L2-4 and MoreHopQA.

E Intermediate question statistics

  • 100% within-path uniqueness holds for ReHoPER across datasets because it selects the first unasked candidate IQ and ends a path when all candidates repeat.The no-look-ahead ablation can repeat questions despite an instruction not to, suggesting prompt-level discouragement alone does not reliably enforce non-repetition.Source: E Intermediate question statistics · p. 26, Table 7 · p. 28, Table 9 · p. 29
  • 43.07 total IQs and 24.25 unique IQs for ReHoPER on MoreHopQA contrast with 60.00 total and 20.51 unique for the no-look-ahead ablation.ReHoPER averages 7.18 IQs per path, all unique, versus 10.00 per path and 5.77 unique for no look-ahead; without replanning, it averages 3.03 per path on MoreHopQA and 3.89 on iLLC L2-4, versus 7.18 and 7.33 for ReHoPER.Source: E Intermediate question statistics · p. 26, Table 6 · p. 27, Table 8 · p. 29
  • 90.04%–96.70% global uniqueness across MuSR subsets contrasts with 55.47% on MoreHopQA, where different paths often converge on similar questions.ReHoPER’s trajectories approach the maximum length on MuSR MM, OP, and TA.Source: E Intermediate question statistics · p. 26, Table 6 · p. 27
  • On iLLC, L2-4 raises average #IQ from 38.62 to 43.99 and #uniqIQ from 17.95 to 22.87 relative to L1-4; L2-8 raises #uniqIQ from 23.27 to 27.37 relative to L1-8.Global uniqueness also tends to be higher in harder L2 variants, while within-path non-repetition is preserved.Source: E Intermediate question statistics · p. 26, Table 7 · p. 28
  • Across paths, lower global uniqueness can reflect overlap rather than within-path repetition; on iLLC, Llama 3.1 8B and gpt-oss often show higher global uniqueness than Phi-4 and Llama 3.1 70B.These diversity statistics complement accuracy by indicating whether paths explore different decompositions or revisit subproblems.Source: E Intermediate question statistics · pp. 26–27, Table 7 · p. 28

F Trajectory changes under replanning

G Hyperparameter optimization

  • T = 0.5 is selected because it performs best across prefixes on iLLC L2-4 and transfers well to MoreHopQA; the 6−10 budget is adopted as a competitive dataset-agnostic configuration.The budget is best for PS and tied for best for CoT on iLLC L2-4, and typically within 1pp of the best on MoreHopQA.Source: G Hyperparameter optimization · p. 32, Table 12 · p. 32, Table 13 · p. 32

H Robustness across repeated runs

Across three repeated runs, ReHoPER’s gains are generally stable, with the largest improvements on the more compositional iLLC L2-4 benchmark. On MoreHopQA, gains are smaller but generally positive across answer-format prefixes.

H Robustness across repeated runs

  • Across three runs, ReHoPER remains stable, with standard deviations generally comparable to Self-Consistency.The authors report that improvements persist across independent decoding runs rather than depending on one favorable sample.Source: H Robustness across repeated runs · p. 33, Table 14 · p. 33
  • On iLLC L2-4, ReHoPER improves over SC from 8.6 to 22.3 accuracy with IO, 8.1 to 24.2 with CoT, and 11.7 to 30.8 with PS.For Phi-4, accuracy rises from roughly 10–13% to more than 54–62% across prefixes, with low run-to-run variation.Source: H Robustness across repeated runs · p. 33, Table 14 · p. 33
  • On MoreHopQA, ReHoPER matches or improves average SC results under all three prefixes, with clearest gains under CoT and PS, though some model-prefix combinations decrease slightly.The paper reports smaller improvements there than on iLLC L2-4, where compositionality is greater.Source: H Robustness across repeated runs · p. 33, Table 14 · p. 33

I Planning ablation details

The planning ablations retain ReHoPER’s prediction, answer, update, and aggregation steps but alter question generation, selection, and termination. Their comparisons therefore assess combined planning-design changes rather than isolating one mechanism.

I Planning ablation details

  • The no-replanning ablation generates one ordered IQ list at each path’s start, answers questions in order, and stops at the lesser of list length or the maximum step count.It replaces planning and selection with list indexing and does not revise the list or apply ReHoPER’s candidate-selection rule.Source: I Planning ablation details · p. 33
  • The no-look-ahead ablation generates one next IQ per step without a candidate horizon or unasked-question selection, and continues to the step cap even if questions repeat.Its prompt nevertheless instructs the model to avoid repetition.Source: I Planning ablation details · p. 33
  • Because the ablations also change selection and termination, their comparisons assess combined design changes; equal limits do not guarantee equal realized trajectory lengths or compute use.The passage identifies Table 2 as the complete accuracy breakdown.Source: I Planning ablation details · p. 33

J iLLC L1-8 and iLLC L2-8 results

The appendix reports per-model accuracy for iLLC L1-8 and L2-8 and documents the models, deployment choices, and intermediate-question prompts used in the experiments. The supplied passages describe these materials but do not state the table’s accuracy outcomes.

J iLLC L1-8 and iLLC L2-8 results

K Model details

  • The model suite spans instruction-tuned LLM families and scales, while larger models use quantized deployments when needed to reduce inference memory requirements.The passage specifies AWQ for Llama 3.1 70B and Mistral Small, and GPTQ for Qwen3; Qwen3 is reported with thinking disabled and enabled.Source: K Model details · p. 34, Table 16 · p. 34

L Intermediate question instructions

M Dataset details and examples

The section describes the reasoning datasets used for evaluation, including controlled iLLC, and presents examples of their task formats.

MuSR

  • MuSR tests multi-step reasoning over story-like inputs across Murder Mysteries, Object Placement, and Team Allocation tasks.The tasks require identifying a culprit, tracking relocated objects, or inferring valid group assignments under narrative constraints.Source: M Dataset details and examples · p. 36

MoreHopQA

  • MoreHopQA evaluates connecting evidence pieces across a context and performing sequential reasoning hops, using the dataset authors’ 150-example subset..Source: M Dataset details and examples · p. 36

iLLC

  • iLLC generalizes Last Letter Concatenation by extracting the i-th-to-last character from each word and concatenating the results.Its L{i}-{w} subsets specify the character position from the end and the number of input words; L1-4 is standard last-letter concatenation, while L2-4 uses second-to-last letters.Source: M Dataset details and examples · p. 36

Post-processing

  • For MoreHopQA and iLLC, post-processing extracts the first word after “ANSWER:”; for MuSR, it extracts the most frequent option number after that marker..Source: M Dataset details and examples · p. 36

Dataset summary

N Sample iLLC L2-4 dialogues

The examples show ReHoPER’s intermediate-question dialogues on iLLC L2-4, including a positive example that produces “ocrr” and a negative example that produces “adad.”

Positive example

  • The positive iLLC L2-4 example asks for second-to-last letters and concatenates the answers into “ocrr.”The dialogue includes intermediate letter questions before asking for the combined result.Source: N Sample iLLC L2-4 dialogues · p. 40

Goal prompt

Negative example

  • The negative example includes word-length questions before reporting “adad” as the concatenated second-to-last letters.The dialogue asks how many letters are in “Dan” before asking for its second-to-last letter.Source: N Sample iLLC L2-4 dialogues · pp. 41–42
Loading 2610.00940v1…