PaperlayerView exact revision on arXiv

Source-linked AI summary

Beyond Examples: High-level Automated Reasoning Paradigm in In-Context Learning via MCTS

Jinyang Wu, Mingkuan Feng, Shuai Zhang, Feihu Che, Zengqi Wen, Chonghua Liao, Jianhua Tao

arXiv:2411.18478v2cs.CL

TL;DR

Traditional in-context learning relies on examples and offers limited explicit guidance for complex reasoning. HiAR-ICL constructs abstract reasoning patterns with MCTS and selects them by problem attributes; with Qwen2.5-7B-Instruct, it surpasses GPT-4o on MATH and AMC.

  • Problem

    Traditional ICL is sensitive to demonstration characteristics, lacks explicit reasoning guidance, and has constrained generalization across differently presented problems with similar logical structures.

    Source: §1 · p. 2

  • Method

    HiAR-ICL uses five atomic actions and MCTS to construct abstract thought cards, then adaptively selects cards by problem characteristics to guide inference.

    Source: §1 · p. 2

  • Results

    HiAR-ICL improves complex-reasoning performance across multiple domains; with Qwen2.5-7B-Instruct, it achieves 80.6% accuracy on MATH versus GPT-4o’s 77.2%.

    Source: §1 · p. 2, §6 · p. 10

  • Takeaways & Limitations

    The work provides empirical foundations for future research on scalable and efficient reasoning frameworks in LLMs.

    Source: §6 · p. 10

    Problem Condition Complexity is the default matching metric, while Subquestion Count and Problem Semantics are optional; more complex designs are left for future work.

    Source: §2.1 · p. 4

Abstract

from arXiv · show

In-context learning (ICL) enables large language models (LLMs) to perform downstream tasks through advanced prompting and high-quality demonstrations. However, traditional ICL paradigms encounter significant limitations in complex reasoning tasks, stemming primarily from their dependence on example quality and absence of explicit reasoning guidance. To address these challenges, we introduce HiAR-ICL, a **Hi**gh-level **A**utomated **R**easoning paradigm in **ICL** that shifts focus from specific examples to abstract reasoning patterns, thereby extending the conventional concept of "context" in ICL. Our approach begins by defining five atomic reasoning actions, upon which we employ Monte Carlo Tree Search to systematically construct high-level reasoning patterns. During inference, HiAR-ICL dynamically selects appropriate reasoning patterns based on problem attributes, providing explicit guidance for the model's reasoning process. Experiments demonstrate HiAR-ICL's effectiveness and efficiency: utilizing only 200 prior samples with Qwen2.5-7B-Instruct, our method achieves 80.6% accuracy on MATH and 62.5% on AMC, exceeding GPT-4o's 77.2% and 57.5%. Our approach enhances performance across models of varying sizes while generalizing effectively across domains. Further analysis reveals that HiAR-ICL can also serve as a plug-and-play inference method compatible with post-training techniques like GRPO. Code and data are available at https://github.com/jinyangwu/HiARICL.

1 Introduction

Traditional ICL is sensitive to demonstration quality, lacks explicit reasoning guidance, and generalizes poorly across differently presented problems. HiAR-ICL replaces example-centered context with automatically constructed reasoning patterns that are selected for each problem.

1 Introduction

  • Traditional ICL depends on demonstration quantity, ordering, and label distributions, lacks explicit guidance, and may require reconstructing examples for differently presented problems with similar logic.The authors note that suboptimal examples can impede reasoning and require considerable human curation.Source: §1 · p. 2
  • HiAR-ICL defines five atomic reasoning actions, uses MCTS and seed data to construct thought cards, then selects cards by problem characteristics to guide reasoning and verification.Verification combines process reward modeling with self-consistency checks.Source: §1 · p. 2
  • HiAR-ICL extends ICL context from specific examples to abstract reasoning patterns and is presented as an automated, adaptive approach with cross-domain generalization.The authors characterize this as teaching how to think rather than what to think.Source: §1 · p. 2
  • 80.6% accuracy on MATH and 62.5% on AMC with Qwen2.5-7B-Instruct exceed GPT-4o’s 77.2% and 57.5%, respectively.The introduction also reports approximately 10× lower time cost than leading test-time inference methods.Source: §1 · p. 2

