Introduction

OPTiMACS (Optimal Parsing Techniques in Message-Aware Computational Structures) is a framework designed to learn the optimal format for passing queries to an LLM, tailored to different tasks. This blog introduces the framework, its key design choices, the reasoning behind them, and some preliminary results. Broadly, OPTiMACS consists of a Task Predictor and a Format Selector. It maintains internal states which are updated using data samples, and these learned states are then used for inference.

Figure 1: The OPTiMACS Framework Architecture

Motivation (why bother!!):

Why Alternative Format?

There are a couple of issues with using Natural Language as the format to encode information to Natural Language.

1. Efficient Token Usage: Natural Language is often verbose. Structured formats strip away conversational "fluff", leading to significant gains in efficiency. Studies have shown up to a 72.7% reduction in token usage [1] in multi-agent systems without sacrificing task success. Formats like TOON (Token-Oriented Object Notation) [17] and POML (Prompt-Optimisation-Markup-Language) [18] are designed for this purpose. (though we limit the results to show a boost in accuracy but rewards on OPTiMACs could be set up to show boost in accuracy and efficiency both.)
2. Reduced Ambiguity: Natural Language is inherently ambiguous (e.g. complex temporal dependencies). Alternative formats can eliminate this ambiguity (e.g., using (E1 < E2 < E3) instead of a long sentence) [1], forcing the model to be precise and mitigating format biases.
3. Enhanced Reasoning: Switching to formats like Code or Logic activates different internal circuits ("inductive biases") better suited for rigorous logic. This can lead to a 3% to 5% improvement in reasoning performance [1]. This parallels the success of frameworks like Chain-of-Thought (CoT) [11], Program of Thoughts (PoT) [12], Tree of Thoughts (ToT) [15], and Graph of Thoughts (GoT) [16].
4. Machine Parsability: In agentic workflows, the output of one agent is the input for another. Structured formats (like JSON) ensure deterministic ingestion, reducing error propagation compared to parsing free-form natural language [1].

Why Use an Adaptive Framework?

Even if we use alternative formats for some tasks, why do we need an entirely new format-finding framework that is theoretically sound and backed by insights?

1. Limited Studies: Current studies are limited to A/B testing using a fixed "bag of formats." They do not discover optimal clusters (tasks) for specialized datasets. Existing research often tests a limited set of 20-30 common formats without providing deeper insights (e.g., if code works better, is it Python or JavaScript? Monolithic or modular?).
2. Out-Of-Domain Generalization: OOD generalization is challenging for these studies. If new data types arrive (e.g., data drift or mode drift), existing static findings may not generalize. Furthermore, existing studies often rely on open-source datasets, making it a hassle to find optimal formats for domain-specific private data.
3. Multi-Agent Complexity: The multi-agent setting is hard to optimize because using Format 1 might lead to a different state compared to Format 2. We need a way to model this interaction and derive optimal strategies for resolving multi-agent communication issues.
4. Fragmented Literature: While alternative formats exist, current studies often rely on narrow, ad-hoc selections of representations, failing to provide a unified theory.
5. Agentic Scaffolding: Existing methods often overlook multi-agent complexities like scaffolding considerations, which are crucial for complex workflows.
6. Lack of Theoretical Grounding: There is a lack of a theoretically grounded framework for efficient format discovery, which we aim to address.

Why OPTiMACS?

Since LLMs are capable of evolution and learning, couldn't we simply ask them to find optimal formats for us? Why do we need a theoretically grounded framework?

1. LLMs might have an internal preference for certain formats, but those preferences may not be optimal for the specific tasks in reality.
2. When performing empirical evaluation, we need a theoretically backed framework to validate results, especially in complex multi-agent settings.

We devise OPTiMACS as a theoretically grounded framework to address these limitations. It identifies optimal formats for tasks in a multi-agent setting using a novel EMDP formulation. We demonstrate the framework's effectiveness on simple datasets and systematically build the concepts from basic A/B Testing to the current EMDP formulation, highlighting its relationship with Contextual Bandits and justifying the need for this unified framework.

Solution (what are we trying to do):

