PaperlayerView exact revision on arXiv

Source-linked AI summary

Do LLMs Understand Sequential Structure? A Controlled Study of Inference and Generation

Jerry Wang, Zhengxiang Wang, Ting Yu Liu, Hsin-Ling Hsu, Yi-Cheng Lai, Tengfei Ma

arXiv:2610.04977v1cs.AI

TL;DR

LLMs are increasingly used as interactive agents, but it remains unclear whether they recover the sequential process behind observed actions, rather than only their surface frequencies. The paper tests this in controlled RPS and stochastic n-gram tasks, finding that recognition does not ensure faithful simulation and higher-order dependencies remain difficult to recover.

  • Problem

    Observed action frequencies do not uniquely identify whether behavior came from independent sampling or history-conditioned rules, leaving open whether LLMs recover the process behind trajectories.

    Source: §1 · pp. 1–2

  • Method

    The paper evaluates strategy identification, distribution matching, and conditional rule execution in controlled two-player RPS and one-player stochastic n-gram tasks.

    Source: §1 · p. 2, §6 · p. 8

  • Results

    Recognition, marginal distribution matching, and conditional rule execution are separable; models degrade when generation requires maintaining higher-order conditional structure.

    Source: §1 · p. 2, §4.5 · p. 7, §6 · p. 9

  • Takeaways & Limitations

    Surface behavioral similarity or correct strategy recognition alone does not guarantee faithful conditional generation.

    Source: §4.5 · p. 7, §6 · p. 9

    The predefined candidate strategy set supports controlled diagnosis but does not cover open-ended strategy discovery.

    Source: Limitations · p. 9

Abstract

from arXiv · show

Large language models (LLMs) are increasingly used as interactive agents and simulators, yet it remains unclear whether they can recover latent sequential structure beyond surface action frequencies. This distinction is critical for behavioral simulation, where actions are often shaped by prior context rather than marginal frequencies alone. We study this question using controlled two-player Rock--Paper--Scissors interactions and a one-player stochastic n-gram continuation task. Across these experiments, we test whether LLMs can identify latent strategies, follow simple Markov rules, and sustain higher-order conditional dependencies. Our framework separates distribution matching from conditional rule following. Results show that longer context does not improve identification, correct recognition does not ensure faithful simulation, and higher-order dependencies substantially degrade rule recovery. Apparent behavioral fidelity can therefore mask incorrect generative mechanisms.

1 Introduction

Similar surface action statistics can arise from different latent processes, so matching aggregate behavior does not establish recovery of the conditional structure that generated a sequence. The paper tests strategy identification and conditional generation in controlled RPS interactions and a stochastic n-gram task, finding higher-order dependencies difficult to recover and sustain.

1 Introduction

  • Similar action frequencies can come from independent sampling or history-dependent rules, so aggregate matching alone does not show that a model recovered the generating process.The paper frames this distinction as central to evaluating sequential behavior.Source: §1 · p. 1
  • The study evaluates whether LLMs can recover conditional processes and sustain them during generation, a gap left open by prior controlled studies of in-context inference.Those studies span simple functions, regression, formal languages, Markov chains, and hidden Markov processes.Source: §1 · p. 2
  • Across RPS and one-player n-gram tasks, longer context does not reliably improve strategy recovery, and higher-order dependencies most clearly degrade performance.The degradation persists with longer prefixes or explicit transition rules, while a prefix-only empirical n-gram estimator remains comparatively stable at high order.Source: §1 · p. 2

2 Related Work

Prior work studies strategic reasoning, opponent inference, and what LLMs learn from context, but these do not by themselves establish recovery of the sequential rule behind observed behavior. This paper distinguishes marginal matching, strategy recognition, and conditional rule execution.

Game-Based Evaluation of LLM Strategic Behavior

  • The paper shifts game-based evaluation from successful play or opponent identification to whether strategic behavior is supported by the correct underlying mechanism.It separates marginal distribution matching, strategy recognition, and conditional rule execution.Source: §2 · p. 2

In-Context Learning of Sequential Structure

  • Work on in-context learning motivates testing whether models infer and sustain sequential dependencies, beyond using prior examples for marginal belief updating.The cited literature connects in-context learning to implicit Bayesian inference, training-data properties, demonstrations, and mechanisms other than conventional rule learning.Source: §2 · p. 2

Distinguishing Marginal Statistics from Markovian Dynamics

  • Classical sequence models distinguish history-conditioned transitions from aggregate frequencies, while opponent-modeling work primarily targets adaptation or decision-making.This paper instead tests whether LLMs recover sequential structure beyond fixed marginal behavior.Source: §2 · pp. 2–3