2 Methodology

HiAR-ICL constructs reusable reasoning templates from seed questions using MCTS, then matches those templates to test questions and verifies candidate solutions. Its method combines a small action vocabulary, reward-and-cost path selection, problem-attribute matching, and two-stage verification.

2 Methodology

  • Thought-card construction uses MCTS to generate reasoning paths from seed questions, while inference adaptively selects patterns based on problem complexity and verifies solutions.The cards are distilled as structured templates to guide subsequent inference.Source: §2 · p. 3, §2.1 · p. 3

2.1 MCTS-powered Thought Card Construction

  • Five atomic actions—System Analysis, One-Step Thought, Chain-of-Thought, Divide and Conquer, and Self-Reflection and Refinement—form the building blocks of chain-structured reasoning patterns.MCTS searches reasoning trajectories generated by a policy LLM, treating the question as the root and subsequent reasoning steps as nodes.Source: §2.1 · p. 3
  • Candidate paths are scored by balancing final reward against action-count cost, and the highest-scoring path per seed question is distilled into abstract thought cards.Cards encode high-level templates and average problem-complexity indicators for questions sharing each template.Source: §2.1 · p. 4
  • The default card-matching criterion is Problem Condition Complexity, while Subquestion Count and Problem Semantics are optional and more complex designs are left for future work.Card attributes include subquestion count, prior-condition count, and semantic representation.Source: §2.1 · p. 4

2.2 Adaptive Reasoning and Verification

  • At inference, the method matches each test question to five relevant thought cards using attribute-specific distances, then follows the selected templates as sequential atomic actions.It uses absolute differences for SC and PCC and cosine similarity for semantic representations.Source: §2.2 · pp. 4–5
  • Verification scores candidate reasoning paths with process supervision, then applies self-consistency checks to the three highest-scoring paths to choose a final solution.The authors report that straightforward self-consistency checks can identify precise reasoning chains without additional supervision.Source: §2.2 · p. 5

3 Experimental Settings

Experiments use 200 randomly sampled training instances to construct thought cards and evaluate on test sets spanning arithmetic, mathematical, commonsense, and scientific reasoning. The study compares HiAR-ICL with example-based ICL, tree-based methods, and leading LLMs using accuracy and per-sample time cost.

3 Experimental Settings

  • The study uses 200 randomly sampled training instances for thought-card construction and evaluates on test sets for arithmetic, mathematical, commonsense, and PhD-level scientific reasoning.The datasets are GSM8K, SVAMP, MATH, AMC, StrategyQA, and GPQADiamond.Source: §3 · p. 5
  • Baselines include zero-shot CoT, few-shot CoT, and CoT+SC; tree-based methods such as ToT and RAP; and leading LLMs including Llama3.1-405B, GPT-4o, and Claude-3.5.Additional comparisons, including Reinforced ICL, are provided in Appendix E.1.Source: §3 · p. 5
  • Evaluation measures strict-match answer accuracy and average time cost per sample to assess computational efficiency against leading search-based approaches.Accuracy compares the model’s final answer with ground truth.Source: §3 · p. 5
  • MCTS uses a maximum tree depth of 5, exploration weight 2.0, and self-consistency termination threshold 0.90; VOC path selection uses balance factor 0.95.Experiments ran with vLLM on Ubuntu 22.04 and NVIDIA A100-80GB GPUs.Source: §3 · p. 5

4 Results and Discussion

HiAR-ICL combines MCTS-built reasoning patterns with adaptive selection and verification. Across benchmarks, it reports strong performance, efficiency, generalization, and compatibility with post-training.

