acceptodds
Under review as a conference paper at ICLR 2027

Beyond the Transcript: Asymmetric Cognitive Graphs for LLM Agents in Social Deduction Games

Abstract

Social deduction requires more than identifying hidden roles: a useful belief must guide actions that preserve credibility and advance a team's objective. We introduce Asymmetric Cognitive Graphs (ACG), an external belief-to-action framework for large language model agents inspired by these demands of human strategic play. ACG separates observed events, private role beliefs, and perceived public attitudes. Probabilistic evidence updates maintain graph memory, while role-conditioned planning balances progress, information, exposure, and coordination through explicit, game-specific action scores. Deployment on either or both sides tests how this integrated intervention redistributes team advantage. We evaluate four settings: a GRAIL-aligned disclosure comparison, role-rich six-player Avalon, homogeneous nine-player Werewolf, and a nine-model Werewolf roundtable. Across three Avalon models, both-side ACG increases Good-side win rates, with two contrasts surviving multiplicity correction; DeepSeek Flash rises from 6.7% to 43.3% over 30 paired seeds (exact McNemar ). Against a GRAIL port, GPT-4.1 ACG achieves 65% versus 30% under member-attributed disclosure, but 20% versus 40% under binary outcomes; these comparisons remain descriptive. Across three homogeneous Werewolf models, Good-only deployment lowers recipient win-rate estimates, whereas Evil-only raises them. The heterogeneous roundtable yields repeatable behavioral profiles without significant paired win-rate differences. These results establish an inspectable architecture for translating social evidence into role-dependent action and reveal how the benefits of structured guidance vary across factions and interaction settings.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Large language model agents, social deduction games, asymmetric cognitive graphs, theory of mind, Bayesian belief updating, multi-agent coordination, strategic planning, Avalon and Werewolf

Reviews

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

This paper aims to answer whether equipping LLM players with a structured strategic assistant can improve their team's performance in games. To answer this question, the authors propose an asymmetric cognitive graph (ACG) framework. The proposed framework can track observed game events, players' private beliefs about other players' hidden roles, and public suspicion and trust. Then, a weight scoring rule that utilizes the recording information can evaluate candidate strategies and provide action recommendations to the LLMs. Experimental studies in Avalon and Werewolf show the impact of the proposed methods on game-playing outcomes.

Critical strengths

This paper studies an important and interesting question: whether providing structured strategic assistance to LLM players can improve their team's performance in game playing. By designing a framework that integrates observed outcomes, private beliefs, and public perceptions and conducting experiments across different games, this paper examines the effects of this assistance and the conditions under which it is beneficial.

Critical weaknesses
  1. Lacking an ablation test makes it difficult to tell which components (observed outcomes, private beliefs, and public perceptions) are necessary or whether a simpler assistant would work just as well.

  2. The experimental results only show the changes in win rates without sufficiently explaining why the proposed structure only helps in some settings and hurts in others. I would expect a clearer explanation to answer the question of "whether providing structured strategic assistance to LLM players can improve their team's performance in game playing".

  3. I would expect more comparisons regarding the existing methods, such as MultiMind. Without sufficient comparison with the existing methods, it is hard for me to evaluate the benefits of ACG or the technical contributions of this work.

Questions for authors
  1. Can you provide ablation results to show that the proposed structure provides benefits over a simple assistant? Specifically, which components are responsible for the performance improvements in Avalon and the degradation in Werewolf?

  2. Can you provide a detailed discussion regarding when the proposed structure improves team performance instead of just listing the change in win rates? Are the negative results caused by incorrect beliefs, ineffective rules, or action overrides?

  3. I would expect more clarification regarding the technical difference between the proposed method and methods such as MultiMind. More discussions and comparisons can better support innovation in ACG design techniques.

3 comments

Thank you so much for your careful review and helpful suggestions. We added component controls, phase-level outcomes, and a direct technical comparison with MultiMind.

1. What improves in Avalon, and why can final wins differ?

The separate Avalon cohort has 50 selected valid completions per arm and distinguishes three outcome stages:

ConditionThree quest successesAssassination lossesGood wins
Baseline43/509/5034/50
Memory only48/5014/5034/50
Planner advice only44/5010/5034/50
Controller only40/505/5035/50
Memory + advice48/5012/5036/50
Full49/5016/5033/50
FlatFull47/5013/5034/50

Exploratory Full-minus-baseline differences are +15.1pp for quest-success fraction, +27.2pp for rejecting Evil-containing teams, and -16.7pp for all-Good approval. Figure 6 reports all seven endpoints and uncertainty. These counts locate where progress is lost; they do not prove that ACG exposes Merlin. Full has no established terminal advantage.

