CopRoute: Dependence-Aware Conformal Routing for Language Models

Detailed Research Summary: CopRoute - Dependence-Aware Conformal Routing for Language Models

As a meticulous researcher, I have thoroughly reviewed the provided text excerpts from the paper CopRoute: Dependence-Aware Conformal Routing for Language Models. This summary synthesizes the core contributions, methodology, and empirical findings of CopRoute to provide a comprehensive understanding of its significance in model routing.

Core Problem Addressed

The fundamental challenge addressed by CopRoute is the limitation of existing risk-controlled routing policies. These traditional methods typically bound the all-miss risk by calibrating a single conformal threshold applied across a nested family of models. The critical flaw, as identified in the paper, is that these policies ignore the dependence structure among model failures. They treat model failures as conditionally independent events, which is often an inaccurate assumption in real-world scenarios where multiple models might fail simultaneously due to shared underlying data or query characteristics.

CopRoute Methodology: Dependence-Aware Ordering and Selection

CopRoute introduces a novel routing policy that explicitly accounts for this dependence structure. Its mechanism is structured around three key decisions made per query:

1. Model Ordering (Dependence-Aware Ranking): Instead of relying on static model performance metrics alone, CopRoute first orders the candidate models based on a dynamic criterion: how many new queries each model is expected to answer correctly beyond those already selected. This ordering is inherently designed to exploit the dependence among failures. The paper demonstrates that under conditional independence assumptions, scoring models in isolation is optimal for any set size. However, when dependence exists, the optimal set of models might not simply consist of the individually best performers; CopRoute's ordering strategy navigates this complexity.

2. Model Selection (Adaptive Depth): For each new query, CopRoute decides how far down this newly established order to proceed from the router’s predicted success probabilities. This allows for a flexible exploration of the candidate set based on the current query context and predicted success likelihoods.

3. Cutoff Calibration (Risk Control): Finally, it selects the smallest cutoff within this ordered sequence that still meets the target all-miss risk (alpha). This ensures that while dependence is accounted for in which models are considered, the final selection adheres strictly to the required risk guarantee.

The paper formalizes this by introducing three guarantees: one for its model ordering, one for its calibrated cutoff, and one for its finite-sample correction. Crucially, the certificate certifying these properties is robust; it does not depend on a specific dependence estimator used, meaning any valid dependence estimator can produce the correct ordering without weakening the guarantee.

Key Theoretical Contributions

The authors establish several significant theoretical findings:

• Dependence and Optimality: They prove that the all-miss probability of a model set is jointly dependent on individual model accuracies and the dependence among model failures. They show that under conditional independence, scoring models in isolation is optimal at every set size. Conversely, when dependence is present, the best set may deviate from simply picking the individually best models.

• Guarantees: Theorem 1 provides a guarantee on the design objective—specifically, bounding the mean position of the first correct model under a fixed order. Appendix D further shows how this guarantee transfers to fresh queries.

• Approximation Guarantees: The fixed tally order achieves a factor four approximation guarantee for minimum-sum set cover on the design set.

• Cutoff Certification: The concept of split calibration certifies the deployed cutoff, with Corollary 1 stating that among all certified cutoffs in a frozen family, the smallest certified cutoff calls the fewest models.

Empirical Results and Performance Superiority

The empirical evaluations conducted on RouterBench and RouterEval datasets demonstrate CopRoute's substantial practical advantages over state-of-the-art risk-controlled policies:

• Call Reduction: On ten datasets from RouterBench and RouterEval, CopRoute achieves the fewest certified calls at target risks of alpha=0.05 (on nine out of ten datasets) and alpha=0.10 (on eight out of ten). This translates to up to 79 percent fewer calls compared to the state-of-the-art risk-controlled policy while maintaining the same certified all-miss risk.

