Reward-Driven LLM Agent Workflows: Synthesizing POMDP Routing and Self-Correction for Autonomous Decision-Making¶

🕒 Published (v1): 2026-07-19 02:51 UTC · Source: Arxiv · link

Why this paper was selected

POMDP routing + self-correction synthesis; principled framework for autonomous LLM agent decision-making

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

TL;DR¶

RLAW (Reward-Driven LLM Agent Workflow) formalizes LLM agent orchestration as a POMDP and augments it with a learned, RL-based critic that evaluates candidate reasoning trajectories before execution. A GNN-based graph memory approximates the belief state. On ALFWorld and WebShop, RLAW achieves a 24.5% absolute improvement in task success rate over ReAct.

Problem¶

Standard LLM agent frameworks (ReAct, Reflexion, ToT) suffer from cascading hallucination errors over long horizons, lack formal mathematical reward objectives, and rely on heuristic self-evaluation (e.g., prompting the LLM to score thoughts 1–5). This produces unreliable self-correction, especially in smaller quantized models, and leaves no principled mechanism for suppressing suboptimal or hallucinatory trajectories before they are executed.

Method¶

The core architecture is a propose-critique-execute loop grounded in a 7-tuple POMDP \(\langle S, A, T, R, \Omega, O, \gamma \rangle\). Because the exact belief state \(b_t\) is analytically intractable in open-ended language environments, it is approximated by combining the raw observation history \(o_{\leq t}\) with a structured Graph Memory \(M_t\), updated at each step via:

\[M_t = f_{\text{update}}(M_{t-1}, o_t, a_{t-1})\]

where node attributes and edge weights encode discovered environment entities and relations (GCN/GAT backbone).

The Actor (the main LLM) proposes candidate action sequences. A separate Critic module—trained with PPO-style value function approximation using the clipped surrogate objective \(L^{\text{CLIP}}(\theta)\)—scores these trajectories by estimating the discounted expected return \(\mathbb{E}_\pi[\sum_t \gamma^t r_{t+1}]\) and discards suboptimal paths before any external environment call. Multimodal inputs (text + vision via CLIP/ViT-LLaMA alignment) feed into the unified state representation. The POMDP routing mechanism determines which belief pathway to follow based on the critic's value estimates rather than greedy argmax generation.

Key Contributions¶

POMDP-grounded routing: Elevates the LLM from a next-token predictor to a formal policy function \(\pi^*\) within a POMDP, with explicit state/action/transition definitions.
RL-based critique module: Replaces heuristic self-reflection with a trained value function approximator (PPO/actor-critic) that prunes hallucinated trajectories pre-execution.
Graph Memory belief approximation: GNN-based structured memory serves as a compressed, non-Euclidean surrogate for the intractable continuous belief state \(b_t\).
Multimodal fusion: Integrates visual frames and language goals into a unified observation space via joint latent embedding projection.
Inference complexity bound: \(O(H \times N_{\text{regen}})\)—bounded linear steps, versus the exponential \(O(B^d)\) of tree/graph search methods.

Results¶

+24.5% absolute task success rate and improved trajectory efficiency over the ReAct baseline on ALFWorld (embodied simulation) and WebShop (web navigation).
Ablation studies confirm the critique module independently and significantly reduces hallucination rates (magnitude not stated in available text).
Smaller, localized models under RLAW outperform larger unconstrained baselines, demonstrating parameter efficiency gains.
Compared baselines: ReAct, Reflexion, Tree/Graph of Thoughts, AutoGPT (see Table 2 in paper).

Limitations¶

Paper text is truncated; the full results section, ablation numbers, and stated limitations (Section 5) are not available for review.
The critic/value network requires separate RL training, introducing offline data collection and training overhead not required by prompting-only baselines.
Graph Memory update function \(f_{\text{update}}\) design details are underspecified in available text; scalability to very large state spaces is unclear.
Evaluation is limited to two benchmarks (ALFWorld, WebShop) plus an undescribed "custom multimodal simulation platform"; generalization to open-domain settings is unverified.
Belief state approximation via graph memory is a heuristic; no formal error bounds on the approximation are provided.
The POMDP formulation assumes a sparse binary reward (\(+1.0\) on completion, \(0\) otherwise), which may not transfer cleanly to tasks with dense or shaped reward signals.

Relevance to Harnesses / Meta-Harnesses¶

RLAW is directly a meta-harness: it wraps an underlying LLM in a structured orchestration layer that enforces routing logic (POMDP belief pathways), pre-execution validation (RL critic), and persistent memory (GNN graph), replacing ad-hoc prompt chaining with a mathematically governed control loop. The propose-critique-execute paradigm is a concrete instantiation of the broader harness design pattern where a controller adjudicates between candidate agent outputs before committing to environment interaction. The bounded \(O(H \times N_{\text{regen}})\) complexity analysis is useful for practitioners sizing harness overhead, and the comparison against ReAct/Reflexion/ToT situates this work squarely in the harness design space. The RL-trained critic as an internal quality gate is a noteworthy alternative to LLM-as-judge scoring used in many existing harnesses.