acceptodds
Under review as a conference paper at ICLR 2027

Beyond Memory: Harnessing Long-Horizon Agents with Explicit Belief States

Abstract

Large language model (LLM) agents can now undertake increasingly complex tasks, but the way they organize interaction history into memory does not ensure a coherent understanding of the current world. We introduce *PoS*, an inference-time framework that constructs and continually maintains explicit belief states as the agent's decision context. Each belief combines an estimate of the current world state with unresolved task requirements, making explicit what the agent still needs to learn and accomplish. To keep this belief reliable and actionable, *PoS* validates its consistency and monitors task progress to detect *Belief Trapping*, where the agent continues to act without making meaningful progress toward the goal. Recovery is then tailored to both the trapping pattern and the type of unresolved task requirement. Experiments on four benchmarks spanning execution and diagnosis show that *PoS* achieves the highest overall performance on every benchmark with all three LLM backbones. Ablations demonstrate the importance of consistency validation and recovery, while context-scaling experiments show resilience to context growth. Together, these results support belief construction and continual maintenance as a foundation for long-horizon context management beyond history retention and compression. Code is available at https://anonymous.4open.science/r/PoS-321C.

Primary area:
foundation or frontier models, including LLMs
Keywords:
long-horizon agents, context management, belief trapping

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_kTHCOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper proposes PoS, an inference-time framework in which an LLM agent maintains an explicit belief about the world. The belief contains the current world state, plus what the agent still needs to learn or check, and what the agent still needs to do to achieve the given goal. At ecah step, PoS selects one of these unresolved information or required actions, and make an action to resolve it. After an action, LLM proposes belief updates, and a validator LLM (Sentinel in this paper) checks every belief update before it is accepted. When the agent stops making progress (e.g., repeating meaningless actions or looping), PoS detects it, diagnoses the type of stall, and gives targeted recovery instructions. Experiments on ALFWorld, LOCA-Bench, RCA-100, and ClinDiag with three backbones show that PoS outperforms all baselines in every setting.

Critical strengths
  • S1. Addresses a practical failure of LLM agents. Looping between states or repeatedly observing without progress is a common failure mode of LLM agents. PoS offers a concrete, online remedy.
  • S2. Clean method design. PoS separates verified from unverified belief updates, separates what to learn or check from what to do, and makes each action target an explicit subgoal, reducing aimless actions. Monitoring for unproductive actions and loops is also a sensible design choice.
  • S3. Broad evaluation and supporting analysis. Evaluation covers 4 benchmarks with 3 LLM backbones. The Belief Trapping analysis (Sec. 4.2) supports both that the targeted problem is real and that the proposed method addresses it. It shows that trapping occurs frequently across benchmarks and backbones, and that the proposed factorized recovery outperforms a generic recovery prompt.
Critical weaknesses
  • W1. Missing belief-only ablation. Table 1 removes validation and recovery only one at a time, so the other component always remains. A belief-only variant, with neither validation nor trapping diagnosis, would help support the paper's claim that belief construction alone is insufficient.

  • W2. Multiple runs needed in evaluation. All results come from a single run as I understand. Please report results over multiple runs with standard deviation.

  • W3. Key definitions need clarification. Several components central to trapping detection are only loosely described:

    • (a) Active-gap projection WΔW^{\Delta}. App. B.2 only says relevant records are selected "through their existing relations." How exactly is it computed, and is it rule-based or LLM-based?
    • (b) Matching of belief elements across steps. Belief elements are free-form text, so the same state can be phrased differently across steps (e.g., "Microwave 1: closed" vs. "Microwave 1 is shut"). How are elements matched when computing the Jaccard distance dJd_J (Eq. 5b) and PXP_X (Eq. 5a)?
Questions for authors

See weaknesses

3 comments
AuthorsOpenReview ↗

Response to Reviewer kTHC

We thank the reviewer for the comprehensive review and for recognizing the practical importance of belief trapping and the design of PoS. Below, we address the requested ablation, repeated evaluations, and implementation clarifications.


W1: Belief-only ablation without validation or recovery.

