PaperlayerView exact revision on arXiv

Source-linked AI summary

Experience-Guided Adaptation of Inference-Time Reasoning Strategies

Adam Stein, Matthew Trager, Benjamin Bowman, Michael Kleinman, Aditya Chattopadhyay, Wei Xia, Stefano Soatto

arXiv:2511.11519v1cs.AIcs.LG

TL;DR

Systems with inference-time memory generally steer text, while more flexible offline strategy optimization remains static after deployment. EGuR uses a Guide and Consolidator to generate complete strategies from problems and accumulated experience. Across five benchmarks, it reports accuracy improvements and lower computational costs, with both metrics improving as experience accumulates.

  • Problem

    Inference-time memory methods steer textual inputs, while more flexible offline strategy optimization remains static after deployment, leaving a gap in continual adaptation of strategy structure.

    Source: §1 · pp. 1–2

  • Method

    EGuR uses an LLM-based meta-strategy with a Guide that generates candidate strategies from the problem and structured experience, and a Consolidator that integrates execution outcomes.

    Source: §1 · p. 2

  • Results

    Across five benchmarks, EGuR achieves up to 14% relative accuracy improvements while reducing computational costs by up to 111x, with both metrics improving as experience grows.

    Source: §6 · p. 10

  • Takeaways & Limitations

    Generating and comparing multiple strategies lets EGuR learn their relative effectiveness, with accuracy and computational efficiency improving over experience.

    Source: §1 · p. 2

    EGUR relies on ground-truth verifier feedback, zero-shot strategy generation that may be suboptimal for unfamiliar problem types, and LLM-managed memory that may not balance size and utility optimally.

    Source: §6 · p. 10

Abstract

from arXiv · show

Enabling agentic AI systems to adapt their problem-solving approaches based on post-training interactions remains a fundamental challenge. While systems that update and maintain a memory at inference time have been proposed, existing designs only steer the system by modifying textual input to a language model or agent, which means that they cannot change sampling parameters, remove tools, modify system prompts, or switch between agentic and workflow paradigms. On the other hand, systems that adapt more flexibly require offline optimization and remain static once deployed. We present Experience-Guided Reasoner (EGuR), which generates tailored strategies -- complete computational procedures involving LLM calls, tools, sampling parameters, and control logic -- dynamically at inference time based on accumulated experience. We achieve this using an LLM-based meta-strategy -- a strategy that outputs strategies -- enabling adaptation of all strategy components (prompts, sampling parameters, tool configurations, and control logic). EGuR operates through two components: a Guide generates multiple candidate strategies conditioned on the current problem and structured memory of past experiences, while a Consolidator integrates execution feedback to improve future strategy generation. This produces complete, ready-to-run strategies optimized for each problem, which can be cached, retrieved, and executed as needed without wasting resources. Across five challenging benchmarks (AIME 2025, 3-SAT, and three Big Bench Extra Hard tasks), EGuR achieves up to 14% accuracy improvements over the strongest baselines while reducing computational costs by up to 111x, with both metrics improving as the system gains experience.

1 Introduction

The introduction identifies a gap between inference-time memory that only steers text and flexible offline optimization that cannot keep learning after deployment. EGuR generates complete strategies from experience, and its reported results improve accuracy and reduce cost across five benchmarks.

Problem

  • Existing approaches either use persistent memory only to steer text or optimize strategies offline and remain static after deployment, leaving continual adaptation of computational structure unresolved.Without persistent memory, systems may repeat costly procedures on solved problems or repeat prior mistakes.Source: §1 · pp. 1–2

Approach

  • An LLM-based meta-strategy generates tailored procedures through a Guide that proposes candidates from the problem and structured memory, and a Consolidator that uses execution outcomes to improve future generation.Successful strategies can be cached for reuse.Source: §1 · p. 2

Contribution

  • EGuR adapts all strategy components, including prompts, sampling parameters, tools, and control logic, rather than only steering an existing strategy's text input.Source: §1 · pp. 1–2
  • Generating and comparing multiple strategies per problem lets the system learn their relative effectiveness, with continual improvement in accuracy and computational efficiency.Source: §1 · p. 2

Results

  • Across five challenging benchmarks, EGuR achieves up to 14% accuracy improvements (EGUR vs. Mem0 on 3-SAT) and reduces computational costs by up to 111x (EGUR vs. DC on Object Counting).Both metrics improve as the system gains experience.Source: §1 · p. 2

2 Strategies For AI Systems

The paper represents strategies as stateful process compositions and classifies them by their structure. It then motivates compiling useful strategies from experience to bridge inference-time memory and offline optimization.

2 Strategies For AI Systems

  • Strategies are stateful processes that map inputs and state to outputs and updated state, providing a unified description of strategy components and feedback.Source: §2 · p. 2

