A 3D Characterization Framework for Intelligent Sequential Decision Making

Sadig Gojayev; Carolina Fortuna

cs.AIOct 8, 2026

A 3D Characterization Framework for Intelligent Sequential Decision Making

Authors: Sadig Gojayev, Carolina Fortuna

Organizations: Department of Communication Systems, Jožef Stefan Institute, SI-1000 Ljubljana, Slovenia

Abstract

Puzzles are widely used to evaluate the reasoning capabilities of artificial intelligence (AI) systems for sequential decision making, yet approaches originating from different paradigms are rarely compared under unified conditions. To address this gap, we introduce a three-dimensional characterization framework that enables the analysts of AI methods by 1) projecting them to the Markov decision process (MDP) sequential decision making formalism, 2) degree of autonomy through human prior ranking of their designs and, 3) skill and computational cost. Using this framework, we analyze how representative graph-based, reinforcement learning, and large language model (LLM)-based approaches differ in their design choices and performance characteristics, instantiated respectively by Neurosolver, forward-backward reinforcement learning (FBRL), and automated thought-of-search (AutoToS), including a double-agent extension of thought-of-search (DA-ToS). The analysis relies on the Tower of Hanoi puzzle that provides a controlled benchmark with well-defined rules and scalable complexity, enabling consistent comparison across increasing problem sizes. The 3D characterization reveals that LLM-based methods, due to their weakly constrained action-space design, shift complexity from architecture to inference-time verification, leading to substantially higher memory and runtime costs than Neurosolver and FBRL.

Figures & tables

Panel of Figure 1 — Fig. 1 : toh for $n=2$ disks and $p=3$ pegs.

State space representation refers to how the mdp state space $S$ is specified in the sense of mdp . The levels of human prior are defined as follows:
High	Humans explicitly design the state representation, fully specifying its structure and semantics, as in symbolic planners based on PDDL [ 27 ] .
Medium	Humans prescribe a high-level representational structure or template, while allowing the system to learn internal parameters or details, as in logical neural networks or partially structured encodings [ 17 ] .
Low	No explicit representational structure is imposed by humans; the model learns state representations end-to-end from interaction or data, as in fully end-to-end reinforcement learning systems trained via self-play [ 28 ] .
Mechanism refers to the algorithmic structure responsible for reasoning and inference. The levels of human prior are defined as follows:
High	Humans design the inference procedure, such as logical rules or search heuristics.
Medium	Humans select the general type of mechanism to employ, while the algorithm handles the details; for example, in Value Iteration Networks [ 29 ] , humans prescribe a value-iteration–based planning structure, while the network learns the reward and transition representations end-to-end.

TABLE I : Levels of Human Prior in Architecture Design.

Knowledge Input concerns how training data, constraints, or reward structures are introduced, directly shaping the transition function $T$ and reward function $R$ in mdp formulation.
High	Humans explicitly specify the training data, define relevant constraints, and design or shape reward structures, fully guiding how the model learns from examples, as in reinforcement learning with human-structured environments and hand-crafted training scenarios (e.g., Q-learning with expert-designed tasks).
Medium	Humans provide curated or loosely structured data without fully specified objectives, allowing the system to organize patterns and infer useful structure while still retaining partial human guidance, such as transformers trained on human-curated datasets.
Low	The model autonomously extracts training signals from large-scale interaction or self-generated experience, with minimal human specification beyond initial setup, as in self-supervised pretraining of large language models on unlabeled data [ 30 ] .
Learning reflects how the model updates its parameters in response to the training signal and the extent of human involvement in this process.
High	Humans explicitly shape the optimization process through curated objectives, staged training procedures, or tightly controlled learning phases, as in reinforcement learning from human feedback (RLHF) for large language models.
Medium	Humans specify general optimization settings—such as learning rates, network architectures, or update rules—while the system autonomously manages the internal learning dynamics, as in Double Deep Q-Networks (DDQN) [ 31 ] .

TABLE II : Levels of Human Prior at Training Stage.