3 Methodology

The methodology uses controlled RPS trajectories and a stochastic n-gram continuation task to separate strategy identification, distributional fidelity, and conditional rule execution. It evaluates increasingly complex rules across several model configurations using identification, rule-following, and distributional metrics.

3.1 Task Description

  • The task asks models to infer latent player strategies from two-player RPS trajectories and, in generation settings, produce continuations consistent with those strategies.Each player selects Rock, Paper, or Scissors at each round; a trajectory records both players’ actions.Source: §3.1 · p. 3

3.2 Player Types

  • Statistical players test recovery of marginal action statistics, whereas deterministic Markov players test whether models infer and follow history-dependent rules.The Markov rules include first-order and second-order histories.Source: §3.2 · p. 3

3.3 Experiment Types and Scale

  • The three RPS experiments progress from strategy identification to first-order inference-and-simulation and then to joint-state or second-order rules, generating 1,000-round continuations in Experiments 2 and 3.Experiment 1 varies context length from 100 to 1,000 rounds; Experiments 2 and 3 use 60 samples per pair type.Source: §3.3 · pp. 3–4

3.4 Models and Experimental Coverage

  • The evaluation includes DeepSeek-V4-Flash, GPT-5, and GPT-5-mini, with GPT-4.1, Gemini 3 Flash, and Qwen3-8B added for Experiment 1.The added models broaden coverage across providers, generations, scales, and open- versus closed-weight settings.Source: §3.4 · p. 4

3.5 Evaluation Metrics

  • Strategy identification is measured by exact-match accuracy, with Markov versus non-Markov differences indicating whether history-dependent strategies are harder to identify.Figure 3 reports accuracy across seven configurations averaged over context lengths and marks significant differences at p < .001.Source: §3.5 · p. 4, Figure 3 · p. 4
  • Generation metrics assess whether actions follow the true rule under generated histories, including strict and cumulative strict match; statistical-player distributions are compared by MSE.Cumulative strict match measures persistence over generated rounds, and positive relative Markov–Non-Markov MSE gaps indicate higher error for Markov players.Source: §3.5 · p. 4
  • For stochastic n-gram continuations, context-conditioned likelihood gain measures improvement over a unigram baseline, while lower state-frequency-weighted Jensen–Shannon divergence indicates better recovery.The metrics compare generated next-action distributions conditioned on history states with the true distributions.Source: §3.5 · p. 4

4 Results

The experiments separate strategy recognition, marginal distribution matching, and conditional rule execution, finding that success on one does not guarantee success on the others. Longer histories do not reliably improve identification, and higher-order dependencies are especially difficult to execute.

4.1 Can models identify latent player strategies?

  • Markov identification accuracy is lower than Non-Markov accuracy for all seven models, significantly so in six; GPT-5 is the exception (p = .095).Increasing history from 100 to 1000 rounds does not improve identification and often degrades it; a maximum-likelihood baseline reaches 100% accuracy at all context lengths.Source: §4.1 · pp. 4–5

4.2 Can models faithfully simulate inferred strategies?

  • Correctly identified players are simulated with better rule match, while wrong-identity cases can still show above-random rule overlap.Wrong identities can correspond to players with similar behavioral rules, so identity errors are structured rather than random.Source: Figure 4 · p. 5, §4.2 · p. 5
  • Strict rule match can meet or exceed identity accuracy, while teacher forcing distinguishes local rule-application errors from difficulty sustaining rules during generation.DeepSeek Reasoner and GPT-5 perform strongly with ground-truth histories, whereas DeepSeek Chat and GPT-5-mini still struggle in that setting.Source: Figure 5 · p. 6, §4.2 · p. 6
  • 8–9% higher MSE for Markov players overall rises to more than 100% in the correct-identity subset; the wrong-identity subset shows the opposite pattern.Among 282 incorrectly recovered strategies, 41.8% remain within TV ≤0.02 and 62.1% within TV ≤0.10 of the target marginal distribution, so marginal fidelity can conceal incorrect rules.Source: §4.2 · pp. 5–6, Figure 6 · p. 7

4.4 Which structures make rule execution harder?

  • Adding joint-state information does not reduce rule-following performance, whereas second-order rules lower strict match despite relatively high rule overlap and identity accuracy.The results implicate maintaining and applying longer historical dependencies rather than representing joint states or recognizing Markovian players.Source: §4.4 · p. 7

4.3 Does generation affect recognition?

  • Generation has no systematic effect on recognition: model-level changes vary, and none of the differences are statistically significant.The results therefore do not explain generation failures through player-identification errors alone.Source: §4.3 · p. 6, Figure 7 · p. 7

