acceptodds
Under review as a conference paper at ICLR 2027

PASTA: PROVENANCE-GUIDED ABDUCTIVE SELECTION FOR TAILORED AGENTS

Abstract

Self-correction repairs a failed LLM agent from feedback on its final output, and a common design choice is to revise or regenerate that output as a whole. We show that, for agents that act on a user profile, this discards information that the trajectory carries in the provenance of its commitments. The dominant failure, which we call inference promotion, turns an inference about the user into a constraint the user never stated and builds later decisions on it; it accounts for 55% of 300 annotated natural failures. PASTA extracts a provenance-typed belief graph from the trajectory, scores each commitment that could explain a verifier-reported violation by a provenance prior and predicted repair, and regenerates from the candidate that best trades this score against downstream cost. With gold answers withheld from every model-visible stage, PASTA reaches 74% repair success against 66% for matched Reflexion and 68% for the strongest simple restart rule, and its margin grows with the number of faults. On five multi-hop and planning benchmarks with injected faults and identical feedback, it outperforms the strongest baseline on every dataset by 2.6 to 9.8 points. On the 300 natural failures, it repairs 76% against 64% for matched full-output retry, comes within one point of annotated-root restart, and cuts reuse of the unsupported belief on follow-up tasks from 30% to 10%. Provenance relative to the user profile is a repair signal, and where to restart is a different question from where the fault began.

Primary area:
foundation or frontier models, including LLMs
Keywords:
LLM agents, self-correction, fault attribution, abductive reasoning, root-cause analysis, personalization, user-conditioned agents, agent reliability

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_hd3JOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes a framework for repairing LLM agent failures by selecting where to restart based on belief provenance, predicted repair success, and downstream cost. Experiments on multiple benchmarks and human-annotated failures show improved repair success over existing self-correction methods and reduced reuse of unsupported beliefs.

Critical strengths
  1. The proposed method is well motivated and has a clear intuition.

  2. The empirical evaluation is broad.

Critical weaknesses
  1. Although the authors compare their method with self-correction baselines, there is no direct comparison made between their method and others like CausalFlow, RIR, and dependency guided rollback repair.

  2. In the restart criterion, the normalized plausibility score is combined with the descendant cost in an equally weighted manner. However, the relative significance of each component is subject to the number of candidates available, thus the dominance of the cost component for large belief networks.

Questions for authors
  1. Could the authors add a workflow diagram showing PASTA pipeline?

  2. How sensitive is the restart selection to the number of candidate nodes and the relative weighting of plausibility and cost? Could the authors provide a sensitivity analysis?

  3. Since the counterfactual proposals are not directly used during regeneration, how well do the predicted repair outcomes align with actual repair success? Have the authors evaluated this consistency?

2 comments
AuthorsOpenReview ↗

Specialized Repair Baselines, Paired Significance, and Oracle Limits

We thank the reviewer for pointing out that a comparison solely against generic self-correction methods does not distinguish PASTA from targeted rollback or counterfactual-intervention approaches. We added direct, matched evaluations of the requested repair paradigms (Section 4.5; Appendix K, Table 14a), and clarified their mechanisms and relationship to PASTA in Section 5.

Common experimental setting. We start with the same 785 initially failed, answer-blind trajectories, provide each method the same task, user profile, fixed observations, and constraint-only violation feedback, and permit at most three repair attempts. Each item combines 3–5 profile/task predicates, with mean 2.6 co-occurring violations. The outcome is strict conjunctive verifier acceptance: leaving any predicate violated counts as failure. This is not the same population or outcome as the 300 natural failures in Table 3a, which average 1.2 violated predicates and are judged on the primary failure by blinded evaluators. The difference matters when interpreting the absolute percentages.

Results and paired tests. PASTA repairs 128/785 (16.31%). Direct LLM step attribution (ATTR, informed by CORRECT) repairs 105/785 (13.38%), a PASTA improvement of +2.93 percentage points (95% CI [+0.64,+5.22], Holm p=0.0280p=0.0280). A DoVer-inspired diagnose/intervene/verify adaptation repairs 102/785 (12.99%) (+3.31 pp, CI [+0.51,+5.99], Holm p=0.0280p=0.0280). Three-attempt matched full-output retry repairs 101/785 (12.87%) (+3.44 pp, CI [+1.15,+5.73], Holm p=0.0114p=0.0114). Dependency-guided rollback repairs 97/785 (12.36%) (+3.95 pp, CI [+1.40,+6.50], Holm p=0.0114p=0.0114); RIR-inspired interval checkpointing repairs 91/785 (11.59%) (+4.71 pp, CI [+2.29,+7.13], Holm p=0.0011p=0.0011). These are paired comparisons with multiplicity correction, not differences between unrelated runs.

CausalFlow comparison. We also implemented a CausalFlow-inspired minimal-intervention baseline for a 100-case candidate-matrix subset. Its repair rate is 17/100 (17.0%), compared with 20/100 (20.0%) for PASTA; its observed mean is 2.34 attempts (Table 14a). This smaller subset provides directional evidence rather than a claim of statistically established superiority. We explicitly label all specialist baselines as single-agent adaptations of the relevant paradigms, not verbatim reproductions of systems designed for other execution environments.

Why the absolute rate is low. We exhaustively evaluated restart candidates at all 3,191 nodes in these 785 belief graphs (11,979 regeneration outcomes; Table 16a). In 626/785 cases (79.75%), no single candidate restart succeeds with the original observations held fixed, often because independent constraints fail simultaneously. Thus even an oracle that sees all candidate outcomes has a 159/785 (20.25%) ceiling within this intervention family. PASTA's 128 successes amount to 80.5% of that oracle-repairable subset, not 16.31% of an unconstrained population. Independent external-gold correctness is 107/746 (14.34%) and strict joint pass is 103/746 (13.81%); we report these to distinguish constraint acceptance from reference correctness.

