# Online Learning for Multi-Layer Hierarchical Inference under Partial and Policy-Dependent Feedback

arXiv: https://arxiv.org/abs/2603.04247 · HTML: https://mlsanity.com/paper/2603.04247/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 32 of its 49 references that are in the map.
- First posted on arXiv 4 Mar 2026.

## Builds on (most cited first, 30 of 32)

- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Measuring Massive Multitask Language Understanding](https://mlsanity.com/paper/2009.03300/) (2020)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Think you have Solved Question Answering? Try ARC, the AI2 Reasoning Challenge](https://mlsanity.com/paper/1803.05457/) (2018)
- [HellaSwag: Can a Machine Really Finish Your Sentence?](https://mlsanity.com/paper/1905.07830/) (2019)
- [Qwen Technical Report](https://mlsanity.com/paper/2309.16609/) (2023)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [GPQA: A Graduate-Level Google-Proof Q&A Benchmark](https://mlsanity.com/paper/2311.12022/) (2023)
- [MMBench: Is Your Multi-modal Model an All-around Player?](https://mlsanity.com/paper/2307.06281/) (2023)
- [MMMU: A Massive Multi-discipline Multimodal Understanding and Reasoning Benchmark for Expert AGI](https://mlsanity.com/paper/2311.16502/) (2023)
- [GPTQ: Accurate Post-Training Quantization for Generative Pre-trained Transformers](https://mlsanity.com/paper/2210.17323/) (2022)
- [Challenging BIG-Bench Tasks and Whether Chain-of-Thought Can Solve Them](https://mlsanity.com/paper/2210.09261/) (2022)
- [Towards VQA Models That Can Read](https://mlsanity.com/paper/1904.08920/) (2019)
- [MathVista: Evaluating Mathematical Reasoning of Foundation Models in Visual Contexts](https://mlsanity.com/paper/2310.02255/) (2023)
- [ChartQA: A Benchmark for Question Answering about Charts with Visual and Logical Reasoning](https://mlsanity.com/paper/2203.10244/) (2022)
- [DocVQA: A Dataset for VQA on Document Images](https://mlsanity.com/paper/2007.00398/) (2020)
- [A Survey on Evaluation of Large Language Models](https://mlsanity.com/paper/2307.03109/) (2023)
- [RouterBench: A Benchmark for Multi-LLM Routing System](https://mlsanity.com/paper/2403.12031/) (2024)
- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Online Learning with Feedback Graphs: Beyond Bandits](https://mlsanity.com/paper/1502.07617/) (2015)
- [GPTAQ: Efficient Finetuning-Free Quantization for Asymmetric Calibration](https://mlsanity.com/paper/2504.02692/) (2025)
- [OmniRouter: Budget and Performance Controllable Multi-LLM Routing](https://mlsanity.com/paper/2502.20576/) (2025)
- [An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraints](https://mlsanity.com/paper/2102.05295/) (2021)
- [Device-Cloud Collaborative LLM Inference with Multi-Modal, Multi-Task, Multi-Turn Conversations](https://mlsanity.com/paper/2502.11007/) (2025)
- [VL-RouterBench: A Benchmark for Vision-Language Model Routing](https://mlsanity.com/paper/2512.23562/) (2025)
- [CoreQ: Learning-Free Mismatch Correction and Successive Rounding for Quantization](https://mlsanity.com/paper/2602.05902/) (2026)
- [Contextual Bandits with Stochastic Experts](https://mlsanity.com/paper/1802.08737/) (2018)
- [A Lyapunov-Based Methodology for Constrained Optimization with Bandit Feedback](https://mlsanity.com/paper/2106.05165/) (2021)
- [The Case for Hierarchical Deep Learning Inference at the Network Edge](https://mlsanity.com/paper/2304.11763/) (2023)

## Abstract (arXiv)

Hierarchical inference systems route tasks across multiple computational layers, where each node may either finalize a prediction locally or offload the task to a node in the next layer for further processing. Learning optimal routing policies in such systems is challenging: inference loss is defined recursively across layers, while feedback on prediction error is revealed only at a terminal oracle layer. This induces a partial, policy-dependent feedback structure in which observability probabilities decay with depth, causing importance-weighted estimators to suffer from amplified variance. We study online routing for multi-layer hierarchical inference under long-term resource constraints and terminal-only feedback. We formalize the recursive loss structure and show that naive importance-weighted contextual bandit methods become unstable as feedback probability decays along the hierarchy. To address this, we develop a variance-reduced EXP4-based algorithm integrated with Lyapunov optimization, yielding unbiased loss estimation and stable learning under sparse and policy-dependent feedback. We provide regret guarantees relative to the best fixed routing policy in hindsight and establish near-optimality under stochastic arrivals and resource constraints. Experiments on large-scale multi-task workloads demonstrate improved stability and performance compared to standard importance-weighted approaches.