Research map / Graph learning / Graph self-supervised learning
GraphRouter: A Graph-based Router for LLM Selections
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes GraphRouter, an inductive heterogeneous-GNN router that models tasks, queries and LLMs as graph nodes and selects LLMs via edge prediction, generalizing to unseen LLMs with few-shot data.
Problem
Selecting the best LLM for each query under performance-cost trade-offs, where existing routers fail to generalize to new LLMs and tasks because they use names/IDs and transductive learning and need per-task retraining.
Approach
Builds a heterogeneous graph of task, query and LLM nodes with query-LLM interaction edges carrying performance and cost, uses LLM-generated textual descriptions embedded by a PLM as inductive node features, and frames routing as edge prediction via a heterogeneous GNN.
Key results
- Under the Balance scenario GraphRouter reaches reward 0.209 vs 0.196 for C2MAB-V and 0.164 for FrugalGPT, with Oracle at 0.231 on the main dataset.
- In the new-LLM few-shot setting GraphRouter (few-shots) improves reward by 9.52% over C2MAB-V while cutting time cost by 99.45% (3.00 vs 542.25).
- On the extended 6-task, 14-LLM dataset GraphRouter improves reward by at least 12.3% over baselines in the Balance scenario (0.122 vs 0.087 for C2MAB-V).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use GraphRouter instead of the strongest reported router baseline | LLM selection · Multi-task interaction dataset, Performance First | Reward: 0.517 -> 0.539 | Helped |
| use GraphRouter instead of the strongest reported router baseline | LLM selection · Multi-task interaction dataset, Balance | Reward: 0.196 -> 0.209 | Helped |
| use GraphRouter instead of the strongest reported router baseline | LLM selection · Multi-task interaction dataset, Cost First | Reward: 0.057 -> 0.064 | Helped |
| use GraphRouter few-shot generalization rather than C2MAB-V | LLM selection for new LLMs · New LLMs, Balance | Reward: 0.189 -> 0.207 | Helped |
| use GraphRouter few-shot generalization rather than C2MAB-V | LLM selection for new LLMs · New LLMs, Balance | Time Cost: 542.25 -> 3.00 | Helped |
| use GraphRouter rather than the strongest reported baseline | LLM selection · Extended multi-task interaction dataset, Performance First | Reward: 0.350 -> 0.393 | Helped |
| use GraphRouter rather than the strongest reported baseline | LLM selection · Extended multi-task interaction dataset, Balance | Reward: 0.087 -> 0.122 | Helped |
| use GraphRouter rather than the strongest reported baseline | LLM selection · Extended multi-task interaction dataset, Cost First | Reward: 0.027 -> 0.046 | Helped |
| use GraphRouter rather than FrugalGPT | LLM selection among LLaMA-series models · LLaMA-series dataset, Performance First | Reward: 0.382 -> 0.422 | Helped |
| use GraphRouter rather than FrugalGPT | LLM selection among LLaMA-series models · LLaMA-series dataset, Balance | Reward: 0.162 -> 0.192 | Helped |
| use GraphRouter rather than FrugalGPT | LLM selection among LLaMA-series models · LLaMA-series dataset, Cost First | Reward: 0.050 -> 0.058 | Helped |
| set GNN hidden size to 32 rather than smaller or larger explored sizes (ablation) | GraphRouter · LLM selection, three scenarios | Reward | Mixed |
Surprising findings
- Smaller LLMs sometimes outperform larger LLMs on specific queries, so always choosing the largest model is not optimal even with unlimited budget.
- Prompting GPT-4 to select an LLM (Prompt LLM) performs poorly under cost-sensitive scenarios, underperforming trained routers.
Limitations
- Authors describe the work as exploratory, with only a small set of tasks and 10-14 LLMs.
- Relies on API-served LLMs with a single cost model (Together API pricing), and results averaged over few rounds.
- Numerical attributes such as token price and context length are only conveyed through text descriptions, which the authors note is an open issue.
Experimental setup
Datasets: Alpaca GSM8K SQuAD Multi-News HumanEval HotpotQA
Benchmarks: Alpaca GSM8K SQuAD Multi-News
Metrics: performance cost reward time cost
Baselines: Largest LLM Smallest LLM Prompt LLM Hybrid LLM FrugalGPT C2MAB-V Oracle
Builds on: Hybrid LLM FrugalGPT C2MAB-V GraphSAGE GAT
Closest papers by meaning
- RouteLLM: Learning to Route LLMs from Preference Data (ICLR 2025 · similarity 0.91)
- Attention Mechanisms Perspective: Exploring LLM Processing of Graph-Structured Data (ICML 2025 · similarity 0.90)
- BEST-Route: Adaptive LLM Routing with Test-Time Optimal Compute (ICML 2025 · similarity 0.89)
- Lookahead Routing for Large Language Models (NeurIPS 2025 · similarity 0.89)
- Can Large Language Models Analyze Graphs like Professionals? A Benchmark, Datasets and Models (NeurIPS 2024 · similarity 0.88)
- Advancing Tool-Augmented Large Language Models: Integrating Insights from Errors in Inference Trees (NeurIPS 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.