Distinct mechanism. Attribution, checkpointing, and full retry can identify a step or re-run from a checkpoint, but PASTA explicitly distinguishes user-stated facts from unsupported model-inferred commitments. It combines a provenance prior, counterfactual predicted repair, and normalized descendant cost to choose a restart that may differ from the earliest causal fault. The claim is therefore not that PASTA invented rollback, but that user-relative provenance improves which partial restart to select. These experiments directly address the missing specialist comparisons while retaining the fixed-observation scope of the evaluation.

AuthorsOpenReview ↗

Workflow, Graph-Size and Cost Sensitivity, and Counterfactual Validity

We thank the reviewer for identifying three connected presentation and mechanism questions: whether cost overwhelms plausibility on large graphs, whether the complete execution flow is understandable, and whether counterfactual proposals predict actual repairs. We now address all three with Figure 2 and Tables 15–16 (Sections 2 and 4.5; Appendix K).

Q1: Workflow (Figure 2). The five-stage diagram makes Algorithm 1 explicit: (1) verify the task/profile constraints and extract a provenance-typed belief graph G=(A,E)G=(A,E); (2) construct candidate set CC from beliefs at the violated step, their ancestors, and the final-decision node; (3) generate minimal counterfactual replacement probes and predicted repair indicators; (4) select a cost-aware restart a∗a^*, preserve the original prefix, and prune the downstream commitments; (5) regenerate the suffix from fixed observations and verify again. Unsuccessful candidates are excluded on subsequent attempts, with their initial plausibility mass down-weighted. The proposal is used to rank candidates, not inserted as a required edit into the regeneration prompt.

W2/Q2: Meaning of equal weighting. For candidate ii, normalized descendant cost is δi=(∣Di∣+1)/max⁡k∈C(∣Dk∣+1)\delta_i=(|D_i|+1)/\max_{k\in C}(|D_k|+1); selection maximizes qi−λδiq_i-\lambda\delta_i, with published λ=1\lambda=1. Although qiq_i sums to one, δi\delta_i is normalized within each graph, so graph size alone need not determine the trade-off. Retried candidates are excluded; for remaining candidates qi(r)=qi(0)/Zrq_i^{(r)}=q_i^{(0)}/Z_r, where Zr=1−(1−α)∑k∈Trqk(0)≤1Z_r=1-(1-\alpha)\sum_{k\in T_r}q_k^{(0)}\leq1. This increases the relative influence of plausibility versus cost on later attempts (Proposition 3).

Direct cost-weight sweep (Table 16b). With λ=0\lambda=0 (plausibility only), first-pick/three-attempt repair is 14.52%/16.43%, saving 24.1% of regenerated tokens versus root restart. At λ=1\lambda=1, the rates are 14.39%/16.31% with 40.2% saving. At λ=2\lambda=2, they become 13.50%/15.41% with 48.6% saving; choosing the cheapest node alone yields 10.83%/13.12% with 61.4% saving. Hence the default sacrifices just 0.12 pp three-attempt repair relative to pure plausibility in exchange for 16.1 pp additional regenerated-token savings. The trade-off is measured, rather than assumed optimal for every application.

Graph-size stratification. For small graphs (K∈2,3K\in{2,3}, n=312n=312), PASTA's first pick repairs 15.06% against 10.96% for uniform random (+4.10 pp). For medium graphs (K∈4,5K\in{4,5}, n=341n=341), the rates are 14.37% versus 10.02% (+4.35 pp); for large graphs (K≥6K\geq6, n=132n=132), 12.88% versus 8.90% (+3.98 pp). This stable relative margin does not support the concern that descendant cost inevitably collapses selection quality at larger KK, while acknowledging that absolute repair becomes harder.

Q3: Proposal versus actual outcome. We regenerated from every one of 3,191 nodes (11,979 outcomes; Table 16). 378 nodes truly repair their case. Counterfactual Boolean proposals identify 254/378 (67.2% recall) and correctly reject 2,427/2,813 (86.3% specificity); TP/FP/TN/FN are 254/386/2,427/124. The Boolean predictor's Brier score is 0.1598, improving modestly to 0.1541 for provenance-weighted normalized qiq_i. First-pick PASTA repairs 113/785 (14.39%) versus random 10.20% (gain +4.20 pp, 95% CI [+2.15,+6.28], p=0.00014p=0.00014). The retry-context comparison is 13.12% versus 9.26% (p=0.00038p=0.00038).

Finally, on 785 cases a three-arm test (Table 15) finds 16.31% repair with prefix-only truncation, 16.05% after adding the proposed replacement (McNemar p=0.93p=0.93), and 15.16% with neutral length-matched text. Accordingly the counterfactual is a useful selection signal, but does not become an edit that the model must obey. This distinction is now explicit throughout the workflow description.

Reviewer_pMvAOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies how to repair failures of LLM agents that act on a user profile. The authors identify a characteristic failure, which they call inference promotion: the agent turns an inference about the user into a constraint the user never stated and builds later decisions on it. They report that it accounts for 55% of 300 natural failures. They propose PASTA, which extracts a belief graph annotated with provenance (profile, tool, external evidence, world knowledge, or model inference) from the trajectory. After the verifier reports a violation, PASTA takes the violated step and its ancestors as candidates, scores each candidate by a provenance prior multiplied by a predicted repair rate, subtracts a downstream cost, and selects the restart point. It then keeps the prefix before that point and regenerates only the suffix. Experiments include an answer-blind comparison on Llama 3.1 8B (74% for PASTA vs. 66% for matched Reflexion), injected-fault experiments on five multi-hop and planning benchmarks, repair on 300 natural failures (76% vs. 64% for full-output retry), and a follow-up evaluation in which reuse of the unsupported belief drops from 30% to 10%.