4.5 Summary

  • Recognition, marginal matching, and conditional rule execution are separable abilities; longer-history dependencies, especially second-order rules, are the main generation bottleneck.Surface behavioral similarity can mask failures to recover and execute sequential structure.Source: §4.5 · p. 7

5 Follow-Up Experiments

The one-player stochastic n-gram task separates conditional rule recovery from player attribution and deterministic rule execution. Models’ context use and rule recovery weaken at high dependency order, and longer prefixes or explicit rules do not consistently remove that degradation.

5.1 One-Player Stochastic Processes

  • The one-player stochastic task tests recovery of conditional transition distributions without player attribution or deterministic-rule execution.It uses probabilistic transitions and evaluates context use beyond unigram frequencies and recovery of the true conditional distribution.Source: §5.1 · p. 7, §5.2 · p. 8

5.2 Factors

  • The study varies n-gram order across 1, 2, 4, and 8 and compares prefix-only prompts with prompts that also provide the rule and transition probabilities.The rule-given setting separates rule inference from rule execution.Source: §5.2 · pp. 7–8

5.3 Key Results

  • A prefix-only n-gram maximum-likelihood baseline remains stable at higher orders, indicating that the observed prefix contains recoverable high-order conditional information.The baseline is evaluated with the same CCLG and WJS metrics.Source: §5.3 · p. 8, §5.2 · p. 8
  • At n = 8, CCLG drops sharply for most models while WJS increases, unlike often-positive CCLG at n = 1 to 4.The results indicate that sparse high-order states make conditional transition structure harder to recover and sustain during generation.Source: §5.3 · p. 8, Figure 9 · p. 8
  • Higher CCLG does not always correspond to lower WJS, so context use and transition-rule recovery are distinct abilities.Some models show context-conditioned gains in lower-order or rule-given settings yet still diverge from the true transition distributions.Source: §5.3 · p. 8, §5.2 · p. 8, Figure 9 · p. 8
  • Neither increasing prefix length from 256 to 2048 nor providing transition rules consistently removes high-order degradation.The authors suggest the bottleneck lies in maintaining transition structure during generation.Source: §5.3 · p. 8, Figure 9 · p. 8

6 Conclusion

The paper presents a controlled framework for testing whether LLMs recover sequential dynamics beyond marginal statistics. Its experiments find that correct recognition or recoverable information does not ensure reliable higher-order conditional generation.

6 Conclusion

  • The framework uses two-player Rock–Paper–Scissors and a one-player stochastic n-gram task to separate strategy recognition, marginal distribution matching, and conditional rule execution.These abilities are often conflated in agent evaluation.Source: §6 · pp. 8–9
  • Higher-order transition recovery remains unreliable even when recoverable information is present and transition rules are explicitly provided.Surface behavioral similarity or correct strategy recognition alone does not guarantee faithful conditional generation.Source: §6 · p. 9

Limitations

The stated limitations bound the study’s strategy space and leave prompt and representation choices open. The accompanying materials specify the candidate strategies and task prompts used for evaluation.

Limitations

  • Players are drawn from a predefined candidate set, so the framework diagnoses recovery under known rules but does not cover open-ended strategy discovery.The authors suggest future work could use larger or learned strategy spaces.Source: Limitations · p. 9
  • Symbolic trajectories and constrained output formats make rule-level evaluation reliable, but the authors cannot guarantee these choices are optimal.The uncertainty includes prompts, trajectory representations, output schemas, and decoding settings.Source: Limitations · p. 9

A.1 Candidate Pool Overview

  • The candidate pool includes static and distribution-based non-Markovian players as well as Markovian or reactive players conditioned on prior game states.Table 2 distinguishes the two groups by row color.Source: Table 2 · p. 12

A.2 Candidate Pool Description

  • The prompt materials describe fixed-distribution strategies and first- and second-order Markov players, with rules based on opponent-only or joint player histories.The candidate descriptions include reactive moves and missing-action rules.Source: §A.2 · p. 13, §A.3.1 · p. 13, §A.3.2 · p. 13

Generation Prompt

  • The RPS generation prompt asks models to infer player strategies and simulate subsequent rounds, while the identification prompt asks them to classify players from trajectories and verify action counts.The simulation prompt also instructs models to avoid repetitive short patterns.Source: §A.4 · pp. 14–15, §A.5 · pp. 15–16

A.6 Prompt for High-Order Generation

  • The high-order generation prompts contrast inferring an n-gram rule from a prefix with continuing a sequence under a supplied rule and transition probabilities.Both prompt types request a symbolic continuation.Source: §A.6 · p. 16

