PaperlayerView exact revision on arXiv

Source-linked AI summary

ASCT: Attentive Search over Counterfactual Trees for Credit Assignment in Agentic Reinforcement Learning

Yang Li, Jinhan Yang, hai liu, Di Wan, Xiyu Chen, Zongsi Xu, Tuo Zhou, Sheng Zhong, Sergey Volkov, Ye Luo, Hao Sun

arXiv:2609.35215v1cs.AI

TL;DR

Agentic workflows are scored by terminal utility, but learning needs credit for the decisions that produce them. ASCT evaluates alternative legal actions from recoverable prefixes and uses actor-centered values to train PPO on actor-sampled trajectories. Its evaluators improve held-out utility over PPO baselines, while deployment uses the actor alone.

  • Problem

    Terminal utility evaluates a complete workflow, but a successful workflow can still contain a poor local choice, so learning needs credit connected to each decision’s downstream consequences.

    Source: §1 · p. 1

  • Method

    ASCT evaluates alternative legal actions from recoverable prefixes at actor-visited states, centers their values with frozen actor probabilities, and uses them to credit actor-sampled PPO decisions.

    Source: §1 · pp. 1–2

  • Results

    All three evaluators improve mean held-out utility over trajectory-return PPO and workflow-adapted VinePPO; ASCT-AgentUCT reaches 0.6187 versus 0.5939 for VinePPO.

    Source: §1 · p. 2

  • Takeaways & Limitations

    ASCT connects executable multi-step action comparisons to actor-trajectory PPO updates, and the learned policy executes without deployment search.

    Source: §8 · p. 12

    Evidence covers one backbone, a finite RAG library, three training seeds, 100-question transfer cohorts, and a constructed description probe.

    Source: §7 · p. 12

Abstract

from arXiv · show

Terminal utility evaluates a complete agentic workflow, but learning requires credit for the decisions within it. We introduce Attentive Search over Counterfactual Trees (ASCT), a framework that turns training-time multi-step search into local action credit. At actor-visited states, an auxiliary tree evaluates alternative legal actions from the same recoverable prefix. Its action-value table is centered by the frozen actor's probabilities and supplies credit for PPO on actor-sampled trajectories. This protocol connects counterfactual evaluation to policy learning while deploying the actor alone. Uniform, UCT, and cost-aware AgentUCT instantiate the framework. On HotpotQA agentic retrieval-augmented generation, all three improve mean held-out utility over trajectory-return PPO and workflow-adapted VinePPO. Across three seeds, ASCT-AgentUCT reaches 0.6187 utility versus 0.5939 for VinePPO, with gains in answer F1 and execution cost, and uses 50.3% fewer recorded auxiliary Qwen tokens. Transfer and component-description studies examine the learned policies beyond the training setting.

1 Introduction

Workflow utility scores complete agentic workflows, but learning also needs credit for individual decisions and their downstream consequences. ASCT evaluates alternative legal actions from recoverable prefixes to train actor-sampled decisions, and its evaluators improve held-out utility over PPO baselines.

1 Introduction

  • Terminal utility combines answer quality and execution cost, yet a successful workflow can still contain a poor local choice, motivating decision-level credit tied to downstream consequences.Source: §1 · p. 1
  • The paper frames ASCT against VinePPO state-value credit by comparing executable alternatives at actor-visited states and training decisions sampled by the actor.VinePPO estimates state values from Monte Carlo continuations for step-wise credit (Kazemnejad et al., 2025).Source: §1 · p. 1
  • ASCT evaluates multi-step legal-action alternatives from recoverable prefixes, centers their action values with frozen actor probabilities, and uses them to credit the actor’s sampled PPO decisions.The actor deploys alone, without the auxiliary search.Source: §1 · pp. 1–2
  • All three evaluators improve mean held-out utility over trajectory-return PPO and workflow-adapted VinePPO; ASCT-AgentUCT reaches 0.6187 versus 0.5939 for VinePPO.ASCT-AgentUCT also combines higher answer F1 with lower execution cost and uses 50.3% fewer recorded auxiliary Qwen tokens.Source: §1 · p. 2
  • The framework links multi-step action comparison at recoverable states with separate evaluation allocation and behavior sampling, actor-centered credit, and an actor-only deployed policy.Uniform, UCT, AgentUCT, and WTB provide inherited search and execution components (Li et al., 2026).Source: §1 · p. 2