Critical strengths
  1. The paper defines a concrete failure mode of personalized agents, inference promotion, clearly and gives a four-element criterion for identifying it. Distinguishing facts stated by the user from inferences made by the model is an intuitive and practically useful repair signal.

  2. The control design of Table 1 is in the right direction. All arms start from the same trajectories and share the repair model, prompt, feedback, and number of attempts, differing only in the restart policy. The selector controls (random candidate, final decision, most recent step) and the ablations that remove the provenance prior, the graph, or proposal scoring isolate the contribution of restart selection itself.

  3. Beyond checking whether the current task passes the verifier, the paper tests whether the unsupported belief resurfaces on a new task after repair, which is a meaningful evaluation angle for repair methods. The authors also report unfavorable results, such as the loss on Amazon records and the results with larger models.

Critical weaknesses

W1. The repair rewrites the final answer from the existing observations rather than re-executing the trajectory, so the main repair results do not show that the agent's trajectory is repaired.

  1. Regeneration receives the task, the profile, the prefix, information about downstream nodes, and the existing tool observations, but not the replacement proposed during candidate scoring (§2 and Appendix I). The re-execution prompt tells the model to use the available tool observations "exactly as given", to "not invent new external facts", and to "return only the final answer" (Appendix P). In the deployment example of Figure 1, after restarting from "needs 99.99% availability", the database and region choices should depend on new query results, but the model can only rewrite them from the original observations. The difference between methods therefore reduces to which node the model is told to start changing from.
  2. The repair rates in Table 1 and Table 3a (74% vs. 66% and 76% vs. 64%) thus measure whether the rewritten final answer is accepted, not whether the agent repaired its trajectory in actual execution. The drop in reuse from 30% to 10% (Table 3b) raises the same issue: if only the final answer is rewritten, it is unclear what the state retained for the follow-up task contains, since Appendix J only says that it is "preserved exactly as the agent would retain it".

W2. The evidence does not show that the gains come from the provenance prior, or that they hold beyond Llama 3.1 8B.

  1. The faults injected in Table 2 are context notes suggesting a near-miss answer and flipped profile constraints. Neither is inference promotion, and the prior gives external evidence and profile facts low weights (0.4 and 0.15, against 1.0 for model inferences), so the gains there cannot be explained by the claimed mechanism. On the 300 natural failures, removing the prior costs 7 points (Table 3a), but the paper does not show where PASTA actually restarts. On 85 annotated TravelPlanner trajectories, its restart points match the annotated earliest faulty step in only 7 cases, with an MRR of 0.21 against 0.22 for a random ancestor (Table 3c). The paper describes this as intended, but it leaves no direct evidence that PASTA restarts from the promoted inference in the 165 promotion cases.
  2. All core results come from Llama 3.1 8B. With DeepSeek-V3 and Gemini-2.5-Flash, Reflexion leads in 7 of 8 cells, most clearly on TruthfulQA (83.3 vs. 41.7 and 75.0 vs. 44.4, Table 13), and the final configuration was not run on these models. The user profiles are mostly synthesized from templates, and on PersonalWAB, the only benchmark whose profiles come from real user histories, every method exceeds 91%, leaving little room to separate them. The tailored agents in the title are therefore not validated in realistic settings.
Questions for authors
  1. How does PASTA differ from DoVer (arXiv:2512.06749), which also intervenes at a suspected faulty point, keeps the prefix, re-executes, and notes that several different interventions can repair the same failure, and from CORRECT (arXiv:2509.24088), which localizes step-level errors in multi-agent trajectories? Could at least one of them be compared under the same setting?
  2. For Table 1, what are the sample size and the task sources, how were the initial failed trajectories produced, and which rule is the "strongest simple restart rule"?
  3. Which tasks and agent do the 300 natural failures come from, and who are the annotators and judges? Why do only 150 of the 165 promotion cases enter the follow-up evaluation, and how are the follow-up tasks constructed and reuse judged?
  4. Can regeneration issue new tool calls and obtain new observations, what exactly does the retained state in the follow-up evaluation contain, and how do the results change if the replacement proposed during candidate scoring is passed to regeneration?
  5. Could you report repair rates on the 300 natural failures separately for promotion and non-promotion cases, together with the share of PASTA's restart points that fall on the promoted inference, the final decision, and other nodes?
  6. How were the provenance weights chosen, and why is one minus the extraction confidence (1−ℓ_i) used to measure how suspicious a belief is, given that a confident extraction does not make the belief correct?
  7. Could you report the final configuration on DeepSeek-V3 or Gemini-2.5-Flash?
8 comments
AuthorsOpenReview ↗

Fixed-Observation Trajectory Repair, Retained State, and Proposed-Edit Ablation

We thank the reviewer for the careful distinction between rewriting a final response and re-executing an agent with new external tool calls (W1/Q4). We agree that the original language risked suggesting stronger operational claims than our experiments support. The revision specifies the execution boundary, follow-up state, and effect of supplying the counterfactual edit (Section 2 and Figure 2; Appendix J; Table 15).

Exactly what is regenerated: PASTA takes a failed trajectory τ\tau, identifies a restart point among the violated step's beliefs and their ancestors, preserves all trajectory steps preceding that point, and regenerates the downstream beliefs, filtering/planning decisions, and answer after that point. The regeneration prompt receives the task, user profile, original prefix, candidate downstream context, and previously obtained observations. It does not issue fresh external API queries or acquire new tool results. We therefore characterize the experiments as closed-world, fixed-observation suffix regeneration, not validation of arbitrary online agent re-execution.

