LLM Routing as Reasoning: A MaxSAT View

Son Nguyen; Xinyuan Liu; Ransalu Senanayake

cs.AIMar 13, 2026

LLM Routing as Reasoning: A MaxSAT View

Authors: Son Nguyen, Xinyuan Liu, Ransalu Senanayake

Organizations: Arizona State University

Abstract

Routing a query through an appropriate LLM is challenging, particularly when user preferences are expressed in natural language and model attributes are only partially observable. We propose a constraint-based interpretation of language-conditioned LLM routing, formulating it as a weighted MaxSAT/MaxSMT problem in which natural language feedback induces hard and soft constraints over model attributes. Under this view, routing corresponds to selecting models that approximately maximize satisfaction of feedback-conditioned clauses. Empirical analysis on a 25-model benchmark shows that language feedback produces near-feasible recommendation sets, while no-feedback scenarios reveal systematic priors. Our results suggest that LLM routing can be understood as structured constraint optimization under language-conditioned preferences.

Figures & tables

Direction Key	Case S (%)	All (%)	Count
I want a model with cheaper cached input.	12 (100%)	0	12
I want a cheaper model.	5 (100%)	0	5
I want a model with cheaper output prices.	1 (100%)	0	1
NONE	101 (51.01%)	97 (48.99%)	198
NONE.	10 (50%)	10 (50%)	20

Table 1: Count and Percentage of each outcome for different keys. Without specifying how many models , the Agent will always recommend some models (

|\mathcal{C}|>1

) to the user.

Figure 1: Coverage Percentage and Recommendation Precision of both LF groups

Figure 2: Percentile and Mean of NF set and model zoo on key objectives.

Figure 3: Direction key without language feedback set results for Case S. (a) per-endpoint selection frequency, b) reasoning/cached-input prevalence, (c) set-size statistics.

Clause $\psi_{j}$	Weight $\hat{w}_{j}(\bot)$
maxout_ge_p75	0.9317
reasoning_enabled	0.9272
ctx_ge_median	0.8011
cached_and_reasoning	0.7762
ctx_p75_and_cached	0.2243
cached_and_cheap_output_in_tier	0.0306

Table 2: Sparse estimate of implicit NF clause weights

\hat{w}(\bot)

fitted on Case S runs (111 runs,

M=25

endpoints,

J=19

candidate predicates).

LLM Routing

Large language model routing selects models, tools, experts, or inference strategies to balance answer quality, cost, latency, and deployment constraints.

See all 349 papers

SeLMRoute: Probabilistic Semantic Evidence for Large Language Model Routing
Sep 28, 2026Vasilis Perifanis, Nikolaos Pavlidis, Symeon SymeonidisLLM Routing
Indigma Innovations · Democritus University of Thrace · Athena Research Center
RouteJudge: An Open Platform for Reproducible and Preference-Aware LLM Routing
Jun 17, 2026Guannan Lai, Haoran Hu, Han-Jia YeLLM Evaluation Pairwise Preference Evaluation
School of Artificial Intelligence, Nanjing University, China · 2National Key Laboratory for Novel Software Technology, Nanjing University, 210023, China · 3SinapisAI
When Should LLMs Search? Counterfactual Supervision for Search Routing
Jul 7, 2026Minho KimKnowledge Augmentation for Language Models LLM Routing
1Sangmyung University · 2DMTLABS.

Sep 28, 2026J/K move · Enter open · S save

SeLMRoute: Probabilistic Semantic Evidence for Large Language Model Routing

Vasilis Perifanis, Nikolaos Pavlidis, Symeon Symeonidis

Indigma Innovations · Democritus University of Thrace · Athena Research Center

LLM Routing

Open paper AskPDF arXiv

Large language model (LLM) routing aims to select the most suitable model for each incoming query. Most existing routers learn this decision directly from query embeddings, model representations, preference data, or clusters of similar examples. Such approaches can be effective, yet the representation used for routing rarely states what a query actually requires. We introduce SeLMRoute, a routing framework that separates the extraction of candidate-independent semantic evidence from the learning of candidate performance and the application of deployment objectives. A decision model first evaluates a set of interpretable questions about the query, such as its reasoning requirements and use of external knowledge, with each judgment retained as a probability distribution. The resulting probabilistic semantic state is used by a lightweight supervised router to estimate candidate model performance. Routing objectives are applied after performance estimation, which allows the same semantic state to support performance-oriented and cost-aware decisions. On the LLMRouterBench (15 datasets, 20 candidate models, 11,481 queries), SeLMRoute achieves an average accuracy of

72.08\% \pm 0.45

, while grouped five-fold out-of-fold evaluation reaches

72.64\%

, compared with

69.23\%

for the strongest fixed candidate. The representation achieves the highest mean performance among the evaluated semantic, dense, lexical, and domain-level representations. In a separate 13-model performance-cost setting, SeLMRoute improves performance in all five grouped splits, with a mean PerfGain of

2.66\%

. Our code is available at https://github.com/Indigma-Innovations/SeLMRoute.

Abstract

LLM Routing

Explore similar work

SeLMRoute: Probabilistic Semantic Evidence for Large Language Model Routing

RouteJudge: An Open Platform for Reproducible and Preference-Aware LLM Routing

When Should LLMs Search? Counterfactual Supervision for Search Routing