Guidance captures the extent to which humans specify task details or constrain model behavior at runtime.
High	Humans provide detailed task instructions, including explicit constraints, edge cases, and step-level guidance, often through fully specified prompts or rule descriptions, as in Least-to-Most prompting techniques [ 32 ] .
Medium	Humans specify high-level task constraints or goals without defining the complete execution structure, such as providing domain rules (e.g., “a smaller disk cannot be placed beneath a larger one” in toh ) while leaving reasoning to the model.
Low	Humans provide only minimal task information—such as specifying the start and goal states in graph-based solvers—while the system autonomously determines the reasoning process and action sequence.
Decision describes how actions or outputs are selected by the system during inference and the extent of human involvement in this process.
High	Humans explicitly drive or supervise the decision-making process, often through interactive or step-wise instructions. The model depends on human-provided reasoning steps, clarifications, or corrective feedback to determine each action, as in interactive planning with large language models (e.g., DEPS) [ 33 ] .
Medium	Humans specify the decision framework or evaluation criteria—such as accuracy thresholds, selection rules, or preferred heuristics—while the system autonomously executes decisions within these constraints, as in safe reinforcement learning approach in constrained mdp [ 34 ] .

TABLE III : Levels of Human Prior at Inference Stage.

Model	State (S)	Action (A)	Transition (T)	Reward (R)	Goal (G)
datos	$\langle$ task prompt, code $c$ , generated feedback $F(c,e)$ (token sequences)	Invoke coding or repair LLM once	Probabilistic token generation: $P(y_{t+1:t+m}\mid x_{1:t})$	1 = working code, 0 = non-working code	Verified succ and isgoal functions
autotos [ 23 ]	$\langle$ task prompt, function, verifier feedback $\rangle$ (token prefixes)	Single LLM generation step	Probabilistic token generation: $P(y_{t+1:t+m}\mid x_{1:t})$	1 = working code, 0 = non-working code	Verified succ and isgoal functions
Neurosolver [ 18 ]	$s\in\{1,2,3\}^{n}$ (symbolic disk–peg assignments)	Legal disk moves	Deterministic: $s^{\prime}=T(s,a)$ , guided by goal-conditioned value signal	Goal reward; penalties for illegal or redundant moves	All disks stacked on target peg (optimal $2^{n}-1$ steps)
FBRL [ 16 ]	Bit string (disk positions)	Valid disk moves (bit changes)	Deterministic: $Q(s_{t},A_{t})\approx\mathbb{E}[R+\gamma\max Q(s_{t+1},A)]$	+1 valid, -1 invalid, +10 for goal	Bit string for disks on Peg C (binary pattern)

TABLE IV : Comparison of selected ToH models in terms of their State, Action, Transition, Reward, and Goal Representations.

Fig. 3 : LLM-based Agents Projection to MDP.

Method	Model	Architecture		Training		Inference
		Representation	Mechanism	Knowledge	Learning	Guidance	Decision	Validation
datos	DeepSeek + Mistral			High	High
	DeepSeek + Gemma	Medium	High	Medium	Medium	Medium	Low	Medium
autotos [ 23 ]	DeepSeek			High	High
	Qwen			Medium	Medium
	Yi	Medium	High	Medium	Medium	High	Low	Medium

TABLE V : Human Prior ranking across Architecture, Training, and Inference Stages.

Model Setup	Disk	Att. / Steps	Tokens	Time (s)	Total E.Mem (MB)	Total O.Mem (MB)
datos
DeepSeek + Gemma	$n$	$6.8\pm 1.5$	$17998.2\pm 3552.5$	$209.21\pm 47.84$	$1.82\times 10^{4}$	$1.55\times 10^{4}\pm 0$
DeepSeek + Mistral	$n$	$5.0\pm 1.5$	$6718.4\pm 1571.0$	$32.69\pm 10.37$	$1.55\times 10^{4}$	$1.43\times 10^{4}\pm 0$
autotos [ 23 ]
DeepSeek	$n$	$4.2\pm 1.0$	$5257.5\pm 975.0$	$23.61\pm 8.80$	$1.40\times 10^{4}$	$1.16\times 10^{4}\pm 0$
Yi	$n$	$2.0\pm 0.0$	$1162.3\pm 64.5$	$26.37\pm 5.06$	$5.47\times 10^{3}$	$6.16\times 10^{3}\pm 0$

TABLE VI : Comprehensive Performance and Memory Comparison across datos , autotos , FBRL, and Neurosolver. All values are reported as mean