4.1 Performance Comparison with Baselines

  • HiAR-ICL improves over traditional ICL across reasoning domains, including Llama3-8B-Instruct on MATH (17.8% to 46.6%) and Qwen2-7B-Instruct on MATH (52.9% to 66.8%).The reported gains span arithmetic, mathematical, commonsense, and PhD-level scientific reasoning, as well as small models.Source: §4.1 · pp. 5–6
  • 80.6% accuracy on MATH lets Qwen2.5-7B-Instruct exceed few-shot GPT-4o (77.2%).Figure 3 provides the intuitive comparison on MATH.Source: §4.1 · p. 6, Figure 3 · p. 7

4.2 Computational Efficiency

  • 21.8× speedup on GSM8K and 21.0× on StrategyQA accompany a 7.0× speedup on MATH.The reported end-to-end time includes offline card construction and online inference; the paper attributes the efficiency to adaptive pattern selection rather than exhaustive search.Source: §4.2 · p. 7, Figure 4 · p. 7

4.3 Out-of-Distribution Generalization

  • With the same 200 seed samples for thought-card construction and SFT, HiAR-ICL preserves robust performance across multiple models and datasets in OOD evaluation.The comparison includes ICL and supervised fine-tuning, which the authors report experience significant performance degradation.Source: Figure 5 · p. 7, §4.3 · p. 8

4.4 Weak-to-Strong Generalization

  • Llama2-7B-built thought cards guide GPT-4o to 79.6% on MATH versus 77.2% with direct CoT, and 95.0% on GSM8K versus 94.3%.The setup uses a weaker model to construct cards that guide a stronger model's inference.Source: §4.4 · p. 8, Table 3 · p. 8

4.5 Ablation Studies and Analysis

  • Replacing structured cards with random action chains drops accuracy 10.4%, while randomly selecting cards rather than matching question complexity drops it 5.0%.These ablations test the value of structured reasoning patterns and complexity-based matching.Source: §4.5 · p. 8
  • SC+PRM achieves optimal verification results; adding more thought cards consistently improves performance but increases computational overhead.The paper identifies balancing performance and cost as a direction for future optimization.Source: §4.5 · pp. 8–9, Figure 6 · p. 9
  • HiAR-ICL is training-free at test time and consistently enhances models that have undergone GRPO training.The paper presents this as evidence of plug-and-play compatibility with post-training techniques.Source: §4.5 · p. 9, Table 5 · p. 9

5 Related Work

Prior ICL methods use examples and instructions to elicit reasoning, while tree-search approaches explore multiple paths but can incur substantial computational overhead. HiAR-ICL shifts toward abstract reasoning patterns and adaptive inference.

In-Context Learning via Examples

  • Example-based ICL, including CoT and self-consistency, relies on demonstrations or multiple reasoning paths, but may generalize poorly and require expert intervention for complex tasks.HiAR-ICL contrasts this with high-level reasoning patterns intended for automated, adaptive inference.Source: §5 · pp. 9–10
  • HiAR-ICL applies high-level reasoning patterns across diverse complex tasks, aiming for efficient inference without human intervention.The paper also notes potential for strong performance with models under 10B parameters.Source: §5 · p. 10

Tree-based Search

  • Tree-search methods such as ToT and GoT explore nonlinear reasoning paths, while advanced methods including AlphaMath and rStar can incur significant computational overhead.The paper positions HiAR-ICL as frontloading computation into prior reasoning patterns.Source: §5 · p. 10

6 Conclusion

The conclusion presents HiAR-ICL as an MCTS-powered approach that integrates abstract reasoning patterns into in-context learning. It reports improvements across complex reasoning tasks and frames automatic abstraction and broader application of such patterns as future research directions.

6 Conclusion

  • HiAR-ICL integrates abstract reasoning patterns into in-context learning, moving beyond approaches based solely on examples.The conclusion characterizes its strategies as adaptive, explicit, and structured.Source: §6 · p. 10
  • The paper reports performance improvements across multiple domains and identifies scalable, efficient reasoning frameworks and broader application of abstracted patterns as research directions.These are presented as potential directions for future work.Source: §6 · p. 10