A same-state test improves factual-citation matching by 4.61pp (111 pairs, 29 seeds; Holm-3 p=0.00018), but not Brier or vote safety, with longer prompts. Factual binding, progress, and winning are distinct outcomes.

2. Do beliefs, rules, or overrides explain the Werewolf decline?

We tested 20 midgame checkpoints, one per seed, from previously inspected, valid newer Good-only games. Five prompt conditions vary belief updates, public perception, and advice; no-controller reuses Full's response. All 100 generations are protocol-valid. Other votes remain fixed; only the current ballot is resolved. This is not independent confirmation or new full games.

ConditionExecuted wolf-target votesCurrent-ballot wolf exiles
Full9/208/20
No soft belief update8/207/20
No derived public view9/208/20
No delivered advice9/208/20
No update + no advice8/207/20
No controller, same Full response8/207/20

One checkpoint traces a positive mechanism: the LLM proposes a Good target; belief updates and control redirect the vote to a wolf, turning a 3-3 tie into a 4-2 wolf exile. Removing updating or control removes this effect; hiding advice or removing public perception does not.

This is a local execution benefit. All four planned comparisons have raw and Holm-adjusted p=1.0; raw votes match across prompts in 19/20 states. Belief-update Brier differences are inconclusive. A census of 25 valid source games finds 19 vote overrides: nine change Good targets to wolves, eight do the reverse, and two preserve alignment.

Appendix H.4 reports all diagnostics, including the incomplete 160-terminal campaign. They test local pathways but do not identify a single cause of historical terminal decline.

3. What is technically different from MultiMind?

MultiMind uses multimodal cues, learned theory-of-mind, and 500-iteration MCTS in five-player One Night Ultimate Werewolf with role swaps. ACG uses explicit evidence updates, separate private beliefs and public support, local role scores, and optional execution control in fixed-role games, without base-LLM fine-tuning.

Related Work and Appendix A.3 compare these designs. Our five-player exploration changed ACG's role-transition model and voting objective, preventing a fair ranking. Appendix H documents historical E2 input risks and the separate Avalon cohort's recovery limits; those results are not pooled.

Thank you for your response. However, I think my questions have not yet been fully addressed. Regarding my first comment, I appreciate the authors' addition of comparisons. However, such comparisons do not directly answer my questions, whether a full assistant is better than a simple assistant. Moreover, I would appreciate it if the authors could clarify the evaluation metrics, as I have no direct research experience on this topic. The current results are really hard to interpret. As per my second comment, I expect a detailed explanation rather than a table listing why those changes occur. As for my last question, I want to help understand why this paper's method/structure is beneficial. Listing the differences does not help me to appreciate the technical innovation and contribution. Given my broad familiarity with this field and no direct research experience on this topic, I retain my current score.

Thank you for reading our response and clarifying your concerns. We respect your assessment and recognize that our reply should have explained the findings more clearly, rather than mainly adding comparisons.

Briefly, ACG aims to distinguish what a player privately believes from what others publicly support, and connect both to action. Our positive evidence is specific: graph-formatted inputs improved factual-reference accuracy in our test, while better quest progress did not translate into more final wins. The current controls do not establish that the full assistant outperforms a simpler one.

Your feedback highlights the need for concrete examples and accessible metrics. Our broader goal is to understand when structured assistance can turn individual evidence into successful team decisions. Your comments will help us communicate that goal and the supporting evidence more clearly.

Thank you again for your time and constructive discussion, also your academic insights and the time and effort you have devoted to our work.

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

The paper introduces Asymmetric Cognitive Graphs (ACG), a runtime framework for LLM agents in social deduction games. ACG maintains separate representations of observed events, private role beliefs, and public standing, and ranks candidate actions using fixed, role-conditioned utility functions. When enabled, executable controllers can also override actions proposed by the language model. The primary experiments evaluate four deployment configurations: neither faction, Good only, Evil only, and both factions. In role-rich Avalon, deployment to both factions increases Good-side win rates, with statistically significant gains for two of three models after multiplicity correction. Werewolf results vary across recipient factions, while the heterogeneous nine-model experiment yields no statistically significant paired win-rate differences.