Why fixed observations can still test a meaningful repair. For the evaluated QA tasks, the available supporting passages have already been retrieved. In PersonalWAB, the full 20-item recommendation slate is available. In TravelPlanner, the relevant sandbox tables are pre-fetched. The original observations thus include the complete candidate set available to the agent in that benchmark. Regenerating after the promoted inference forces the system to reapply user constraints and select downstream decisions from those observations, while preserving unaffected earlier steps. This is more structured than free-form final-output retry, but we agree it does not test whether new searches, database queries, or environment interactions would change after a rollback. The USD 500-budget deployment scenario in Figure 1 is illustrative; it is not evidence that PASTA re-queries cloud providers after changing the uptime assumption. Open-world tool re-execution is now an explicit limitation.

What persists across the second turn. The follow-up evaluation does not simply prompt a model with the final answer string. It preserves accepted belief-graph commitments and the final Task 1 summary as session state. If the selected restart is a promoted inference or an upstream ancestor, the selected commitment and its descendants are pruned from that accepted state. The follow-up presents a new entity, date range, or destination under the same user profile, designed so that the original unstated constraint could be improperly reapplied (Appendix J). Blinded judges check whether the Task 2 trace/output enforces that unsupported constraint. This is evidence about recurrence in the benchmark's retained-state representation, not a demonstration of arbitrary persistent memory repair.

Follow-up results and sample selection. Of 165 natural inference-promotion cases, 150 have paired multi-session second-turn tasks; the other 15 are single-turn items without a paired follow-up template. Exactly the same 150 cases are used for every arm, and reuse is counted over all 150 rather than only successful repairs. After PASTA, the unsupported belief recurs in 15/150 (10%) versus 45/150 (30%) for full-output retry and 28% for final-decision restart (Table 3b). These numbers show that choosing a restart can affect retained commitments and later behavior within the stated protocol.

Does passing the proposed replacement help? We performed a three-arm, 785-case ablation with 2,355 evaluations (Table 15). Standard prefix-only regeneration repairs 128/785 (16.31%), with 107/746 (14.34%) external-gold correctness. Conditioning suffix regeneration on the counterfactual proposed replacement repairs 126/785 (16.05%), with 104/746 (13.94%) external-gold correctness (Δ=−0.25\Delta=-0.25 pp, 95% CI [-3.06,+2.42], exact McNemar p=0.93p=0.93). A length-matched neutral control repairs 119/785 (15.16%). The proposed edit is therefore a diagnostic ranking probe; giving it to the generator does not improve repair under this evaluation. We have stated both this finding and the closed-world boundary directly rather than calling the outcome general open-world trajectory repair.

AuthorsOpenReview ↗

Natural Inference Promotion, Restart Location, and Provenance Evidence

We agree with the reviewer's distinction between injected failures that are not inference promotion and naturally occurring errors of the type PASTA is designed to address. The injected context-note and flipped-constraint tasks in Table 2 evaluate general repair under matched feedback; they should not be offered as direct evidence of the promotion mechanism. We therefore added a mechanism-specific analysis of the 300 natural failures, plus restart localization, provenance-prior sensitivity, and real-user-history results (Tables 3, 16b, 17a; Section 4.3; Appendix J).

Separately identifying promotion. Two blinded authors coded each natural failure against four conditions (Table 10): (i) a fact actually stated in the profile, (ii) a distinct inference not supported by that fact, (iii) the inference promoted into an operative requirement, and (iv) downstream decisions depending on it. Agreement is approximately κ=0.78\kappa=0.78. 165/300 (55%) meet all four criteria. This separates the claimed failure mechanism from generic answer errors or corruption in external evidence. It also explains why a provenance prior favoring model-inferred commitments may help more for these cases than on corrupted Amazon product attributes, where the observed evidence itself is wrong.

Promotion-specific repair (Table 17a). On 165 inference-promotion failures, PASTA repairs 133/165 (80.6%), versus 105/165 (63.6%) for matched full-output retry: Δ=+17.0\Delta=+17.0 pp, p<0.0001p<0.0001. On the 135 non-promotion failures, the rates are 95/135 (70.4%) versus 87/135 (64.4%), a smaller +5.9 pp gap (p=0.038p=0.038). Together these are 228/300 (76%) versus 192/300 (64%), matching Table 3a. The larger promotion-specific gap is the most direct evidence that PASTA's gains are concentrated in the failure mode motivating its design; it does not claim the method only helps promotion failures.

Where PASTA actually restarts. In the 165 promotion cases, the selected restart falls at the promoted inference in 103/165 (62.4%), at another ancestor/intermediate node in 35/165 (21.2%), and at the final decision in 27/165 (16.4%). This directly addresses the missing restart distribution. The low agreement with the earliest annotated fault on a separate 85-item TravelPlanner attribution sample (PASTA top-1 7/85, MRR 0.21 versus random ancestor MRR 0.22) answers a different question. PASTA optimizes successful, economical restart, not exact earliest-fault labeling. Indeed, Proposition 2 favors cheaper admissible later nodes when multiple restart positions work. We do not treat low earliest-fault agreement as a high attribution score.

Why the provenance prior matters. Equation 2 uses πi=wρimax⁡(0.05,1−ℓi)\pi_i=w_{\rho_i}\max(0.05,1-\ell_i) with fixed weights 1.0 (model inference), 0.6 (world knowledge), 0.4 (external evidence), 0.25 (tool), 0.15 (profile fact). These encode that an unsupported inferred rule is a stronger restart suspect than the correctly stated profile fact it cites; they were not tuned per dataset. Importantly, ℓi\ell_i is confidence in the extraction/grounding of that commitment, not the probability the belief is correct. Removing the (1−ℓi)(1-\ell_i) factor yields 12.99% first-pick repair rather than 14.39%; replacing provenance weights with uniform weights yields 11.46%; perturbing the weights by ±25\pm25% changes the first-pick rate by only -0.25 pp (p=0.78p=0.78; Table 16b). The original 300-case prior-removal ablation also falls from 76% to 69% (Table 3a).

