Beyond the Current Observation: Evaluating Multimodal Large Language Models in Controllable Non-Markov Games

The Hidden State Bottleneck in Multimodal Agents

As we push multimodal large language models (MLLMs) toward closed-loop autonomy—think robotic manipulation or multi-turn tool use—we are moving away from simple "look and answer" tasks. In these real-world scenarios, an agent must act based on observations that are no longer visible. This is the realm of Non-Markovian environments (settings where the current observation is insufficient for optimal action). In these regimes, the agent must reconstruct a "belief state" (an internal summary of hidden, task-relevant information) from its entire interaction history.

Currently, most benchmarks for multimodal agents fail to isolate this specific capability. Existing suites typically either expose the full state to the model, bundle memory with other confounding skills like rule discovery or exploration, or only test recall after an episode has finished. This is a "remember-to-answer" setting. This creates a blind spot. We might think a model is a great planner. However, it might actually just be failing to remember where it saw a specific object three turns ago.

A new paper introduces RNG-Bench (Reconstructive Non-Markov Games) to address this. By using controlled environments where the hidden state is explicitly measurable, the authors aim to disentangle whether a model is making bad decisions or simply suffering from catastrophic forgetting.

The failure of "Remember-to-Answer" benchmarks

The status quo in long-context and memory evaluation is fundamentally decoupled from action. Most benchmarks treat memory as a retrieval task. The model reads a transcript or a series of images and answers a question at the end. While this tests if information exists in the context window, it ignores the causal nature of interaction. In a true closed-loop system, a single recall error doesn't just result in a wrong answer. It results in a wrong action, which generates a new, potentially incorrect observation. This compounds the error throughout the episode.

Furthermore, existing agent suites bundle hidden information with complex tasks like free-form action formatting or environmental exploration. If a model fails to navigate a room, is it because it forgot the layout, or because it doesn't understand the movement commands? The authors argue that current benchmarks cannot answer this. As shown in, in a Markov game like Chess, the visible board is a sufficient statistic (the current state contains all necessary info) for the next move. In a Non-Markov game like Matching Pairs, the visible state is insufficient. The model must reconstruct the hidden state from history to act correctly.

Isolating belief-state tracking via RNG-Bench

To isolate the "remember-to-act" requirement, the authors developed RNG-Bench. It features two complementary games that stress different types of hidden states.

1. Matching Pairs: This game targets static, categorical memory. Cards are briefly revealed and then flipped face-down. The agent must remember the identity-location bindings to find matches. This isolates the ability to retain discrete, factual information.
2. 3D Maze: This game targets dynamic, spatial memory. The agent receives egocentric (first-person) views as it navigates a procedural maze. It must incrementally integrate these local views into a global spatial map (including topology, position, and orientation) to reach a goal.

The benchmark is built on a unified harness. It allows for controlled difficulty across three axes: grid/map size, visual pattern complexity, and observation modality (text, 2D patches, or 3D renderings). Crucially, the authors introduce the Memory Gap metric. They compare a model's performance against an "oracle" (a condition that injects the true hidden state at every step). This allows them to mathematically separate failures caused by poor decision-making from those caused by forgetting.

Performance collapses as the state scales

The results suggest that frontier MLLMs are hitting a significant wall regarding state maintenance. The paper reports that performance drops precipitously as the complexity of the hidden state increases. In Matching Pairs, the authors note that for Qwen3.5-397B, the score collapses from 90.6% on a 4×4 grid to a mere 0.7% on a 12×12 grid .

Similarly, in the 3D Maze, the Game Score (GS)—a metric combining success, efficiency, and exploration—for Qwen3.5-397B peaks at a 7×7 scale and then declines as the maze grows .

The Memory Gap analysis provides the "why." The authors find that for most models, the majority of residual errors stem from forgetting earlier observations rather than suboptimal planning. When external memory is provided—such as a memory map for cards or a minimap for the maze—performance improves. However, the recovery is uneven. In Matching Pairs, external memory roughly doubles the score for models like Kimi-K2.5. In the 3D Maze, it recovers a much smaller portion of the gap .

This indicates that spatial navigation involves a tighter coupling of memory and active planning.

Interestingly, the paper finds that visual recognition is a primary driver of this bottleneck. Even when the context window is theoretically large enough, switching from text-based observations to noisy image-based observations causes a massive performance degradation. This suggests that the "memory" problem in MLLMs is often a "perception-to-state" problem. The model fails to reliably bind visual identifiers into a stable internal representation that persists across turns.

What the benchmark leaves out

While RNG-Bench is a rigorous diagnostic tool, it has clear boundaries. First, it is limited to two specific game environments. While these are excellent for isolating state tracking, they may not capture the nuance of more complex, semantic-heavy environments.

Second, the Memory Gap metric is presented as a practical diagnostic rather than a perfect causal decomposition. It relies on an oracle injection. This assumes the model could act optimally if it knew the state. However, in highly complex or stochastic environments, the gap between "knowing the state" and "executing the optimal policy" might be much wider than this metric implies.

Finally, the study focuses on a single model family (Qwen3.5) for its fine-tuning demonstration. While the results show promising transfer to general multimodal benchmarks, we do not yet know if the "optimal-policy rollout" recipe scales efficiently across different architectures.

The verdict: Instrument your state-tracking

If you are building agents meant for long-horizon, closed-loop interaction, you should take this paper seriously. The core takeaway is that context length is a vanity metric if your visual backbone cannot maintain a stable belief state. The fact that stripping the textual action history from the prompt causes Matching Pairs performance to collapse by roughly 75% [Table 5] is telling. It proves that models are currently relying on the "log" of their own actions to compensate for weak internal state tracking.

Is this ready for your production pipeline? Not as a standalone evaluator, but as a diagnostic. If your agent is looping in a corner or repeating failed actions, don't just throw more tokens at the context window. Use the logic of RNG-Bench. Check if the failure is a lack of information (forgetting) or a lack of reasoning (planning). If it's forgetting, your path forward is likely better visual grounding or supervised fine-tuning on trajectory data, not just a larger KV cache.