2.1 Representing Strategies

  • The formalism makes prompts, sampling parameters, tools, and control flow explicit and composable, allowing a meta-strategy to alter them, including removing code execution.Source: §2.1 · p. 3

2.2 The Strategy Landscape

  • Strategies are workflows without recursion, agents when dynamic and recursive, and pipelines when neither recursion nor dynamic branching is present.Source: §2.2 · p. 3
  • Strategy performance is task-dependent: Code is best for 3-SAT and Word Sorting but worst for AIME and Movie Recommendation; Eval-Opt often achieves similar accuracy to Self-Consistency at half the cost.Source: §2.2 · p. 3
  • More expressive strategies may fail to select suitable behavior and can cost substantially more than simpler strategies, creating a quality-cost trade-off termed overthinking.Source: §2.2 · p. 4

2.3 Incorporating Feedback to Strategies

  • Prior approaches split inference-time state limited to input steering from offline whole-strategy optimization that becomes static; EGuR instead compiles useful strategies on the fly from experience.Source: §2.3 · p. 4

3 Experience-Guided Reasoner (EGUR)

EGUR generates complete, problem-specific strategies from past experience, with a Guide proposing candidates and a Consolidator updating memory from execution outcomes. Its design supports strategy exploration, comparison, reuse, and selective memory retention.

3 Experience-Guided Reasoner (EGUR)

  • The optimal strategy differs across tasks: Code excels on 3-SAT and Word Sorting but performs poorly on Movie Recommendation and AIME.Strategies nearer the top-left of Figure 3 are best in accuracy and cost for a task.Source: Figure 3 · p. 5
  • The strategy categories distinguish pipelines without conditionals, workflows using conditionals, and agents using recursion.Table 1 organizes common strategies by design patterns and tools.Source: Table 1 · p. 5

3.1 General Design

  • The Guide produces a complete strategy specification upfront, while the Consolidator uses execution outcomes and verifier feedback to improve future generation.Specifications include LLM calls, sampling parameters, tools, and control flow; the Consolidator maintains structured memory.Source: §3.1 · p. 5, §3 · p. 5
  • For each problem, EGUR can execute k candidate strategies in parallel, collect answers, traces, costs, and verifier feedback, then update context.The algorithm returns the first candidate's answer and the updated context.Source: §3.1 · p. 6

3.2 Strategy Selection with the Guide

  • The Guide conditions k candidate strategies on the query and relevant experience, allowing relative comparison; larger k increases diversity and discovery potential at higher cost.The Consolidator records relative performance among strategies on similar problems to inform future generation.Source: §3.2 · p. 6

3.3 Feedback Integration with the Consolidator

  • The Consolidator abstracts execution experiences into a Strategy Library for successful strategies and General Notes for heuristics, failures, and useful techniques.The Guide receives this context directly and performs retrieval and synthesis in-context.Source: §3.3 · p. 6
  • Selective retention prioritizes recent experiences and frequently accessed patterns while removing outdated information to limit memory growth.The Consolidator generates memory insertions and deletions that are parsed and applied.Source: §3.3 · p. 6

4 Experiments

EGUR is evaluated on five reasoning tasks with three models against stateless and memory-based baselines. The experiments examine accuracy and cost, dynamic strategy generation, comparative evaluation, and strategies learned from experience.

4.1 Experimental Setup

  • Evaluation covers AIME, 3-SAT, and three BBEH tasks, using three models, verifier feedback, prequential accuracy, and cumulative strategy-execution cost.Held-out evaluation uses three seeds; continual updates use one seed.Source: §4.1 · p. 7

4.2 RQ1: Does EGUR outperform baselines in accuracy and cost?

  • 96.0% accuracy at $0.152 cost on 3-SAT for Claude 3.7 Sonnet EGUR-5 compares with CodeAct’s 77.0% at $0.257 and Dynamic Cheatsheet’s 89.9% at $76.353.Across held-out evaluations, EGUR-5 improves accuracy while reducing cost as experience grows.Source: §4.2 · p. 7, Figure 4 · p. 8

4.3 RQ2: Does dynamic strategy generation improve over existing stateful strategies?

  • Unlike input-steering methods, EGUR generates tailored complete strategy specifications and can remove tools, change sampling parameters, or switch between agentic and workflow approaches.Across tasks, it achieves superior accuracy while reducing costs by 2–111× through complete strategy adaptation.Source: §4.3 · pp. 7–8

4.4 RQ3: Is comparative strategy evaluation important for continual improvements?

  • EGUR-1 outperforms the stateless EGUR-ZS, and EGUR-5 usually outperforms EGUR-1; higher exploration also reduces cost as comparative evaluation finds efficient strategies faster.Larger improvements are reported on 3-SAT and object counting.Source: §4.4 · p. 8