B Models

The study evaluates several proprietary and open-weight model configurations across its experiments. The reported identification gap is mostly negative, indicating that Markov players are generally harder to identify than non-Markov players.

B Models

  • The study reports API identifiers and access dates for its models, while proprietary GPT-5 properties such as parameter count, architecture, and training corpus are not publicly disclosed.Table 3 summarizes model identifiers and access dates.Source: B Models · p. 18
  • The model set spans proprietary OpenAI, Google, and DeepSeek models and the open-weight Qwen3-8B checkpoint.GPT-4.1 and Gemini 3 Flash broaden provider coverage; Qwen3-8B adds a smaller open-weight model.Source: B Models · pp. 18–19

C Experiment Scale

  • Experiments 1 and 2 evaluate seven and four model configurations, respectively, while Experiment 3 uses DeepSeek Reasoner for controlled structural analysis.Experiments 1 and 2 use first-order opponent-only players; Experiment 3 includes four Markov player sets.Source: C Experiment Scale · p. 19

D Markov–Non-Markov Accuracy Gap

  • The Markov-minus-Non-Markov identification accuracy gap is mostly below zero across models and context lengths.Negative values mean Markov players are harder to identify, supporting additional difficulty beyond longer input length alone.Source: D Markov–Non-Markov Accuracy Gap · p. 19

E MLE Recoverability Check for Strategy Identification

The closed-pool MLE recoverability check identifies every player from the same trajectories used in the LLM experiment, while its posterior is concentrated on the correct candidate. Experiment 1 evaluates identification across context lengths for seven model configurations and both player types.

E MLE Recoverability Check for Strategy Identification

  • The estimator scores each candidate by marginal-action likelihood for distribution players or smoothed rule-consistency likelihood for deterministic Markov players, then selects the highest-scoring identity.It uses the same trajectories, context lengths, candidate pools, and ground-truth labels as the LLM experiment.Source: E MLE Recoverability Check for… · p. 20
  • 100% accuracy at every context length is achieved by the closed-pool MLE recoverability check, showing that player identities are statistically recoverable from the observed trajectories.The check uses the same trajectories and candidate pools as the LLM identification experiment.Source: E MLE Recoverability Check for… · pp. 19–20, Figure 11 · p. 21
  • The top-ranked candidate receives nearly all posterior mass for non-Markov players, with even stronger concentration for Markov players.The MLE baseline therefore does not find Markov players intrinsically more ambiguous than statistical players, unlike the LLM results.Source: E MLE Recoverability Check for… · pp. 20–21, Figure 12 · p. 21

F Experiment 1: Strategy Identification Across Context Lengths

  • Experiment 1 reports identification accuracy for seven model configurations at 100, 200, 500, and 1000 context rounds, separately for Markov and Non-Markov players.The supplied passage identifies the evaluation conditions but does not report the results for those configurations.Source: F Experiment 1: Strategy… · p. 21

G OLS Analysis of Length Effects

The OLS analysis finds a negative relationship between input length and identification accuracy, while output-length relationships vary by model. Reformatting trajectories as a structured table does not consistently improve identification.

G OLS Analysis of Length Effects

  • The OLS analysis fits separate regressions for each model, relating identification accuracy to input length and generated output length.Input length is estimated from saved prompt-bearing report content; output length is measured in generated-response characters.Source: G OLS Analysis of Length Effects · p. 21
  • Identification accuracy has a consistently negative relationship with input length across all evaluated models.The authors interpret this as evidence that longer histories do not improve identification, even within the models’ effective context windows.Source: G OLS Analysis of Length Effects · p. 21
  • Output length has model-dependent associations with accuracy: GPT-5 and GPT-5 mini show significant negative slopes, while DeepSeek Chat and DeepSeek Reasoner show no significant relationship.Overall, longer responses do not reliably improve identification and may sometimes reflect uncertainty or over-generation.Source: G OLS Analysis of Length Effects · pp. 21–22

H Prompt-Format Ablation

  • The row-wise structured trajectory format does not consistently improve identification; performance rises in some settings but falls or remains nearly unchanged in others.The ablation compares raw and structured-table formats for GPT-5-mini and GPT-4.1 at 100 and 1000 context rounds.Source: H Prompt-Format Ablation · p. 22

I Error Patterns and Markov Identification Metrics

Identification errors are structured: models confuse behaviorally similar identities and may fail to detect Markovian rules, not merely choose the wrong identity. Markov detection varies substantially across models and context lengths.