Real-history personalization. PersonalWAB profiles are constructed from real purchases, ratings, and reviews, unlike the synthetic profile templates elsewhere. Although the full benchmark has a >91% accuracy ceiling effect, the 45 initially failed natural PersonalWAB cases show 37/45 (82.2%) repair for PASTA versus 30/45 (66.7%) for retry. In the separate harder 785-case pool's 110-item PersonalWAB slice, the rates are 19.1% versus 14.5%. These are limited but direct real-history failure-slice tests, not a claim of deployed personalization. Profile redraws favor PASTA in 92/100 samples on average, but the preregistered bottom-decile robustness criterion fails; that limitation remains disclosed.

AuthorsOpenReview ↗

Baseline Implementations, Evaluation Protocols, and Stronger Models

We thank the reviewer for requesting enough protocol detail to reproduce and interpret the comparisons, rather than accepting headline rates alone. Appendix J now specifies the matched and natural-failure cohorts and annotation process; Section 4.5 and Appendix K add adapted specialist baselines and final-configuration scale tests. This reply addresses Q1–Q3 and Q7, complementing our separate replies on execution scope and inference promotion.

Q1: Relation to DoVer and CORRECT. We agree that prefix preservation and intervention alone are not new. DoVer focuses on step interventions and subsequent verification; CORRECT concerns locating erroneous steps in a multi-agent trajectory. Our distinct question is which restart should be chosen when an agent operating under a specific user's profile promotes its own inference into a user constraint. PASTA scores user-relative provenance, predicted counterfactual repair, and downstream regeneration cost. We added DoVer-inspired step intervention and direct LLM step attribution (ATTR, motivated by CORRECT), plus RIR-inspired checkpointing, dependency rollback, and retry. Because the original methods target different agent settings, we describe these as single-agent adaptations, not exact reproductions.

Matched specialist evaluation (Table 14a). The 785 initially failed answer-blind cases receive identical constraint-only feedback, fixed observations, and a three-attempt cap. PASTA repairs 128/785 (16.31%) versus 105/785 (13.38%) for ATTR (+2.93 pp, Holm p=0.028p=0.028), 102/785 (12.99%) for DoVer-inspired repair (+3.31 pp, Holm p=0.028p=0.028), 101/785 (12.87%) full retry (+3.44 pp, Holm p=0.011p=0.011), 97/785 (12.36%) dependency rollback (+3.95 pp), and 91/785 (11.59%) RIR-inspired checkpointing (+4.71 pp). A CausalFlow-inspired baseline on 100 cases repairs 17% versus 20% for PASTA; we do not claim that smaller difference establishes superiority. Each item stacks 3–5 constraints (mean 2.6 violations), requiring every predicate to pass. Exhaustive candidates show a 20.25% within-graph oracle ceiling, so these rates are not directly comparable to Table 3a's simpler primary-failure grading.

Q2: Table 1 sample and strongest simple rule. Table 1a is based on 300 initially failed answer-blind Llama 3.1 8B trajectories, 75 each from HotpotQA, 2Wiki, MuSiQue, and Bamboogle/StrategyQA profile-conditioned tasks. Initial outputs were generated at temperature 0 and retained when at least one task/profile constraint failed. Every arm begins with the same failed trajectory and receives the same task, profile, model, feedback, and up-to-three-attempt limit. The strongest simple restart rule is the earliest violated ancestor (root restart), achieving 68.0%, compared with matched Reflexion 66% and PASTA 74%. Gold answers and target-bearing fields are withheld from every model-visible stage and reserved for final scoring.

Q3: Natural-failure origin and annotation. The separate 300 natural failures, generated with Llama 3.1 8B at temperature 0, are TravelPlanner 75, LongMemEval 60, 2Wiki 60, MuSiQue 60, and PersonalWAB 45. Two author annotators/judges independently coded promotion using four explicit criteria and evaluated repaired outputs while blinded to method identity/order (κ≈0.78\kappa\approx0.78 for promotion). Among the 165 promotion cases, 150 have paired multi-session follow-ups; the remaining 15 are single-turn items lacking follow-up templates. Task 2 changes an entity, date, or destination under the same profile. Accepted belief-graph commitments and Task 1 summaries are retained, and blinded judging checks whether the unsupported Task 1 requirement recurs in the Task 2 trace/output. This evaluates reuse over the same 150 cases for all arms (Appendix J).

Q7: Final configuration at scale. We did run the requested answer-blind final method on two stronger backbones, with matched Reflexion and quote-normalized JSON parsing over 322 deduplicated failures per model (Table 13b). On DeepSeek-V3, PASTA is 80/322 (24.84%) versus 68/322 (21.12%) (Δ=+3.73\Delta=+3.73 pp, p=0.0169p=0.0169); on Gemini-2.5-Flash, 74/322 (22.98%) versus 63/322 (19.57%) (Δ=+3.42\Delta=+3.42 pp, p=0.0266p=0.0266). We retain Table 13a's unfavorable earlier runs and explain answer-bearing binary feedback and Gemini's 42% schema-parser drop. The new tests answer the scale question under the final protocol without rewriting the historical evidence.

Reviewer_DMg7OpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

PASTA studies inference promotion: an agent silently elevates an unsupported inference about a user into a new requirement, which could potentially override explicit user constraints (e.g., budget).

To repair such failures, PASTA extracts a provenance-labeled belief graph, distinguishing user-provided facts from model inference, tools, and external sources. It ranks commitments by suspicion and predicted repair benefit, then selects a restart point that balances repair potential against regeneration cost. It preserves earlier work, regenerates the remainder, and verifies the result.

The authors report 74% repair success versus 66% for matched Reflexion in an answer-blind controlled experiment, and 76% versus 64% for matched retry on 300 natural failures. Follow-up tests also show less reuse of unsupported beliefs.