4.5 RQ4: Does EGUR learn novel and useful strategies from experience?

  • EGUR learns to specify libraries, add code snippets and error handling, and vary strategy specificity; for object counting it favors one detailed LLM call over CodeAct.For word sorting, it distinguishes algorithmic cases suited to Python sorting from reasoning cases handled with CoT and verifier-based fallback.Source: §4.5 · pp. 8–9
  • Learned heuristics tailor tool use and computational investment to problem characteristics, increasing or simplifying strategies as appropriate.Additional examples are reported in Appendix D.Source: §4.5 · p. 9

5 Related Work

Related work includes adaptive prompting, inference-time memory, and offline strategy optimization. The paper distinguishes its approach by combining experience-based adaptation with complete strategy generation at inference time.

Prompting strategies

  • Prompting approaches elicit reasoning with fixed scaffolds, while some methods dynamically compose per-instance strategies but remain stateless across instances.Examples include CoT, Self-Consistency, PoT, CodeAct, Self-Discover, and Meta-Prompting.Source: §5 · p. 9

Prompt adaptation from inference-time state or training

  • Prompt and memory adaptation can update inputs to fixed workflows, while trained routers select among fixed strategies; these approaches cannot freely adapt strategy structure.Inference-time memory systems include Dynamic Cheatsheet and Buffer of Thoughts; DSPy and TextGrad use training data or verifier feedback for optimization.Source: §5 · pp. 9–10

Full strategy adaptation

  • ADAS searches agent programs offline and at task level, whereas EGUR performs online, instance-level adaptation and test-time strategy search.The paper frames EGUR as unifying dynamic strategies, memory-based learners, and automated design.Source: §5 · p. 10

6 Conclusion

EGUR generates complete strategies at inference time from accumulated experience, improving accuracy and reducing cost across five benchmarks. The conclusion also identifies limitations in feedback, strategy generation, and memory management.

6 Conclusion

  • Across five benchmarks, EGUR achieves up to 14% relative accuracy improvements while reducing computational costs by up to 111x.Both metrics improve as the system gains experience.Source: §6 · p. 10
  • EGUR learns heuristics for choosing agentic strategies versus workflows, deciding when tools help, and tailoring computational investment to problem difficulty.Source: §6 · p. 10
  • Effective learning uses ground-truth verifier feedback; the Guide may be suboptimal on unfamiliar problem types, and LLM-based memory management may not balance memory size and utility optimally.The authors identify weaker feedback, Guide training, and meta-learning for memory management as directions for future work.Source: §6 · p. 10

A Related Work Taxonomy

B.1 Syntax

The appendix specifies a strategy language, its stateful-process semantics, Guide and memory-updater roles, and recursive strategy-cost definitions.

B.1 Syntax

  • The syntax separates values, expressions, and programs, with programs supporting state access and updates, sequential or parallel composition, conditionals, and fixpoints.Values include strings, floats, booleans, null, lists, and dictionaries; expressions include indexing, append operations, arithmetic, lambdas, and function application.Source: §B.1 · pp. 13–14

B.2 Semantics

  • Programs denote stateful processes; the state space can track conversation logs, code-execution state, execution traces, and strategy cost as processes compose.Sequential, parallel, and conditional composition are given process meanings.Source: §B.2 · pp. 14–15

B.3 Guide and Consolidator

  • The Guide maps a query to a solving strategy while retaining state between queries, and the memory updater maps current experience and running state to updated state.Source: §B.3 · p. 15

B.4 Strategy Cost

  • Strategy cost is defined recursively from base-process execution costs, with conditional costs selected by the branch taken and fixpoint cost given by a least fixed point.Source: §B.4 · p. 15

B.5 EGUR Implemented as a Strategy

The appendix represents EGUR and common reasoning approaches in the strategy language, specifying EGUR’s inputs and outputs and the procedures used by several baselines.

B.5 EGUR Implemented as a Strategy

  • Algorithm 2 represents EGUR as a strategy that takes a question, context, and exploration factor, then returns an answer and updated context.The appendix makes sequential and parallel process composition explicit.Source: §B.5 · pp. 15–16
  • Figure 6 presents strategy-language implementations of CoT, Self-Consistency, Code, and Eval-Opt.Source: Figure 6 · p. 16

B.6 Common Strategies

  • CoT is one tool-free LLM call; Code writes and executes code once; Eval-Opt critiques optimizer-generated candidates; Self-Consistency majority-votes over 10 CoT samples; CodeAct iterates code generation and execution.CodeAct is described as prototypical of an agentic workflow.Source: §B.6 · p. 16

