OR for AI That Does OR: Routing LLMs up the Escalator inside the OSCAR Framework

1. Introduction

• A feasible formulation may still exclude better solutions, and this paper assesses solution correctness for one target instance rather than correctness across every instance consistent with the description.A misread constraint or objective can produce code that solves to optimality while representing a different problem.Source: §1 · pp. 2–3
• OSCAR certifies an offline Simulator against labeled decision examples, then uses it to compare candidate solutions and continue searching after feasibility.Once certified, its improvement loop requires no human intervention.Source: §1 · pp. 2–3, §1.1 · p. 3

1.1. Our Contributions

• The Escalator models improvement search as sequential decisions under unobserved difficulty, with cost-ordered escalation optimal under conditions and a prior-free schedule with a constant-factor guarantee.The guarantee compares expected loss with a clairvoyant and depends only on success probabilities.Source: §1.1 · p. 3
• OSCAR achieved 95% to 100% accuracy across five problems, while Codex and Claude Code averaged token costs 3.1 and 5.8 times OSCAR’s, respectively.The two small models used by OSCAR had single-attempt accuracies averaging 29% and 48%; resampling one-shot formulations matched OSCAR’s accuracy but cost 1.6 to 3.3 times as much on problems rarely solved in one attempt.Source: §1.1 · pp. 3–4

1.2. Managerial Insights

• Before upgrading to frontier models, firms should evaluate what available models can achieve through verification and iterative improvement, accounting for cost and confidentiality.OSCAR can use open-weight models locally or in the cloud, depending on those requirements.Source: §1.2 · p. 4
• Firms should maintain labeled feasible and infeasible decisions alongside written rules, so the Simulator follows known outcomes when an LLM’s interpretation conflicts with those examples.These examples make intended operating rules explicit and help build and test the Simulator.Source: §1.2 · p. 4
• Firms can adjust OSCAR’s attempt-allocation and restart settings and add models as LLM capabilities and prices change.The framework’s simple operating rules are intended to let firms continue benefiting from model improvements.Source: §1.2 · p. 4

1.3. Related Literature

• OSCAR’s routing analysis accommodates a menu containing both specialized optimization models and general-purpose models.Specialized models can serve as Coders for compatible problem classes.Source: §1.3 · p. 5
• OSCAR certifies its Simulator with externally supplied labeled decisions before generation, keeps it fixed, and uses it to compare candidates beyond the first feasible solution.It allocates costly attempts to seek further improvements rather than stopping at feasibility.Source: §1.3 · p. 6
• Unlike query-level routing, OSCAR models repeated attempts on one problem under shared latent difficulty, allows repeated calls to the same models, and computes a routing schedule and competitive bound.The routing inputs include models’ success probabilities and prices.Source: §1.3 · p. 7
• The known-prior model updates beliefs about shared latent difficulty after failures to allocate repeated LLM attempts and decide when to stop; prior-free analysis compares Escalator’s expected loss with a benchmark that observes difficulty but not future outcomes.The analysis draws on Bayesian sequential experimentation and competitive analysis of online decisions.Source: §1.3 · p. 7

2.1. Comparing Formulations through a Simulator

• Because formulations can misread rules and assess objectives within different feasible regions, OSCAR compares candidate plans using an external Simulator rather than an LLM arbiter.The Simulator reports feasibility and, for feasible plans, objective value; OSCAR retains the best-ranked formulation and continues searching after finding a feasible plan until its routing policy stops.Source: §2.1 · pp. 7–8
• OSCAR adds decision syntax and labeled feasible/infeasible examples to standard problem and instance inputs, using them to test and certify an LLM-written Simulator before formulation generation.Construction iteratively checks example classifications and available objective values, revises failed cases, and assesses whether rejection explanations identify the violated rule, location, and magnitude.Source: §2.1 · pp. 8–9

2.2. Preliminary Observations