\pm

MAD ∗ .

Explore similar work

May 7, 2026cs.AI

Agentick: A Unified Benchmark for General Sequential Decision-Making Agents

AI agent research spans a wide spectrum: from RL agents that learn from scratch to foundation model agents that leverage pre-trained knowledge, yet no unified benchmark enables fair comparison across these approaches. We present Agentick, a benchmark for sequential decision-making agents designed to evaluate RL, LLM, VLM, hybrid, and human agents on common ground and to power research on the fundamental challenges of sequential decision-making. Agentick provides 37 procedurally generated tasks across six capability categories, four difficulty levels, and five observation modalities, all exposed through a single Gymnasium-compatible interface. The benchmark ships with a Coding API, oracle reference policies for all tasks, pre-built SFT datasets, a composable agent harness, and a live leaderboard. An evaluation spanning 27 configurations and over 90,000 episodes reveals that no single approach dominates: GPT-5 mini leads overall at 0.309 oracle-normalized score while PPO dominates planning and multi-agent tasks; the reasoning harness multiplies LLM performance by 3-10x; and ASCII observations consistently outperform natural language. These findings highlight the substantial room for improvement that remains across all agent paradigms. Agentick's capability-decomposed, multi-modal design provides the empirical infrastructure needed to drive progress toward general autonomous agents, both as an evaluation framework and as a training ground for RL post-training of foundation models in truly sequential environments.

Roger Creus Castanyer, Pablo Samuel Castro, Glen Berseth

Mila Quebec AI Institute · Université de Montréal · Mila Quebec AI Institute Université de Montréal +1

AI Agent Evaluation AI Agent Benchmarks

Ask PDF

Sep 17, 2026cs.CL

PetriBench: Benchmarking LLM Reasoning over Dynamic State Spaces

Characterizing LLM reasoning remains an open challenge, as many existing benchmarks isolate specific reasoning skills, rely on external knowledge, or are costly to extend. We introduce PetriBench, a compact, fully self-contained, and scalable benchmark for evaluating LLM reasoning over dynamic state spaces using Petri nets, a mature formalism for modeling real-world concurrent and distributed systems. PetriBench organizes reasoning into four task families varying by scope and temporal horizon, with Easy, Medium, and Hard levels generated by increasing structural complexity and evaluated against exact ground truth. Across a diverse set of proprietary and open-weight models, accuracy decreases consistently with difficulty, while harder instances expose increasingly distinct task-specific capability profiles. Additional analyses show that test-time compute improves performance but interacts differently with different reasoning tasks, and that procedural generation yields smooth scaling with structural complexity. Together, these results show that PetriBench provides a unified and extensible setting for probing the strengths, limits, and scaling behavior of LLM reasoning.

Pyrros Koussios, Benjamin Jäger, John Hua Yao +3

ETH Zürich · Stanford University

LLM Evaluation Temporal Reasoning in Language Models

Ask PDF

May 27, 2026cs.AI

Tree of Thoughts as a Classical Heuristic Search Problem: Formal Foundations and Design Patterns

Large Language Models (LLMs) have demonstrated remarkable reasoning capabilities, yet their standard generation process -- auto-regressive token prediction -- is inherently myopic and prone to cascading errors. To address this, the Tree-of-Thoughts (ToT) framework creates a search space over intermediate reasoning steps, allowing search models to explore, look ahead, and backtrack. However, current ToT research remains fragmented across Natural Language Processing and Automated Planning communities, often using inconsistent terminology and ad-hoc implementations. Consequently, we synthesize the ToT landscape through a unified taxonomy based on classical heuristic search terminology. We map LLM-based reasoning to classical search components: state representation (granularity of thoughts), successor generation (prompting operators), and heuristic evaluation (self-assessment of progress). We analyze existing work within the context of our taxonomy and identify emerging design patterns: systematic search (Best-First Search) for shallow, deterministic tasks and lookahead-heavy strategies (DFS, MCTS) for deep multi-step reasoning. We conclude by identifying open algorithmic challenges at the intersection of heuristic search and LLM reasoning, and call on the heuristic search community to engage with this emerging domain.

Guni Sharon

Texas A&M University

Inference-Time Search Tree of Thoughts LLM Reasoning

Ask PDF