Critical strengths
  • The separation of private role beliefs from public standing is a well-motivated design choice. An agent may have strong evidence against another player without sufficient credibility or public support to act on that evidence effectively. ACG explicitly represents this distinction, while the role-conditioned utility scores make its influence on action selection inspectable. The equations and worked examples further clarify the induced decision policy.

  • The faction-specific deployment experiments provide a more informative evaluation than comparing the complete system against a language-only baseline alone. They show that the recipient faction does not consistently benefit and that deployment to both factions can alter the balance of advantage differently across games. The authors report paired outcomes, uncertainty intervals, and multiplicity-adjusted tests, while appropriately distinguishing statistically significant findings from descriptive trends. The negative results in Werewolf are also informative.

Critical weaknesses
  • The experiments do not isolate the contributions of the individual architectural components. ACG jointly introduces graph-based memory, role-conditioned planning, and executable controllers. Because the controllers can override team proposals, votes, or targets, the observed win-rate changes may be driven primarily by the hand-designed control policy. The baseline and ACG conditions also differ in the contextual information supplied to the model.

  • The paper appropriately characterizes ACG as an integrated intervention, but the evaluation leaves its central architectural contribution insufficiently established. Without component ablations or an information-matched alternative representation, it remains unclear whether the three-view graph is necessary, whether the planner benefits specifically from this representation, or whether simpler memory structures and control heuristics could achieve comparable results.

Questions for authors

In one of the primary Avalon settings, how do graph-memory-only, planner-only, and controller-only variants perform? A controller-only ablation would be particularly informative because the evaluated system can override the model’s proposed actions. Does the full system retain an advantage over a simpler representation with the same information content and strategic guidance?

3 comments

Thank you so much for your careful review and helpful suggestions. We added the requested memory, planner-advice, controller, and same-information controls. The revision distinguishes a measurable representation benefit from overall policy performance.

What benefit comes from the representation?

In a same-state test, Graph and Flat receive the same primitive facts and instructions, with no supplied posteriors, plans, or controllers. Factual-citation matching improves from 91.33% to 95.94% on 111 complete pairs from 29 source seeds (+4.61pp; seed-bootstrap 95% CI [2.83, 6.42]pp; Holm-3 p=0.00018). The metric checks cited fact IDs against their subject-relation-object tuples. This isolates a factual-binding benefit from executable rules, though not from prompt length: Graph uses 8.79% more input and 31.30% more output tokens. Brier and vote safety do not improve. Table 3 and Appendix H.1 report all endpoints and protocol failures.

What happens when memory, advice, and control are separated?

The separate Avalon cohort has 50 selected valid completions per condition:

ConditionGood wins
Baseline34/50
Memory only34/50
Planner advice only34/50
Controller only35/50
Memory + advice, no controller36/50
Full33/50
FlatFull34/50

Controller-only computes a plan internally but gives the LLM neither memory nor advice. FlatFull retains Full's derived fields, advice, and controller, changing their serialization. These are delivery and execution controls, not removal of all graph computation. Figure 1 and Table 4 now make that distinction explicit.

Does Full retain an advantage over a simpler assistant?

We have not established this. Full's contrasts with controller-only, memory + advice, and FlatFull are not significant (Holm-3 p=1.0 each); this does not establish equivalence. The controls nevertheless answer whether a terminal gain can currently be assigned to memory, advice, or control: these data do not support that attribution.

Appendix H.5 also reports a length-matched path/encoding test (95/96 valid responses; 23 complete quartets), without reliable Brier or vote benefit. An independent scalar event-ledger replay retains primitive updates and planner/controller algorithms but removes cumulative pair-conflict updates and path memory. On Full-source trajectories, scalar has lower Brier error (0.1961 vs. 0.2135) and higher proposal purity by 2.37pp. This is conditional replay, not a terminal tournament.

Our claim is specific: structured fact presentation improves factual binding, and the integrated interface makes belief-to-action decisions inspectable. We do not claim unique graph necessity or Full superiority over same-information simple assistance. Appendix H separately documents historical E2 request-log information-boundary risks and the new cohort's recovery/selection limits; the cohorts are not pooled.

We would like to add two clarifications to our earlier response: what the factual-citation gain measures, and what happens when execution control is disabled.

What the factual-citation gain means. The metric checks whether a citation reports an observed relationship correctly, not just whether its fact ID exists. We rechecked the 111 paired responses: every cited ID was valid in both conditions, but the subject-relation-object content failed to match a visible fact in 34 of 988 Graph citations, versus 58 of 624 Flat citations. Graph produced more citations yet fewer incorrect tuples. These are descriptive citation counts; the reported +4.61-percentage-point effect weights source seeds equally, rather than pooling citations as independent samples. Both conditions receive the same facts and instructions, without supplied posteriors, plans, or controllers. This is a factual-binding benefit without execution intervention. Graph prompts are longer, so it does not isolate representation from token budget.