A1:

  • Belief-only ablation: We added the Belief-only variant with both consistency validation and trapping diagnosis/recovery removed, retaining belief construction, updates, and gap-guided interaction. We evaluated it over five runs across all four benchmarks and three backbones. Table R3 reports the complete results for PoS and all three ablation variants.

  • Why belief maintenance matters: Removing both consistency validation and trapping diagnosis/recovery further reduces the performance compared with removing either component alone, highlighting the importance of these two maintenance mechanisms. Full PoS exceeds Belief-only by 4.90–17.16 percentage points across all 12 settings. These comparisons further support the central point made in the Introduction: belief construction is only the starting point. And maintaining the belief by validating belief updates and diagnosing and recovering from trapping helps translate the belief representation into reliable task performance.

Table R3. Full PoS and three ablation variants. Entries report mean ± sample standard deviation (%) over five runs. “−” denotes removal from full PoS.

MethodQwen3.7-PlusKimi-K3GLM-5.3
ALFLOCARCAClinALFLOCARCAClinALFLOCARCAClin
Belief-only71.64 ± 2.9441.90 ± 2.3829.13 ± 3.2940.40 ± 1.3887.31 ± 1.7565.71 ± 2.1744.27 ± 1.1150.03 ± 0.9890.15 ± 1.1161.41 ± 1.7240.78 ± 1.9447.68 ± 1.75
− Trapping Diagnosis73.88 ± 1.4947.70 ± 1.1833.59 ± 0.5342.32 ± 0.5088.36 ± 0.8569.79 ± 1.8246.80 ± 1.6051.52 ± 1.4991.64 ± 0.6264.84 ± 1.2842.52 ± 0.8149.01 ± 0.33
− Consistency Validation73.88 ± 0.5344.00 ± 0.9331.65 ± 0.5343.74 ± 1.2491.64 ± 0.3367.43 ± 1.0248.54 ± 0.9754.24 ± 0.1594.63 ± 0.8262.51 ± 0.3147.18 ± 0.5350.83 ± 1.31
PoS (Ours)88.81 ± 1.4056.27 ± 0.7138.25 ± 1.6245.33 ± 0.5094.03 ± 0.5373.98 ± 1.1851.46 ± 0.6954.93 ± 0.4197.01 ± 0.5371.58 ± 0.6849.32 ± 0.4352.75 ± 0.38

W2: Evaluation over multiple runs.

A2:

  • Results over five runs: We evaluated PoS, all five baselines, and all three ablations five times in total, and report mean ± standard deviation across all four benchmarks and three backbones. PoS outperforms all baselines in each run, demonstrating a consistent advantage across repeated evaluations. Please see our public response, “Response to All Reviewers” for the complete results in Table R1 and the accompanying analysis. We will update the main results table and evaluation protocol in the paper accordingly.

W3(a): Computation of the active-gap projection.

A3(a):

  • Computation of the active-gap projection: Projection uses rule-based matching over the LLM-maintained belief. We first select entities whose names or types share a normalized keyword with the active gap's target or reason. We include their states and any states whose descriptions share such a keyword, together with those states' entities. In a single pass, we then select relations connected to these records or whose descriptions share such a keyword, and include their endpoints. At each detection, we recompute the projections of all world states in the current window using the same current active gap. We will detail these selection rules in Appendix B.2.

W3(b): Matching belief elements across steps.

A3(b):

  • Matching belief elements across steps: Each state is bound to an entity through its ID, and the LLM updates the existing structured belief incrementally under the prescribed schema. The update prompt provides the current records and specifies that unmodified records remain unchanged. For the reviewer’s example, an observation stating “Microwave 1 is shut” can be incorporated by retaining the existing “closed” state record, avoiding unnecessary rephrasing across steps. Jaccard distance is then computed over normalized structured records.

We hope this clarification addresses your concern, and if you find our response helpful, we kindly request the reviewer to consider adjusting the rating.

Thank you for the detailed response. The requested ablation and the repeated evaluations have been incorporated into the revision, and they address my concerns. I maintain my score at 3.

As a minor suggestion, showing statistics how often the baselines fall into belief trapping would make the paper more convincing.

AuthorsOpenReview ↗

Response to Reviewer kTHC

Dear Reviewer kTHC,

Thank you for reviewing our responses and the revised manuscript. We appreciate your confirmation that the additional ablation and repeated evaluations address your concerns.

