cs.AIOct 4, 2026
SaveDo LLMs Understand Sequential Structure? A Controlled Study of Inference and Generation
Organizations: University of Illinois Urbana-Champaign · Stony Brook University · National Chengchi University
Abstract
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.
Figures & tables
Figure 1: Similar action proportions can arise from different latent generative processes and policies.
Figure 2: Ability-based evaluation pyramid, from strategy identification to increasingly complex conditional generation.
Figure 3: Identification accuracy across seven model configurations, averaged across context lengths. Bold model labels and asterisks indicate significant Markov–Non-Markov differences ( ).
Figure 4: Rule-following performance by identity condition.
Figure 5: Cumulative strict rule match across generated rounds. Solid lines show cumulative strict rule match, while dashed lines show overall identity accuracy as reference values rather than upper bounds.
| Model | All cases | Correct-ID subset |
|---|---|---|
| DeepSeek Chat | 52.5% | 66.7% |
| DeepSeek Reasoner | 93.3% | 97.2% |
| GPT-5 | 82.5% | 89.5% |
| GPT-5-mini | 54.2% | 70.0% |
Table 1: Teacher-forced next-step accuracy under ground-truth interaction histories. All cases reports accuracy over the full evaluation set, while Correct-ID subset includes only cases in which the player identity was correctly inferred.
Figure 8: Results on complex Markov input structures. Panel (a) shows rule-following performance, and Panel (b) shows identity identification accuracy across the same settings.
Figure 9: Context use and rule recovery across n-gram order with prefix length 2048.
Appendix figures & tables31 assets
Supplementary material from the paper’s appendix.
Appendix
| ID | Name | Rock | Paper | Scissors | Type / Rule |
| A | Pure Scissors | 0% | 0% | 100% | Non-Markovian Static |
| B | Pure Rock | 100% | 0% | 0% | Non-Markovian Static |
| C | Pure Paper | 0% | 100% | 0% | Non-Markovian Static |
| D | Uniform Random | 33.3% | 33.3% | 33.4% | Non-Markovian Distribution |
| E | Rock + Paper | 50% | 50% | 0% | Non-Markovian Distribution |
| F | Rock + Scissors | 50% | 0% | 50% | Non-Markovian Distribution |
Table 2: Candidate pool of player strategies used in the Rock-Paper-Scissors experiments. Green rows denote non-Markovian players, including deterministic static players and distribution-based players. Orange rows denote Markovian or reactive players that condition their actions on previous game states.
| Model | API Identifier | Access Date |
|---|---|---|
| DeepSeek Chat | deepseek-chat | Apr. 30, 2026 |
| DeepSeek Reasoner | deepseek-reasoner | Apr. 30, 2026 |
| GPT-5 | gpt-5 | Apr. 30, 2026 |
| GPT-5-mini | gpt-5-mini | Apr. 30, 2026 |
| GPT-4.1 | gpt-4.1 | Jul. 8, 2026 |
| Gemini 3 Flash | gemini-3- flash-preview | Jul. 8, 2026 |
Table 3: API identifiers and access dates for all models used in this study.
| Experiment | Models | Context | Samples | Player / rule sets |
|---|---|---|---|---|
| Exp. 1: Strategy Identification | 4 configs | Given 100, 200, 500, or 1000 observed rounds | 50 stat–stat, 50 Markov-as-P1, and 50 Markov-as-P2 per context length | A–P with X/Y/Z. Each game contains either two statistical players or one statistical player and one Markov player. |
| Exp. 2: Simple Markov Inference-and-Simulation | 4 configs | Given a 1000-round source trajectory | 60 Markov-as-P1 and 60 Markov-as-P2 | A–P with X/Y/Z. Each game contains one statistical player and one first-order opponent-only Markov player. |
| Exp. 3: Complex Markov Inference-and-Simulation | deepseek-reasoner | Given a 1000-round source trajectory | 60 Markov-as-P1 and 60 Markov-as-P2 per rule family | A–P with X/Y/Z, Q/R/S, x/y/z, and T/U/V, covering first-order opponent-only, first-order joint-state, second-order opponent-only, and second-order joint-state rules. |
Table 4: Evaluation scale for the three main two-player experiments. A–P denotes the statistical player pool. X/Y/Z, Q/R/S, x/y/z, and T/U/V denote the Markov rule families defined in Table 2 .
Figure 10: Markov-minus-Non-Markov identification accuracy gap across context lengths. Negative values indicate that Markov players are harder to identify than Non-Markov players. Error bands denote 95% confidence intervals.
Figure 11: Exact-match strategy identification accuracy of the non-LLM maximum-likelihood recoverability check across context lengths. The estimator uses the same trajectories and candidate pools as the LLM identification experiment and achieves 100% accuracy at every context length.
Figure 12: Top-5 normalized posterior probabilities under the candidate-pool MLE closed-set identification check. The left panel reports results for true non-Markov players, and the right panel reports results for true Markov players.
Figure 13: Identification accuracy across context lengths for all seven model configurations, reported separately for Markov and Non-Markov players.
Figure 14: OLS visualizations of the relationship between identification accuracy and length-related variables. The left panel shows input length versus accuracy, and the right panel shows output length versus accuracy. In both panels, each subplot corresponds to one model, and the fitted line with shaded band shows the model-wise OLS regression with its 95% confidence interval.
| Model | Rounds | Markov | Non-Markov |
|---|---|---|---|
| GPT-5-mini | 100 | 58.0 29.0 | 72.0 98.0 |
| GPT-5-mini | 1000 | 40.0 24.0 | 30.0 46.0 |
| GPT-4.1 | 100 | 70.0 61.0 | 87.3 87.0 |
| GPT-4.1 | 1000 | 42.0 56.0 | 66.0 54.0 |
Table 5: Identification accuracy (%) under raw and row-wise structured trajectory formats. Each entry reports raw structured-table accuracy.
Figure 15: Confusion-matrix diagnostics for strategy identification. The left panel reports identity-level confusions over the full candidate pool, while the right panel aggregates predictions across the evaluation setting.
Figure 16: Markov-specific strict identification metrics across context lengths. The four panels report strict accuracy, precision, recall, and F1 for Markov player identification. Each curve corresponds to one model, and the x-axis indicates the number of context rounds.
Figure 17: Forecasting and distributional prediction metrics across context lengths. The panels report total variation distance, Brier score, and expected value loss. Each point shows the mean metric value for one model under one context-length condition. Each curve corresponds to one model, and the x-axis indicates the number of context rounds.
Figure 18: Relative CE gap between Markov and non-Markov players. Positive values indicate higher Markov error. The CE-based result follows the same qualitative pattern as the MSE-based result in Figure 7 .
Figure 19: Binary Markov/non-Markov confusion matrices. These diagnostics separate broad class recognition from exact identity recognition and show whether model errors come from confusing the two player families or from finer-grained identity mistakes.
Figure 20: Full identity-level confusion matrices. Rows correspond to true player identities and columns correspond to predicted identities. Off-diagonal structure indicates that identity errors are not uniformly random, but often occur among behaviorally similar players.
| Set | Order | State representation |
|---|---|---|
| XYZ | First-order | Opponent-only |
| QRS | First-order | Joint-state |
| TUV | Second-order | Joint-state |
| XYZ-opp | Second-order | Opponent-only |
Table 6: Complex Markov sets used to stress test conditional generation. The sets separate the effect of joint-state representation from the effect of higher-order historical dependency.
Figure 21: Binary Markov versus non-Markov confusion matrices for the complex Markov sets. The matrices provide a class-level diagnostic of whether the model identifies Markovian behavior.
Figure 22: Full identity confusion matrices for the complex Markov sets. These matrices show exact player-level attribution errors and complement the binary Markov versus non-Markov view.
Figure 23: Cumulative CE and MSE over generated windows. Distributional drift can reflect changes in state visitation or trajectory-level marginal distributions, even when strict rule following remains stable.
Figure 24: Cumulative generation dynamics over generated windows. Panel (a) reports cumulative strict-rule dynamics, showing that rule-following behavior is largely determined early in the generated trajectory. Panel (b) reports cumulative rule-overlap dynamics, which captures local rule-component similarity and should be interpreted separately from strict rule execution.
Figure 25: Rule-level overlap and strict-match breakdown. The comparison shows that local rule overlap can remain high even when exact rule execution is substantially lower.
| Model | Exp1 Acc. | Exp2 Acc. | Significant? | ||
|---|---|---|---|---|---|
| DeepSeek-Chat | 0.21 | 0.18 | 0.56 | 0.576 | No |
| DeepSeek-Reasoner | 0.75 | 0.78 | -0.53 | 0.600 | No |
| GPT-5 | 0.67 | 0.56 | 1.67 | 0.096 | No |
| GPT-5-mini | 0.23 | 0.26 | -0.52 | 0.607 | No |
Table 7: Two-proportion z-test comparing recognition accuracy between Exp1 and Exp2.
Figure 26: Cross-entropy as n-gram order increases, using prefix length 2048. Lower values indicate better generation quality under the true n-gram process. The results show that raw generation quality deteriorates at higher order, especially at .
Figure 27: Entropy gap as n-gram order increases, using prefix length 2048. Lower values indicate closer stochasticity to the true n-gram process. Higher-order processes lead to larger stochasticity mismatch.
Figure 28: Valid completion rates across n-gram orders, prompting settings, models, and prefix lengths. This figure serves as a sanity check for whether metric differences are driven by invalid completions.
Figure 29: Degeneration diagnostics for the prefix-only setting with prefix length 2048. Unique n-gram ratios and maximum periodicity measure whether high-order generation leads to repetition, periodicity, or diversity collapse.
Figure 30: Detailed rule-access effects by model and prefix length. Values show rule-and-probs minus prefix-only differences. Explicit rule access does not consistently improve CE or CCLG, suggesting that high-order failure is not only a rule-inference problem.
Figure 31: Detailed prefix-length effects by model. Values show long-prefix minus short-prefix differences. Longer prefixes do not consistently improve CE or CCLG, especially at higher n-gram orders.
Figure 32: Effects of explicit rule access and longer prefix evidence. Negative values in CE(rule) - CE(prefix) indicate that providing the rule lowers CE, while positive values in CCLG(2048) - CCLG(256) indicate benefit from a longer prefix. The effects are inconsistent across models and n-gram orders, showing that explicit rules and longer prefixes do not reliably solve high-order dependency.
Figure 33: Prefix-only empirical n-gram MLE baseline under the rule-and-probabilities setting, evaluated by weighted JS divergence. The baseline uses only the observed prefix and remains competitive with or better than LLM generations, especially at higher orders.
Figure 34: Prefix-only empirical n-gram MLE baseline under the rule-and-probabilities setting, evaluated by context-conditioned likelihood gain. LLMs can benefit from low-order context, but this benefit often collapses at order 8, while the empirical n-gram baseline remains comparatively stable.
More in this topic
Language Model Generation Evaluation
Language model generation evaluation measures the quality, reliability, diversity, and task fit of outputs produced by language models.
See all 384 papers