PaperlayerView exact revision on arXiv

Source-linked AI summary

ForkPilot: Self-Evolving Policy for Retrospective Search in Long-Horizon Agents

Xinyue Zeng, Shivam Shandilya, Guilherme Potje, Leonardo Nunes, Rakshanda Agarwal, Ranveer Chandra, Emre Kiciman, Dawei Zhou, Tusher Chakraborty

arXiv:2610.04889v1cs.AI

TL;DR

Delayed outcomes make it hard to isolate the value of intermediate search decisions, while evolving observations and environments can stale learned estimates. ForkPilot models this changing gain-cost trade-off and learns a search policy that adapts across completed tasks. Across benchmarks and backbones, it achieves comparable state-of-the-art performance with token usage reduced by up to 59.2%.

  • Problem

    Delayed, entangled outcomes obscure the incremental benefit of additional retrospective search, while evolving observations and environments can make learned search-value estimates stale.

    Source: §1 · p. 2

  • Method

    ForkPilot uses Search Value Dynamics to characterize search gain and cost, then learns a policy from completed trajectories and updates it as new trajectories become available.

    Source: §1 · pp. 2–3, §3.2 · p. 6

  • Results

    Across 6 diverse benchmarks and 7 LLM backbone families, ForkPilot achieves comparable state-of-the-art performance while reducing token usage by up to 59.2%.

    Source: §1 · p. 3

  • Takeaways & Limitations

    ForkPilot frames long-horizon retrospective search as dynamic computation allocation under Attribution Complexity and Adaptation Complexity.

    Source: §6 · p. 11

    The source-to-current bound does not certify the learned margin or deployed controller, and its shift terms are unavailable during deployment.

    Source: §3.1 · p. 5

Abstract

from arXiv · show

Interactive language-model agents increasingly solve complex tasks through long-horizon, multi-call reasoning, where errors in beliefs or actions can compound across tool interactions. Retrospective search can recover from such failures but is prone to misallocation. Delayed outcomes obscure the contribution of intermediate search decisions, leading to Attribution Complexity, while evolving execution evidence leads to Adaptation Complexity, where previously learned estimates become stale. To address these challenges, we first introduce Search Value Dynamics (SVD), which characterizes the evolving trade-off between the gain and cost of retrospective search. Building on SVD, we propose ForkPilot, a self-evolving two-stage policy-learning framework. In the first stage, ForkPilot learns a search-value policy offline from completed trajectories through automatically constructed outcome comparisons. In the second stage, it makes search decisions based on current observations and then self-evolves by incorporating newly completed trajectories into subsequent policy updates. We evaluate ForkPilot across 6 diverse benchmarks and 7 widely used LLM backbone families, including four open-source families, GPT-5.6 Sol, and Opus 4.8 in a production agentic system, against 9 competitive baselines, including a real-world harness deployment used by hundreds of thousands of paid users. ForkPilot achieves comparable state-of-the-art performance while reducing token usage by up to 59.2%, demonstrating its efficacy.

1 Introduction

Retrospective search can revisit failed or partial trajectories, but allocating it is difficult because delayed outcomes obscure the value of intermediate decisions and evolving evidence can stale learned estimates. ForkPilot introduces Search Value Dynamics and a self-evolving policy, achieving comparable state-of-the-art performance with lower token usage.

1 Introduction

  • Retrospective search uses trajectory actions, observations, and completion feedback to revisit beliefs and decisions, gather observations, and explore alternatives.When earlier states can be restored, it can fork from one while preserving the valid action prefix; the archive example revises a mistaken belief after checking key bindings.Source: §1 · p. 1
  • Delayed, entangled outcomes create Attribution Complexity, while changing observations and environments create Adaptation Complexity by making learned search-value estimates stale.These challenges motivate questions about understanding search value under delayed rewards and dynamically allocating inference resources through accumulated experience.Source: §1 · p. 2
  • ForkPilot builds on Search Value Dynamics, which characterizes how the gain-cost trade-off of retrospective search evolves.Its two-stage policy learns from completed trajectories, then makes decisions from current observations and incorporates newly completed trajectories into later updates.Source: §1 · pp. 2–3
  • Across 6 benchmarks and 7 LLM backbone families, ForkPilot achieves comparable state-of-the-art performance while reducing token usage by up to 59.2%.The evaluation includes a production agentic system and 9 competitive baselines, including a real-world harness deployment.Source: §1 · p. 3

2 Preliminaries

Retrospective search allocates forks and rollout depth from partial observations under a task-level computation budget. Its value is defined through paired replays, while the policy is restricted to decisions based on currently available information and permitted completed experience.