2 Related Work

Related work spans state-value and counterfactual credit, tree-based agentic learners, and search allocation or execution reuse. ASCT differs by evaluating legal-action values at separately sampled actor states while PPO updates only actor-trajectory decisions.

Auxiliary evaluation and credit

  • VinePPO supplies step credit from Monte Carlo state values, while ASCT estimates action values through workflow execution; both credit the main actor trajectory.COMA instead uses a policy-weighted counterfactual baseline with a centralized critic (Foerster et al., 2018).Source: §2 · p. 2

Tree-based RL for agentic decisions

Search allocation and execution reuse

  • UCT allocates trials using reward and uncertainty, while ASCT uses AgentUCT’s reuse-aware allocation and WTB execution infrastructure to acquire training credit and assess acquisition cost and the learned actor.LATS and related methods search for deployed actions (Zhou et al., 2024; Koh et al., 2024); AgentUCT and WTB are from Li et al. (2026).Source: §2 · p. 2

3 Problem Formulation

The formulation treats an agentic decision as a choice among finitely many legal actions from a state containing the task, executed workflow prefix, and observations. Learning maximizes expected terminal utility, with recoverable prefixes enabling alternative continuations.

3 Problem Formulation

  • A state contains the task, executed workflow prefix, and observations, and the actor chooses from a finite legal action set.Source: §3 · p. 3
  • Terminal workflow utility combines answer quality and execution cost, and the learning objective is expected terminal utility.The PPO learner is held fixed to compare credit estimators, with B terminal trials per evaluated state.Source: §3 · p. 3
  • Recoverable prefixes permit alternative continuations at actor-visited states, while equal logical budgets may require different physical work.Auxiliary work is logged separately from workflow execution utility; RQ2 defines the cost-adjusted metrics.Source: §3 · p. 3

4 ASCT

ASCT separates actor behavior from auxiliary evaluation: trees compare legal actions from recoverable workflow prefixes, then actor-centered credit trains the actor’s sampled decisions. Search supplies training-time information; deployment uses the actor alone.

4 ASCT

  • At each visited state, a frozen actor samples its action while an independent random stream evaluates alternatives from recoverable copies of that state.Source: §4 · p. 3
  • Tree nodes represent workflow prefixes and edges legal actions; trials execute selected paths to completion, and each root-action value averages its trial returns.Root coverage evaluates every action before repeat allocation when B ≥ |A(s)|.Source: §4 · p. 3
  • ASCT credits the sampled action relative to the actor; the actor-centered credit supplies a local policy-gradient signal before normalization and clipping.Source: §4 · p. 3
  • Uniform balances visits, UCT uses utility and exploration, and AgentUCT also accounts for predicted uncached cost; WTB restores shared prefixes and executes uncached suffixes.The evaluators and VinePPO use WTB execution infrastructure.Source: §4 · p. 3
  • Each actor decision records its state, sampled action, behavior probability, and centered credit; PPO uses the behavior probability in its ratio, while auxiliary branches stay outside update trajectories.The next iteration refreshes states and credit with the updated actor, and deployment runs the actor alone.Source: §4 · pp. 3–4
  • Figure 1 contrasts ASCT action-value credit with VinePPO state-value credit while showing that both share actor-trajectory PPO updates.Solid arrows denote behavior records, dashed arrows auxiliary information, and frozen probabilities center ASCT’s action table.Source: Figure 1 · p. 4

5 Experiments

The experiments evaluate ASCT on HotpotQA agentic RAG, measuring held-out policy utility, auxiliary evaluation cost, transfer, and description-guided component choice. All methods share a workflow and learning protocol, with final-policy comparisons against PPO and VinePPO.

