Skip to content

MATA: A Trainable Hierarchical Automaton System for Multi-Agent Visual Reasoning

🕒 Published (v1): 2026-01-01 · Source: ICLR · Venue: ICLR 2026 · link

Why this paper was selected

ICLR 2026; MATA: trainable hierarchical automaton for multi-agent visual reasoning

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

MATA organizes multi-agent visual reasoning as a hierarchical finite-state automaton (Mealy machine) where a trainable LLM-based "hyper agent" learns the cross-agent transition policy, replacing brittle hand-written routing rules. Three specialized agents (fast perception, one-shot reasoning, stepwise reasoning) act as automaton states and share append-only memory; the hyper agent is fine-tuned on MATA-SFT-90K, a 90K-example dataset derived from transition-trajectory tree search. MATA achieves state-of-the-art results on GQA and other visual reasoning benchmarks, outperforming both prior compositional systems and competitive monolithic VLMs.

Problem

Compositional and agentic visual reasoning systems either (a) use a single agent insufficient for diverse reasoning demands, or (b) organize multiple agents in hand-coded pipelines that propagate upstream errors, cannot redirect on failure, and cannot reason about functionally overlapping ("competitive") agents where the selection criterion is ambiguous and task-dependent. Prior automaton-based work (NAVER/Cai et al. 2025) relies on manually written transition rules that break as the agent set grows.

Method

MATA is formalized as a Mealy machine \(M_\theta = (S, S_0, \Sigma, \Lambda, \delta_\theta, \Gamma)\) with: - Hyper automaton states: \(S_\text{agent} = \{\texttt{ONESHOT}, \texttt{STEPWISE}, \texttt{SPECIALIZED}\}\) plus lifecycle states \(\{\texttt{INITIAL}, \texttt{FINAL}, \texttt{FAILURE}\}\). - Learned transition \(\delta_\theta\): a fine-tuned Qwen3 (4B) LLM reads a textual snapshot of shared memory \(m_t\) and predicts \(s_{t+1} \in S\) by emitting a <NextState> tag; execution step: \(s_{t+1} = \delta_\theta(s_t, m_t)\). - Sub-automata: each agent state executes a small rule-based sub-automaton (LLM prompting, code generation/execution, verification, error correction) before returning control to the hyper agent. - Shared memory: append-only store \(m_{t+1} = m_t \cup \Delta m_t\) accumulating perception results, program history, verifier feedback, and task metadata — auditable by design. - Dataset generation (MATA-SFT-90K): for each image-query pair \((v,q)\), a bounded transition-trajectory tree \(\mathcal{T}(v,q)\) is expanded to depth \(T\) by branching over all next-state candidates. Leaf nodes are scored by task metric (IoU for visual grounding, Acc for VQA). Node values propagate bottom-up: \(V(s) = \max_{s' \in \text{Child}(s)} V(s')\). Optimal labels are \(s^*_t \in \arg\max_{s \in \text{Child}(s_t)} V(s)\), producing \((x_i, s^*_i)\) pairs. SFT of the hyper agent uses AdamW with cosine decay, 5% warm-up, batch size 64, 8 epochs on \(N=90{,}854\) examples from GQA, OK-VQA, and RefCOCO variants.

Key Contributions

  • Hierarchical deterministic FSA system (MATA) unifying neuro-symbolic compositional reasoning with collaborative (context-sharing across agents) and competitive (functionally overlapping agents vying on the same subtask) multi-agent design.
  • Trainable hyper agent as the inter-agent transition policy \(\delta_\theta\), keeping intra-agent micro-steps rule-based.
  • MATA-SFT-90K: a 90,854-example SFT dataset built via transition-trajectory tree expansion and bottom-up value propagation.
  • Three evaluation configurations: domain-specific, domain-transfer, and general (jointly trained).

Results

  • GQA (compositional VQA): MATA General 64.9%, Domain-Specific 64.7% vs. HYDRA 52.8%, ViperGPT 37.9%, VisRep 51.4%, GPT-4o 58.5%, InternVL3.5 63.8%, InternVL3 62.4%.
  • MATA surpasses all listed prior compositional methods (training-required and training-free) on GQA.
  • MATA is competitive with or exceeds strong monolithic VLMs (Qwen2.5-VL 62.4%, InternVL2.5 61.5%, InternVL3.5 63.8%) while being interpretable.
  • The paper reports SOTA across multiple benchmarks (OK-VQA, RefCOCO/+/g, Ref-Adv); full tables are not included in the provided excerpt.

Limitations

  • Near-exhaustive trajectory tree expansion for dataset generation is only tractable at the current three-agent scale; the branching factor grows exponentially with additional agents.
  • Domain-transfer evaluation is scoped to the hyper agent's transition policy only — sub-agents are not retrained for new domains.
  • Hard step cap \(T=15\) may terminate complex reasoning episodes prematurely.
  • SFT on greedy-optimal trajectories does not explore suboptimal paths, which could limit robustness to out-of-distribution transitions.

Relevance to Agentic AI / LLM Agents

MATA is a direct contribution to the problem of learned meta-control in multi-agent systems: rather than hard-coding which agent handles which subtask, it trains a lightweight LLM orchestrator to route dynamically based on accumulated execution history. The transition-trajectory tree approach — expand all branches, score leaves, propagate values, SFT on optimal decisions — is a generalizable recipe for training agent routers without end-to-end RL. The explicit support for competitive agents (multiple agents capable of the same subtask, with the meta-controller choosing based on past failure) addresses a genuine gap in prior orchestration literature, which almost exclusively assigns disjoint roles. The shared append-only memory as a universal context substrate for multi-agent coordination is an architectural pattern directly applicable to broader agentic pipelines.