What improves without overrides. In Avalon, Good must first complete three successful quests, then survive an assassination attempt. Table 4 separates these stages. Memory only and memory + advice each reach three quest successes in 48/50 games, compared with 43/50 at baseline and 40/50 with controller only. In both memory conditions, the ACG execution controller is disabled: it cannot replace the LLM's proposed action. The common internal processor still runs, so these are delivery controls, not removal of graph computation. The quest-progress pattern is therefore also present without action overrides. These are descriptive counts from the selected valid completions. Later assassination losses offset some of the extra quest completions, which explains why final wins alone do not reveal this pattern.

FlatFull addresses a different question: it retains Full's derived state, advice, and controller, changing their serialization. Its comparison with Full tests how the same assistant information is presented. The no-controller arms instead let us examine whether the LLM can use the supplied memory without having its decision replaced. Separating these questions helps distinguish support for the model's reasoning from direct control of its actions.

Reviewer_wa5nOpenReview ↗

Response to the author's rebuttal

Thank you for the responses and additional experiments, which address some of my concerns. However, my main concern remains: the full system has yet to demonstrate an advantage over simpler alternatives. Although the graph representation improves factual citation accuracy, it has not shown clear improvements in belief estimation or voting decisions. I therefore maintain my original score.

Reviewer_1jX8OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper proposes a framework for converting modeling beliefs and selecting actions in social deduction games, particularly Werewolf and Avalon. The framework maintains observations, beliefs, and player attitudes and uses uncertainty to update an underlying graph memory. This is then used to produce decisions/actions when playing the game. Experiments are run over Werewolf and Avalon and compared to a single baseline (GRAIL) over a variety of model families.

Critical strengths
  • Decision making from beliefs in cooperative/competitive partially observable environments (social deduction) is a challenging task, and the method's separation of belief, credibility, and actions is a reasonable setup.

  • The modular architecture is straightforward and relatively interpretable to external observers.

Critical weaknesses
  • The language of this paper makes it quite hard to understand, as it frequently uses colloquial terms with no clear meaning in a technical context. For example what is a "GRAIL-port"? What is "GRAIL-aligned Avalon"? The experimental design is not clearly explained. Is Figure 2 showing ACG against itself? This figure isn't even referenced in the paper as far as I can tell (this is true for all other figures as well). What is the GRAIL-aligned comparison in Figure 3? Four "families" (E1-E4) are defined but I don't see these referred to in the results. To be blunt, this paper reads like it was in part or in whole generated by an LLM and the readability suffers for it.

  • Likewise, the methodology is unclear to me. It appears that the likelihood ratios in the Bayesian style update are manually defined (see Table 3 in appendix) rather than learned from data. Why? Were these manually specified by some domain expert? How does this scale to new tasks? This all appears to be a highly specific, engineered framework based entirely on heuristics and is applied to specific social deduction games (Avalon/Werewolf).

  • The experimental analysis is fairly limited as well. Just showing coarse win rate metrics and little else.

  • There are no ablations over framework components, showing which components hurt or help.

Questions for authors
  1. Can you clarify the experimental design?

  2. Can you clarify the methodology and how heuristic values are obtained?

2 comments

Thank you so much for your careful review and suggestions. We sincerely apologize for the confusion caused by our presentation and undefined terms. We have revised the experimental description, clarified parameter sources, and added component analysis. Changes in the November 13 revision are marked in blue; references below refer to that version.

1. Experiments and figures

Regarding Figure 2: yes, in the both-side arm, ACG-assisted Good plays against ACG-assisted Evil. The other arms equip neither side, only Good, or only Evil. All win rates refer to Good; a decrease under Evil-only deployment benefits the receiving side.

Table 1 now connects each experiment to its rules and results:

StudySetting and comparisonResults
E1Six-player Avalon, no special roles; baseline, Good-only ACG, adapted GRAIL; two disclosure rulesFig. 3
E2Six-player Avalon with Merlin, Percival, Morgana, Assassin; four deployment arms, three modelsFig. 2, Table 2
E3Nine-player Werewolf, one model in all seats; four armsFig. 4
E4Nine-player Werewolf, nine model endpoints; four armsFig. 5

Result subsections now use E1-E4 and explicitly reference figures. We replaced "GRAIL-port" with "adapted GRAIL decision chain." E1 uses our local runner, not GRAIL's original benchmark. It reveals either individual quest actions or only success/failure; individual attribution is an information-channel diagnostic. We also clarify that our Avalon runner executes the last team after five rejections instead of awarding Evil the game.

2. Method and parameter sources

