PaperlayerView exact revision on arXiv

Source-linked AI summary

OptLLM: Optimal Assignment of Queries to Large Language Models

Yueyue Liu, Hongyu Zhang, Yuantian Miao, Van-Hoang Le, Zhiqiang Li

arXiv:2405.15130v1cs.SEcs.CLcs.LG

TL;DR

Because LLM services vary in cost and performance, choosing a model for each query involves balancing accuracy and expense. OptLLM predicts model performance and searches for non-dominated query assignments. Across varied tasks, it matches the best individual LLM’s accuracy at lower cost and improves on other multi-objective algorithms.

  • Problem

    Different LLMs have different costs and task performance, making it difficult to choose query assignments that balance accuracy and expense.

    Source: §I · p. 1

  • Method

    OptLLM predicts query-level LLM performance with uncertainty estimation, then iteratively uses destruction and reconstruction to generate non-dominated assignments.

    Source: 2) Robust-aware predicted accuracy in… · p. 4, 2) The heuristic search · p. 5

  • Results

    Across varied tasks, OptLLM matches the best individual LLM’s accuracy with 2.40%–49.18% lower cost, and improves accuracy by 2.94%–69.05% or saves 8.79%–95.87% in cost versus other multi-objective algorithms.

    Source: §I · p. 2

  • Takeaways & Limitations

    OptLLM offers users non-dominated query-assignment options spanning highest expected accuracy to lowest cost, selectable by budget and performance requirements.

    Source: §VIII · p. 10

Abstract

from arXiv · show

Large Language Models (LLMs) have garnered considerable attention owing to their remarkable capabilities, leading to an increasing number of companies offering LLMs as services. Different LLMs achieve different performance at different costs. A challenge for users lies in choosing the LLMs that best fit their needs, balancing cost and performance. In this paper, we propose a framework for addressing the cost-effective query allocation problem for LLMs. Given a set of input queries and candidate LLMs, our framework, named OptLLM, provides users with a range of optimal solutions to choose from, aligning with their budget constraints and performance preferences, including options for maximizing accuracy and minimizing cost. OptLLM predicts the performance of candidate LLMs on each query using a multi-label classification model with uncertainty estimation and then iteratively generates a set of non-dominated solutions by destructing and reconstructing the current solution. To evaluate the effectiveness of OptLLM, we conduct extensive experiments on various types of tasks, including text classification, question answering, sentiment analysis, reasoning, and log parsing. Our experimental results demonstrate that OptLLM substantially reduces costs by 2.40% to 49.18% while achieving the same accuracy as the best LLM. Compared to other multi-objective optimization algorithms, OptLLM improves accuracy by 2.94% to 69.05% at the same cost or saves costs by 8.79% and 95.87% while maintaining the highest attainable accuracy.

I. INTRODUCTION

Because LLM services differ in cost and performance, assigning each query to a suitable model is a cost–accuracy tradeoff. OptLLM predicts query-level performance and searches for non-dominated assignments, with experiments reporting lower costs and improved accuracy across tasks.

I. INTRODUCTION

  • LLM services have different pricing and performance, and larger models cost more without guaranteeing better results for every task.The paper notes that query volume can make LLM use costly, while smaller models may suit less complex tasks.Source: §I · p. 1
  • On log parsing, OptLLM reaches 71.69% accuracy at $3.27, versus Mixtral 8x7B’s 59.05% at $3.68.The figure compares OptLLM solutions with individual LLMs on this task.Source: §I · pp. 1–2, Figure 1 · p. 1
  • OptLLM frames query assignment as multi-objective optimization and combines performance prediction with iterative destruction and reconstruction to generate non-dominated solutions.The prediction component estimates whether candidate LLMs will process each query successfully; the optimization component searches for assignments balancing cost and accuracy.Source: §I · p. 2
  • Across general NLP and domain-specific tasks, OptLLM matches the best individual LLM’s accuracy with 2.40%–49.18% lower costs.Against other multi-objective algorithms, it improves accuracy by 2.94%–69.05% or saves 8.79%–95.87% in cost while maintaining each baseline’s highest attainable accuracy.Source: §I · p. 2