We also appreciate your suggestion to report trapping incidence for the baselines, which would strengthen the comparison. Because trapping emerges during an agent’s interactions, measuring its incidence across methods requires a consistent way to identify it from their trajectories, including those of baselines without explicit beliefs. Given the lack of a widely accepted criterion for identifying belief trapping across different agent architectures, we plan to explore a common assessment protocol and extend this comparison to the baselines in future work.

Thank you again for your constructive feedback and careful evaluation.

Best regards, The authors of PoS

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

PoS gives an LLM agent an explicit belief state instead of only a raw trajectory. It tracks the world state and unresolved goals. It checks consistency and tries to recover when progress stalls. The paper evaluates on ALFWorld, LOCA-Bench, RCA-100, and ClinDiag with three backbones.

Critical strengths
  1. The gains are broad. PoS improves on all four benchmarks with three backbones. On Qwen, ALFWorld rises from 72.39% to 88.81%.

  2. The evaluation is more complete than a single score table. It includes recovery ablations and a generic-recovery baseline. The paper also reports token costs, which makes the trade-off clear.

Critical weaknesses
  1. The comparison is not compute-matched. On RCA-100, PoS uses 1,800.13K tokens per episode, compared with 355.70K for Raw Trajectory. This is about 5×. We cannot tell how much of the gain comes from the extra calls.

  2. The mechanism is not directly validated. The paper does not check belief correctness or trapping detection accuracy. There are also no paired confidence intervals. So the evidence is promising but not decisive.

Questions for authors
  1. Do the gains remain under a token- or call-matched baseline?

  2. Can you add paired confidence intervals and a direct evaluation of belief correctness and trapping detection?

  3. Can you include a belief-only ablation with both validation and recovery removed?

2 comments
AuthorsOpenReview ↗

Response to Reviewer PLdc (Part 1/2)

Thank you for your careful review and for recognizing the broad improvements and the supporting ablation and cost analyses. Our clarifications are below:


W1 & Q1: Performance at comparable inference cost.

A1:

Reviewer bUbp raised the same concern about whether the gains of PoS come from additional token consumption. Following the suggestion to allocate additional computation to evidence review and self-critique, we conducted the following experiment.

  • Performance comparison at comparable token cost: PoS still retains a clear accuracy advantage when additional computation is allocated to evidence review and self-critique. On RCA-100 with Qwen3.7-Plus, we augmented Raw Trajectory with three stages of review, without constructing a belief state:

    1. Check tool observations;
    2. Examine causal reasoning;
    3. Review the next action or final submission.

This baseline consumes 1,670.80K tokens per episode, equivalent to 92.82% of PoS's total consumption, but only achieves 17.48% joint accuracy, compared with 38.83% for PoS. PoS therefore retains a gain of 21.35 percentage points at comparable token cost.

MethodJoint accuracy (%)Total tokens per episode (K)
Raw Trajectory24.27355.70
Raw Trajectory + Review17.481,670.80
PoS38.831,800.13
  • Why more tokens do not translate into better performance: The review baseline consumes 4.70× the tokens of Raw Trajectory, yet its joint accuracy decreases by 6.79 percentage points. Our trace inspection showed that additional review and self-critique made the agent more conservative. The agent indeed checked observations and candidate reasoning more closely, but the additional reflection led it to explore fewer alternative explanations and even reject promising hypotheses during review. Therefore, greater token consumption does not necessarily translate into better performance. PoS's advantage comes from belief-state maintenance and belief-trapping diagnosis and recovery, which direct additional computation toward productive exploration. Together with the ablations, this comparison supports the architectural advantage of PoS in using additional tokens to improve performance.

Q3: Belief-only ablation without validation or recovery.

A3:

  • Belief-only ablation: We added the requested variant with both consistency validation and trapping diagnosis/recovery removed, retaining belief construction, updates, and gap-guided interaction. We evaluated it over five runs across all four benchmarks and three backbones. Table R3 reports the complete results for PoS and the three ablation variants.

  • Why belief maintenance matters: Removing both consistency validation and trapping diagnosis/recovery further reduces mean performance compared with removing either component alone, highlighting the importance of these two maintenance mechanisms. Full PoS exceeds Belief-only by 4.90–17.16 percentage points across all 12 settings. These comparisons further support the central point made in the Introduction: belief construction is only the starting point. Continually validating belief updates and diagnosing and recovering from trapping helps translate the belief representation into reliable task performance.