Appendix of HiAR-ICL

A Further Discussions on HiAR-ICL and In-Context Learning

HiAR-ICL remains within ICL while redefining context as abstract reasoning patterns rather than task-specific examples. Its discussion situates this shift against example-based learning and describes a structured reasoning approach built from atomic actions.

A Further Discussions on HiAR-ICL and In-Context Learning

  • HiAR-ICL adds MCTS pre-computation but remains within ICL because inference uses generated reasoning patterns as natural-language instructions.This retains ICL’s linguistic-context mechanism while extending its preparation stage.Source: A Further Discussions on HiAR-ICL and… · p. 17
  • HiAR-ICL broadens context from task-specific demonstrations to abstract reasoning patterns intended to support cross-task generalization.The authors describe this as a redefinition of context that enriches the conventional concept.Source: A Further Discussions on HiAR-ICL and… · p. 17

B.2 LLM Reasoning

  • LLM reasoning is framed as a sequence of generated steps, while prior approaches include prompting, CoT, ToT, and MCTS.The model’s state includes the input problem and preceding reasoning steps.Source: §B.2 · p. 18

B.3 In-Context Learning

  • Traditional ICL uses task demonstrations drawn from a joint distribution, and prior work has emphasized example quality, prompting, and scaling.The paper contrasts that example-level analogy with its focus on high-level reasoning patterns.Source: §B.3 · p. 18

C Algorithm Details

  • HiAR-ICL’s overview identifies MCTS-powered thought-card construction and adaptive reasoning-pattern use with verification as its two components.Its algorithm discussion motivates a wider action space than existing tree-based methods’ restricted sets.Source: C Algorithm Details · p. 19, §C.1 · p. 19, Table 7 · p. 19

C.1 Action Space

  • The five actions are system analysis, one-step thought, chain-of-thought, divide and conquer, and self-reflection and refinement.They cover problem analysis, stepwise generation, decomposition, and revision.Source: §C.1 · p. 19

C.2 Monte Carlo Tree Search

This section describes how MCTS constructs prior reasoning patterns, how problem complexity informs their selection, and how candidate solutions are verified. The experiments use several open-source instruction models, generally below 10B parameters.

C.2 Monte Carlo Tree Search

  • HiAR-ICL uses MCTS to construct prior reasoning patterns, then references thought cards at inference to adapt strategies to problem complexity with lower time complexity than traditional tree search.The authors describe this as trading off efficiency and effectiveness while maintaining a comprehensive search space and overall performance.Source: §C.2 · p. 20
  • MCTS leaf-node rewards use self-consistency confidence from majority voting, while intermediate-node Q-values start at 0 and update during backpropagation.The method avoids adding a separate reward model.Source: §C.2 · p. 20

C.3 Thought Card Selection

  • Problem complexity is assessed through subquestion count, condition complexity, and semantic similarity; the paper adopts condition complexity as its primary metric.The authors report minimal statistical variation among the three metrics and suggest weighted ranking as future work.Source: §C.3 · p. 20

C.4 Verification

  • Verification scores reasoning paths with process supervision, then applies self-consistency checks to the top three; the paper also reports using PRM by default.It says self-consistency can still be used when no verification model is available.Source: §C.4 · pp. 20–21

D.1 Models

  • Experiments evaluate HiAR-ICL on multiple open-source instruction models, generally with fewer than 10B parameters, and also analyze combinations with base models.The listed models include Llama, Yi, and Qwen variants.Source: §D.1 · p. 21

D.2 Datasets

The evaluation uses math, commonsense, and scientific-reasoning datasets, with seed samples for thought-card construction and test sets for evaluation. It compares baselines and measures accuracy and reasoning time.

D.2 Datasets

  • The evaluation includes GSM8K, SVAMP, MATH500, AMC, StrategyQA, and GPQA Diamond, spanning mathematical, commonsense, and scientific reasoning tasks.The MATH evaluation uses the 500-problem subset, while GPQA Diamond contains 198 questions.Source: §D.2 · pp. 21–22

