A note on conditional PAC-efficient reasoning in large language model routing

[Submitted on 25 Nov 2025 (v1), last revised 6 Aug 2026 (this version, v2)]

View PDF HTML (experimental)

Abstract:We study distribution-free risk control for model routing, motivated by large language model reasoning. We formalize pointwise conditional efficiency under a probably approximately correct guarantee and show that it forces a nearly impossible router: at almost every input where the fast model exceeds the target loss, the algorithm must route to the expert with probability at least one minus the prescribed error level. We therefore introduce a restricted conditional formulation based on a prespecified family of conditioning sets, together with an explicit router. The proposed router achieves finite-sample conditional validity and, under separation and margin conditions, near-oracle expert usage. The main insight is that the level of conditioning determines whether distribution-free reliability can coexist with computational savings: pointwise control is too strong, whereas structured setwise control remains feasible.

Submission history

From: Hao Zeng [view email]
[v1] Tue, 25 Nov 2025 17:08:08 UTC (49 KB)
[v2] Thu, 6 Aug 2026 14:15:54 UTC (75 KB)