A. Large Language Model and Its Application

  • The paper covers general NLP tasks such as text classification and domain-specific log parsing, which replaces changing log variables with placeholders.Its text-classification example assigns a news headline to one of four categories.Source: A. Large Language Model and Its… · p. 2

B. Multi-objective Optimization

The paper formulates query assignment as a multi-objective problem: maximize accuracy while minimizing API cost. It defines the assignment variables and constraints so that each query is allocated to one LLM.

B. Multi-objective Optimization

  • A multi-objective optimization problem seeks tradeoffs among conflicting objectives; here the objectives are to maximize correctly processed queries and minimize total API cost.The goal is to offer a set of cost-effective, high-performing solutions across general NLP and domain-specific tasks.Source: B. Multi-objective Optimization · pp. 2–3, A. Problem Scope · p. 3

B. Problem Formulation

  • The formulation represents each query by its token count and each candidate LLM by its per-token price, determining query-model cost.The assignment variable is binary, indicating whether query i is assigned to model k.Source: B. Problem Formulation · p. 3
  • The optimization minimizes total cost and maximizes the percentage of successfully processed queries, subject to assigning each query to one LLM.The formulation defines per-query cost and accuracy and restricts the assignment variable to binary values.Source: B. Problem Formulation · p. 3

IV. PROPOSED APPROACH

OptLLM has prediction and optimization components: it estimates each candidate model’s success probability for a query, then uses those estimates to allocate queries. Its prediction procedure aggregates bootstrap models and accounts for prediction uncertainty.

IV. PROPOSED APPROACH

  • OptLLM’s prediction component estimates the probability that each candidate LLM will successfully process a given query, and its optimization component uses those estimates to allocate queries.Figure 3 presents the framework’s architecture.Source: §IV · p. 3, Figure 3 · p. 4

A. The Prediction Component

  • A multi-label classification model with uncertainty estimation predicts candidate LLM performance for each query, addressing the uncertainty of success before processing.The model is intended to improve prediction reliability and stability.Source: A. The Prediction Component · p. 3

1) Bootstrap-based training and aggregation:

2) Robust-aware predicted accuracy in aggregation:

OptLLM adjusts predicted accuracy using uncertainty, then searches the cost–accuracy trade-off from two extreme allocations. The initialization uses the cheapest and highest-predicted-accuracy allocations as Pareto solutions.

2) Robust-aware predicted accuracy in aggregation:

  • The accuracy objective averages query-level predicted accuracies, while α controls how much uncertainty adjusts each weighted-mean prediction.At α = 0, uncertainty is disregarded; positive α values add the uncertainty term, while negative values subtract it.Source: 2) Robust-aware predicted accuracy in… · p. 4

B. The Optimization Component

  • OptLLM initializes optimization with the highest-predicted-accuracy and lowest-cost solutions, then iteratively searches for non-dominated solutions.The search applies destruction and reconstruction until its termination criterion is met.Source: B. The Optimization Component · p. 4

1) Initialization:

  • The cheapest allocation sc and highest-accuracy allocation sh are both Pareto solutions.The proof relies on neither extreme being dominated without contradicting its status as the minimum-cost or maximum-accuracy solution.Source: 1) Initialization · p. 5

2) The heuristic search:

The heuristic search alternates destruction, which prioritizes one objective, with reconstruction, which refines allocations toward non-dominated solutions. It searches in both cost-saving and accuracy-improvement directions.