Before diving deeper into theoretical formulations, let's first understand the problem we are trying to solve and some technical terms.

Preliminaries

We introduce the key concepts used in our framework:

• Policy (π): A strategy mapping states (contexts) to actions (decisions), denoted as π(a|s).
• Contextual Bandits: A simplified reinforcement learning setting where an agent observes a context, selects an action, and receives an immediate reward, without state transitions. We use this for single-step prompting.
• Markov Decision Processes (MDPs): A framework for sequential decision-making characterized by states, actions, transitions, rewards, and a discount factor. We employ this for multi-agent coordination where current decisions alter the dialogue trajectory.
• Off-Policy Learning: Learning the value of a target policy (optimal formats) while following a different behavior policy for exploration.

Problem Formulation

We now formulate the problem of optimal format selection. Below we motivate from simple solution to the final EMDP formulation, giving justification for various design choices along the way.

1. A/B Testing (Global Optimization):

   The simplest approach is to gather all possible formats and perform A/B testing to identify a single globally best format. However, this ignores instance-specific preferences (e.g., within the same dataset, "calculation" tasks might prefer code, while "algebra" tasks might prefer symbolic formats).

   Formulation: We seek a single format $f^*$ that maximizes expected reward across the entire dataset $D$:
   $f^* = \operatorname*{argmax}_{f \in \mathcal{F}} \mathbb{E}_{x \sim D} [R(x, f)]$

2. Contextual Bandits (Local Optimization):

   To address the limitations of A/B testing, we assign clusters to data points and learn optimal formats per cluster. We differentiate this from standard bandits by using:

   1. Tabular State-Action Space: for interpretable policy learning.
   2. Ensemble Exploration: exploring multiple strategies for each data point to accelerate learning.

   Formulation: We learn a policy $\pi(f|t)$ where $t$ is the task cluster. The optimal format $f_t^*$ for cluster $t$ is:
   $f_t^* = \operatorname*{argmax}_{f \in \mathcal{F}} Q(f, t)$
   where $Q(f, t)$ estimates the expected reward of using format $f$ for tasks in cluster $t$.

   Algorithm 1: OPTiMACS for 1-step LLM Call

   Input: Training Dataset $\mathcal{D}$ (Training) / Query $x$ (Inference)
   If Training:
     1. Task Selection: Cluster all $x_i \in \mathcal{D}$ into semantic tasks $\mathcal{T}$.
     2. Format Learning: For each $x_i \in \mathcal{D}$:
         $C \leftarrow \emptyset$  // Candidate set
         For each strategy $k \in \{1...K\}$:
             $c_k \leftarrow \text{Strategy}_k(x_i, t_i, Q)$
             $C \leftarrow C \cup \{c_k\}$
         For $f \in C$:
             $\hat{y} \leftarrow \text{LLM}(x_i, f)$, $r \leftarrow \text{Verify}(\hat{y}, y_i)$
             $Q(t_i, f) \leftarrow Q(t_i, f) + r$  // Update score
   Else (Inference):
     1. $t \leftarrow \text{ClassifyTask}(x)$
     2. Return $f^* = \operatorname*{argmax}_f Q(t, f)$