Critical strengths
  • A useful problem formulation and an intuitive repair strategy: the paper identifies inference promotion, which treats unsupported model inferences as user requirements, and uses provenance to guide repair.

  • Meaningful empirical support: the answer-blind controlled experiments and natural-failure evaluation show improved repair success over matched baselines, while the provenance ablation supports the value of abductive ranking.

Critical weaknesses
  • The rule-based verifier seems less practical PASTA assumes a rule-based verifier that detects and localizes constraint violations. It remains unclear how robust the method is to missed violations, false alarms, or incorrect localization, particularly beyond benchmark-checkable constraints.

  • The abductive score needs stronger justification Although the ablations support its usefulness, the score combines fixed provenance weights and extraction confidence with an LLM’s predicted repair benefit. Sensitivity to these choices, and the correspondence between predicted benefit and actual repair success, are insufficiently justified.

  • The strongest evidence is narrow. The clean studies use Llama 3.1 8B. Several broader QA experiments provide expected-answer information. An earlier configuration loses to Reflexion in 7 of 8 stronger-model comparisons, and the final version wasn’t tested there. This doesn’t necessarily suggest the final method fails, but leaves a question mark. (Table 13)

  • The efficiency claim is incomplete. The reported 40% saving concerns regenerated tokens versus annotated-root restart, but not total cost. Graph extraction and candidate scoring also cost inference. It is desirable to have repair success at matched total compute, not just matched attempt counts.

Questions for authors
  • Stronger-model generalization Could you evaluate the final configuration on stronger models under the same answer-blind, matched-feedback protocol as the clean studies? What explains the earlier configuration’s weaker performance in Table 13, and is there evidence that the final changes address those failures?

  • End-to-end efficiency What is the total inference cost, which includes graph extraction, replacement proposals, candidate scoring, and all regeneration attempts? Does PASTA retain its advantage over retry and simpler restart strategies when compared at matched total token or monetary budgets, rather than matched attempt counts?

  • Verifier robustness How does PASTA behave when violation feedback is incomplete, incorrect, or mislocalized? Could you clarify the population and failure types behind the 3% false-acceptance finding in Appendix L, and which constraints your verifier cannot assess?

  • Abductive ranking justification

Beyond the existing component ablations, how sensitive are results to the provenance weights and extraction-confidence term? Do the predicted repair scores reliably rank actual repair success?

4 comments
AuthorsOpenReview ↗

Final-Configuration Replication on DeepSeek-V3 and Gemini-2.5-Flash

We thank the reviewer for highlighting the apparent failure to generalize beyond Llama 3.1 8B and the unfavorable stronger-model results in the earlier Table 13. We agree this was an important unresolved question. The revision preserves the earlier unfavorable results as Table 13a and adds a new test of the final PASTA configuration on 322 deduplicated answer-blind failures for each of DeepSeek-V3 and Gemini-2.5-Flash (Section 4.5; Appendix K, Table 13b).

What the earlier table actually tested. Table 13a evaluated an answer-informed, nonsequential earlier configuration, not the final answer-blind method with sequential retry. Reflexion led PASTA in seven of eight DeepSeek/Gemini benchmark cells. We did not dismiss these results; we inspected the evaluation path and identified two concrete protocol artifacts that made the original comparison unreliable as a test of final-configuration generalization.

First, on binary QA tasks such as TruthfulQA/StrategyQA, the original flat violation feedback conveyed the opposite-polarity label on a wrong prediction to full-output Reflexion. Thus Reflexion could invert its answer without repairing the reasoning or violating commitment. This was especially relevant to the large TruthfulQA gap. Second, the original strict no-retry JSON extraction parser rejected 42.0% of Gemini-2.5-Flash belief-graph calls, often due to unescaped internal quotation marks, so Gemini schema compliance was only 58.0%. These failed parses were counted as failed PASTA cases, confounding method quality with a serialization defect. The source audit and the before/after schema rates are reported rather than silently overwriting Table 13a.

Final matched protocol. In the new runs, gold answers and target-bearing metadata are withheld at every model-visible stage: initial trajectory, graph extraction, proposal/scoring, verifier feedback, and regeneration. Gold/reference answers are used only for independent final evaluation. PASTA and matched Reflexion receive the same failed instances, constraint-only feedback, model, and attempt limit. The parser uses quote-normalized JSON handling rather than auto-failing on harmless escaping errors. Compliance reaches 98.4% on DeepSeek-V3 (versus 94.1% raw) and 97.8% on Gemini-2.5-Flash (versus 58.0% raw).

Results on DeepSeek-V3. Final PASTA repairs 80/322 (24.84%) versus 68/322 (21.12%) for matched Reflexion, an improvement of Δ=+3.73\Delta=+3.73 pp (95% CI [+0.93,+6.52]). The paired discordant counts are 17 PASTA-only successes versus 5 Reflexion-only, yielding an exact two-sided McNemar p=0.0169p=0.0169. This gives a paired test of the final protocol, rather than inferring scale from other models' results.

Results on Gemini-2.5-Flash. Final PASTA repairs 74/322 (22.98%) compared with 63/322 (19.57%) for matched Reflexion: Δ=+3.42\Delta=+3.42 pp (95% CI [+0.62,+6.21]). Discordant pairs are 16 versus 5, with exact McNemar p=0.0266p=0.0266. This reverses the direction of the older comparison under the final answer-blind, parse-normalized setting.

Interpretation and scope. The new tests demonstrate an advantage on two additional stronger backbones for the final evaluated configuration. They do not establish that PASTA wins for every backbone or all prompt distributions; earlier Table 13a remains as evidence of sensitivity to feedback serialization and methodology. The principal lesson is that stronger-model comparisons must control both answer leakage and schema compliance, not merely model identity. We have made the configuration distinction explicit in Section 3 and Appendix K so readers can identify exactly which claim each table supports.