2) The heuristic search:

  • Figure 4 depicts B as a feasible solution formed by releasing cost from non-dominated A, and C as a new non-dominated solution after reconstructing B.The figure illustrates how reconstruction follows destruction in the search.Source: Figure 4 · p. 5, 2) The heuristic search · p. 5
  • Destruction releases cost from the high-accuracy solution or seeks an accuracy gain from the cheaper solution, temporarily prioritizing one objective.For cost reduction, queries offering the largest savings are reassigned until the specified cost gap is met; for accuracy, the search targets the specified accuracy gap.Source: 2) The heuristic search · p. 5
  • Reconstruction favors accuracy improvement per unit cost and reassigns queries until the accuracy-to-cost quotient cannot increase further.The process retains or replaces solutions according to whether they are non-dominated.Source: 2) The heuristic search · p. 6

A. Research Questions

The evaluation asks whether OptLLM allocates queries effectively and efficiently, whether its components contribute, and how hyperparameters affect performance. It tests NLP and domain-specific tasks against individual LLMs and multi-objective optimization algorithms.

A. Research Questions

  • The experiments address allocation effectiveness and efficiency, component contributions, and the effects of hyperparameter settings.These are the three research questions guiding the evaluation.Source: A. Research Questions · p. 6

1) Natural Language Processing (NLP) tasks:

  • NLP evaluation covers text classification, question answering, sentiment analysis, and reasoning using 12 LLMs from four providers.The tasks use AGNEWS, COQA, HEADLINES, and SCIQ; the raw data includes prompts, references, model outputs, and cost.Source: 1) Natural Language Processing (NLP)… · p. 6

2) Domain-specific tasks:

  • The domain-specific evaluation uses log parsing with eight LLMs on LogPai data spanning 16 software systems.The data includes queries and full prompts, ground-truth references, LLM outputs, and execution cost.Source: 2) Domain-specific tasks · pp. 6–7

1) Individual LLM:

  • Individual-LLM baselines process the entire query set with one model, and their cost and successful-completion proportion are measured.This reflects the common practice of assigning a task to a specific LLM.Source: 1) Individual LLM · p. 7

2) Classic multi-objective optimization algorithms:

  • OptLLM is compared with six multi-objective algorithms using the same prediction component for a fair comparison of optimization strategies.The comparison includes NSGA-II, MOPSO, MOEA/D, R-NSGA-II, SMS-EMOA, and MOEA/D-GEN.Source: 2) Classic multi-objective… · p. 7

D. Evaluation Metrics

Single-solution performance is evaluated by total API cost and the percentage of jobs processed correctly. Multi-objective algorithms are assessed against an exhaustively generated Pareto-front reference using quality, distribution, and runtime measures.

1) Evaluating single solution performance:

  • Single-solution evaluation uses total LLM API cost and the percentage of jobs processed correctly as its two objectives.Cost is minimized and accuracy is maximized.Source: 1) Evaluating single solution… · p. 7

2) Multi-objective optimization evaluation metrics:

  • The reference Pareto front is generated by exhaustive search, starting with the cheapest allocation and repeatedly reallocating the cheapest job that can raise accuracy.The process ends when accuracy can no longer be increased.Source: 2) Multi-objective optimization… · p. 7
  • IGD measures distance from obtained solutions to the true Pareto front, while Δ measures diversity and uniformity along the obtained front.Lower IGD indicates a better distribution and approximation; a smaller Δ indicates higher diversity and distribution.Source: 2) Multi-objective optimization… · p. 7
  • Runtime is recorded in minutes for each algorithm under a shared termination condition of 200 iterations.Execution time measures computational efficiency for generating the solution sets.Source: 2) Multi-objective optimization… · p. 7

E. Implementation

OptLLM is evaluated against individual LLMs and multi-objective algorithms, with implementation settings reported. It matches the best individual LLM’s accuracy at lower cost and outperforms the compared algorithms on several solution-quality measures.

E. Implementation

  • Experiments were averaged over 10 runs; Optuna tuned parameters, with OptLLM settings µ=100, GN=50, and α=0.5.Implementations used Python 3.11, with NSGA-II, R-NSGA-II, and SMS-EMOA from Pymoo and MOPSO and MOEA/D from Pygmo.Source: E. Implementation · pp. 7–8