3. Markov Decision Process with Off-Policy Exploration (Multi-Agent Optimization):

   Contextual bandits work for 1-shot calls but fail in multi-agent settings due to:

   1. State Transitions: Unlike bandits where contexts are independent, agent actions (formats) fundamentally alter the dialogue trajectory and subsequent states.
   2. Delayed Rewards: The success of an interaction is often only observable at the end of a multi-turn conversation, exacerbating the credit assignment problem.
   3. Lack of Strategic Lookahead: Standard contextual bandits optimize myopically for the immediate step, failing to plan for long-term goal convergence essential in collaborative tasks.
   4. Combinatorial Explosion: The space of possible trajectories grows exponentially if we consider all strategies in parallel.

   Formulation: We model the multi-agent interaction as an MDP tuple $(\mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma)$:

   • $\mathcal{S}$: State space (conversation history).
   • $\mathcal{A}$: Action space (set of available formats $\mathcal{F}$).
   • $\mathcal{P}$: Transition probability $P(s'|s, f)$ of moving to state $s'$ given format $f$.
   • $\mathcal{R}$: Reward function $R(s, f)$.
   The goal is to find a policy $\pi^*$ maximizing cumulative reward: $\pi^* = \operatorname*{argmax}_\pi \mathbb{E}[\sum_{t=0}^T \gamma^t R(s_t, f_t)]$.

   Off-Policy Exploration: To efficiently explore the vast space of formats while learning, we employ a behavior policy $\mu$ different from the target policy $\pi^*$. The agent selects actions based on $\mu$, which is a weighted mixture of three components:
   $\mu(a|s) = w_Q \cdot \pi_{\text{greedy}}(a|s) + w_L \cdot \pi_{\text{learning}}(a|s) + w_D \cdot \pi_{\text{diversity}}(a|s)$
   where:

   • $\pi_{\text{greedy}}$: Exploits the best-known format.
   • $\pi_{\text{learning}}$: Explores promising but uncertain formats.
   • $\pi_{\text{diversity}}$: Ensures coverage of the search space.

4. Expanding Markov-Decision Process with Off-Policy Exploration (EMDP)

   To address this, we model the system as a Markov Decision Process (MDP), where task clusters serve as states to capture the evolving context. This allows optimizing for long-term expected returns. We mitigate the explosion of trajectories by using a weighted sampling of strategies.

   However, standard MDPs fail here because they assume a fixed universe of states and actions. In our setting, this assumption breaks due to:

   1. Evolving State-Action Spaces: Agents discover novel tasks and optimal formats online, so the set of possibilities is constantly growing.
   2. Non-Stationarity: The environment changes as the spaces expand, meaning old optimal strategies might become outdated.
   3. Latent State Uncertainty: Task categories are inferred rather than observed directly, creating a "partially observable" challenge (we don't know the exact state, only a probability).

   To resolve these, we propose the Expanding Markov Decision Process (EMDP). EMDP differs from a standard MDP by introducing two distinct phases:

   1. State-Action Expansion Phase: Agents actively discover novel tasks and optimal formats, expanding the known universe of states and actions.
   2. Convergence Phase: The system stabilizes into the standard MDP formulation as the state-action space fully forms and the optimal policy converges.

   This dual-phase approach allows OPTiMACS to handle the non-stationary and evolving nature of open-ended multi-agent interactions.

   Algorithm 2: OPTiMACS Algorithm

   Initialize: for all $s \in \mathcal{T}$, $a \in \mathcal{F}(s)$:
     $Q(s,a) \leftarrow$ arbitrary
     $C(s,a) \leftarrow 0$
     $\mu(a|s) \leftarrow w_Q \pi_Q(a|s) + w_L \pi_L(a|s) + w_D \pi_D(a|s)$ (behavior policy)
     $\pi(s) \leftarrow$ a deterministic policy that is greedy wrt $Q$
   
   Repeat until convergence or max iterations:
     $msg \leftarrow$ Sample from the set of queries/problems
     Generate Episode using behavior policy $\mu(a|s)$:
       Repeat until episode end:
         $\mathcal{T}_{t} \leftarrow \text{TaskCategorization}(msg, \text{context})$
         $\mathcal{F}_t \leftarrow \mu(T_{t}, \text{context})$
         $prompt \leftarrow \text{ApplyStructure}(msg, \mathcal{F}_t)$
         $msg, R_{t+1} \leftarrow \mathfrak{A}_t(prompt)$
         If Expansion Phase:
           $\mathcal{T} \leftarrow \mathcal{T} \cup \{\mathcal{T}_{t}\}$, $\mathcal{F} \leftarrow \mathcal{F} \cup \{F_t\}$
         End If
         $t \leftarrow t+1$
       Until Episode end
   
     $G \leftarrow 0$
     $W \leftarrow 1$
     For $t = T-1, T-2, \ldots$ down to $0$:
       $G \leftarrow \gamma G + R_{t+1}$
       $C(\mathcal{T}_t, \mathcal{F}_t) \leftarrow C(\mathcal{T}_t, \mathcal{F}_t) + W$
       $Q(\mathcal{T}_t, \mathcal{F}_t) \leftarrow Q(\mathcal{T}_t, \mathcal{F}_t) + \frac{W}{C(\mathcal{T}_t, \mathcal{F}_t)}[G - Q(\mathcal{T}_t, \mathcal{F}_t)]$
       $\pi(\mathcal{F}_t|\mathcal{T}_t) \leftarrow 1$ if $\mathcal{F}_t=\operatorname*{argmax}_a Q(\mathcal{T}_t, a)$ else $0$ (with ties broken arbitrarily)
       $W \leftarrow W \cdot \frac{\pi(\mathcal{F}_t|\mathcal{T}_t)}{\mu(\mathcal{F}_t|\mathcal{T}_t)}$
       If $W = 0$:
         Exit For Loop
       End If
     End For
   

OPTiMACS operates like a smart translator between agents. Instead of letting afgents chat in unstructured plain text, it intervenes to structure their messages into the most effective format (like JSON, XML, or even Python code) for the specific task at hand. It does this through a continuous learning process.

1. Task Classification (Understanding the Context)

First, when an agent wants to send a message, OPTiMACS analyzes it to understand the underlying Task. Using an internal LLM, it categorizes the message into semantic buckets (e.g., "Mathematical Reasoning", "Data Retrieval", "Code Generation").

Why? A format that works for writing a poem (Plain Text) is terrible for sorting a list of numbers (JSON/Python). Knowing the task is the first step to picking the right tool.

2. Format Selection (The "Policy")

Once the task is identified, the system needs to decide how to format the message. It uses a learned Policy to pick the best format from its library. But how does it know which one is best? It uses a mixture of three clever strategies:

1. Past Experience (Q-Learning): It looks at a "scoreboard" (Q-table) to see which formats have successfully solved this kind of task in the past. If "JSON" worked 90% of the time for "Data Retrieval", it picks that.
2. Smart Guessing (LLM Sampler): If it's unsure, it asks an LLM: "Given this message, what format would make it clearest?" This allows the system to discover completely new formats it hasn't seen before (Hard-Mining).
3. Trying New Things (Diversity): Occasionally, it deliberately tries a rare or unused format. This ensures it doesn't get stuck in a rut and keeps exploring potentially better options (Soft-Mining).

3. Evolving Over Time (Expansion & Convergence)

The system isn't static. It goes through two distinct phases:

• Expansion Phase: Early on, it's like a curious student. It actively invents new task categories and tries out wild new formats to see what works.
• Convergence Phase: Later, it acts like a seasoned expert. It stops experimenting and focuses on exploiting the best strategies it has found, locking in the most efficient communication protocols.

Experiments

We tested OPTiMACS on challenging datasets that require complex reasoning and coordination.

Datasets

• GSM+ (Mathematical Reasoning) [2]: A hard version of GSM8k where a team of 3 agents (Solver, Coder, Verifier) must collaborate to solve multistep math problems.
• Multi-Hop QA (Information Exchange): We used HotpotQA [3], WikiHopQA [5], and NarrativeQA [4]. Here, a 5-agent team holds different pieces of information (like a puzzle) and must communicate effectively to answer a complex question.

Dynamic Evolution (RQ5)

Does the system actually "learn"? Yes. The chart below shows how OPTiMACS discovers new formats rapidly during the Exploration Phase and then stabilizes as it identifies the optimal set during the Convergence Phase.

Baselines

We compared OPTiMACS against state-of-the-art approaches:

1. Vanilla MAS (Natural Language): Agents talk to each other in plain English, just like standard chatbots.
2. Autoform: A strong baseline where an LLM is asked to propose a static format upfront (e.g., "Always use JSON").
3. Fixed Formats: We also tested rigid formats like XML, YAML, and Python Code to see if one size fits all.

Research Questions

We aimed to answer three key questions:

• RQ1: Performance: Does learning a dynamic format actually lead to better answers?
• RQ2: Dynamic vs. Static: Is it better to adapt on the fly, or just pick one good format (like JSON) and stick to it?
• RQ3: Efficiency: Does adding structure make messages clearer and shorter (fewer tokens), or just add bloat?

Results

The results were clear: Adaptability wins. By learning the best format for each specific message, OPTiMACS outperformed both standard natural language and rigid, pre-defined formats.

1. Performance Gains (RQ1)

Across all datasets and models (including GPT-4o, o3, and Phi-4), OPTiMACS consistently achieved higher accuracy. For instance, with GPT-4o:

• GSM+ (Math): Improved from 86.5% (Vanilla) → 89.5% (OPTiMACS).
• HotpotQA: Improved from 65.1% → 69.1%.
• NarrativeQA: Saw a massive jump from 51.3% → 57.2%.

2. Dynamic vs. Static Formats (RQ2)

We found that no single format is perfect for everything. While JSON works well for data tasks, it failed in reasoning tasks where "Math" or "Code" formats excelled.

• Fixed JSON: averaged 52.7% accuracy across tasks.
• Fixed Code: averaged 58.1%.
• OPTiMACS (Dynamic): averaged 59.3%, beating every single fixed format strategy by adapting on the fly.

3. Efficiency & Discovery (RQ3)

Surprisingly, better performance didn't mean higher cost. In fact, structured messages were often more concise than chatty natural language.

• Token Usage: Reduced by 18.8% in HotpotQA and 8.7% in GSM+.
• New Formats: Over 50% of the formats OPTiMACS used were newly discovered during its Expansion Phase, proving that humans don't always know the best way to prompt a model – but the model can learn it.

Discussion

Why Formats Work

• Prompt Equalization: Formats help bring reasoning paths for similar data and contexts closer together, similar to how Chain-of-Thought [6] works.
• Ambiguity Minimization: Forcing structured schemas minimizes ambiguity and forces the model to attend to specific information that might otherwise be overlooked.

Insights

• LLMs often have non-obvious preferences. For example, for table tasks, column-oriented formats worked well; for SQL, specific schema constraints were effective.
• Models generally prefer compact structures over verbose natural language.
• There is significant "format bias" – variance in performance across different formats can be massive (up to 253%), highlighting the importance of selection.

Future Directions

• Exploring code-based formats (e.g., using Python for sorting vs Assembly for memory modeling).
• Investigating mixtures of formats for information segregation.
• Designing novel formats suited for specific purposes, such as token efficiency or context passing.

Limitations

A key key limitation is the dependency on the LLM's ability to follow format conversion instructions. Performance is bounded by how effectively the underlying model can adhere to the requested structure.

Conclusion

OPTiMACS provides a unified framework for learning optimal communication representations in both single-agent and multi-agent systems. By treating format selection as a learning problem, we bridge the gap between rigid protocols and ambiguous natural language.

Related Works

Recent studies have shown that specific structured representations often outperform natural language. However, relying on fixed formats can vary in effectiveness. Approaches like Autoform attempt to query LLMs for formats but can be inconsistent.

Our work differs from:

• Custom Infrastructure (MCP, FIPA-ACL [8]): Which provide candidates but not the intelligence to select them.
• Prompt Optimization (APE, OPRO): Which optimize semantics, whereas we optimize syntax (format).
• Reasoning Frameworks (CoT, PoT): Which structure reasoning logic; we optimize the message syntax within these steps.

Appendix: Theoretical Analysis

A.1 Justification for MDP (vs. Bandits)

We model multi-agent coordination as a Markov Decision Process (MDP) rather than the simpler Contextual Bandit framework used in single-agent prompting. The core reasons are:

• State Transitions: in multi-turn dialogue, a format choice (Action) fundamentally alters the conversation history (State). Bandits assume actions don't change the state.
• Long-Term Rewards: A "good" format might yield no immediate clarity but enable a solution 5 turns later. MDPs optimize for this cumulative return ($\sum \gamma^t R_t$), whereas bandits optimize only the immediate step.

A.2 Expanding MDP (EMDP) Convergence

A key theoretical challenge is that OPTiMACS constantly adds new formats, meaning the Action Space $\mathcal{A}$ is mathematically "expanding." Standard RL proofs assume fixed sets.

References