What Makes a Social Agent's Interactions Effective? Learning from Verifiable Outcomes in Paired Worlds
Current social agent benchmarks reward fluent conversation but ignore whether agents actually reach valid plans that respect hidden constraints. This paper introduces HICO-Bench, a benchmark where two agents with private information must coordinate verifiable outcomes, and PaCPO, a reinforcement learning method that redistributes terminal rewards across turns by checking tentative plans against paired worlds. The work matters because it reveals that high LLM-judged conversation ratings frequently mask infeasible or unsupported agreements, and provides a concrete credit-assignment mechanism to train agents on verified social outcomes rather than just dialogue style.
The paper makes a compelling case that LLM-judged conversation ratings are insufficient for evaluating social agents, and it backs this claim with a carefully designed benchmark and a theoretically clean credit-assignment algorithm. HICO-Bench's paired-worlds structure is elegant, and PaCPO's potential-based shaping correctly preserves total episode return while injecting verifiable, turn-level rewards. However, the absolute performance gains are modest and the benchmark's scope is deliberately narrow, leaving open how well the approach generalizes to less structured interaction.
The paired-worlds design is the paper's strongest conceptual contribution: by fixing the public context and varying exactly one private condition, the authors create a rigorous counterfactual where any agent that responds identically in both worlds necessarily fails at least one scenario. The outcome evaluation is also well-decomposed, separating Feasibility (a rule-based check that independent records match and satisfy private constraints) from Integrity (an LLM-judge check that the conversation actually supports the recorded plan). Theoretically, PaCPO is sound because its potential-based reward shaping redistributes the terminal reward without altering the total return of each conversation.
Despite the clever design, absolute success rates remain alarmingly low across all methods and models; for example, resource allocation stays at 17.5% Verified Success even for PaCPO, and the two scheduling families are essentially unsolved. The reliance on an LLM judge for Integrity is a notable vulnerability that the authors acknowledge, and the minimal human validation limits confidence in judge alignment. Additionally, the benchmark is restricted to six highly structured coordination families with pre-encoded rules, so it remains unclear whether the lessons transfer to richer, less formal social settings where outcomes cannot be verified by a program.
The central empirical claim that conversation ratings poorly predict verifiable outcomes is well supported by the multi-model benchmark, where 35.99% of high-Goal conversations fail Verified Success across thirteen LLMs. The comparison between RL methods is mostly fair because all systems share the same terminal reward and total training dialogue budget, but a subtle discrepancy remains: group-based baselines such as GRPO and GiGPO cover only 48 training scenarios due to their $G=4$ grouping, whereas PPO and PaCPO cover all 96. The ablation results directly support PaCPO's key design choices, showing that replacing the cross-world plan with a same-world candidate drops Verified Success by about 2 percentage points, although these margins are small.
The authors disclose extensive implementation details, including algorithm pseudocode, full hyperparameters ($\alpha=0.25$, $\beta=0.10$, actor LR $2\times 10^{-6}$, GAE with $\gamma=1$, $\lambda=0.95$), and exact loss formulas, which should allow reproduction once artifacts are released. However, the paper currently describes only an intended release of scenarios, prompts, and checkpoints, meaning independent replication is blocked until materials are actually published. Reproduction would also require substantial compute resources and access to multiple proprietary models, since PaCPO generates over 57,000 additional tentative-plan tokens per training run and relies on external API models for evaluation and partners.
Effective social interaction requires more than fluent responses: agents must reach plans that fit the participants' needs and circumstances. Existing evaluations of social agents mainly rely on LLM judges that rate the conversation, without checking the resulting plan. We introduce HICO-Bench, a benchmark of 180 everyday coordination scenarios, such as resource allocation, scheduling, and authorization, in which two agents with private information converse and then independently record the plan they agreed on. A program checks Feasibility (the two records match and satisfy both participants' private conditions), and an LLM judge checks Integrity (the conversation supports the recorded plan); passing both is a Verified Success. Each scenario has two versions that share the same public context but differ in one private condition, so the correct plan differs between them. Across thirteen LLMs, 36% of conversations rated highly for goal completion fail Verified Success. To learn from outcomes that arrive only at the end of a conversation, we propose Paired-Credit Policy Optimization (PaCPO). After each turn, PaCPO asks the agent for a tentative plan, checks it in both versions of the scenario, and rewards the turns after which the tentative plans fit their respective versions. PaCPO raises Qwen3-8B's Verified Success from 20.4% to 28.3%.
Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.
No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.