We agree that the original text did not clearly separate the architecture from its game-specific engineering.

Section 3 and Figure 1 now explain the three views: the ledger records who said or did what; the ego graph stores private facts and role estimates; the public graph tracks suspicion and stated support. Recording a claim does not verify it. Suspecting an opponent and having public support to act are different signals. Figure 1 also distinguishes the LLM's proposed action from the controller's executed action.

Section 3.3 and Appendix B.3 distinguish three parameter sources:

  • Evidence weights: default likelihood pairs are developer-specified strengths, not fitted frequencies or established expert calibration. Development records trace the contradiction pair's reduction from (0.68, 0.32) to (0.55, 0.45) to false contradictions caused by mixed-stance parsing.
  • Joint-quest failure propensities: these derive from 25 archived GPT-4.1 development games. Failures/Evil-player actions by round are 7/23, 10/29, 32/35, 15/16, and 9/9. The implemented vector (0.30, 0.35, 0.91, 0.94, 0.99) approximates these frequencies, capping the last value for numerical stability. Shared development/evaluation seeds preclude seed-held-out calibration.
  • Action-score coefficients: fixed preferences over risk, progress, exposure, and coordination, not learned win probabilities.

Fixed weights make decisions inspectable, but do not establish optimality. A new game requires visible event types, evidence weights, legal actions, and role-specific scores. The shared three-view interface does not make adaptation automatic.

3. Component analysis and evidence beyond wins

Tables 3-4 and Figure 6 add two analyses.

A same-state graph-versus-flat test supplies identical primitive facts and instructions, without supplied posteriors, plans, or controllers. Across 111 pairs from 29 seeds, factual-citation matching rises from 91.33% to 95.94% (+4.61pp; seed-bootstrap 95% CI [2.83, 6.42]pp; Holm-3 p=0.00018). This measures fact-ID and subject-relation-object binding. Brier and vote safety do not improve, and graph prompts are longer: the supported benefit is better factual binding, not graph necessity.

A separate Avalon cohort has 50 selected valid completions per arm: baseline, memory only, advice only, controller only, memory plus advice, Full, and FlatFull. All retain internal processing; FlatFull changes serialization of the same derived information. Full reaches three quest successes in 49/50 games versus 43/50 at baseline, but assassination losses rise from 9/50 to 16/50, leaving Good wins at 33/50 versus 34/50. This separates quest progress from final success, without establishing a terminal advantage. Figure 6 reports all seven process endpoints with uncertainty.

Appendix H documents the historical E2 request-log problem: private reasoning appeared in other players' contexts, limiting attribution of those historical win contrasts. New studies are reported separately.

We appreciate your careful reading and hope these concrete revisions make the method, its contribution, and its limits easier to assess.

We would like to add a few details to our earlier response about what the hand-set weights mean and how they affect decisions.

What the weights mean. A speech contradiction can be ambiguous, so we give it less weight than an attributed failure. In revised Eq. (3), the pairs (0.55, 0.45) and (0.90, 0.10) correspond to multipliers of about 1.22 and 9 on the odds that a player is Evil, before event-strength scaling and clipping. These values express assumptions about evidence strength, not calibrated event frequencies. Their effects can be checked and the values adjusted without retraining the LLM.

Sensitivity to score weights. We also checked how much the planner's choices depend on the exact score coefficients. Extending the fixed-state analysis in Appendix B.3, we reproduced all 12,330 logged Werewolf plan selections. Changing each of seven utility coefficients and two risk-control parameters by +/-20%, one at a time, left 96.88%-100% of choices unchanged across the 18 settings. Agreement was still 98.50%-100% for the 6,019 decisions with all candidate scores strictly between 0 and 1 and a unique top choice. The stability therefore does not come solely from clipped scores or ties. This is a post-hoc check of score rankings in recorded states, not a test of belief calibration or performance in new games.

A concrete component effect. A decision in Appendix H.4 gives a concrete example. The LLM proposes voting for Player4, a Good player. Belief updating raises Player5's estimated Evil probability from 0.3333 to 0.6452, and the planner/controller instead executes a vote for Player5, a wolf. With the other ballots fixed, this turns a 3-3 tie into a 4-2 wolf exile. Without either belief updating or execution control, the vote stays on Player4. Removing the written advice does not undo the correction.

Across the 20 tested checkpoints, Full produced nine wolf-target votes, compared with eight when either updating or control was removed; the difference was not statistically significant. We use this case to explain how the components work together, not to claim an average advantage. Here, the correction depends on using the updated belief at execution, not on showing the LLM more advice.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.