D.3 Baselines

  • For thought-card construction, the authors randomly sample 200 training instances from each dataset; other tree-based methods and closed-source models use reported results or reproduced official settings.The paper states that cross-distribution transfer was validated in the main text.Source: §D.2 · p. 22, §D.3 · p. 22

D.4 Card Distribution

  • Reasoning-action chains grow in length and diversity with problem complexity, while some patterns remain consistent across datasets and support out-of-domain generalization.The number and complexity of actions depend on the problem; a simple example may use one action, while a complex one uses a longer chain.Source: §D.4 · p. 22

D.5 Evaluation Details

  • The evaluation reports answer accuracy and average reasoning time, with all time measurements recorded on the same A100 GPUs.Accuracy compares the model’s final answer with ground truth under a predefined answer format.Source: §D.5 · p. 22

E.1 Detailed Comparison with Powerful LLMs and Methods

HiAR-ICL is reported to outperform powerful models and other ICL and tree-based methods, with a large gain over ToT for Llama3-8B on MATH. The authors also describe combining it with larger reasoning models.

E.1 Detailed Comparison with Powerful LLMs and Methods

  • Both Qwen2.5-7B and 14B with HiAR-ICL are reported to surpass many models with over 100B parameters, including on challenging MATH.The passage describes a significant MATH advantage but supplies no specific values here.Source: §E.1 · p. 23
  • 46.6% MATH accuracy for Llama3-8B with HiAR-ICL versus 17.8% with ToT is reported as a 2.6× improvement.The comparison is part of a broader report that HiAR-ICL consistently outperforms advanced ICL and tree-based methods.Source: §E.1 · p. 23

E.2 Combination with Large Reasoning Models

  • HiAR-ICL can be combined with larger reasoning models such as QwQ-32B-Preview, with the paper reporting even better performance.The cited table’s scope is performance on MATH.Source: §E.2 · p. 23, Table 12 · p. 24

E.3 Multi-Task System

Across multi-task, SFT, difficulty-stratified, and efficiency evaluations, HiAR-ICL achieves competitive performance and improves results across evaluated settings. Reported findings include gains on harder MATH problems and high STG accuracy with substantially lower cost than rStar.

E.3 Multi-Task System

  • Using 150 seed samples—50 each from mathematical, arithmetic, and commonsense reasoning—HiAR-ICL constructs multi-task thought cards and achieves competitive performance.Source: §E.3 · p. 24, Table 13 · p. 25

E.4 Integration with SFT

  • Up to 26.6% average improvement across multiple benchmarks is reported for base models, while instruction-tuned models improve consistently across all evaluated tasks.The integration experiments evaluate Llama3-8B and Llama3.1-8B, including pretrained and instruction-tuned versions.Source: Table 14 · p. 25, §E.4 · p. 25

E.5 Performance across Problem Complexity

  • +7.7% accuracy improvement is reported for Qwen2.5-7B-Instruct on MATH level 4, versus an average 2.6% boost across easier levels 1–3.Source: Table 15 · p. 26, §E.5 · p. 26

E.6 Detailed Computational Cost

  • On STG, HiAR-ICL achieves the highest accuracy while using only 5% of the time required by rStar.The per-sample cost includes offline card construction and online inference; offline overhead is fixed and its amortized cost diminishes as test-sample count grows.Source: Table 16 · p. 26, §E.6 · p. 26

E.7 Ablation Studies

The ablation reports that the expanded atomic-action space improves performance over more restrictive approaches, while case studies illustrate advantages on challenging problems.

E.7 Ablation Studies

  • The Llama3-8B-Instruct ablation reports significant performance improvements from the expanded atomic-action space compared with approaches using typically restrictive action spaces.Source: Table 17 · p. 27, §E.7 · p. 27

F Case Study

Loading 2411.18478v2…