2.1 Challenges in Long-horizon Retrospective Search

  • The controller observes a summary of task, trajectory, explored branches, and remaining budget, then chooses a feasible allocation such as fork count and rollout depth.It cannot observe the full environment state or future events; u0 continues execution without forking.Source: §2.1 · p. 3
  • Paired replay compares an allocation with no forking from the same restored state under coordinated randomness, a common continuation rule, and the same total-budget constraint.Completed pairs provide learning and evaluation targets, but deployment does not require paired replay at every decision.Source: §2.1 · p. 3
  • Attribution Complexity measures the variability of completed rewards from a search allocation at a fixed observation; with n independent paired replays, sample-mean variance is AΓ_t(u)/n.Greater attribution complexity requires more completed pairs for the same sampling precision.Source: §2.1 · p. 3
  • Adaptation Complexity arises because new observations or environment changes can shift the reward law, making source estimates stale at a fixed input.For rewards in [0, 1], the source-to-current expected reward difference is bounded by 2 TV(P, Q), and by 2DKL(P∥Q) when the stated finite-KL condition holds.Source: §2.1 · p. 3

2.2 Problem Definition

  • The problem seeks causal policies that select feasible actions using current observable inputs and parameters fitted only on permitted completed experience.A hard budget constrains each complete execution, while λ governs the reward-cost trade-off among feasible decisions; updates occur after tasks finish.Source: §2.2 · p. 4

3 Learning Retrospective Search Allocation

Search Value Dynamics characterizes uncertainty in estimating the value of retrospective search and the discrepancy that can arise when source estimates are reused. ForkPilot addresses these challenges with cross-task policy refitting and within-task decisions based on updated observations and search evidence.

3.1 Search-value dynamics

  • Attribution uncertainty combines paired-replay variation in reward and cost with ambiguity when different histories map to the same controller input.At fixed input and action, the variance of the sample mean net effect decreases as VΓ_src(u)/n; representation ambiguity adds a second variance term.Source: §3.1 · p. 4
  • Changing observations, explored branches, remaining budget, or environment can make source estimates stale and can change the feasible action menu.These shifts motivate rescoring at eligible decisions, but do not establish that a newly fitted prediction is more accurate.Source: §3.1 · pp. 4–5
  • The source-to-current search-value bound diagnoses estimation uncertainty and shift, but it does not certify the learned margin or deployed controller.Its probability statement is not uniform over adaptively chosen inputs or menus, and its shift terms are unavailable at deployment.Source: §3.1 · p. 5

3.2 FORKPILOT: Two-stage Self-evolving Policy

  • Stage I learns search effects and their reliability from paired completed trajectories, then refits policy parameters as newly completed deployment tasks expand the source pool.Each pair labels only its selected action; training needs neither human allocation labels nor paired replay at every deployment decision.Source: §3.2 · p. 6
  • Stage II keeps fitted parameters fixed within each task, repeatedly rescoring the current feasible menu and selecting a positive-lower-score action, a capped probe, or no search.The capped probe is chosen by lowest predicted normalized full-execution cost difference when an upper score is positive; otherwise the controller skips the round.Source: §3.2 · p. 6

4 Experiments

FORKPILOT is evaluated against nine baselines across six benchmarks and seven backbone families, with tests of efficiency, scale robustness, frontier-model deployment, feedback leakage, and sample-efficient self-evolution.

4.1 Experimental Settings

  • The evaluation spans six benchmarks and seven backbone families, compares nine baselines, and includes open-weight and proprietary models.Benchmarks cover workflow automation, tool-user interaction, software engineering, multimodal tool use, web interaction, and general interactive tasks.Source: §4 · p. 6, §4.1 · pp. 7–8

4.2 Consistent Efficiency across Various Benchmarks

  • 36.2% raw-token savings and 30.3% uncached-token savings accompany a +0.23-point mean task-score change relative to full RTS across six benchmarks.Benchmark-level raw-token savings range from 31.8% on SWE-bench to 39.8% on AutomationBench, with mean score changes within +0.50 points.Source: Table 1 · p. 7, §4.2 · p. 9

4.3 Robust Efficiency across Different Backbone Scales

  • At 4B, 9B, 27B, and 122B-A10B scales, raw-token savings are 28.5%, 33.7%, 37.0%, and 35.8%, while mean score changes remain +0.27, +0.27, +0.30, and +0.23 points.Uncached-token savings at those scales are 23.7%, 28.8%, 32.5%, and 31.0%, respectively.Source: Table 2 · p. 8, §4.3 · p. 9