5.1 Agentic workflow and RAGSpace

  • The HotpotQA RAG workflow permits up to three retrieval rounds, and the actor chooses query, retrieval, evidence, continuation, and reranking decisions.Methods share the actor, workflow, splits, and PPO configuration; final checkpoints are evaluated on 400 test questions over three seeds.Source: §5.1 · pp. 5–6, Table 1 · p. 5

5.2 RQ1: Does counterfactual credit improve the final policy?

  • 0.6187 utility for ASCT-AgentUCT versus 0.5939 for VinePPO, a 0.0248 gain; all three ASCT evaluators improve mean held-out utility over VinePPO and trajectory-return PPO.The gain comprises 0.0151 from higher answer F1 and 0.0097 from lower execution cost.Source: Table 2 · p. 6, Figure 2 · p. 6, §5.2 · p. 6
  • AgentUCT gains 0.0307 and 0.0339 utility over VinePPO on medium- and hard-difficulty questions, while VinePPO is slightly higher on easy questions.The gains are reported across the difficulty panels, which share the utility scale and method order.Source: §5.2 · pp. 6–7, Figure 3 · p. 7

5.3 RQ2: What does auxiliary evaluation cost, and when is it valuable?

  • AgentUCT records 193.09 million auxiliary Qwen tokens, 50.3% fewer than VinePPO and 2.02–2.28% fewer than the other ASCT evaluators.The reduction versus VinePPO chiefly reflects avoided auxiliary actor-continuation scoring; VinePPO uses fewer environment tokens.Source: §5.3 · p. 7, Table 3 · p. 8
  • AgentUCT has the highest mean Jsearch in each iteration and the lowest full-run auxiliary cost; its mean value curve crosses PPO at approximately 360,358 assumed uses.The amortization projections assume the specified token weight and future-use utility, and amortize auxiliary expenditure only.Source: §5.3 · p. 8, Figure 4 · p. 9, Figure 5 · p. 9

5.4 RQ3: Does the learned policy transfer across question distributions?

  • Without further updates, AgentUCT raises utility over VinePPO from 0.5767 to 0.5982 on 2Wiki, while on MuSiQue utility is 0.0048 versus −0.0047.On 2Wiki it improves both F1 and execution words; on MuSiQue lower execution cost offsets slightly lower F1.Source: §5.4 · p. 9, Table 5 · p. 10

5.5 RQ4: Do trained policies retain description-guided component choice?

  • With the retriever fixed, ASCT selects it on 93.3–96.0% of questions under the correct evidence relation, but 19.7–37.3% when that relation is removed.Name-only descriptions yield zero selection, and the opposite relation yields 2.7–5.0%; this is a controlled probe with constructed tags.Source: Table 6 · p. 10, §5.5 · p. 10

6 Discussion

The discussion uses learned-policy comparisons and fixed-state diagnostics to assess ASCT’s action-evaluation interface and its controls.

What the learned-policy results establish

  • Gains across Uniform, UCT, and AgentUCT support the action-evaluation interface across search rules, and Uniform’s effectiveness indicates cost-aware allocation is not required.The discussion frames the methodological contribution as connecting executable multi-step alternatives to actor-trajectory updates.Source: §6 · pp. 10–11

Tree allocation and evaluation budget

  • At B = 12, Uniform lowers repeat Q SD from 0.1203 to 0.0619 and raises sign agreement from 63.3% to 80.0%, using 1.7% more tokens.The Q-SD ordering reverses at B = 48.Source: §6 · p. 11
  • At 48 trials, UCT, AgentUCT, and Uniform reach evaluated utilities 0.6464, 0.6584, and 0.5322, with sign agreement 66.7%, 90.0%, and 90.0%.Figure 6 reports fixed-state repeatability diagnostics, not learned-policy effectiveness.Source: §6 · p. 11, Figure 6 · p. 11

