Labeling news articles with fine-grained propaganda narratives works best when a large language model (LLM) reasons down the label tree in stages: first the broad topic, then the main narrative, then the sub-narrative. That staged reasoning is expensive. On a monitoring stream of thousands of articles in five languages, nobody can afford to run it on every article. This proposal treats the question "which articles get the expensive model, and how deep does it go for each" as a scheduling problem of the kind solved in stochastic resource allocation. A cheap fine-tuned encoder labels everything. A per-step budget of LLM calls is then spent according to an index policy, meaning a rule that gives each article a single priority score computed only from that article's own state and spends the budget on the highest-scoring ones. The policy comes from a linear-programming relaxation of the whole corpus problem.
The relaxation gives two things a confidence threshold cannot. The first is a non-myopic priority. An article may be worth a cheap stage-two check only because a stage-three check would then pay off a lot, and the priority score can value that. The second is a computable upper bound on the expected accuracy that any routing policy could reach under the same budget. So we can say not only "our router beats thresholding" but also "our router is within $x\%$ of the best possible router."
Core Claim
The per-document sample F1 used in SemEval-2025 Task 10 is an average of per-article F1 scores. That makes it additive across articles. Budgeted escalation over a corpus is therefore a weakly coupled Markov decision process: many small independent decision problems, one per article, tied together only by a shared per-step capacity.
Each article becomes an "arm" with a handful of states. A state records how deep in the taxonomy the article has been verified and the calibrated confidence bucket of its best unverified branch. A clock counts down to the article's labeling deadline, which makes the arm "restless": its situation changes even when it is not served. The available actions are to wait, verify the next candidate branch with a small LLM stage, or run the full hierarchical prompt.
We claim three things. First, a priority policy derived from the LP relaxation reaches most of the quality of full escalation at a small budget fraction. Second, it beats the myopic "largest immediate expected gain" rule specifically when gains are back-loaded in the hierarchy. Third, its gap to the LP bound shrinks as the batch size grows, as asymptotic-optimality theory predicts. If the second claim fails, the honest conclusion is that greedy routing suffices for this task, and we will report it that way.
Relation to Prior Work
The narrative side supplies the motivation and the expensive component. H3Prompt classifies with three-step LLaMA-3.2 prompting from category to narrative to sub-narrative and placed first on English. TGSC routes parent decisions into child prompts. On English it reports sample F1 of 0.321 against 0.196 for a flat variant, and it names irreversible cascade errors as the main weakness. ThoughtFlow distills GPT-4o reasoning chains into Gemma2-9B. All three run the full staged pipeline on every article, and none asks how quality degrades when only some articles can receive it.
cocoa motivates our reward design. Fine-tuned encoders scored 0.00 F1 on Protagonist and Antagonist sub-roles despite about 91% accuracy, and zero-shot GPT models scored 0% on subcategories. Our reward can up-weight rare sub-narratives, so the budget flows toward articles likely to contain them.
The hyperbolic propaganda classifier backs off to a parent label when leaf confidence is low. That is a per-article threshold rule with no budget coupling, and the system did not beat a flat XLM-RoBERTa baseline. This constrains us: geometric structure alone did not help, so our gains must come from allocation and not from representation.
The control side supplies the method. Two lines of work show that priority policies derived from an LP relaxation approach the relaxation's upper bound as the number of arms grows. The projection-based Lyapunov analysis proves an $O(1/\sqrt{N})$ gap for fully heterogeneous arms with multiple actions, using an LP-priority policy with reassignment. This matters for us because every article has its own transition probabilities. The Whittle-index analysis shows an exponentially small gap when the fixed point is non-singular, with under 0.1% loss at 50 arms. In singular cases the loss is around 4%, and we will test which regime our instances fall in.
Finite-horizon single-pull bandits handle deadline-limited activation, which matches articles that must be labeled before they go stale. The closest application is multi-task inference co-scheduling. It derives "gain indices" for scheduling vision inference under compute and bandwidth limits and reports up to 26× lower discounted error than max-age-first. Its arms are physical sensing tasks valued by freshness, not taxonomic label uncertainty.
Balancing Act connects LLMs and restless bandits in the opposite direction. There the LLM writes reward functions for a health-intervention bandit, and no LLM compute is ever scheduled.
Research Program
We first build the arm model from data. A multilingual encoder is fine-tuned on Subtask 2 training data, following the discriminative classifier of bbStar, and calibrated per language. On a held-out portion of training data, we then measure how often each escalation action changes the predicted label set and by how much per-article F1 improves. We measure this as a function of confidence bucket, depth, language and topic. These empirical frequencies are the transition and reward estimates for each arm. Because article features differ, arms are heterogeneous, which is the regime the projection-based result covers.
Next we solve the corpus-level relaxation. Let $y_{i,t}(s,a)$ be the probability that article $i$ is in state $s$ and receives action $a$ at step $t$. Let $r_i(s,a)$ be its expected F1 gain, $c(a)$ the LLM cost of action $a$, and $\alpha$ the budget fraction. The relaxation is
$$ \max_{y}\ \sum_{i,t,s,a} y_{i,t}(s,a)\, r_i(s,a) \quad \text{s.t.} \quad \sum_{i,s,a} c(a)\, y_{i,t}(s,a) \le \alpha N \ \ \forall t, $$
together with per-arm flow-conservation constraints. Its optimal value upper-bounds the expected reward of any feasible policy. The deployed policy ranks arm–action pairs by the LP's priorities and fills the hard budget greedily, as in the reassignment policy of the projection-based analysis. We do not use a Whittle index, because indexability is not guaranteed with multiple actions.
For macro-F1 and rare sub-narratives, the reward weights each label by inverse training frequency. This is a linearization, and we report both the weighted objective and the official metrics.
Finally, we separate planning error from estimation error. We rerun the policy with "oracle" transitions estimated from test labels. The difference between the estimated-model policy and the oracle-model policy is the cost of not knowing the dynamics, which the literature flags as the main open problem for these guarantees.
Baselines
The naive reference is the calibrated encoder alone, with zero LLM budget. We found no reported result on Lacuna for an encoder-only Subtask 2 baseline matching this setup, so we measure it ourselves.
The quality ceiling is full escalation: H3Prompt-style staged prompting on every article, with the same LoRA-tuned LLaMA-3.2 used as our expensive action. The reference number is H3Prompt's English development result: F1 Macro Coarse 0.577 and F1 Samples Fine 0.482, with its union ensemble at 0.623 and 0.516 (H3Prompt). For Hindi, the comparable reference is ThoughtFlow's 0.569 coarse and 0.535 sample F1 (ThoughtFlow). We rerun the ceiling ourselves so that models and prompts are identical to those our actions use.
The strongest budgeted competitor is uncertainty thresholding. Each step, it sends the $\alpha N$ articles with the highest predictive entropy through full escalation. We found no reported result on Lacuna for budgeted escalation on this task.
The sharpest competitor is the myopic gain rule. It uses the same estimated transitions as our policy but ranks by one-step expected F1 gain per unit cost, essentially the gain-index idea of the co-scheduling paper without lookahead.
A per-article beam baseline keeps the top-$k$ branches at each level, in the spirit of the hyperbolic fallback and of TGSC. It is tuned to spend the same budget on average.
All methods share the encoder, the LLM, the prompts, the action costs and the data splits. Every threshold, $k$ and weight gets the same tuning budget on a development split.
Two ablations isolate the key ingredients. The first is the myopic rule itself, which removes lookahead. The second is our policy with uniform label weights, which removes the rare-label reweighting. Beating the competitors means higher sample F1 at matched budget, across at least four of five languages, with paired bootstrap confidence intervals excluding zero. Gains should be largest at $\alpha$ between 0.1 and 0.3.
Why not just…?
Why not just escalate the least confident articles? This is the most natural rule, and on a single step with a single action it is close to the right knapsack solution. It fails when confidence and value come apart. An article can be very uncertain between two sub-narratives that the large model also confuses, so escalating it buys nothing. Another can be confidently wrong at the parent level, which is the cascade-error case TGSC describes. The entropy-threshold baseline directly measures whether this matters on Task 10.
Why not just use the greedy gain-per-cost rule with the same learned transitions? This is the real threat. If gains from verification are front-loaded, the myopic rule will match the LP policy. We commit to reporting this. We will also construct a diagnostic split of articles whose correct sub-narrative sits under a low-confidence parent, where lookahead should matter most. If the LP policy shows no advantage even there, the contribution reduces to the upper bound and the estimation analysis, and we will present it that way.
Why not just do beam search inside each article? Beam search fixes irreversible pruning for one article. However, it spends the same width on easy and hard articles, and it has no notion of a shared budget. The matched-budget beam baseline tests whether reallocating budget across articles beats widening search within them. It also tests whether combining the two, by making "expand next branch" one of our actions, beats both.
Proposed Experiments
The main experiment uses SemEval-2025 Task 10 Subtask 2 in Bulgarian, English, Hindi, Portuguese and Russian. Articles arrive in simulated streaming batches, and each article has a deadline of $D$ steps. For each method we trace sample F1 and macro coarse F1 against the budget fraction $\alpha$. We report the fraction of the full-escalation gain recovered, recall on sub-narratives in the rarest training quartile, and the realized gap to the LP bound.
The first decisive check is validity: the LP value must upper-bound realized F1 under oracle transitions. If it does not under estimated transitions, that measures model misspecification and is reported as such.
The second check is scaling. We vary batch size $N$ from 25 up to the full test pool, pooling languages to reach larger $N$, and fit the gap's decay. A $1/\sqrt{N}$ trend would match the heterogeneous-arm result, and a much faster decay would indicate the non-singular regime of the Whittle analysis. We also check whether the LP solution sits on a budget boundary, which predicts which regime we are in.
The third check is the lookahead diagnostic split described above.
The fourth check transfers the same policy to Subtask 1 entity framing. The rare Protagonist and Antagonist sub-roles from cocoa give a concrete target there: nonzero F1 on those classes at a 20% budget would show that reweighting turns the budget toward exactly the classes that collapse under plain fine-tuning.
References
- GateNLP at SemEval-2025 Task 10: Hierarchical Three-Step Prompting for Multilingual Narrative Classification
- YNUzwt at SemEval-2025 Task 10: Tree-guided Stagewise Classifier for Entity Framing and Narrative Classification
- DUTtask10 at SemEval-2025 Task 10: ThoughtFlow: Hierarchical Narrative Classification via Stepwise Prompting
- cocoa at SemEval-2025 Task 10: Prompting vs. Fine-Tuning: A Multilevel Approach to Propaganda Classification
- Hierarchical Classification of Propaganda Techniques in Slavic Texts in Hyperbolic Space
- Projection-based Lyapunov method for fully heterogeneous weakly-coupled MDPs
- Exponential asymptotic optimality of Whittle index policy
- Finite-Horizon Single-Pull Restless Bandits: An Efficient Index Policy For Scarce Resource Allocation
- Computation and Communication Co-Scheduling for Timely Multi-Task Inference at the Wireless Edge
- Balancing Act: Prioritization Strategies for LLM-Designed Restless Bandit Rewards
- bbStar at SemEval-2025 Task 10: Improving Narrative Classification and Explanation via Fine Tuned Language Models