Table R3. Full PoS and three ablation variants. Entries report mean ± sample standard deviation (%) over five runs. “−” denotes removal from full PoS.

MethodQwen3.7-PlusKimi-K3GLM-5.3
ALFLOCARCAClinALFLOCARCAClinALFLOCARCAClin
Belief-only71.64 ± 2.9441.90 ± 2.3829.13 ± 3.2940.40 ± 1.3887.31 ± 1.7565.71 ± 2.1744.27 ± 1.1150.03 ± 0.9890.15 ± 1.1161.41 ± 1.7240.78 ± 1.9447.68 ± 1.75
− Trapping Diagnosis73.88 ± 1.4947.70 ± 1.1833.59 ± 0.5342.32 ± 0.5088.36 ± 0.8569.79 ± 1.8246.80 ± 1.6051.52 ± 1.4991.64 ± 0.6264.84 ± 1.2842.52 ± 0.8149.01 ± 0.33
− Consistency Validation73.88 ± 0.5344.00 ± 0.9331.65 ± 0.5343.74 ± 1.2491.64 ± 0.3367.43 ± 1.0248.54 ± 0.9754.24 ± 0.1594.63 ± 0.8262.51 ± 0.3147.18 ± 0.5350.83 ± 1.31
PoS (Ours)88.81 ± 1.4056.27 ± 0.7138.25 ± 1.6245.33 ± 0.5094.03 ± 0.5373.98 ± 1.1851.46 ± 0.6954.93 ± 0.4197.01 ± 0.5371.58 ± 0.6849.32 ± 0.4352.75 ± 0.38
AuthorsOpenReview ↗

Response to Reviewer PLdc (Part 2/2)

W2 & Q2: Belief correctness, trapping detection, and paired confidence intervals.

A2:

Belief trapping lacks an established gold-standard metric for automatic assessment, so distinguishing trapping from productive investigation relies on expert judgment. We therefore asked 3 experienced SREs familiar with RCA to assess belief correctness and trapping detection in 30 PoS traces from RCA-100 with Kimi-K3. We report the mean of the metrics computed separately by each SRE.

  • Belief correctness: The SREs judged 93.25% of factual records and 91.80% of hypotheses reasonable on average. Facts were checked against the observations available at each step, while hypotheses were assessed for evidence-supported plausibility and appropriate uncertainty. These results support the ability of PoS to maintain beliefs that faithfully reflect available observations while retaining plausible hypotheses for further investigation.
Belief recordsReasonable (%)Problematic (%)Undetermined (%)
Facts93.251.944.81
Hypotheses91.804.273.93
  • Trapping detection: The SRE assessment supports the effectiveness of our trapping-detection mechanism, with 76.50% precision and 95.90% recall. The SREs distinguished sustained lack of task-relevant progress from useful evidence collection and elimination of candidate causes. The high recall shows that most trapping events were correctly detected, enabling targeted recovery. Figure 3 further demonstrates the benefit of targeted recovery after trapping is detected.

  • Paired confidence intervals: To obtain more robust experimental conclusions, we repeated the main experiments four additional times, giving five runs in total. The complete mean ± standard deviation results are provided in our public response, “Response to All Reviewers.” For each benchmark–backbone setting, we compared PoS with the baseline having the highest five-run mean and calculated the score difference within each matched run on the fixed benchmark cases. Table R2 reports the mean gains and run-level paired 95% confidence intervals calculated from these five differences. All 12 intervals lie above zero, supporting a consistent performance advantage across repeated executions.

Table R2. Mean gains and run-level paired 95% confidence intervals. Entries give the mean gain [95% CI] in percentage points and the comparator. Intervals use a t distribution with four degrees of freedom. LHH = LongHorizon-Harness, Hi = HiAgent, Raw = Raw Trajectory.

BenchmarkQwen3.7-PlusKimi-K3GLM-5.3
ALFWorld18.51 [14.50, 22.51] (LHH)2.09 [0.88, 3.30] (LHH)1.64 [0.63, 2.66] (LHH)
LOCA-Bench3.89 [1.58, 6.19] (LHH)2.59 [0.46, 4.72] (ACON)5.26 [4.26, 6.25] (ACON)
RCA-10010.10 [7.91, 12.29] (Hi)9.13 [7.51, 10.74] (Hi)8.16 [6.33, 9.98] (Hi)
ClinDiag4.37 [1.27, 7.47] (PACE)4.27 [2.45, 6.09] (LHH)6.13 [3.12, 9.13] (Raw)