1) Comparison with individual LLMs:

  • At the best individual LLM’s accuracy, OptLLM’s cost savings range from 2.40% on SCIQ to 49.18% on LogPai.For AGNEWS, GPT-4 reaches 0.90 accuracy at cost 126.58; OptLLM matches that accuracy at cost 75.77, saving 40.14%.Source: Table II · p. 8, 1) Comparison with individual LLMs · p. 8

2) Comparison with classic multi-objective optimization algorithms:

  • OptLLM consistently delivers the highest accuracy; on AGNEWS it matches MOPSO’s 82.18% for $5.10 versus $51.15, saving 90.03%.The comparison uses the same accuracy attained by the strongest baseline algorithm.Source: 2) Comparison with classic… · p. 8
  • On AGNEWS, OptLLM achieves IGD 0.13 versus MOPSO’s second-best 11.61; it also has the smallest ∆ across scenarios and is around 5 times faster.Runtime comparison is for generating the same number of solutions.Source: 2) Comparison with classic… · p. 8
  • On AGNEWS, the highest accuracy is 88.74% for OptLLM, versus 83.67% without robust-aware prediction and 69.54% without optimization.The figure describes these components as helping find solutions with higher accuracy.Source: Figure 5 · p. 8

B. RQ2: Ablation Study

The ablation study finds that both optimization and robust-aware prediction contribute to OptLLM’s ability to find high-accuracy solutions. Robust-aware prediction matters most when the prediction model is suboptimal.

B. RQ2: Ablation Study

  • Without optimization, the variant labels an LLM correct when predicted success exceeds 0.5, then assigns each query to the cheapest qualifying LLM.This variant can produce low-cost solutions but fails to identify high-accuracy solutions; the authors report that optimization improves solution quality and diversity.Source: B. RQ2: Ablation Study · p. 9
  • When the prediction model is highly accurate, removing robust-aware prediction has minimal effect; the robust-aware function is useful when predicted accuracy is suboptimal.The authors attribute this to a smaller difference between predicted and robust-aware accuracy when the prediction model performs well.Source: B. RQ2: Ablation Study · p. 9
  • OptLLM’s robust-aware prediction function and heuristic optimization significantly enhance overall capability; on AGNEWS, the version without robust-aware prediction performs better than the version without optimization, but OptLLM excels in searching for solutions with higher accuracy.Source: B. RQ2: Ablation Study · p. 9

C. RQ3: Effect of Hyper-Parameter Settings

The hyperparameter analyses describe tradeoffs in solution-set size, runtime, and prediction training data. The paper also contrasts its one-time query-allocation setup with prior work and concludes that OptLLM supplies non-dominated options for users’ budget and performance requirements.

C. RQ3: Effect of Hyper-Parameter Settings

  • Increasing GN generates more solutions but increases computation time, while IGD and ∆ remain similar across settings.GN controls objective distance during the optimization component’s destruction phase.Source: 1) The grid parameter GN · p. 9, Table VII · p. 10

2) The training data size of prediction component:

  • As prediction training data grows, ∆ consistently increases while IGD decreases slightly overall; the authors choose 1% of the dataset for training.The passage presents the 1% setting as a tradeoff; it does not provide the remainder of that explanation.Source: 2) The training data size of… · p. 9, Table VIII · p. 10

VII. RELATED WORK

  • Prior query-allocation work is described as often requiring substantial training data, such as 50%, whereas OptLLM uses 1% and targets one-time allocation for a cost-accuracy tradeoff.The related-work discussion names FrugalGPT and FORC among earlier approaches.Source: §VII · p. 10

VIII. CONCLUSION

  • OptLLM offers diverse non-dominated query-assignment solutions spanning highest expected accuracy to lowest cost, for users to select by budget and performance requirements.The conclusion reports that experiments find OptLLM outperforms baseline methods in assignment effectiveness and efficiency.Source: §VIII · p. 10
Loading 2405.15130v1…