Technical Summary: Opti-Q: A Constraint-Based Optimization Framework for Multi-LLM Question Planning

1. Problem Statement

The deployment of Large Language Models (LLMs) for Question Answering (QA) faces significant challenges regarding nondeterminism, heterogeneous resource profiles (financial cost, latency, energy), and varying performance across different question types. While recent work suggests that coordinated multi-LLM collaboration can outperform single "best" models, naive execution strategies (e.g., always querying all models or using fixed cascades) often lead to inefficient resource usage, higher costs, and suboptimal answer quality.

Current orchestration frameworks (e.g., LangChain, DSPy) often rely on developer-scripted workflows or dynamic, myopic decisions made at execution time without considering downstream consequences. There is a lack of systems that treat multi-LLM orchestration as a cost-based, multi-objective query planning problem where the optimal execution plan (sequential, parallel, or hybrid) is selected before execution based on user-specified constraints (budget, latency, energy) and desired answer quality (QoA).

2. Methodology: The OPTI-Q Framework

OPTI-Q is a database-inspired, cost-based optimizer that implements a "plan-before-execute" paradigm for multi-LLM QA. It models the problem as a Multi-Objective Optimization (MOO) task where the goal is to find Pareto-optimal plans balancing QoA against financial cost, latency, and energy.

A. Modeling and Formalization

• Question Model: A question $Q$ is defined by a prompt, topic, and user constraints ($F_{max}, L_{max}, E_{max}, QoA_{min}$) and a weight vector $W$ for objective prioritization.
• Plan Model: Plans are represented as Directed Acyclic Graphs (DAGs) where nodes are LLM invocations (physical operators) and edges represent data flow.
  • Sequential Operators: Pass intermediate answers as context to subsequent models.
  • Parallel Operators: Run multiple models concurrently.
  • Blending Operators: Merge outputs from parallel branches using a dedicated "blender" model.
• Optimization Goal: Maximize $[QoA(\pi), -Financial(\pi), -Latency(\pi), -Energy(\pi)]$ subject to user constraints.

B. Core Components

1. PERFDB (Statistics Catalog):

   • A performance database populated offline and incrementally from benchmarks and execution traces.
   • Stores statistics (QoA, cost, latency, energy) for individual LLMs and composed subplans, keyed by execution context (topic, operator type, model).
   • Enables pre-execution estimation of plan metrics without running the plan. It handles stochasticity by storing variance estimates and confidence intervals.

2. Cost-Benefit Estimation:

   • Token Estimation: Predicts input/output token counts based on model-specific tokenizers and historical output lengths to estimate costs.
   • QoA Estimation: Uses a topic-conditioned lookup in PERFDB. For composed plans, it applies multiplicative relative-effect factors (for sequential steps) and averaging relative-change factors (for blending) derived from historical traces to estimate the quality of the full plan.
   • Resource Estimation: Calculates financial cost (fixed + variable per token), energy (proportional to tokens), and latency (linear with token volume, parallel branches take the max time).

3. Plan Generation and Search:

   • Encoding: Plans are encoded compactly as a connectivity map (adjacency matrix) and a model assignment vector.
   • Search Space: The space of possible plans is combinatorial and NP-hard to optimize exhaustively.
   • Optimization Engines: OPTI-Q supports a "pluggable" engine with three strategies:
     • Dynamic Programming (DP): Exact solver for small instances; uses pruning to manage state-space explosion.
     • Hill Climbing (HC): Lightweight greedy heuristic for fast, local search.
     • NSGA-II: A multi-objective evolutionary algorithm used as the default for large plan spaces to approximate the Pareto frontier.
   • Selection: The optimizer generates a set of non-dominated feasible plans. The final plan is selected based on user weights $W$ applied to normalized objectives.

C. Implementation

• System: Modular framework integrating an optimizer with an execution engine.
• Models: Tested with five open-source models (Gemma-3:27B, LLaMA3-ChatQA, Qwen2.5, Phi-4, Mistral) running locally via Ollama.
• Blending: Uses Gemma-3:27B as the designated blender, outperforming specialized components like GenFuser in validation.
• Prompting: Employs Zero-Shot prompting with specific context and blending prompts to guide model behavior.

3. Key Contributions

1. Cost/Benefit Formulation: A formalization of multi-LLM QA planning as a constrained multi-objective optimization problem, explicitly balancing QoA, cost, latency, and energy.
2. Statistics-Driven Optimizer: A system that enumerates and prunes sequential/parallel/hybrid workflows, estimating quality and resource costs prior to execution using a historical statistics catalog (PERFDB).
3. Integrated System: A working prototype that dynamically routes questions across open-source LLMs, selecting optimal execution graphs in real-time.

4. Experimental Results

The framework was evaluated on MMLU-Pro (multiple-choice) and SimpleQA (open-ended) benchmarks against four state-of-the-art baselines (ThriftLLM, LLM-Ensemble, FrugalGPT, LLM-Blender).

• Performance Gains: Under user-specified budgets, OPTI-Q improved average QoA by ≈58% on SimpleQA and ≈41% on MMLU-Pro compared to the strongest budget-aware baselines at matched per-question costs.
• Scalability: NSGA-II provided the best scalability-quality trade-off, maintaining near-reference Pareto frontier quality with planning times in the low tens of seconds (e.g., 21s for $k=5$ operations).
• Robustness to Data Scarcity: In "cold-start" scenarios (Level 0 PERFDB coverage), OPTI-Q still outperformed baselines. As historical data increased (Levels 1–4), QoA improved significantly (e.g., +66.7% on MMLU-Pro), and resource estimation errors decreased sharply.
• Budget Adherence: The system maintained high budget adherence (88–96%), with overruns primarily driven by cost rather than latency.
• Comparison to Commercial APIs: OPTI-Q achieved higher QoA than commercial models (e.g., Claude Opus 4.6, GPT 5.4) on SimpleQA while costing significantly less (37.8× and 14.5× less, respectively, when accounting for external server costs). On MMLU-Pro, it achieved competitive quality (0.82 vs. 0.871 for Gemini 3.5 Flash) at a fraction of the cost.

5. Significance and Claims

The paper claims that database-style planning yields better quality–resource trade-offs for multi-LLM QA compared to dynamic, myopic orchestration or fixed ensembles.

• Paradigm Shift: It demonstrates that treating LLM orchestration as a declarative query planning problem, rather than a procedural scripting task, allows for dynamic, question-specific adaptation that maximizes utility under constraints.
• Practical Viability: The results suggest that structured, statistics-driven planning provides a practical foundation for adaptive LLM orchestration, enabling systems to balance performance and efficiency without relying on expensive, high-capability commercial APIs.
• Future Potential: The authors posit that this "plan-before-execute" abstraction can extend beyond QA to richer Retrieval-Augmented Generation (RAG) and agentic workflows, provided new operators can be characterized with similar cost-benefit profiles in the statistics catalog.