4.4 Consistent Efficiency on Frontier Black-box Models

  • On proprietary backbones, FORKPILOT uses 58.8–77.8% of RTS raw tokens and 40.8–76.3% of uncached tokens while remaining comparable in performance.Compared with RDS, it scores higher in all four settings while reducing raw inference cost by 53.1–78.9%.Source: §4.4 · p. 9, Table 3 · p. 9

4.5 Leakage-Free Feedback and Sample-Efficient Self-Evolution

  • Feedback-masked scores are similar to the original, while shuffling feedback across tasks lowers scores by 1.4–2.8 points relative to feedback-masked.The audit concludes that observed gains are not driven by evaluator-information leakage through the retrospective prompt.Source: §4.5 · p. 10, Table 4 · p. 10
  • With 25% of the training split, FORKPILOT recovers 81–85% of the full-training improvement across evaluated AutomationBench settings.The figure plots the fraction of full-training improvement recovered against the fraction of the training split used for policy learning.Source: §4.5 · p. 10, Figure 2 · p. 10

5 Related Work

Related work covers retrospective search and adaptive computation, alongside methods that learn from completed interactions. The paper distinguishes its focus on allocating retrospective computation during execution.

Retrospective Search and Adaptive Computation

  • Retrospective search revisits earlier decisions and explores alternative trajectories, while metareasoning studies which computations are worth performing under limited resources.Examples include Tree of Thoughts, Language Agent Tree Search, ExACT, and methods that adapt test-time computation to difficulty, confidence, or complexity.Source: §5 · pp. 10–11

Learning to Control Search

  • Experience-based methods use prior trajectories to build reflections, memories, optimized context, or reusable skills, rather than learning how much retrospective computation to allocate during execution.The passage names Reflexion, ReasoningBank, ACE, GEPA, and Trace2Skill.Source: §5 · p. 11

6 Conclusion

The conclusion frames retrospective search as dynamic computation allocation under attribution and adaptation challenges, and presents FORKPILOT as a self-evolving policy-learning approach. Across six benchmarks and multiple backbone families, it reports comparable state-of-the-art performance with token savings up to 59.2%.

6 Conclusion

  • Delayed outcomes obscure intermediate search decisions, while evolving execution evidence can make previously learned estimates stale.The paper names these challenges Attribution Complexity and Adaptation Complexity.Source: §6 · p. 11
  • FORKPILOT learns a search-value policy offline from completed trajectories, then makes decisions on current observations and updates the policy with newly completed trajectories.Search Value Dynamics characterizes the evolving trade-off between retrospective-search gain and cost.Source: §6 · p. 11
  • Across six benchmarks and multiple widely used LLM backbone families, FORKPILOT achieves comparable state-of-the-art performance while reducing deployment-time token usage by up to 59.2%.Source: §6 · p. 11

A Derivation and Scope of Search Value Dynamics

The derivation separates paired net-effect variation from variation in reward alone and uses a conditional variance decomposition to describe uncertainty across histories represented by the same controller input.

A Derivation and Scope of Search Value Dynamics

  • The paired net effect combines reward and normalized cost, so variation in reward alone does not determine its sampling variation.For conditionally independent paired draws at a fixed input and action, the mean’s variance scales with the net-effect variance divided by the number of pairs.Source: §A.1 · p. 15
  • Conditioning on the controller representation decomposes value variation into residual variation after history is known and variation across histories mapped to the same input.The derivation defines the permitted history H, its representation Z, and the history-conditioned expected net value g(H, u).Source: §A.1 · p. 15
  • The variance identities do not establish that pairing reduces variance relative to a particular unpaired estimator.The source explicitly limits what can be inferred from the identities themselves.Source: §A.1 · p. 15

A.2 Proof of Theorem 1

The section gives a fixed-quantity proof and its local decision implications, then specifies how the controller represents states, learns from paired replays, forms operational scores, acts, and updates after completed tasks.

A.2 Proof of Theorem 1

  • With fixed inputs, menu, counts, and replay rule, a simultaneous source-sampling event bounds all candidate actions; the theorem does not cover adaptively chosen inputs or menus.Replay samples across actions need not be independent, and the source-fitted predictor’s realized discrepancy is retained explicitly.Source: §A.2 · pp. 15–16, §A.3 · p. 17

A.3 Decision consequences and scope

  • Positive lower scores rule out skip as a local maximizer, nonpositive upper scores make skip locally optimal, and more informative inputs can raise expected best value under a fixed menu and history distribution.These are local implications; the information comparison does not establish a closed-loop guarantee.Source: §A.3 · p. 17

B Model Configuration

  • The model-configuration section specifies the task and information boundaries used for source collection, feature construction, and controller fitting.The action-level specification is presented as additional to the system walkthrough.Source: B Model Configuration · p. 17