Actor-rollout evaluation within the interface

  • Uniform improves test utility over ActorRollout at every seed and uses 60.2% fewer auxiliary tokens.The contrast tests the full suffix-evaluation mechanism, including allocation and continuation sampling.Source: §6 · p. 11, Table 7 · p. 11

Learning from branch collections

  • The AT2PO adaptation performs close to PPO under the shared configuration, without method-specific tuning.Branch records remain fixed within each update and refresh the next iteration.Source: §6 · p. 11

7 Limitations

The evidence is bounded by the tested model, library, cohorts, and probe, as well as by assumptions of recoverable execution and finite legal actions.

7 Limitations

  • Evidence covers one backbone, a finite RAG library, three training seeds, 100-question transfer cohorts, and a constructed description probe.These are the reported evaluation settings.Source: §7 · p. 12
  • ASCT’s applicability is delimited by recoverable execution and finite legal actions.Source: §7 · p. 12
  • Frozen-state repeatability diagnoses evaluation but does not isolate each component’s contribution to policy gains.Cost projections use the stated auxiliary-token convention; time and price require calibration.Source: §7 · p. 12

8 Conclusion

ASCT turns multi-step workflow comparisons into actor-centered credit for PPO on actor-sampled decisions, with the learned policy executing without deployment search.

8 Conclusion

  • ASCT turns multi-step workflow comparisons into actor-centered credit for PPO on actor-sampled decisions.Source: §8 · p. 12
  • Three evaluators improve mean held-out utility, while cost accounting and transfer studies characterize the gains.Source: §8 · p. 12
  • The learned policy executes without deployment search.Source: §8 · p. 12

Reproducibility statement

The experiment package retains artifacts for reported results, while recomputing retained results and reproducing training are separate procedures.

Reproducibility statement

  • The package retains per-question results, QID manifests, training ledgers, compact credit records, and fixed-state search traces.Source: Reproducibility statement · p. 12
  • Appendices A–G document artifact scope and link reported quantities to retained artifacts.Paper sources and vector figures accompany the manuscript.Source: Reproducibility statement · p. 12
  • Recomputing retained results is separate from reproducing training, which additionally requires recorded models, datasets, and runtime dependencies.Source: Reproducibility statement · p. 12

AI use statement

The paper discloses several uses of generative AI. Its evaluators differ in how they allocate search trials and reuse workflow prefixes.

AI use statement

  • Generative AI assisted with related-work identification, experimental implementation, drafting, revision, methodology feedback, and reference, formatting, and code-test checks.The authors state that they take responsibility for the final submission and its claims.Source: AI use statement · p. 12

A.1 Evaluator and update implementation

  • Uniform samples expansions and continuations uniformly, while UCT allocates repeat visits using mean utility and an exploration bonus.Both rules retain uniform expansion and continuation sampling as described for UCT.Source: §A.1 · p. 14
  • AgentUCT incorporates predicted uncached continuation cost into selection and cost-weights candidate-action sampling.WTB reuses materialized prefixes and executes only uncached suffixes; estimated cost guides allocation, while the ledger records realized work.Source: §A.1 · p. 15

A.2 Online PPO training and tree-free deployment

The section specifies actor-sampled PPO training, fixed workflow prompts and query refinement, auxiliary-token accounting, and held-out evaluation procedures. It also describes paired method comparisons and cost-adjusted projections.

A.2 Online PPO training and tree-free deployment

  • At each actor-visited state, PPO records the actor-sampled action and its actor-centered auxiliary credit; deployment uses the trained actor without auxiliary trees.The frozen actor defines sampling, baseline weights, and the PPO denominator, so the ratio starts at one before updating.Source: §A.2 · pp. 15–16

A.3 Fixed prompts and query refinement

  • Continue uses deterministic query refinement that prioritizes evidence titles appearing in the question and extracts a bridge entity with fixed text patterns.If those patterns do not apply, the query uses a fixed template; the procedure makes no LLM call.Source: §A.3 · p. 18