C Full results

The appendix points to prequential results and reports where full results across models, holdout datasets, and training checkpoints are presented.

C Full results

  • Prequential evaluation results for all models are reported in Table 3.Source: C Full results · p. 16
  • Full results for all methods, three models, and five holdout datasets across four evenly spaced training checkpoints are provided in Tables 4–8.Source: C Full results · p. 16
  • The full-results tables cover all methods across four checkpoints during training.Source: C Full results · p. 16

D Example Generated Strategies

The examples show generated strategies combining task-specific prompts, model-call settings, voting, retries, and tool execution. A before-and-after Object Counting example answers the same problem correctly at lower cost after training.

D Example Generated Strategies

  • The Sarc Triples strategy uses a tailored prompt, five independent model calls at temperature 0.5, and majority voting.The example describes a GPT-OSS-120B generated strategy.Source: D Example Generated Strategies · pp. 16–18
  • Table 3 reports that EGuR consistently achieves the best accuracy-cost trade-offs across datasets.The table presents prequential accuracy and cost by dataset.Source: Table 3 · p. 17
  • After training, the Claude 3.7 Sonnet Object Counting strategy answers the same problem correctly for $0.062, versus an incorrect $0.166 answer before training.The examples concern one particular BBEH Object Counting problem.Source: D Example Generated Strategies · p. 18
  • The Object Counting workflow can request Python code, execute it, and continue model turns until it finds a final answer.The shown model call uses temperature 0.7 with thinking enabled.Source: D Example Generated Strategies · p. 20
  • The Object Counting prompt directs the model to count animals and musical instruments separately, then return their absolute difference.It also instructs the model to use final quantities in stories about changing amounts.Source: D Example Generated Strategies · p. 21

E Example Learned Context

This section shows how the Guide turns relevant experience into runnable workflows that balance accuracy and computation, and how the Consolidator uses execution feedback to retain effective strategies and actionable lessons. Together, their instructions shape strategy generation and preserve useful memory while limiting unnecessary growth.

E Example Learned Context

  • For movie-group appeal, the learned memory identifies same language and era, similar accessibility, comparable mainstream-versus-niche positioning, and consistent tone and pacing as reliable similarity indicators.The final memory is described as including multiple entries and a task–best-strategy pair for future problems.Source: E Example Learned Context · pp. 21–22
  • For subjective similarity analysis, CoT with deep thinking is more cost-effective than CodeAct or Evaluator-Optimizer, and a structured prompt can provide enough guidance without code execution or multiple calls.The prompt guides comparison through criteria such as genres, audience, and reception, and asks for explicit ratings or rankings.Source: E Example Learned Context · p. 22

F Prompts

  • The paper provides complete Guide and Consolidator prompts, which define the two strategies used by EGUR.Source: F Prompts · p. 23

F.1 Guide

  • The Guide is instructed to output a runnable Python strategy function that sets up an LLM workflow or agent, rather than solving the target problem itself.Strategies may use model calls, Python execution, parsing utilities, and available memory; the prompt lists composable elements including CoT, decomposition, voting, and iterative feedback.Source: §F.1 · pp. 23–24
  • The Guide incorporates relevant memory into strategy structure and prompts, reuses a stored task–best-strategy pair when available, and ignores irrelevant entries.Memory can contribute advice, code, pitfalls, or examples to prompts.Source: §F.1 · p. 27
  • The Guide balances accuracy and cost by using more computation after errors or on hard problems and simpler approaches when problems are easy; it recommends CoT for many non-algorithmic tasks and CodeAct for algorithmic tasks.When two strategies seem equally likely to be correct, it favors the less costly one.Source: §F.1 · p. 27

F.2 Consolidator

  • The Consolidator prompt supplies strategy-execution traces, final answers, and verifier outputs indicating whether answers are correct.Source: §F.2 · pp. 27–28
  • For each task, save the correct-answer strategy with the greatest reliability or lowest cost, replacing an existing entry only when the new strategy is better; save no strategy if all attempts are wrong.Memory contains one (task, best strategy) pair per task, and incorrect strategies must not be saved.Source: §F.2 · p. 28
  • Extract actionable lessons from reasoning traces—such as working code, tool configurations, useful heuristics, and failure mitigations—without inventing fixes or retaining strategies that produced incorrect answers.The instructions favor reusable information that reduces future reasoning time or cost and reject redundant or incomplete material.Source: §F.2 · p. 28
  • Preserve task–best-strategy pairs when editing memory, delete other entries cautiously, and keep memory under 10,000 tokens to avoid distraction.The instructions warn that other entries or code may refer to an entry being deleted.Source: §F.2 · p. 29
Loading 2511.11519v1…