CS Paper Radar

CERBO: Certified Recourse at a Requested Rate for Gradient-Boosted Trees

Farhan Shahriyar Hossain, Taufikur Rahman Fuad, Md. Zarif Bin Hasnat, Md Abrar Jahin, Md Rizwan Parvez

cs.LG cs.AIcs.CY ·submitted 2026-11-02 14:45 UTC · v1

Abstract

Recourse-aware learning trains models so that people who receive an adverse decision can reverse it with an affordable change. For gradient-boosted decision trees (GBDTs), the existing method, RABIT, exposes a single recourse weight whose effect on the recourse rate is abrupt and data-dependent, and its training bound cannot certify recourse for any rejected individual. We present Certified Recourse Boosting (CERBO), which takes a requested recourse rate and returns a GBDT with certified actions: it tracks exact additive effort along tree paths, trains against committed boxes (a family of bounds that contains RABIT's and certifies a within-budget action for each training sample) and adjusts the weight after every tree until the certified rate meets the request. A calibration step guarantees the rate on new individuals, and the certifier runs on any tree ensemble, including XGBoost and LightGBM, in milliseconds per person without a solver. In RABIT's own experimental protocol, at equal accuracy, CERBO raises the recourse ratio from 0.90 to 0.99 on FICO and from 0.64 to 0.77 on Bail. Under additive costs on six data sets, it raises the area under the accuracy-recourse frontier in all 12 settings, and in simulated deployments it guarantees recourse to 70% of rejected individuals in 11 of 12 settings, against 2 for RABIT.

Comment
23 pages, 6 figures, 15 tables

Closest papers

Nearest neighbours by meaning across the whole index.

CRAFT-GBM: Selecting Best Features for Gradient-Boosted Machine Learning

cs.LG math.ST ·2026-11-09 ·Basil Kuok, Yi Zhou, Yao Xuan, Shuping Li, Ke-Wei Huang
similarity 0.61
Abstract

Feature subsampling is used to accelerate gradient-boosted trees, yet standard approaches fix the feature count in advance and largely ignore the split-gain evidence accumulated during training. We introduce CRAFT-GBM (Confidence-Ranked Adaptive Feature Tracking), a native LightGBM extension that uses this evidence to adapt which---and, by default, how many---features are searched each boosting round. CRAFT-GBM transforms root-split gains into bounded observations and constructs joint time-uniform bounds valid under adaptive, non-stationary training histories. In its default endogenous mode, after initialization, CRAFT-GBM retains exactly the features that cannot yet be ruled out as best, letting the selected feature-set size $K_t$ emerge from training history rather than a pre-specified fraction. With probability at least $1-δ$, every feature with the largest expected gain is retained jointly across all rounds after initialization. When a feature fraction $f$ is specified instead, CRAFT-GBM ranks features by their interval point estimates and provides an approximate top-$K$ guarantee for feature budget $K_f$. We implement CRAFT-GBM within LightGBM while preserving its native feature-bundling representation, and evaluate it across 14 public and synthetic dataset families and four noise-augmented settings. In the fully endogenous setting, CRAFT-GBM reduces per-fit training time by 39.74\% with 1.04\% lower test loss in the geometric mean across all 18 RQ1 experiments. Under pre-specified feature fraction $f$, Exogenous CRAFT-GBM also yields aggregate training-time reductions up to 13.52 percentage points larger than random feature subsampling, with no increase in aggregate test loss relative to full-feature LightGBM. Accumulated training evidence can thus support adaptive feature search with statistical guarantees while retaining the practical advantages of native gradient boosting.

0.14

Can a Cacheable Decision Model Follow Rules?

cs.AI cs.CLcs.LG ·2026-09-29 ·Dushyant Rajput, Nirdesh Chauhan, Siddharth Kosaraju
similarity 0.59
Abstract

Certo is a small non-generative decision model (Qwen3-4B): it scores candidate actions from their text and returns a probability, instead of generating an answer. The accurate design reads the state, the rules, and each candidate together (a joint scorer), so cost grows with the menu. Independent encoding lets each candidate be encoded once and reused across states (about 5x cheaper at 77 candidates), but separates state from candidate. We ask how much rule-sensitivity survives that move, and whether it can be trained back. Four experiments on Certo: (1) the tested conversion to cacheable scoring loses rule-sensitivity (recall@1 1.00 -> 0.24) while the joint scorer holds 1.00, and a shortlist+rerank rescue fails; (2) targeted counterfactual supervision restores strong performance on held-out synthetic rule tasks (paraphrase, counterfactual, composition; reproducible across seeds), though we do not isolate whether predictions depend on the supplied rule; (3) on real rules the added benefit is not established -- after fixing a truncation confound, the joint scorer wins significantly on the short tier (0.861 vs 0.500) and directionally on the hard tier (0.655 vs 0.483, n=29); (4) a matched cross-domain real-prose mixture did not help and reduced contract accuracy (-9.3, -16.2 points). A cacheable encoder can be made rule-sensitive on its training distribution, but transfer to unseen-source real rules is not established; the joint scorer keeps an edge at the cost of caching.

0.51

TreeWalker: Partial Evaluation for Grouped Tree-Ensemble Inference

cs.LG cs.PFcs.PL ·2026-10-02 ·Durmus Karatay, Richard Newman
top venuebenchmarktheorycode/data similarity 0.58
Abstract · 23 pages, 9 figures, 11 tables. Accepted at NeurIPS 2026. Code and data: https://github.com/Shopify/treewalker/tree/neurips2026-final

Many prediction tasks evaluate a trained tree ensemble on groups of rows that share feature values: discrete-time survival models expand each patient into $G$ time steps, click-through-rate models score every item in a search session, and scenario analyses vary a few inputs while holding the rest fixed. Standard inference treats each row independently and ignores this input-side correlation. We present TreeWalker, which instantiates partial evaluation for grouped tree-ensemble inference: constant features are static, varying features dynamic. TreeWalker walks each tree once per group, partitions a row bitmask at varying splits, and skips empty subtrees via an unsplit shortcut. It reads standard LightGBM and XGBoost models; training is unchanged. We prove a structural work decomposition: per-tree work splits into the constant-projected subtree size $|T_c|$, $G$ leaf writes, and a predicate-mask provisioning cost $Q$. For the trace evaluator, per-row work approaches $(d_v+1)/(d+1)$ as $G \to \infty$, giving asymptotic speedup $1/(1-\barρ_G)$. On Intel, TreeWalker is ${\sim}3\times$ faster than a row-independent traversal at the reference model size ($T{=}500$, $L{=}8$; $G{=}16$ for SUPPORT/FLCHAIN and empirical groups for Expedia) and $7.7$--$9.1\times$ faster at $G{=}128$ on the survival datasets; on Arm, $2.5$--$2.9\times$ and $5.5$--$6.0\times$. On a scenario-analysis benchmark it is faster in all $16$ configurations on both machines. For f64 models, outputs match treelite GTIL up to tree-ordering roundoff; for f32 models, TreeWalker's f64 leaf accumulation is closer than native f32 to an exactly rounded reference on every audited row.

0.53

DRACO: Fine-Grained Credit Assignment with Dynamic Rubrics for Long-Horizon Agent Training

cs.AI cs.LGcs.SE ·2026-09-03 ·Shubham Gandhi, Saurabh Goyal, Kiran Kate, Yara Rizk
code/datahighly cited similarity 0.58
Abstract

Reinforcement Learning from Verifiable Rewards works well when a task has a programmatic checker, but most long-horizon agent domains have none. We work in the outcome-blind setting, where ground-truth success signals are not available. Multi-criteria rubrics are a popular way to supply such a reward; they are scored once per trajectory, but a single scalar is a poor signal across tens of steps. We propose DRACO: Distributing Rubric-based Advantage for Credit Optimization. It generates rubrics dynamically during training to track the policy's evolving capability, scores those rubrics once per completed trajectory, and redistributes that judgment over the steps responsible for annotated rubrics to produce differentiated per-step advantages in GRPO. The redistribution is closed-form and does not introduce any trained attribution module. On AppWorld, DRACO gains 15.9 points over the base model and 5.3 points over GRPO trained with a sparse ground-truth reward, despite not using any verifiers itself. On out-of-domain Tau-Bench, it gains 5.3 points over the base model even without a frontier judge, beating both ground-truth-reward training and other rubric-based training settings. The code for DRACO is available at https://github.com/IBM/draco.

0.55

Patching the Blind Spots: Reversible LLM Rule Overlay for Frozen Fraud Detectors

cs.LG cs.AIcs.CL ·2026-11-05 ·Bo Qu, Zhurong Wang, Frank Zahradnik, Ming Ouyang
benchmarkhot direction similarity 0.58
Abstract · 12 pages, 1 figure, 8 tables

Gradient-boosted trees dominate industrial tabular fraud classification, but even a well-trained model has blind spots, and retraining a deployed model is not always safe. We bring LLM reasoning to patching such a model without modifying it: LLMs read its tree digest and SHAP attributions, reason about the fraud it misses, and propose rules anchored on features it underweights, screened and calibrated into a reversible log-lift overlay at the production cut-off. Single-LLM benefit is high-variance and inverts between datasets, so we pool three diverse backbones by logit averaging, trading peak gain for a bounded worst case. On an experimental detector trained on sampled, selection-biased real-world e-commerce data, tuned continued training regresses, whereas the overlay gains on average +2.26% recall at equal precision ($Δ$R@P) and +1.60% precision at equal recall ($Δ$P@R). Replayed offline on a legacy production detector, the overlay, calibrated on one month and frozen, stays more precise at equal recall for seven months (+5.64% $Δ$P@R). On seven bias-shift variants of a public benchmark it raises $Δ$P@R on all and keeps $Δ$R@P near neutral. LLM reasoning over a model's diagnostics can improve a deployed tabular classifier through readable predicates naming the fraud they cover.

0.34

Algorithmic Recourse Under Competition

cs.LG cs.AI ·2026-09-30 ·Shahin Jabbari
theory similarity 0.58
Abstract

Algorithmic recourse provides individuals who have received undesirable outcomes from machine learning models with suggestions for minimum-cost improvements to achieve the desired outcome. A central assumption when computing recourse is that the decision rule remains fixed throughout the recourse implementation phase. We challenge this assumption in settings where individuals compete for limited resources. In such settings, widespread recourse implementation can change the acceptance threshold even when the scoring model that is used to evaluate individuals remains the same. This change in acceptance threshold can, in turn, invalidate the original recourse recommendations (i.e., following the recourse may not lead to the desired outcome). To address this problem, we introduce a framework called recourse under competition that jointly optimizes for recommendation recipients and the recommended score target they need to satisfy to balance the recourse cost and post-shift validity among initially rejected individuals. We develop an algorithm based on the Implicit Function Theorem and empirically analyze its performance. Experiments on synthetic and real datasets show that personalized score targets can achieve higher validity, albeit at a higher cost. In contrast, common score targets generally offer favorable cost-validity trade-offs for lower to medium validity values.

0.47

CERO: Where and When to Allocate Rollouts for RL Post-Training

cs.LG cs.AI ·2026-10-07 ·Yiming Zong, Yige Wang, Xing Hu, Jiashuo Jiang, Zuo-Jun Max Shen
similarity 0.57
Abstract

Adaptive rollout methods for group-relative reinforcement learning typically allocate a fixed per-update budget across prompts. We instead study how to coordinate a finite rollout budget over the entire training horizon. We formulate this problem using a concave surrogate utility of cumulative prompt exposure and introduce CERO, an online primal dual scheduler for prompt admission and budget pacing. In our experiments, each admitted prompt receives a fixed-size response group. CERO instead adapts which prompts are selected, how often they are revisited across rounds, and how many groups are generated in each round. A compact Fenchel representation linearizes the dependence on cumulative exposure, while projected online gradient descent updates prompt-specific supporting slopes and a shared budget price using reward-variation feedback and budget deviations. We establish pathwise guarantees for the surrogate allocation objective against fixed-rate and same-path time-varying benchmarks, with explicit terms for proxy discrepancy and rate variation. Under matched training-response budgets, CERO attains the highest avg@16 macro-average on each of three backbones across five mathematical reasoning benchmarks. Mechanistic analyses link CERO's prompt choices to within-group reward contrast, while multi-seed ablations show gains from adaptive pacing over both uniform and preset spending schedules.

0.23

Where Tree Ensembles Decide: Structural Local Explanation with Decision Predicate Graphs

cs.LG ·2026-11-13 ·Sylvio Barbon Junior, Luca Longo
hot direction similarity 0.57
Abstract · Code, data and results: https://doi.org/10.5281/zenodo.24201497. Supplementary material attached as an ancillary file

Tree ensembles are among the most accurate models for tabular data, yet the computation behind a single prediction is spread over hundreds of decision rules. Feature attributions and counterfactuals explain such predictions through the influence of features or a change of the input, leaving open which of the thresholds applied by the trees a prediction responds to, while structural explanations compress these rules and lose the trees behind them. To address this gap, we propose a local Decision Predicate Graph (local DPG), which gathers the rules executed for a sample into a verifiable record of the computation, with a class support that reproduces every explained prediction. From these rules we select the critical predicate, the executed predicate whose crossing is estimated to move the model most strongly toward a chosen class, which offers the user a concrete threshold and the trees that share it, without an external explainer. Across 16 datasets and four ensemble families, it separates differently predicted neighbours better than random and nearest-threshold predicates. A single crossing recovers the true class in 46-69% of wrong predictions, against 29-50% when the same rule is applied to the feature ranked first by TreeSHAP, a measure close to the selection criterion, and on planted faults it finds the faulty threshold in 46-71% of the resulting errors, against 6-21% at random. Although training-free edits of these predicates did not reduce the error on unseen data, the critical predicate complements attributions and counterfactuals by naming where a prediction can be changed.

0.32