B.1 State and action representation

  • The controller state uses permitted-prefix features, while a recurrent encoder maps observable state and the host supplies feasible actions and resource information.Features include event and tool categories, branch relations, outcomes, depth, search count, token use, and bounded summaries of tool arguments and observations.Source: §B.1 · p. 17

B.2 Paired replay protocol, targets, and value prediction

  • Paired replay compares each candidate with skipping from the same restored state, using matched permissions, budget rules, and continuation policy; rejected pairs are excluded from fitting.Table 6 describes two continuations per arm, and source-collection costs count both executed arms and other collection calls.Source: §B.2 · pp. 18–19, Table 6 · p. 19

B.3 Empirical margin and interval-consistent stopping rule

  • An empirical margin combines a support-dependent term with a calibrated residual quantile to form lower and upper operational scores, which govern regular execution, probing, and skipping.The scores are decision scores; under exchangeability the construction gives marginal coverage for a new realized paired target, not conditional-mean coverage.Source: §B.3 · p. 20

B.4 Runtime rule and pseudocode

  • At each opportunity, the runtime rule selects a positive-lower-score action, otherwise an eligible positive-upper-score probe, otherwise skips that round; a skip does not end the task.If support or the artifact is unavailable, the declared host fallback applies within the hard budget.Source: §B.4 · pp. 20–21, Table 7 · p. 21

B.5 Online updates and censoring

  • Only completed eligible tasks enter later fitting blocks; within-task parameters remain frozen, while later artifacts may be refit from completed source tasks before subsequent evaluation.Truncated executions without evidence of future improvement are censored rather than assigned zero search value.Source: §B.5 · p. 22

B.6 Baseline definitions

The section distinguishes rollout-allocation baselines from context or memory interventions and specifies the evaluated backbone and image-adapter scope.

B.6 Baseline definitions

  • RTS explores alternative continuations from earlier states with three beams, whereas RDS continues only from the final resumable node of one initial rollout.The eight matrix comparators are BoN-5, RTS, RDS, ACE, ReasoningBank, Reflexion, GEPA, and Trace2Skill; BoN-1 and GHCP appear only in the separate frontier-model comparison.Source: §B.6 · p. 22

C.1 Released model checkpoints

  • The backbone matrix contains no proprietary models, and reproducibility requires pinning each release revision and its serving and decoding configuration.The controller uses observable events rather than model activations or gradients.Source: §C.1 · p. 23, Table 9 · p. 23
  • Image-bearing observations use the same frozen Qwen3.5-9B adapter for every backbone, so visual-task scores describe the adapted interface rather than native-interface results.Adapter tokens, including those from unsuccessful branches, count toward each method’s cost.Source: §C.1 · p. 23

C.2 Task groups, outer folds, and source roles

The evaluation uses task-grouped outer folds and fixed source roles, with manifests recording run configuration; token accounting distinguishes deployment costs from learning costs and amortization.

C.2 Task groups, outer folds, and source roles

  • Controller support requires at least 20 distinct source tasks for an action and a five-nearest-task distance no greater than the source 90th percentile; otherwise the recorded fallback applies.Trigger, cap, support, and fallback settings are frozen from source validation.Source: §C.2 · p. 24
  • The 600-task AutomationBench panel uses three grouped outer folds, each with 400 source tasks and 200 held-out tasks, with related instances and replay arms kept within task groups.Methods share the same outer split, and each aggregate combines out-of-fold predictions.Source: §C.2 · p. 24
  • Within-benchmark learning does not establish transfer to a new environment or unseen backbone, and source roles remain disjoint as the source pool grows.Predictor fitting, margin fitting, and residual calibration use separate task-grouped roles.Source: §C.2 · p. 24

C.3 Token costs, learning cost, and amortization

  • Raw deployment cost subtracts cache-hit input tokens from input tokens and adds output tokens; learning-inclusive cost also accounts for source collection and online updates.With positive per-task savings, the approximate break-even deployment count is (Csrc + Cupdate)/∆C.Source: §C.3 · p. 24

C.4 Robustness to Host Rollout Scheduling

The section tests whether ForkPilot’s efficiency holds across host schedules and bounds how several additional comparisons should be interpreted. It also specifies cold-start, saturation, stopping-rule, and mechanism-control protocols.