• Qwen3.6-Flash’s formulation reached the optimum 23 times, compared with 19 times when Qwen3.5-Flash wrote the initial formulation and Qwen3.6-Flash refined it; refinement used more tokens.This comparison motivates discarding a weaker Coder’s unsuccessful revisions before a stronger Coder takes over.Source: §2.2 · p. 10
• Runs reaching the optimum typically did so within three to five revisions, while runs still unsuccessful then seldom succeeded by thirty and late revisions could degrade code.The observations motivate periodically discarding revisions and returning to the best formulation retained so far.Source: §2.2 · p. 10
• Independent structure-constructor calls may yield slightly different structures that affect formulation quality, but revision can still produce a correct formulation; feeding syntax-error messages to the cheapest model resolved nearly all such errors in tests.Source: §2.2 · p. 10
• At $0.007 per Reviewer call versus $0.013 per Coder call, average input and output tokens were 5,528 and 6,077 versus 6,696 and 11,184.A Coder call cost about 1.8 times as much; output counts include thinking tokens.Source: §2.2 · p. 11
• Increasing the Coder’s model tier costs more than increasing the Reviewer’s tier, affecting the cost of a revision attempt.Source: §2.2 · p. 11

• The structure constructor turns the description into a schema listing required parameters, data types, dimensions, and one-line explanations; later calls receive both schema and original description.Source: §3 · p. 12
• A strong model produces the initial formulation in one shot, which becomes the incumbent without any guarantee of correctness.Source: §3 · p. 12
• The Reviewer receives problem information, the formulation, and Simulator feedback, then gives revision advice; the Coder uses that advice to produce a candidate formulation and solver code.Source: §3 · p. 12
• Every feasible solution outranks every infeasible one; feasible candidates are compared by Simulator-recomputed objective values, while infeasible candidates rank by fewer violated rules.Source: §3 · p. 12
• A candidate replaces the incumbent only when it ranks strictly higher; OSCAR returns the standing incumbent when the policy stops or a wall-clock or spending ceiling is reached.Source: §3 · pp. 12–13
• The routing policy selects Reviewer and Coder LLMs and decides when to stop; stronger models may improve the incumbent more often but cost more, and difficulty is unobserved.Source: §3 · p. 13

4.1. General Formulation of Sequential Improvement Search

• Progress is fewer rule violations before feasibility and a better Simulator objective afterward; Type 1 and Type 2 windows begin with infeasible and feasible incumbents, respectively.Source: §4.1 · pp. 13–14
• The analysis isolates one window, assuming fixed hidden difficulty and a constant reward G per certified improvement rather than modeling formulation changes or gain size.These simplifications make it possible to study routing decisions without modeling the full improvement trajectory.Source: §4.1 · p. 14
• Each action is a costed ordered Reviewer–Coder pair whose success probability depends on hidden state; success earns G and ends the window, while failure leads to another routing decision.Source: §4.1 · pp. 14–15
• Escalator plans may repeat or skip configurations but never move backward in cost order; with L tiers, same- or adjacent-tier menus contain 3L−2 configurations rather than L².This restriction is described as easier to tune in practice and reduces what must be measured before the policy can run.Source: §4.1 · pp. 14–15

4.2. Exact Optimality in the Two-by-Two Case

• With two configurations and a known prior over two improvable states (plus a non-improvable state in Type 2 windows), the infinite-horizon POMDP has an optimal Escalator routing plan.The subsection establishes this structure for the two-by-two case.Source: §4.2 · p. 16
• As failures accumulate, the pairwise advantage of ordering A before B can change sign at most once, and only from nonnegative to nonpositive.The single-crossing condition rules out the reverse cost-effectiveness ranking across easy and hard states.Source: §4.2 · pp. 18–19
• Under Assumption 1(ii), when the stated conditions hold, replacing a routing plan’s terminal A call with B does not decrease its value.A may be an inexpensive early choice, but a final call cannot provide information for later decisions, so B’s greater capability can make it preferable.Source: §4.2 · p. 19
• Under Assumption 1(i)–(iii), an optimal deterministic plan calls A for n_A attempts and then B for n_B, with n_B = 0 if n_A = ∞.This Escalator plan attains the infinite-horizon optimal value for every reachable belief.Source: §4.2 · p. 20
• In Type 1 windows, stopping before success is never strictly optimal under Assumption 1(iv); in Type 2 windows, every optimal plan stops after at most ⌊G(1 − μ_o)/(μ_o c_A)⌋ consecutive failures.In Type 1, calling B until success has nonnegative expected net reward; in Type 2, enough failures make continuation’s expected reward lower than its calling cost.Source: §4.2 · p. 20
• Under the stated two-by-two assumptions and conditions, an optimal policy can be chosen to call both configurations, with a finite A-block in the Type 1 case.The common condition makes beginning with A optimal; the additional Type 1 conditions permit a finite A-block followed by a B-block.Source: §4.2 · pp. 20–21