I Error Patterns and Markov Identification Metrics

  • At 1000 rounds, DeepSeek Chat’s Markov recall is 0.14, strict F1 is 0.113, and strict precision is 0.095, indicating sharply reduced reliability in detecting Markov structure.Its recall is 0.42 at 100 rounds and 0.44 at 500 rounds.Source: I Error Patterns and Markov… · p. 23
  • DeepSeek Reasoner’s Markov recall remains 0.78 at 1000 rounds, while its strict accuracy decreases from 0.955 at 100 rounds to 0.855 at 1000 rounds.Its precision falls from 1.000 at 100 and 200 rounds to 0.684 at 1000 rounds.Source: I Error Patterns and Markov… · p. 23
  • GPT-5’s Markov recall falls from 0.92 at 100 rounds to 0.70 at 500 rounds, then recovers to 0.80 at 1000 rounds, showing no consistent improvement with more context.GPT-5 mini’s recall is 0.58 at 100 rounds and 0.40 at 1000 rounds, with a low of 0.34 at 500 rounds.Source: I Error Patterns and Markov… · p. 24
  • The confusion-matrix and strict-metric analyses indicate that Markov difficulty includes failure to detect transition-dependent behavior, beyond errors in selecting an exact identity.Errors often link behaviorally similar identities, while strict Markov metrics distinguish failure to detect Markov behavior from failure to identify the player correctly.Source: I Error Patterns and Markov… · pp. 22–24

J Forecasting and Distributional Prediction Metrics

Forecasting metrics show that longer contexts can degrade distributional predictions for weaker models, while stronger or reasoning-oriented models remain more stable. Additional diagnostics find higher cross-entropy error for Markov players in overall and correct-identity conditions, and structured confusion among identities.

J Forecasting and Distributional Prediction Metrics

  • Total variation compares true and predicted action distributions, Brier score compares induced win-draw-loss outcome probabilities, and expected value loss measures squared decision-level error.Lower expected value loss means the model better preserves the win-loss utility implied by true behavior.Source: J Forecasting and Distributional… · p. 24
  • Forecasting metrics complement identity accuracy by assessing predictive information in generated action counts; longer contexts can worsen distributional mismatch or prediction loss for weaker models, while DeepSeek Reasoner and GPT-5 remain more stable.Total variation distance applies only to static distribution players; the three error metrics are lower when forecasting quality is better.Source: J Forecasting and Distributional… · pp. 24–25, Figure 17 · p. 26

K Additional Distributional Diagnostics

  • The CE gap follows the MSE pattern: Markov players have higher error overall and under correct identity, while the incorrect-identity condition shows a smaller or negative gap.The reported pattern supports greater distributional difficulty when reproducing the exact target behavior.Source: K Additional Distributional Diagnostics · p. 25, Figure 18 · p. 26

L Additional Identification Diagnostics

  • Binary Markov/non-Markov matrices assess family recognition, while full identity matrices show that errors often concentrate among behaviorally similar players.A model can identify the broad family correctly yet still confuse specific identities.Source: L Additional Identification Diagnostics · p. 26

M Complex Markov Sets

  • The complex Markov sets vary dependency order and whether rules condition on opponent-only or joint-state information.The table frames these as distinct structural factors for stress-testing conditional generation.Source: M Complex Markov Sets · p. 26, Table 6 · p. 26

N Complex Markov Identification Diagnostics

Across these diagnostics, LLMs can confuse exact player identity with rule execution, and stable rule-following can coexist with distributional drift. In the n-gram task, higher-order generation degrades, while extra context or explicit rules do not reliably resolve the failures.

N Complex Markov Identification Diagnostics

O Complex Markov Distributional and Temporal Diagnostics

P Complex Markov Identity-Conditioned and Rule-Level Diagnostics

  • Some Markov rules retain high local overlap but lower strict match, indicating that capturing transition components is easier than executing the exact rule across required states or histories.The breakdown shows this difficulty can vary within the same Markov set.Source: P Complex Markov Identity-Conditioned… · p. 28, Figure 25 · p. 30

Q Statistical Significance Test for Recognition and Simulation

  • None of the four models’ Exp1–Exp2 recognition-accuracy differences reaches conventional 0.05 significance, so numerical changes should be interpreted cautiously.GPT-5 has the largest difference, but it remains marginal and statistically nonsignificant.Source: Q Statistical Significance Test for… · p. 30, Table 7 · p. 31

R One-Player Raw Likelihood and Stochasticity Diagnostics

S One-Player Validity and Coverage; T One-Player Degeneration Diagnostics

U One-Player Rule-Access Effects; V One-Player Prefix-Length Effects; W One-Player Information and Context Effects

X One-Player Prefix-Only Structured Baseline

Loading 2610.04977v1…