We hope this clarification addresses your concern, and if you find our response helpful, we kindly request the reviewer to consider adjusting the rating.

Reviewer_bUbpOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

PoS maintains an explicit, task-conditioned representation of entities, states, relations, and unresolved epistemic or achievement gaps. A Belief Sentinel checks updates against available evidence, while a health monitor detects stalled progress and constructs recovery prompts based on both the trapping pattern and the blocked gap type. The paper evaluates execution and diagnosis across four benchmarks and three backbones. PoS leads every aggregate benchmark/backbone comparison, and ablations indicate that both validation and recovery contribute to the gains.

Critical strengths
  1. The distinction between an unresolved information need and an unachieved world state is useful. It gives the recovery mechanism a clearer target than simply asking the agent to reconsider its previous actions.
  2. The improvement is unusually consistent across the reported settings. For example, Qwen3.7-Plus reaches 88.81% on ALFWorld versus 72.39% for the strongest baseline, and 38.83% joint accuracy on RCA-100 versus 28.16% (Table 1). Gains also remain with the stronger backbones.
  3. The ablations and generic-recovery comparison go beyond demonstrating a complete system. Removing validation is particularly harmful on execution tasks, while removing recovery hurts diagnosis as well. The disclosure that total token use increases substantially, despite lower Task Agent consumption, is valuable.
  4. The implementation discussion is reasonably candid: it identifies the omitted ACON training stages, the PACE encoder replacement, and the lack of fixed API snapshots. This helps delimit what was actually compared.
Critical weaknesses
  1. The main unresolved issue is inference-budget matching. On RCA-100, PoS uses 1,800.13K tokens per episode against 355.70K for Raw Trajectory (Table 2). The component ablations also change compute. A comparable investment in repeated evidence review, self-critique, or a generic verifier could explain part of the gain. Figure 3 helps isolate recovery content, but does not establish that the full architecture is preferable at equal total cost.
  2. The health monitor is evaluated mostly through its own detections and downstream success. There is no independently annotated set of trapped and productive transitions from which to estimate false alarms or missed detections. In diagnosis, any sufficiently large absolute confidence movement counts as progress; oscillation or unsupported changes can satisfy this rule. Recurrence is intended to address this, but its reliability depends on semantic alignment and confidence comparisons that deserve direct validation.
  3. The formal POMDP motivation is stronger than the implemented representation warrants. PoS stores selected natural-language claims and independent confidence values, rather than a calibrated posterior over latent states. The paper should distinguish this operational state estimate from the sufficiency properties of a Bayesian belief state, and explain how uncertainty survives an incorrect Sentinel judgment.
  4. Some improvements are small in case counts, particularly the 1.49-point ALFWorld gain with GLM-5.3. Deterministic decoding does not quantify dataset uncertainty or eliminate service variation. Paired intervals would help, and LOCA-Bench uncertainty should account for the repeated instantiations of only 15 underlying tasks.
Questions for authors
  1. At the same total-token budget, how does PoS compare with a verifier or self-critique baseline, and can the cost breakdown be extended beyond RCA-100?
  2. Can you annotate a sample of transitions independently and report trapping-detection precision/recall, Sentinel correction accuracy, and cases where recovery interrupts useful exploration?
  3. How are semantically equivalent entities, states, and gaps aligned across steps, and how sensitive are the gains to this alignment and to the health thresholds?
7 comments
AuthorsOpenReview ↗

Response to Reviewer bUbp (Part 1/3)

We thank the reviewer for the detailed review and for recognizing the insights into the problem and the experimental results. Below, we respond to the concerns in a structured manner:


W1 & Q1: Inference-budget matching and computational cost.

A1:

  • Performance comparison at comparable token cost: PoS still retains a clear accuracy advantage when additional computation is allocated to evidence review and self-critique. Following your suggestion, we augmented Raw Trajectory with three stages of review on RCA-100 using Qwen3.7-Plus:

    1. Check tool observations;
    2. Examine causal reasoning;
    3. Review the next action or final submission.