4.3. A Competitive Guarantee in the General Case

• For general menus, Algorithm 1 increases staged spending budgets and selects configurations using state-independent weights to construct an Escalator policy.At each stage it chooses the configuration with the largest reach target for that budget and adds calls until the scheduled calls reach that target; its configuration switches increase call cost.Source: §4.3 · pp. 22–23
• The deterministic prior-free Escalator policy has competitive ratio at most 4h(κq(s*)) and at most 5.2κq(s*), uniformly over hidden states.The upper bound is minimized at κq(s*) = 1, where it is approximately 5.194.Source: §4.3 · pp. 23–24
• For Type 1 windows, extending the final configuration weakly reduces expected loss when repeating it is worthwhile in every improvable state.This condition supports continuing with the final configuration rather than stopping after the menu.Source: §4.3 · p. 24

4.4. The Policy OSCAR Runs

• OSCAR preserves cost ordering, tunes attempt counts directly, escalates when a configuration’s allotment is exhausted, and stops differently for Type 1 and Type 2 windows.Type 2 stops after exhausting the menu without improvement; Type 1 repeats the final configuration until an improvement is certified.Source: §4.4 · pp. 24–25
• A large external stopping limit can cap the Type 1 extension, but no Section 5 run reached it.Section 4.3 supports the distinction under its stated conditions.Source: §4.4 · p. 25
• Each window begins from the incumbent, later attempts revise the latest draft, and the loop reverts to the incumbent when the Coder tier increases.During the Type 1 extension, it also reverts after every restart interval of uncertified attempts.Source: §4.4 · p. 25
• The Type 1 extension returns to the incumbent after every r = 3 uncertified attempts in the experiments.The restart interval is denoted r.Source: §4.4 · p. 25

5.1. Comparison with One-Shot and Frontier Coding Agents

• The study covered five problems because OSCAR needs problem-specific syntax and labeled examples, while preparation and benchmark ambiguities constrained which problems could be retained.The selected problems were kept without changing their benchmark components.Source: §5.1 · p. 26
• 95% to 100% accuracy was reached on four problems with one attempt per configuration; on Routing, accuracy rose from 72% to 95% with more attempts.The higher Routing allocation added $0.11 per run, with each improvement certified by the Simulator.Source: §5.1 · pp. 26–27, Table 3 · p. 27
• Single attempts reached the reference optimum in 48% of runs with Qwen3.6 and 29% with Qwen3.5, averaged across the five problems.The configurations paired the two models as Reviewer and Coder, in cost order, and used restart interval r=3.Source: §5.1 · pp. 26–27
• Across five problems, OSCAR cost $0.193 per run, versus $0.600 for Codex and $1.127 for Claude Code.These frontier-agent costs were 3.1 and 5.8 times OSCAR’s, respectively; OSCAR’s cost includes Simulator construction.Source: §5.1 · p. 27, Table 3 · p. 27

5.2. Contribution of the Improvement Loop

• The resampler independently draws one-shot formulations, retains the best Simulator-accepted solution, and stops after k consecutive draws without improvement.It removes the Reviewer, incumbent revision, and routing from OSCAR’s improvement loop.Source: §5.2 · p. 27
• On Routing, Packing, and Scheduling, resampling to match OSCAR’s accuracy cost 1.6 to 3.3 times as much; on Graph and Quadratic, it cost 0.7 to 1.0 times as much.These estimates use the smallest resampling count within 1% of OSCAR’s most accurate tested setting.Source: §5.2 · p. 28, Table 4 · p. 28

OSCAR

