EDM 2025 · WLIEDM Workshop · with Igor Bogdanov
Cutting LLM grading costs by 78% with a bandit
Finding the best prompting strategy for LLM essay scoring usually means testing every strategy on every essay. We treat each strategy as an arm of a multi-armed bandit that learns which one works while it grades.
What I did
Four grading "recipes" for IELTS Writing Task 2 essays (multi-step vs single-step assessment, with vs without calibration examples) became four bandit arms. The controller observes agreement with examiner ground-truth scores as its reward and shifts traffic toward the recipe that earns it.
What I found
The bandit matched exhaustive grid search on scoring accuracy (Quadratic Weighted Kappa) while using 78.4% fewer LLM calls and 72.8% fewer tokens, and correctly converged on the best recipe, multi-step with examples.
Why it matters
Prompt choice is usually frozen offline and re-tuned by hand whenever models or prices change. Framing it as online learning makes the choice self-updating, a pattern that applies to any high-volume LLM pipeline, not just essay scoring.
Watch the bandit allocate 500 essays
An animated reconstruction of the allocation reported in the paper: exploration spreads essays across all four recipes early, then traffic concentrates on the winner.
Final allocation from the paper: 332 / 67 / 56 / 45 essays; 1,697 LLM calls and 2.96M tokens vs 7,870 calls and 10.92M tokens for grid search. Multi-step recipes cost 4 calls per essay, single-step 1, which is why call savings outpace essay counts.