B Token ledger and cost-adjusted value

  • The auxiliary-token ledger records realized environment execution after reuse and auxiliary actor scoring, while keeping main-trajectory and optimizer scoring separate.The ledger includes recorded embedding and reranking calls; AgentUCT's allocation estimate instead proxies remaining generative work.Source: B Token ledger and cost-adjusted value · p. 18
  • ∆U = 0.02481849 and ∆T = −195,286,252.33 tokens for ASCT-AgentUCT versus VinePPO, yielding a positive projected value difference for every N > 0.The comparison uses total auxiliary cost.Source: B Token ledger and cost-adjusted value · p. 19

C Difficulty-resolved policy results

  • Held-out questions are grouped into easy, medium, and hard sets of 76, 256, and 68 questions, respectively, and endpoints use the official answer scorer.The groups partition the same 400 test questions; results are reported as means and sample standard deviations across three training seeds.Source: C Difficulty-resolved policy results · p. 21, Table 13 · p. 21

D Learning interfaces, evaluator rules, and paired records

E Training credit and frozen-state allocation controls

The section examines how ASCT's credit and search-allocation choices behave in fixed-state controls, then reports continuation and component diagnostics. It also describes retained evidence for recomputing results.

E Training credit and frozen-state allocation controls

  • Actor-weighted versus uniform-action centering changes the sign on 3,117 of 36,000 multi-action decisions (8.66%) in the recorded training decisions.The comparison holds each recorded Q table fixed and evaluates the sampled action's advantage under the two baselines.Source: E Training credit and frozen-state… · p. 22, Table 14 · p. 23
  • At 12 trials, internal allocation lowers repeat Q SD by 48.6% and raises credit-sign agreement by 16.7 percentage points at 1.7% greater token cost.At 48 trials, Uniform's Q SD is 0.0484 versus root MC's 0.0368, while sign agreement is 90.0% versus 83.3%; the ordering depends on budget.Source: E Training credit and frozen-state… · pp. 23–24
  • In the binary-state diagnostic, Uniform tree evaluation lowers mean repeat Q SD from 0.0149 to 0.0064 versus root MC, using 4,158 versus 3,899 environment tokens.Because both reference batches agree on action order at every state, this binary cohort cannot reveal sign differences between actor and uniform baselines.Source: E Training credit and frozen-state… · p. 24, Table 17 · p. 24
  • At 48 trials, full AgentUCT reduces mean executed tokens by 3.4% relative to UCT and raises credit-sign repeat agreement from 66.7% to 90.0%.At 12 trials, AgentUCT uses 3.7% more tokens; these controls make no policy updates.Source: E Training credit and frozen-state… · p. 24
  • At 48 evaluations, UCT and AgentUCT reach mean utilities 0.6464 and 0.6584 versus 0.5322 for Uniform, with Jsearch values 0.5721, 0.5866, and 0.4551, respectively.Credit repeat agreement is 66.7% for UCT and 90.0% for both AgentUCT and Uniform; the curves concern two existing training questions.Source: E Training credit and frozen-state… · p. 26

F Component protocol and continuation diagnostics

  • ASCT-ActorRollout's matched test-utility differences from ASCT-Uniform are −0.0077, −0.0294, and −0.0143 for seeds 11, 23, and 37.ActorRollout changes the continuation mechanism and trains its own evolving actor; the protocol audit found no centering violations.Source: F Component protocol and continuation… · p. 27
  • The AT2PO workflow adaptation reports test utility 0.5647±0.0042 and F1 0.6945±0.0041 across three seeds, with 696.15 ± 19.53 million auxiliary tokens per run.Its paired test-utility difference from PPO is −0.0004 ± 0.0063; this is an exploratory evaluation without method-specific tuning.Source: F Component protocol and continuation… · p. 27

G Retained evidence

  • The retained data package includes matched per-question endpoints, seed-level auxiliary ledgers, compact credit records, and component and transfer probes.Reproducing training also requires the recorded models, indices, and runtime.Source: G Retained evidence · p. 27

Related papers

Loading 2609.35215v1…