• OSCAR uses a certified Simulator to compare candidates and continues searching beyond feasibility through iterative improvement and cost-ordered escalation.The conclusion recommends assessing available models with verification and iterative improvement before upgrading to frontier models.Source: §6 · p. 28

Routing results

• For two configurations and difficulty levels with a known prior, an optimal policy has an Escalator structure; general menus receive a prior-free competitive guarantee.Algorithm 1 constructs an Escalator schedule for general menus.Source: §6 · p. 28

Benchmark results

• 95% to 100% accuracy at the reported settings across five benchmark instances is achieved by OSCAR using two small LLMs.The reported token costs are lower than Codex and Claude Code in a limited frontier-agent comparison.Source: §6 · p. 28

Deployment and preparation

• Two small LLMs used in the reported study can be deployed locally on a single GPU, while local or cloud deployment can suit cost and confidentiality requirements.Labeled decision examples alongside plain-language descriptions help clarify business rules and support Simulator construction.Source: §6 · p. 28

Future research directions

• The study evaluates solution correctness on a single target instance, leaving formulation correctness across all instances consistent with the description for future work.That broader requirement calls for a separate layer to develop and validate comprehensive verification procedures independently of formulation generation.Source: §6 · p. 29
• Future work includes improving computational performance and reducing manual data preparation.The authors suggest combining solve-time evaluations with Simulator evaluations and adapting Simulator construction to build and check data-reading routines.Source: §6 · p. 29

Supplying partial decision examples

• Complete feasible examples alone do not establish that every constraint is checked correctly, especially if no example approaches violating it.Partial examples can isolate a constraint in a fragment, with respecting or violating labels; pairs differing in one respect are especially useful.Source: Supplying partial decision examples · p. 32
• Partial-example labels must be confirmed by the firm or derived from perturbations of existing labeled decisions, rather than accepted solely from the formulation models.During Simulator construction, a flag prevents intentionally omitted decisions from being treated as errors; the flag is not used in OSCAR runs.Source: Supplying partial decision examples · p. 32

Certifying violation messages

• Correct rejection labels alone do not give the Reviewer enough feedback for revision; violation messages need to explain the rule, location, and magnitude.A separate LLM scores whether messages identify those elements, and can supply replacement wording while preserving labels.Source: Certifying violation messages · p. 32

EC.1. Pseudocode for Simulator Construction and the OSCAR Framework

• Simulator construction starts with the cheapest writer and advances after its round budget is exhausted; problems outside the benchmark study sometimes required human help, mainly for formatting.The construction procedure checks examples and malformed inputs, and returns a Simulator fixed for subsequent OSCAR runs.Source: Certifying violation messages · pp. 32–33
• An OSCAR session initializes an incumbent, gives the Reviewer its feedback for revision advice, and evaluates candidates against the incumbent.A candidate that improves the incumbent updates it and immediately starts a new window; escalation returns to the incumbent when the Coder tier increases.Source: Certifying violation messages · pp. 33–34

EC.2.1. Proof of Lemma 1

• Finite-call optimal values converge to the infinite-horizon value, using a truncation argument that bounds the reward available after the first k calls.The proof then takes the limit in the finite-horizon Bellman equation.Source: EC.2.1. Proof of Lemma 1 · p. 34

EC.2.2. Proof of Lemma 2

• For comparing two call orders, expected success reward and continuation value are invariant to order, so the proof reduces the comparison to expected calling costs.The proof also uses posterior updates and a full-support prior in its local comparison argument.Source: EC.2.2. Proof of Lemma 2 · p. 35

EC.2.3. Proof of Lemma 3

• In the Lemma 3 proof, the replaced call is terminal, so it incurs no further cost.The proof also invokes Assumption 1(ii), which implies p_B(β) ≥ p_A(β).Source: EC.2.3. Proof of Lemma 3 · p. 36

EC.2.4. Proof of the Escalator Structure in Equation (9) of Theorem 1

• Finite-horizon optimal plans can be chosen as A^nA B^nB, and a subsequence argument establishes an infinite-horizon optimal plan of the same Escalator form.The finite-horizon proof first reduces the action sequence to at most three blocks, then removes the terminal A-block; the infinite-horizon proof treats both β_o=0 and β_o>0.Source: EC.2.4. Proof of the Escalator… · pp. 37–39