This baseline consumes 1,670.80K tokens per episode, (92.82% of PoS's total consumption), but only achieves 17.48% joint accuracy, compared with 38.83% for PoS.

MethodJoint accuracy (%)Total tokens per episode (K)
Raw Trajectory24.27355.70
Raw Trajectory + Review17.481,670.80
PoS38.831,800.13
  • Why more tokens do not translate into better performance: The review baseline consumes 4.70× the tokens of Raw Trajectory, yet its joint accuracy decreases by 6.79 percentage points. Our trace inspection showed that additional review and self-critique made the agent more conservative. The agent indeed checked observations and candidate reasoning more closely, but the additional reflection led it to explore fewer alternative explanations and even reject promising hypotheses during review. Therefore, greater token consumption does not necessarily translate into better performance. PoS's advantage comes from belief-state maintenance and belief-trapping diagnosis and recovery, which direct additional computation toward productive exploration. Together with the ablations, this comparison supports the architectural advantage of PoS in using additional tokens to improve performance.

  • Cost breakdown beyond RCA-100: We chose RCA-100 for detailed cost analysis because it has the largest relative token overhead among the four benchmarks under Qwen3.7-Plus, with PoS using 5.06× the total tokens of Raw Trajectory. On ALFWorld, LOCA-Bench, and ClinDiag, the Raw → PoS costs are 49.65K → 88.29K (1.78×), 1,539.75K → 2,841.27K (1.85×), and 31.48K → 108.22K (3.44×) tokens per episode, respectively.


W2 & Q2: Independent validation of trapping detection and Sentinel corrections.

A2:

Belief trapping lacks an established gold-standard metric for automatic assessment, so distinguishing trapping from productive investigation relies on expert judgment. We therefore asked 3 experienced SREs familiar with RCA to review 30 PoS traces from RCA-100 with Kimi-K3.

MetricResult (%)
Trapping-detection precision76.50
Trapping-detection recall95.90
Sentinel correction accuracy among adopted revisions97.80
  • Detection and correction quality: The SREs assessed task-relevant progress and whether adopted revisions correctly repaired valid issues without introducing related errors. Detection precision and recall are averaged across the three SREs. The high recall shows that most trapping events were identified for recovery, while most alerts were confirmed. The high correction accuracy of sentinel provides strong support for the correctness of belief updates.

  • Unsupported confidence oscillations and recurrence: Confidence updates must be supported by observations, and unsupported oscillations were uncommon in the reviewed traces. Substantial evidence-supported changes can therefore indicate diagnostic progress. Recurrence additionally detects returns to earlier confidence configurations over matched hypotheses (Appendix B.3), capturing cycles that single-step changes can miss. The human assessment directly validates the detection mechanism, which includes recurrence checking, with 95.90% recall.

  • Cases where recovery interrupts useful exploration: In a Qwen3.7-Plus trace where the root cause was Redis unavailability, the agent had already collected Redis connection-timeout logs from cart. Recovery then directed it to check email and currency. The agent followed this instruction by querying both services, temporarily shifting its investigation away from Redis. Such cases were uncommon. Recovery generally improved investigation, often guiding the agent toward a productive direction within one or two subsequent steps.

AuthorsOpenReview ↗

Response to Reviewer bUbp (Part 2/3)

W3: POMDP motivation, belief representation, and Sentinel errors.

A3:

  • Relation to the POMDP belief state: We agree that PoS's structured belief differs from a Bayesian posterior with its sufficiency properties. In our scenarios, such as medical and failure diagnosis, large latent state spaces and incomplete knowledge of environment dynamics make accurate posterior estimation difficult. As described in Sec. 3.1, following the POMDP formulation, PoS maintains a structured, task-conditioned belief to estimate the world state from available observations. Its confidence scores describe individual inferences rather than a joint posterior. We will make this distinction more explicit in Sec. 3.1.

  • Preserving uncertainty during Sentinel validation: Two safeguards address this concern: validation focuses on inconsistencies, and the Task Agent reviews Sentinel's feedback. Sentinel is designed to flag clear internal inconsistencies or explicit contradictions with observations, so uncertain inferences and unresolved gaps can remain in the belief. Each issue must include supporting evidence. As described in Sec. 3.2, the Task Agent reassesses the feedback before revising the belief, allowing incorrect or unsupported issues to be rejected rather than automatically accepted.


W4: Statistical uncertainty and small performance differences.

A4:

  • Results over five runs: We evaluated every method in the original main comparison over five runs and report mean ± standard deviation across all four benchmarks and three backbones. PoS outperforms all baselines in each run, demonstrating a consistent advantage across repeated evaluations. Please see our public response, “Response to All Reviewers ” for the full results and analysis.

  • Limited headroom on ALFWorld with GLM-5.3: The strongest baseline already achieves 95.37% success in this setting, leaving limited room for further improvement. PoS raises this to 97.01%. Across five matched runs, the mean gain is 1.64 percentage points, with a run-level paired 95% confidence interval of [0.63, 2.66]. Larger gains are evident with other backbones and on other benchmarks. For example, PoS improves over the strongest baseline by 18.51 percentage points on ALFWorld with Qwen3.7-Plus and 8.16 points on RCA-100 with GLM-5.3.

  • Coverage across LOCA task types: The gains extend across different task types. As detailed in Appendix C.1.2, the 15 underlying tasks cover Cross-source Workflows, Structured Analytics, and Environment Operations, with five tasks in each category. The category-level results in Appendix E.1, Table 10 show that PoS exceeds the strongest baseline in eight of the nine category–backbone comparisons. The gains vary across categories and backbones, but are not confined to a single task type. We recognize that these are 15 underlying tasks with repeated instantiations, and report the five-run standard deviations as execution variability on this benchmark.

AuthorsOpenReview ↗

Response to Reviewer bUbp (Part 3/3)

Q3: Cross-step alignment and sensitivity to health thresholds.

A5:

  • How belief elements are aligned: During belief construction and updates, the schema and examples guide the agent to reuse existing IDs and consistent descriptions for semantically equivalent elements, allowing direct matching by ID across steps. For elements that remain unmatched, including those expressed with different wording, the LLM checks semantic equivalence to establish the correspondence before persistence and recurrence are computed. These constraints make alignment a limited correspondence check over existing records. We therefore use a fixed alignment procedure and focus the sensitivity analysis on the detection thresholds.

  • Sensitivity to detection thresholds: PoS retains its performance advantage across all tested threshold settings. We chose ALFWorld because its distribution of detected trapping patterns is relatively balanced across Static, Cycle, and Drift (Fig. 3). Using Qwen3.7-Plus, we evaluated five values per threshold, changing one threshold at a time while keeping other settings fixed. Success rates ranged from 85.82% to 90.30% within ±0.05 of the defaults, compared with the default result of 88.81%. Across the full tested ranges, PoS achieved 81.34%–90.30%, consistently above the strongest baseline, LongHorizon-Harness (72.39%). We will include this analysis in the main text.

Threshold sensitivity on ALFWorld with Qwen3.7-Plus.

MethodHealth θ_HRecurrence distance ε_WCycle θ_RSuccess (%)
LongHorizon-Harness———72.39
PoS (default)0.250.150.7588.81
PoS0.150.150.7586.57
PoS0.200.150.7588.81
PoS0.300.150.7589.55
PoS0.350.150.7584.33
PoS0.250.050.7581.34
PoS0.250.100.7586.57
PoS0.250.200.7590.30
PoS0.250.250.7587.31
PoS0.250.150.6583.58
PoS0.250.150.7085.82
PoS0.250.150.8087.31
PoS0.250.150.8582.09

We hope this clarification addresses your concern, and if you find our response helpful, we kindly request the reviewer to consider adjusting the rating.

Comments on the paper

2 comments
AuthorsOpenReview ↗

Response to All Reviewers

We sincerely appreciate the time and effort all reviewers devoted to these thoughtful and comprehensive reviews. We are glad to see recognition of both the practical problem we address and the value of PoS. Your suggestions for additional experiments and clearer explanations help us strengthen the empirical evidence and make the paper more informative and easier to follow.

We address each reviewer’s comments in separate responses. This public response summarizes the results and analysis of our additional Belief-only ablation and five-run evaluation. Table R1 brings together the results for PoS, all five baselines, and three ablations across all four benchmarks and three backbones.

  • Consistent advantages across repeated runs: PoS outperforms all five baselines in each of the five runs across all 12 benchmark–backbone settings, with mean gains of 1.64–18.51 percentage points over the strongest baseline in each setting. Its standard deviations range from 0.38 to 1.62 percentage points, showing limited variation across runs while preserving its performance advantage.

  • Why belief maintenance matters: The new Belief-only variant retains belief construction, updates, and gap-guided interaction while removing both consistency validation and trapping diagnosis/recovery. Its mean performance is lower than both single-component ablations in all 12 settings, and full PoS exceeds it by 4.90–17.16 percentage points. These results further support the central point made in the Introduction: belief construction is only the starting point. Continually validating belief updates and diagnosing and recovering from trapping helps translate the belief representation into reliable task performance.

We will incorporate the five-run results, the belief-only ablation, and these analyses into the paper.

Table R1. Main results over five runs. Entries report mean ± sample standard deviation (%) over five runs. The highest mean in each backbone–benchmark setting is bold.

MethodQwen3.7-PlusKimi-K3GLM-5.3
ALFLOCARCAClinALFLOCARCAClinALFLOCARCAClin
Raw Trajectory62.09 ± 2.5543.28 ± 1.2224.85 ± 3.1939.47 ± 1.2782.24 ± 1.7869.83 ± 0.9437.48 ± 2.4449.34 ± 0.3394.03 ± 1.1863.70 ± 1.2231.26 ± 0.8146.62 ± 2.40
ACON66.42 ± 1.4049.41 ± 2.0827.77 ± 1.4740.60 ± 0.7080.45 ± 0.9771.39 ± 1.3140.39 ± 2.4439.83 ± 1.1694.93 ± 1.1166.32 ± 1.1134.17 ± 1.0645.93 ± 1.04
PACE67.76 ± 0.6217.87 ± 0.7427.38 ± 2.9440.96 ± 2.5384.93 ± 1.9341.56 ± 1.6535.73 ± 1.0649.90 ± 0.3494.48 ± 1.1338.29 ± 0.9437.86 ± 0.6944.40 ± 1.25
HiAgent65.82 ± 1.4424.46 ± 2.2428.16 ± 2.6640.33 ± 2.6489.55 ± 1.9747.58 ± 1.5542.33 ± 0.8747.28 ± 2.7094.33 ± 1.0045.26 ± 1.4741.17 ± 1.1144.57 ± 0.66
LongHorizon-Harness70.30 ± 2.7152.38 ± 1.1827.38 ± 1.6039.37 ± 2.0791.94 ± 0.6268.08 ± 1.4738.83 ± 2.3850.66 ± 1.4695.37 ± 0.3363.70 ± 2.0430.87 ± 0.4345.86 ± 1.12
PoS (Ours)88.81 ± 1.4056.27 ± 0.7138.25 ± 1.6245.33 ± 0.5094.03 ± 0.5373.98 ± 1.1851.46 ± 0.6954.93 ± 0.4197.01 ± 0.5371.58 ± 0.6849.32 ± 0.4352.75 ± 0.38
− Consistency Validation73.88 ± 0.5344.00 ± 0.9331.65 ± 0.5343.74 ± 1.2491.64 ± 0.3367.43 ± 1.0248.54 ± 0.9754.24 ± 0.1594.63 ± 0.8262.51 ± 0.3147.18 ± 0.5350.83 ± 1.31
− Trapping Diagnosis73.88 ± 1.4947.70 ± 1.1833.59 ± 0.5342.32 ± 0.5088.36 ± 0.8569.79 ± 1.8246.80 ± 1.6051.52 ± 1.4991.64 ± 0.6264.84 ± 1.2842.52 ± 0.8149.01 ± 0.33
Belief-only71.64 ± 2.9441.90 ± 2.3829.13 ± 3.2940.40 ± 1.3887.31 ± 1.7565.71 ± 2.1744.27 ± 1.1150.03 ± 0.9890.15 ± 1.1161.41 ± 1.7240.78 ± 1.9447.68 ± 1.75
AuthorsOpenReview ↗

A Kind Reminder for Reading the Response

Dear Reviewers,

We have revised the paper and added further results to address your comments. As the rebuttal period draws to a close, we would greatly appreciate it if you could take a look at our updated response. We would also welcome any further feedback or remaining concerns.

Thank you for your time and consideration.

Best regards, The authors of PoS

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.