AuthorsOpenReview ↗

End-to-End Inference Cost and Cost-Repair Comparisons

We agree that regenerated-token savings alone do not establish efficiency. The previously highlighted approximately 40% saving measures regenerated suffix tokens relative to annotated-root restart in the natural-failure study, not extraction, counterfactual probing, ranking, and regeneration together. To address W4/Q2 we added a full provider-call audit and a new cost-annotated baseline study (Section 4.5; Appendix K, Tables 14a–b and 16b).

Accounting boundary. PASTA extracts a belief graph, computes provenance priors, generates counterfactual probes, scores candidate nodes, and regenerates from selected prefixes for up to three attempts. A successful unchanged trajectory typically uses two model calls; a repaired trajectory takes roughly 2+∣C∣+k2+|C|+k calls, with k≤3k\leq3 attempts. Earlier Table 11 counted only agent and extraction tokens and thus understated PASTA's total cost. The revised results aggregate 8,536 historical provider call records, including the relevant pipeline stages, using cold USD prices and full-run rather than one-step accounting (Table 14b).

Whole-run benchmark suite (Table 14b). Mean cost per case is USD 0.002550 for PASTA, versus USD 0.003069 for Reflexion (PASTA 16.9% cheaper), 0.002976 for Self-Refine (14.3% cheaper), 0.003777 for SelfCheckGPT (32.5% cheaper), and 0.016570 for Tree of Thoughts (84.6% cheaper). Matched full-output retry costs USD 0.002471: PASTA is USD 0.000079 more, so we describe it as near-matched, not cheaper. On the separate 300 natural failures, PASTA repairs 76% versus 64% for matched retry, but we keep the cost and repair cohorts distinct rather than treating the audit as an exact matched-dollar replication of Table 3a.

The harder matched-failure pool (Table 14a). The new 785-case answer-blind pool has 3–5 simultaneous profile/task predicates (mean 2.6 violated predicates), scored by a strict conjunctive verifier. Three-attempt PASTA repairs 128/785 (16.31%), costing USD 0.00406/case. Three-attempt full-output retry repairs 101/785 (12.87%), costing USD 0.00382/case. Thus PASTA gains Δ=+3.44\Delta=+3.44 pp (95% CI [+1.15,+5.73], Holm-adjusted p=0.0114p=0.0114) for an incremental USD 0.00024/case. This makes the marginal cost and paired improvement explicit; it does not pretend the cost is identical.

Restricting PASTA to one attempt. Including extraction and probing, PASTA's first pick repairs 113/785 (14.39%) at USD 0.00180/case, less than half the total cost of three-attempt full retry (USD 0.00382) while achieving a higher repair rate than that retry (12.87%). This one-attempt configuration also outperforms the repair percentages of specialist 3-attempt baselines: ATTR 13.38%, DoVer-inspired 12.99%, dependency rollback 12.36%, and RIR-inspired 11.59%. However, these specialist methods cost USD 0.00112–0.00155/case, and are therefore cheaper than one-attempt PASTA. We label this low-cost, not strictly equal-dollar, evidence.

Efficiency versus restart placement (Table 16b). The score qi−λδiq_i-\lambda\delta_i makes this trade-off controllable. At λ=0\lambda=0 (no cost penalty), three-attempt repair is 16.43% with 24.1% regenerated-token savings. At published λ=1\lambda=1, it is 16.31% with 40.2% savings; at λ=2\lambda=2, 15.41% with 48.6% savings. This separates suffix token economy from full inference cost. Our conclusion is a favorable measured cost/repair trade-off under the tested workloads, not a universal constant-dollar Pareto frontier. A strictly dollar-matched sweep across all specialized methods remains an informative future comparison.

AuthorsOpenReview ↗

Verifier Robustness, Provenance Sensitivity, and Ranking Calibration

We thank the reviewer for raising two separable concerns: whether a rule verifier can be trusted when feedback is incomplete or wrong (W1/Q3), and whether the provenance-weighted score predicts actual repair rather than merely reflecting heuristic choices (W2/Q4). The revision adds verifier-scope audits, controlled feedback corruption, exhaustive candidate evaluations, and prior perturbations (Section 4.5; Appendices K–L, Tables 16–17).

Verifier coverage and the 3% figure. The evaluated verifier can check codified constraints such as numeric budgets and arithmetic, explicit exclusions, JSON schema, and itinerary/task rules. It cannot reliably adjudicate uncodified stylistic or cuisine preferences, subjective multi-attribute trade-offs, or general semantic correctness. The previous 3.0% independent-check disagreement concerns verifier-accepted outputs in the audited population. It decomposes into 1.8% soft stylistic/cuisine preferences and 1.2% unstated trade-offs outside the formal predicate set; 0.0% false acceptance on audited hard arithmetic/exclusion checks. We do not interpret this as a general 97% accuracy guarantee for a real-world verifier or as evidence that the method detects all implicit user preferences (Appendix L, Table 17b).

False alarms and mislocalization (785-case noise test). Starting from 16.31% clean-verifier repair, injecting 10% synthetic false-alarm/mislocalized step feedback yields 14.51% (loss 1.80 pp); 20% noise yields 12.91% (loss 3.40 pp). Under the same perturbations, direct step attribution (ATTR) falls from 13.38% to 7.78% (loss 5.60 pp) and 4.28% (loss 9.10 pp). A user-relative provenance prior gives correctly grounded profile facts low suspicion (wρ=0.15w_{\rho}=0.15), so a noisy localization signal need not force PASTA to rewrite a stated constraint. These are controlled synthetic perturbations, not deployment measurements.