EC.2.5. Proof of Parts (i) and (ii) in Theorem 1

• When μ_o=0, stopping before success is never strictly optimal, and an optimal plan can have n_A=∞ or n_B=∞; if γ_B,h<γ_A,h, n_A can be finite.In the latter case, the proof gives an optimal plan A^r B^∞ for finite r.Source: EC.2.5. Proof of Parts (i) and (ii) in… · p. 40
• When μ_o>0, any optimal plan has finitely many calls, with N≤⌊G(1−μ_o)/(μ_o c_A)⌋.An infinite plan has value −∞, and scheduled calling costs are incurred in state o, yielding the stated bound.Source: EC.2.5. Proof of Parts (i) and (ii) in… · p. 40

EC.2.6. Proof of Corollary 1

• One call to A followed by stopping weakly dominates immediate stopping and every B-only plan, so an optimal Escalator plan can be chosen to begin with A.The proof bounds the expected reward of any nonempty B-only plan by G(1−μ_o)−c_B.Source: EC.2.6. Proof of Corollary 1 · pp. 40–41
• For a Type 1 window with γ_B,h<γ_A,h, the corollary’s optimal plan is A^(r+1)B^∞ for some finite r≥0.The proof obtains this by combining an initial A call with an A^r B^∞ continuation after failure.Source: EC.2.6. Proof of Corollary 1 · p. 41
• For a Type 2 window, the proof uses that the optimal plan is finite, handles plans containing B directly, and begins a separate argument for A-only plans.The supplied passage ends during the A-only analysis, before its conclusion is stated.Source: EC.2.6. Proof of Corollary 1 · p. 41
• V_μ(A_n;stop) is non-decreasing through n_0 and non-increasing thereafter, making stopping after n_0 calls to A optimal among finite A-only plans.Source: EC.2.6. Proof of Corollary 1 · p. 41
• Because an A-only plan is globally optimal in the case considered, V_μ(A_n0;stop) equals J∞(μ).Source: EC.2.6. Proof of Corollary 1 · p. 41
• Under part (ii), adding one B call after n_0 failed calls to A is also optimal; n_0 ≥ 1, so both blocks are nonempty.Source: EC.2.6. Proof of Corollary 1 · p. 42

EC.3.1. Proof of Proposition 1

• The proof of Proposition 1 concludes that the returned routing plan is an Escalator policy.Its argument establishes a strictly increasing cost ranking across the selected configurations.Source: EC.3.1. Proof of Proposition 1 · p. 42

EC.3.2. Proof of Theorem 2

• The Escalator policy’s reward gap is bounded by four times the smaller of expected Φ(U) and G.The proof bounds expected loss using Ψ(U), which accounts for scheduled-call costs and forgone reward.Source: EC.3.2. Proof of Theorem 2 · pp. 44–45
• Theorem 2 proves a competitive-ratio bound of CR(πEP) ≤ 4h(κq(s*)).The bound follows after comparing the reward gap across states and taking a supremum.Source: EC.3.2. Proof of Theorem 2 · p. 45

EC.4.1. Models, Menu and Settings

• Qwen3.6-Flash writes initial formulations and later repairs, while Qwen3.5-Flash builds schemas and handles the first two syntax repairs.Attempts are abandoned after the same error recurs three times; COPT runs single-threaded with a memory cap per solve.Source: EC.4.1. Models, Menu and Settings · p. 46

EC.4.2. Baselines

• One-shot baselines use Qwen3.5-Flash for up to ten repair rounds, with 100 repetitions per model and problem.Claude Code and Codex each run five independent agents per problem without access to the trusted checker, reference solution, Simulator, or feedback.Source: EC.4.2. Baselines · p. 46

EC.4.3. Cost Accounting

• Each run is charged the Simulator’s full build cost, and the stronger Coder is the largest recurring expense.This represents a run from scratch while evaluating OSCAR conditional on the constructed Simulator.Source: EC.4.3. Cost Accounting · p. 46