• Cost Efficiency: The improvements are most pronounced on reasoning benchmarks. For instance, on MuSR (at alpha=0.10), CopRoute requires only 12.7 calls, compared to 44.6 for RACER-G and 55.2 for BaRP—a significant reduction in inference cost without sacrificing final-answer accuracy or the certified risk level.

• General Robustness: CopRoute is shown to be superior across various datasets, targets, and routers (including FlexRouter and RACER variants). The gain stems primarily from the co-failure order, as replacing this ordering with a design-marginal order incurs a significant call penalty (up to 27 calls), whereas swapping the router or recalibrating the cutoff has minimal impact.

• Scalability: The policy maintains its leading performance across larger model pools (up to 500 models) and various deployment distributions.

Limitations and Operational Considerations

Despite its strengths, a diligent researcher must note the limitations:

1. Certificate Scope: The certificate bounds the average all-miss risk over a deployment distribution, which is not a per-query guarantee. This means it certifies the overall performance profile of the deployed set, not necessarily every single query outcome deterministically.

2. Stopping Rule Nuance: The dependence-corrected stopping rule (CopRoute-Dep) does not consistently outperform the independence-based default (CopRoute-Ind) in all cases. Its primary advantage often derives from the co-failure order itself rather than the stopping correction mechanism.

3. Recalibration Requirement: The cutoff must be recalibrated whenever the deployment pool or query distribution changes, adding a small operational overhead (about one call on average after a pool change).

Conclusion

CopRoute represents a significant advancement in model routing by moving beyond simplistic independence assumptions to explicitly model and exploit the dependence structure among model failures. By integrating dependence-aware ordering with adaptive selection and rigorous risk calibration, it achieves state-of-the-art performance in terms of minimizing certified inference calls while rigorously controlling the all-miss risk. Its demonstrable superiority across multiple benchmarks validates its theoretical framework, positioning it as a highly efficient and robust routing policy for large language model inference systems.

1. Bold Header: Dependence-Aware Routing Policy CopRoute

CopRoute orders models by how many new queries each one answers correctly beyond those already selected and decides per query how far down that order to go, and then picks the smallest cutoff that still meets the target risk, which allows for a dependence-aware routing rule to account for the fact that models trained on similar data or built from similar architectures tend to fail on the same queries.

2. Bold Header: Certified All-Miss Risk Guarantee

The system can provide a distribution-free guarantee by using a split calibration step where, under certain conditions, it can certify the all-miss risk, as Theorem 2 states that If this set is empty, return NON-CERTIFIED; otherwise return bk = min Kcert.

3. Bold Header: Reduced Inference Cost

The improved system can achieve significant cost savings by attaining the fewest certified calls on nine of ten datasets at a target risk of 0.05 and on eight of ten at 0.10, making up to 79 percent fewer calls (median 24 percent) than the state-of-the-art risk-controlled policy.

Set-based language model routing aims to increase the coverage of the event where at least one model answers a query correctly while controlling the number of inference calls made. Existing risk-controlled routing policies bound the all-miss risk (the probability that every model in the selected set fails) by calibrating a single conformal threshold and applying it to a nested family of model sets. Because each model is scored in isolation, these policies ignore the dependence structure of model failures. Models that share training data or architecture tend to fail on the same queries, so two individually strong models can be jointly redundant while a weaker but complementary model covers the queries that the others miss. To account for this dependence, which existing risk-controlled policies ignore, we propose CopRoute, which orders models by how many new queries each one answers correctly beyond those already selected, decides per query how far down that order to go, and then picks the smallest cutoff that still meets the target risk. We show that CopRoute's ordering attains, on the design data, the best guarantee any efficient fixed-ordering algorithm can give for the average number of calls to the first correct model, and that a separate calibration step certifies the all-miss risk of the deployed sets. On RouterBench and RouterEval, CopRoute attains the fewest certified calls on nine of ten datasets at a target risk of 0.05 and on eight of ten at 0.10, making up to 79 percent fewer calls (median 24 percent) than the state-of-the-art risk-controlled policy at the same certified all-miss risk.