C.4 Robustness to Host Rollout Scheduling

  • Sequential ForkPilot uses 11.1% and 14.2% fewer raw tokens, and 27.6% and 28.5% fewer uncached tokens, than parallel ForkPilot on AutomationBench and τ 3-Bench, respectively.Scores increase from 69.00 to 75.00 and from 64.43 to 64.95; latency is not measured.Source: §C.4 · p. 25, Table 11 · p. 25
  • Under both parallel and sequential schedules, ForkPilot reduces uncached tokens versus schedule-matched RTS, though the quality–cost trade-off varies by schedule.Savings are 44.4%/59.2% under parallel execution and 36.5%/64.1% under sequential execution on AutomationBench/τ 3-Bench.Source: §C.4 · p. 25, Table 11 · p. 25

C.5 Scope of the frontier-model comparison

  • At the Opus 4.8 AutomationBench operating point, ForkPilot uses 22.2% fewer raw and 23.7% fewer uncached inference tokens than Opus RTS, with a 0.0416 lower task score.The comparison is descriptive; aggregate records do not establish a noninferiority interval or matched-cost superiority.Source: §C.5 · p. 25, Table 12 · p. 26

D.1 True cold start and nested source-size curves

  • The cold-start and nested-source-size protocol starts with no trained weights, calibration residuals, source normalizers, or experience memory, and keeps held-out tasks outside updates.Learned artifacts are frozen before evaluation, while batch and online fitting use expanding source prefixes.Source: §D.1 · p. 26

D.2 Saturation and order sensitivity

  • The first 90% crossings occur at 300 tasks for 9B batch, 300 for 9B online, 200 for 27B batch, and 300 for 27B online, supporting early, noisy saturation rather than a universal threshold.Because mean curves can reverse at larger source sizes, normalization uses the best observed state on the evaluated grid.Source: §D.2 · pp. 26–27

D.3 Manual and learned stopping under the same action scope

  • The manual rule skips the current round when the permitted incumbent score reaches its threshold; the learned-stopping-only policy chooses between a fixed action and skipping.The principal contrast is learned stopping versus a source-selected manual control at matched cost; full ForkPilot additionally varies fork/depth and probes.Source: §D.3 · p. 27

D.4 Same-host mechanism controls

  • The current-score controller uses only incumbent score, remaining budget, action descriptor, and feasibility mask, while the event analysis tests whether new evidence changes allocation targets.The hindsight action uses completed paired continuations and is not claimed to be available online.Source: §D.4 · p. 27

E Additional Results

The additional-results tables describe stopping-rule and mechanism comparisons, event-conditioned evidence, identifier masking, cross-benchmark replication, and frontier-backbone evaluations.

Stopping-rule ablation

  • Table 13 reports AutomationBench stopping-rule operating points and paired intervals for two predeclared comparisons, including a ±2% raw-cost equivalence criterion.Manual and learned-stopping-only policies share a singleton fork/depth action and no probe; full ForkPilot uses the complete action menu.Source: Table 13 · p. 28

Mechanism contrasts

  • Table 14 gives paired effects of full ForkPilot against four named mechanism ablations on AutomationBench, with simultaneous 95% hierarchical intervals.Positive score differences and negative raw-token differences favor full ForkPilot.Source: Table 14 · p. 28

Mechanism ablation

  • Table 15 compares AutomationBench mechanism variants under a shared host, feasible actions, paired source records, held-out tasks, and matched controller seeds.Full, probe, and skip frequencies are percentages of retrospective opportunities and sum to 100 within each row.Source: Table 15 · p. 29

Event-conditioned evidence

  • Table 16 examines event-conditioned changes in paired net search value, using sign flips before and after new events and agreement with hindsight actions.Refreshed-versus-frozen-prefix utility is normalized paired net value.Source: Table 16 · p. 29

Identifier-masking control

  • Table 17 evaluates identifier masking by replacing newly revealed literal identifiers with typed placeholders while preserving event type, schema, success/error status, and value length.Source: Table 17 · p. 29

Cross-benchmark replication

  • Table 18 reports cross-benchmark replication on WorkArena++ with Qwen3.5-27B using the AutomationBench source-selection and information-boundary setup.Source: Table 18 · p. 30

Frontier-backbone evaluation

  • Table 19 details task scores and inference-token totals and ratios for frontier proprietary backbones, with score differences relative to full RTS in matched settings.GHCP uses the strict task-success metric; negative token savings indicate higher cost than RTS.Source: Table 19 · p. 30

Frontier-backbone comparison

  • Table 20 compares frontier proprietary backbones using task scores and raw/uncached token ratios relative to full RTS; lower ratios are better.For GHCP and GEPA, scores use the reported Strict metric; GHCP denotes the production GitHub Copilot harness, and RDS is depth-only retrospective search.Source: Table 20 · p. 31
Loading 2610.04889v1…