Missed violations (false negatives). On multi-violation trajectories, with 10% of violation signals dropped, upstream-ancestor restart retains 14.14% repair (loss 2.17 pp); with 20% dropped, it retains 12.61% (loss 3.70 pp, about 77% of the clean rate). Restarting upstream can remove several dependent bad commitments even when the verifier reveals only part of the problem. But entirely unreported, non-shared, or non-formalizable constraints remain a limitation.

Candidate-level predicted versus actual repair. We exhaustively regenerate from 3,191 candidate nodes across 785 failed graphs (11,979 outcomes, Table 16a). Of 378 nodes whose restart actually repairs the case, the Boolean counterfactual indicator identifies 254: 67.2% recall. Among 2,813 nonrepairing nodes, it rejects 2,427: 86.3% specificity (TP/FP/TN/FN = 254/386/2,427/124). The Boolean indicator has Brier 0.1598; provenance-weighted normalized qiq_i gives 0.1541. This is a modest calibration improvement, not a claim of perfect predicted probabilities. Importantly, the selection outcome independently improves: first-pick PASTA repairs 113/785 (14.39%) versus 10.20% for a uniform random candidate (Δ=+4.20\Delta=+4.20 pp, 95% CI [+2.15,+6.28], p=0.00014p=0.00014).

Prior definition and sensitivity. Equation 2 uses πi=wρimax⁡(0.05,1−ℓi)\pi_i=w_{\rho_i}\max(0.05,1-\ell_i), with fixed weights 1.0 model inference, 0.6 world knowledge, 0.4 external evidence, 0.25 tool observations, 0.15 profile facts. Here ℓi\ell_i is confidence that the commitment was correctly extracted/grounded, not proof that the belief is true; the 0.050.05 floor avoids a zero prior for an extracted node. We do not fit these weights per benchmark. Perturbing them by ±25\pm25% gives 14.14% first-pick repair (change −0.25-0.25 pp, p=0.78p=0.78), versus default 14.39%. Dropping (1−ℓi)(1-\ell_i) gives 12.99%; uniform provenance weights yield 11.46% (Table 16b). These experiments substantiate the direction of the prior while leaving learned, domain-adaptive priors as future work.

I would like to thank authors for their response. Given that they provide solid results on model generation, end-to-end inference and repair cost, ranking calibration and verification robustness, I would raise the score.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Revised Experiments and Reviewer Responses

We thank the Area Chair and all three reviewers for their detailed critiques. The revised manuscript expands the experimental evidence and clarifies what PASTA does and does not establish. We provide separate, numbered replies to each reviewer so that each concern can be evaluated against the relevant manuscript result.

New specialized comparisons (Section 4.5; Appendix K, Table 14a). We evaluate PASTA against direct step attribution (ATTR, motivated by CORRECT), DoVer-inspired intervention, dependency-guided rollback, RIR-inspired checkpointing, and matched full-output retry. On 785 answer-blind multi-constraint failures, PASTA repairs 128/785 (16.31%) versus 11.59%–13.38% for these comparators; paired Holm-adjusted tests give p≤0.028p\leq0.028. These failures are harder than the 300-case natural cohort: they contain 3–5 stacked constraints (mean 2.6 simultaneous violations) and require every constraint to pass. Exhaustively testing 3,191 candidate nodes gives a 20.25% within-graph oracle ceiling, explaining the lower absolute rates. The adapted baselines are not claimed to reproduce the original multi-agent systems exactly.

End-to-end efficiency (Section 4.5; Table 14b). We account for graph extraction, counterfactual proposals, scoring, and regeneration using 8,536 provider call records. On the main multi-attempt suite, PASTA costs USD 0.00255/case, versus USD 0.00307 for Reflexion, 0.00298 for Self-Refine, 0.00378 for SelfCheckGPT, 0.01657 for Tree of Thoughts, and 0.00247 for full retry. On the harder 785-case pool, three-attempt PASTA costs USD 0.00406/case (16.31% repair) versus USD 0.00382 (12.87%) for retry; a one-attempt PASTA configuration repairs 14.39% at USD 0.00180. Cheaper specialized methods are not strictly dollar-matched, a distinction retained in our analysis.

Mechanism, robustness, and scope (Section 2; Tables 15–17). Figure 2 now traces verification, belief-graph extraction, abductive probing, restart choice, and suffix regeneration. A 785-case edit-conditioning ablation finds 16.31% repair from node-only truncation versus 16.05% when the diagnostic replacement is passed to regeneration (p=0.93p=0.93): the proposal informs selection but is not required as a replacement instruction. Across 11,979 candidate outcomes, first-pick PASTA repairs 14.39% versus 10.20% for random selection (p=0.00014p=0.00014). Sensitivity experiments vary graph size, cost weight, and provenance priors; verifier experiments inject false alarms and missed violations. We explicitly limit our claims to closed-world regeneration from fixed retrieved/tool observations, not new external API calls.

Natural failures and broader models (Tables 13b and 17a). Among 165 natural inference-promotion failures, PASTA repairs 133/165 (80.6%) versus 105/165 (63.6%) for retry and restarts at the promoted inference in 62.4%. On 322 deduplicated answer-blind failures, the final PASTA configuration exceeds matched Reflexion on DeepSeek-V3 (24.84% versus 21.12%, p=0.0169p=0.0169) and Gemini-2.5-Flash (22.98% versus 19.57%, p=0.0266p=0.0266). We retain the earlier unfavorable, answer-informed results and document the feedback-leakage and JSON-parsing artifacts. The reviewer-specific replies address all remaining questions, including limits of verifier coverage and profile generalization. We also retain the unfavorable earlier Amazon-record result and the failed preregistered bottom-decile profile-robustness criterion. These qualifications distinguish documented improvements from claims we cannot yet support in open-world tool execution or unformalized user preferences.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.