Token Budget Allocation

Follow this topic Ask about this topic

Momentum

38 papers in the last four weeks, up 23% on the four weeks before. 0.4% of all new papers.

Jul 13Week of Sep 28

Latest papers 267

Apr 29, 2026cs.CL

OCR-Memory: Optical Context Retrieval for Long-Horizon Agent Memory

Autonomous LLM agents increasingly operate in long-horizon, interactive settings where success depends on reusing experience accumulated over extended histories. However, existing agent memory systems are fundamentally constrained by text-context budgets: storing or revisiting raw trajectories is prohibitively token-expensive, while summarization and text-only retrieval trade token savings for information loss and fragmented evidence. To address this limitation, we propose Optical Context Retrieval Memory (OCR-Memory), a memory framework that leverages the visual modality as a high-density representation of agent experience, enabling retention of arbitrarily long histories with minimal prompt overhead at retrieval time. Specifically, OCR-Memory renders historical trajectories into images annotated with unique visual identifiers. OCR-Memory retrieves stored experience via a \emph{locate-and-transcribe} paradigm that selects relevant regions through visual anchors and retrieves the corresponding verbatim text, avoiding free-form generation and reducing hallucination. Experiments on long-horizon agent benchmarks show consistent gains under strict context limits, demonstrating that optical encoding increases effective memory capacity while preserving faithful evidence recovery.

Jinze Li, Yang Zhang, Xin Yang +5

The University of Hong Kong · University of North Texas · University of Tsukuba +1

History Token Budget Allocation

Apr 28, 2026cs.LG

Budget-Constrained Causal Bandits: Bridging Uplift Modeling and Sequential Decision-Making

Treatment allocation under budget constraints is a central challenge in digital advertising: advertisers must decide which users to show ads to while spending a limited budget wisely. The standard approach follows a two-stage offline pipeline - first collect historical data to estimate heterogeneous treatment effects (HTE), then solve a constrained optimization to allocate the budget. This works well with abundant data, but fails in cold-start settings such as new campaigns, new markets, or new customer segments where little historical data exists. We propose Budget-Constrained Causal Bandits (BCCB), an online framework that learns which users respond to ads while simultaneously spending the budget, making treatment decisions one user at a time. BCCB unifies three components into a single sequential process: learning individual-level ad effectiveness, exploring users whose response is uncertain, and pacing the budget over time. We evaluated on the Criteo Uplift dataset, a large-scale advertising dataset from a real randomized controlled trial. Our key finding is a data-efficiency crossover: offline methods require approximately 10,000 historical observations to produce reliable results, while BCCB operates effectively from the very first user. Furthermore, BCCB exhibits 3-5x lower performance variance between runs, making it more practical for real campaign planning. Among purely online methods, BCCB consistently outperforms standard Thompson Sampling, budgeted Thompson Sampling, and greedy HTE estimation across all budget levels tested.

Abhirami Pillai

utdallas

Ads Treatment Allocation Token Budget Allocation Heterogeneous Treatment Effects Sequential Decision Making Rise

Apr 28, 2026econ.EM

Auditing Marketing Budget Allocation with Hindsight Regret

Organizations routinely make strategic budget allocations under operational constraints, but often lack a principled way to assess whether realized allocations were close to the best feasible choices in hindsight. We present a retrospective auditing framework based on hindsight regret, defined as the opportunity cost of the realized allocation relative to a constraint-faithful benchmark under the same budget and stability guardrails. The framework estimates regime-specific spend--response functions from historical logs, computes feasible hindsight allocations via constrained optimization, and propagates uncertainty through Monte Carlo evaluation to produce regret distributions, expected lift, and probability-of-improvement summaries. This separates allocation inefficiency from uncertainty in the estimated response surfaces. Experiments on real marketing allocation logs show that the framework yields interpretable post-hoc diagnostics and reveals a practical trade-off between allocation flexibility and detectability: moderate feasible reallocations often capture most measurable gain, while larger shifts move into weak-support regions with higher uncertainty. The result is a practical method for auditing historical budget decisions when online experimentation is costly or infeasible.

Nilavra Pathak, Olivier Jeunen, Eric Lambert

Expedia Group · New York, USA · aampe +2

Token Budget Allocation Model Auditing Bayesian Experimental Design Hindsight

Apr 27, 2026cs.CL

Dual-Track CoT: Budget-Aware Stepwise Guidance for Small LMs

Large Language Models (LLMs) solve many reasoning tasks via chain-of-thought (CoT) prompting, but smaller models (about 7 to 8B parameters) still struggle with multi-step reasoning under tight compute and token budgets. Existing test time reasoning methods such as self consistency (sampling multiple rationales and voting), Tree-of-Thoughts (search over intermediate thoughts), and critique revise loops improve performance, but often at high token cost and without fine-grained step-level control. This project1 aims to address that gap: can Small Language Models (SLMs) reason reliably using the same or fewer tokens? This question is both scientific and practical. Scientifically, it probes whether process supervision and simple test-time controls (such as token budgets and rejection of redundant steps) can substitute for model scale or large sampling counts. Practically, many deployments (on-device, low-latency, or cost-constrained settings) cannot afford huge models or dozens of sampled rationales per query. A method that improves SLM reasoning at fixed cost would therefore be directly useful.

Sagnik Chatterjee, Atharva Patil, Sricharan Ramesh

LLM Reasoning Strategies Small Large Language Models Chain-of-Thought Reasoning Token Budget Allocation Test Time Guidance

Apr 24, 2026cs.LG

Spend Less, Fit Better: Budget-Efficient Scaling Law Fitting via Active Experiment Selection

Scaling laws are used to plan multi-million-dollar training runs, but fitting those laws can itself cost millions. In modern large-scale workflows, assembling a sufficiently informative set of pilot experiments is already a major budget-allocation problem rather than a routine preprocessing step. We formulate scaling-law fitting as budget-aware sequential experimental design: given a finite pool of runnable experiments with heterogeneous costs, choose which runs to execute so as to maximize extrapolation accuracy in a high-cost target region. We then propose an uncertainty-aware method for sequentially allocating experimental budget toward the runs most useful for target-region extrapolation. Across a diverse benchmark of scaling-law tasks, our method consistently outperforms classical design-based baselines, and often approaches the performance of fitting on the full experimental set while using only about 10% of the total training budget. Our code is available at https://github.com/PlanarG/active-sl.

Sijie Li, Shanda Li, Haowei Lin +3

Peking University · Carnegie Mellon University · Datadog

Bayesian Experimental Design Scaling Laws Token Budget Allocation Extrapolation

Apr 24, 2026cs.LG

Adaptive Head Budgeting for Efficient Multi-Head Attention

Multi-head attention enables Transformers to capture diverse representations, but all attention heads are typically activated for every input, regardless of task complexity. For coarse-grained tasks such as text classification, where relevant information is often global, this fixed allocation can introduce unnecessary computation. We propose BudgetFormer, a Transformer architecture that dynamically allocates attention heads on a per-input basis. The model learns both a head budget and a relevance distribution to select the most informative heads. To support effective head selection, we introduce a training strategy that balances exploration and exploitation. Experiments on text classification tasks show that BudgetFormer reduces FLOPs and memory usage while matching or surpassing the performance of standard multi-head attention. These results highlight adaptive head allocation as an effective approach to improving Transformer efficiency and performance.

Bilal Faye, Abdoulaye Mbaye, Hanane Azzag +1

Multi-Head Attention Transformer Architectures Token Budget Allocation Relevance

Apr 24, 2026cs.CL

RouteLMT: Learned Sample Routing for Hybrid LLM Translation Deployment

Large Language Models (LLMs) have achieved remarkable performance in Machine Translation (MT), but deploying them at scale remains prohibitively expensive. A widely adopted remedy is the hybrid system paradigm, which balances cost and quality by serving most requests with a small model and selectively routing a fraction to a large model. However, existing routing strategies often rely on heuristics, external predictors, or absolute quality estimation, which fail to capture whether the large model actually provides a worthwhile improvement over the small one. In this paper, we formulate routing as a budget allocation problem and identify marginal gain, i.e., the large model's improvement over the small model, as the optimal signal for budgeted decisions. Building on this, we propose \textbf{RouteLMT} (routing for LLM-based MT), an efficient in-model router that predicts this expected gain by probing the small translators prompt-token representation, without requiring external models or hypothesis decoding. Extensive experiments demonstrate that our RouteLMT outperforms heuristics, quality/difficulty estimation baselines, achieving a superior quality-budget Pareto frontier. Furthermore, we analyze regression risks and show that a simple guarded variant can mitigate severe quality losses.

Yingfeng Luo, Hongyu Liu, Dingyang Lin +6

School of Computer Science and Engineering, Northeastern University, Shenyang, China · NiuTrans Research, Shenyang, China

Large Language Model Routing Translation Quality Token Budget Allocation

Apr 23, 2026cs.AI

Tool Attention Is All You Need: Dynamic Tool Gating and Lazy Schema Loading for Eliminating the MCP/Tools Tax in Scalable Agentic Workflows

The Model Context Protocol (MCP) has become a common interface for connecting large language model (LLM) agents to external tools, but its reliance on stateless, eager schema injection imposes a hidden per-turn overhead the MCP Tax or Tools Tax that practitioner reports place between roughly 10k and 60k tokens in typical multi-server deployments. This payload inflates the key-value cache, is associated with reasoning degradation as context utilization approaches published fracture points around 70%, and turns token budgets into a recurring operational cost. We introduce Tool Attention, a middleware-layer mechanism that generalizes the "Attention Is All You Need" paradigm from self-attention over tokens to gated attention over tools. Tool Attention combines (i) an Intent Schema Overlap (ISO) score from sentence embeddings, (ii) a state-aware gating function enforcing preconditions and access scopes, and (iii) a two-phase lazy schema loader that keeps a compact summary pool in context and promotes full JSON schemas only for top-k gated tools. We evaluate on a simulated 120-tool, six-server benchmark whose per-server token counts are calibrated to public audits of real MCP deployments. In this simulation, Tool Attention directly reduces measured per-turn tool tokens by 95.0% (47.3k -> 2.4k) and raises effective context utilization (a token-ratio quantity) from 24% to 91%. End-to-end figures for task success, latency, cost, and reasoning quality are reported as projections derived from the measured token counts combined with published deployment telemetry; they are not measured on live LLM agents, and we mark projected values explicitly throughout. Taken together, the results support a simple thesis: protocol-level efficiency, not raw context length, is a binding constraint on scalable gentic systems. The code for this work is accessible at https://github.com/asadani/tool-attention

Anuj Sadani, Deepak Kumar

Model Context Protocol Gating Agentic Workflows Agentic Token Budget Allocation

Apr 22, 2026cs.LG

LKV: End-to-End Learning of Head-wise Budgets and Token Selection for LLM KV Cache Eviction

Long-context inference in Large Language Models (LLMs) is bottlenecked by the linear growth of Key-Value (KV) cache memory. Existing KV cache compression paradigms are fundamentally limited by heuristics: heuristic budgeting relies on statistical priors rather than task objectives, causing resource misallocation, while heuristic selection relies on coupled query-key interactions or static inductive biases (e.g., attention sinks). To address this limitation, we introduce LKV (Learned KV Eviction), which formulates KV compression as an end-to-end differentiable optimization problem. LKV integrates LKV-H to learn task-optimized global budgets, and LKV-T to derive intrinsic KV importance without materializing attention matrices. This design bypasses heuristic proxies, strictly aligning compression with task objectives. Extensive evaluations demonstrate that LKV achieves state-of-the-art performance on both LongBench and RULER benchmarks at high compression rates. In particular, on LongBench, LKV achieves near-lossless performance with only 15% KV cache retention. Crucially, our analysis identifies learned budgeting as the dominant driver of fidelity, demonstrating that data-driven allocation is essential to overcome the limitations of hand-crafted heuristics.

Enshuai Zhou, Yifan Hao, Chao Wang +7

University of Science and Technology of China, Hefei, China · State Key Lab of Processors, Institute of Computing Technology, CAS, Beijing, China · University of Chinese Academy of Sciences, Beijing, China

Key-Value Cache Compression Large Language Model Compression Question-Answering Benchmarks Token Budget Allocation Inductive Bias

Apr 22, 2026cs.LG

Energy-Based Open-Set Active Learning for Object Classification

Active learning (AL) has emerged as a crucial methodology for minimizing labeling costs in deep learning by selecting the most valuable samples from a pool of unlabeled data for annotation. Traditional AL operates under a closed-set assumption, where all classes in the dataset are known and consistent. However, real-world scenarios often present open-set conditions in which unlabeled data contains both known and unknown classes. In such environments, standard AL techniques struggle. They can mistakenly query samples from unknown categories, leading to inefficient use of annotation budgets. In this paper, we propose a novel dual-stage energy-based framework for open-set AL. Our method employs two specialized energy-based models (EBMs). The first, an energy-based known/unknown separator, filters out samples likely to belong to unknown classes. The second, an energy-based sample scorer, assesses the informativeness of the filtered known samples. Using the energy landscape, our models distinguish between data points from known and unknown classes in the unlabeled pool by assigning lower energy to known samples and higher energy to unknown samples, ensuring that only samples from classes of interest are selected for labeling. By integrating these components, our approach ensures efficient and targeted sample selection, maximizing learning impact in each iteration. Experiments on 2D (CIFAR-10, CIFAR-100, TinyImageNet) and 3D (ModelNet40) object classification benchmarks demonstrates that our framework outperforms existing approaches, achieving superior annotation efficiency and classification performance in open-set environments.

Zongyao Lyu, William J. Beksi

The University of Texas at Arlington, Arlington TX 76019, USA

Pool-Based Active Learning Active Learning Open-Set Recognition Unlabeled Data Token Budget Allocation

Apr 21, 2026cs.LG

Budgeted Online Influence Maximization

We introduce a new budgeted framework for online influence maximization, considering the total cost of an advertising campaign instead of the common cardinality constraint on a chosen influencer set. Our approach better models the real-world setting where the cost of influencers varies and advertisers want to find the best value for their overall social advertising budget. We propose an algorithm assuming an independent cascade diffusion model and edge level semi-bandit feedback, and provide both theoretical and experimental results. Our analysis is also valid for the cardinality constraint setting and improves the state of the art regret bound in this case.

Pierre Perrault, Jennifer Healey, Zheng Wen +1

Adobe Research, San Jose, CA · ENS Paris-Saclay · DeepMind +1

Influence Function Ads Token Budget Allocation Cardinality

Apr 21, 2026cs.AI

GRASPrune: Global Gating for Budgeted Structured Pruning of Large Language Models

Large language models (LLMs) are expensive to serve because model parameters, attention computation, and KV caches impose substantial memory and latency costs. We present GRASPrune, a structured pruning framework applied after pretraining that jointly prunes FFN channels and KV head groups under a single global budget. Instead of learning importance scores without constraints and applying the budget only after training, GRASPrune learns lightweight gate scores with a projected straight-through estimator that enforces a hard mask satisfying the budget at every step while keeping the backbone weights frozen. After the mask is fixed, we calibrate scaling factors on the retained units to mitigate scale mismatch caused by pruning, and fold these factors into the pruned weights to obtain a smaller dense checkpoint with no extra parameters at inference. On LLaMA-2-7B, GRASPrune removes 50% of parameters and achieves 12.18 perplexity on WikiText-2 while maintaining competitive average zero-shot accuracy on five benchmarks, using four epochs on 512 unlabeled calibration sequences on a single NVIDIA A100 80GB GPU without any full model fine-tuning.

Ziyang Wang, Jiangfeng Xiao, Chuan Xiao +3

Beijing Institute of Technology, Zhuhai · Shenzhen University · Osaka University

Large Language Model Compression Unstructured Pruning Structured Pruning Token Budget Allocation Gating

Apr 18, 2026cs.LG

R&F-Inventory: A Large-Scale Dataset for Monotonic Inventory Estimation in Reach and Frequency Advertising

Reach and Frequency (R&F) contract advertising is an important form of widely used brand advertising. Unlike performance advertising, R&F contracts emphasize controllable delivery of UV and PV under given targeting, scheduling, and frequency control constraints. In practical systems, advertisers typically need to view the UV, PV change curves at different budget levels in real time when creating an R&F contract. However, most existing publicly available advertising datasets are based on independent samples, lacking a characterization of the core structure of the "budget-performance curve" (including UV and PV) in R&F contracts.This paper proposes and releases a large-scale R&F contract inventory estimation dataset. This dataset uses the R&F contract context consisting of "targeting-scheduling-frequency control" as the basic context, providing observations of UV and PV corresponding to multiple budget points within the same context, thus forming a complete budget-performance curve. The dataset explicitly includes a time-window-based frequency control mechanism (e.g.,"no more than 3 times within 5 days") and naturally satisfies the monotonicity and diminishing marginal returns characteristics in the budget and scheduling dimensions. We further derive the theoretical maximum exposure ceiling and use it as a consistency check to evaluate data quality and the feasibility of model predictions. Using this data set, this paper defines two standardized benchmark tasks: single-point performance prediction and reconstruction of budget-performance curves, and provides a set of reproducible baseline methods and evaluation protocols. This dataset can support systematic research on problems such as structural constraint learning, monotonic regression, curve consistency modeling, and R&F contract planning.The code for our experiments can be found at https://github.com/pengyunshan/RF-Inventory.

Yunshan Peng, Ji Wu, Wentao Bai +6

Kuaishou Technology, Beijing, China

Ads Inventory Control Maximization Token Budget Allocation

Apr 16, 2026cs.CV

VisPCO: Visual Token Pruning Configuration Optimization via Budget-Aware Pareto-Frontier Learning for Vision-Language Models

Visual token pruning methods effectively mitigate the quadratic computational growth caused by processing high-resolution images and video frames in vision-language models (VLMs). However, existing approaches rely on predefined pruning configurations without determining whether they achieve computation-performance optimality. In this work, we introduce , a novel framework that formulates visual token pruning as a Pareto configuration optimization problem to automatically identify optimal configurations. Our approach employs continuous relaxation and straight-through estimators to enable gradient-based search, solved via the Augmented Lagrangian method. Extensive experiments across 8 visual benchmarks demonstrate that effectively approximates the empirical Pareto frontier obtained through grid search and generalizes well across various pruning methods and VLM architectures. Furthermore, through learnable kernel functions, we investigate layer-wise pruning patterns and reveal that multi-step progressive pruning captures VLMs' hierarchical compression structure, achieving superior accuracy-efficiency trade-offs compared to single-layer approaches.

Huawei Ji, Yuanhao Sun, Yuan Jin +4

Shanghai Jiao Tong University, Shanghai, China · University of Edinburgh, Edinburgh, UK

Visual Token Pruning Recent Vision-Language Models Structured Pruning Pareto Frontier Token Budget Allocation Artificial Intelligence Search

Apr 12, 2026cs.LG

Query Lower Bounds for Diffusion Sampling

Diffusion models generate samples by iteratively querying learned score estimates. A rapidly growing literature focuses on accelerating sampling by minimizing the number of score evaluations, yet the information-theoretic limits of such acceleration remain unclear. In this work, we establish the first score query lower bounds for diffusion sampling. We prove that for

d

-dimensional distributions, given access to score estimates with polynomial accuracy

\varepsilon=d^{-O(1)}

(in any

L^p

sense), any sampling algorithm requires

\widetildeΩ(\sqrt{d})

adaptive score queries. In particular, our proof shows that, within any polynomial total-query budget, successful sampling requires searching over

\widetildeΩ(\sqrt{d})

distinct noise levels, providing a formal explanation for why multiscale noise schedules are necessary in practice.

Zhiyang Xun, Eric Price

UT Austin

Diffusion Sampling Optimal Sample Complexity Uncertainty Score Lower Bounds Information-Theoretic Limits Queries+1

Mar 12, 2026cs.CV

HiAP: A Multi-Granular Stochastic Auto-Pruning Framework for Vision Transformers

Vision Transformers require significant computational resources and memory bandwidth, severely limiting their deployment on resource-constraint hardware. Most structured pruning methods reduce theoretical cost effectively, yet they typically operate at a single structural granularity and depend on multi-stage pipelines with importance ranking, auxiliary solvers or post-hoc magnitude thresholding, followed by a separate fine-tuning phase to recover accuracy. We propose Hierarchical Auto-Pruning (HiAP), which casts ViT pruning as a single budget-aware learning problem and jointly allocates sparsity across four granularities in one end-to-end phase. HiAP introduces stochastic Gumbel-Sigmoid gates at macro level (attention heads and FFN blocks) and micro level (intra-head dimensions and FFN neurons), and optimizes them against the task loss together with an analytical MAC cost term. The budget coefficient steers the network to a target compute level while the gates gradually harden into a dense, smaller sub-network at convergence. It does not require importance heuristics, ranking metrics, auxillary solvers or secondary fine-tuning. On ImageNet with DeiT small, HiAP automatically discovers hetergenous architectures, pruning depths, heads, and width by different amount across layers, and reaches competitive accuracies against substantially more complex pruning pipelines at comparable compute from a single training run.

Andy Li, Aiden Durrant, Milan Markovic +1

School of Natural and Computing Sciences, University of Aberdeen · School of Computing Sciences, University of East Anglia · Department of Physics and Technology, UiT The Arctic University of Norway

Self-Supervised Vision Transformers Vision Transformer Transformer Architectures Feed-Forward Token Budget Allocation

Jan 29, 2026cs.AI

ShardMemo: Scope-Before-Routing for Agentic Memory Retrieval

Agentic systems accumulate persistent memory across sessions, tools, and tasks, and a later request must retrieve from it under two distinct constraints: which memories it is permitted to access, and which are relevant under a limited search budget. Existing memory systems handle access scope in two flawed ways: applying scope after retrieval wastes probe budget on inadmissible memories, while treating scope as a learned ranking feature makes a hard constraint depend on router quality. We present SHARD-MEMO, an agentic memory system built on scope-before-routing: metadata predicates first identify the admissible shards, and a learned router then selects a small number of them for shard-local approximate nearest neighbor retrieval. Given the supplied scope predicate and metadata, this separates hard admissibility from learned relevance ranking, so inadmissible shards cannot consume shard-probe budget. We evaluate on LoCoMo, HotpotQA, and ToolBench, covering conversational, long-context, and procedural memory. Under matched supervision and fixed budgets, SHARDMEMO improves over a learned router baseline by roughly +3 F1 on LoCoMo; in end-to-end LoCoMo evaluation it improves over the strongest evaluated memory baseline by up to +6.8 F1, with gains on HotpotQA and ToolBench.

Yang Zhao, Chengxiao Dai, Mengying Kou +2

Anonymous

Agentic Memory Retrievers Agentic Metadata Token Budget Allocation

Jan 29, 2026cs.LG

More Bang for the Buck: Improving the Inference of Large Language Models at a Fixed Budget using Reset and Discard (ReD)

The performance of large language models (LLMs) on verifiable tasks is usually measured by pass@k, the probability of answering a question correctly at least once in k trials. At a fixed budget, a more suitable metric is coverage@cost, the average number of unique questions answered as a function of the total number of attempts. We connect the two metrics and show that the empirically-observed power-law behavior in pass@k leads to a sublinear growth of the coverage@cost (diminishing returns). To solve this problem, we propose Reset-and-Discard (ReD), a query method of LLMs that increases coverage@cost for a given budget, regardless of the pass@k form. Moreover, given a pass@k, we can quantitatively predict the savings in the total number of attempts using ReD. If pass@k is not available for the model, ReD can infer its power-law exponent. Experiments on three LLMs across coding (HumanEval), math (GSM8K), and reasoning (MMLU-Pro) benchmarks demonstrate that ReD substantially reduces the required attempts, tokens, and USD cost to reach a desired coverage, while also offering an efficient way to measure inference power-laws. ReD's advantage is maintained for imperfect verifiers and outperforms the tested allocation baselines.

Sagi Meir, Tommer D. Keidar, Noam Levi +2

School of Chemistry, Tel Aviv University, Tel Aviv 6997801, Israel · The Center for Physics and Chemistry of Living Systems, Tel Aviv University, Tel Aviv 6997801, Israel · School of Physics and Astronomy, Tel Aviv University, Tel Aviv 6997801, Israel +1

LLM Inference Optimization Token Budget Allocation

Dec 25, 2025stat.ML

Nonnegative matrix factorizations and related compositional models: Equivalence, identifiability, and an application on the grain-size analysis of sediments

Across fields such as machine learning, social science, and geology, considerable attention has been given to models that factorize a nonnegative matrix into the product of two or three matrices, subject to nonnegative or row-sum-to-1 constraints. Although these models are to a large extent similar or even equivalent, they are presented under different names, and their similarity is not well known. This paper highlights similarities among five models, latent budget analysis (LBA) and latent class analysis (LCA) from social science, end-member analysis (EMA) from geology, probabilistic latent semantic analysis (PLSA) and nonnegative matrix factorization (NMF) from machine learning. We focus on the identifiability of these models. We prove that the solution of LBA, EMA, LCA, PLSA is unique if and only if the solution of NMF is unique. Consequently, existing uniqueness theorems for NMF directly apply to LBA, EMA, LCA, PLSA, and vice versa. We also provide a brief review of algorithms for the estimation of these models. We illustrate NMF on a sedimentary grain-size distribution dataset from sedimentary geology, and end the paper with a discussion of closely related model: archetypal analysis.

Qianqian Qi, Peter G. M. van der Heijden, Maarten A. Prins

Hangzhou Dianzi University, China · Utrecht University, the Netherlands · University of Southampton, UK +1

Nonnegative Matrix Factorization Identifiability Similarity and Metrics Token Budget Allocation

Nov 17, 2025cs.LG

FuseSampleAgg: One-Pass Neighborhood Estimation for Budgeted Knowledge-Graph Refresh and Validation

Operational knowledge-graph (KG) pipelines in networking and cybersecurity increasingly need to refresh embeddings under strict time, memory, and audit budgets, especially as curated feeds and LLM-assisted extraction accelerate KG updates. A recurring per-step cost in mini-batch KG learning is neighborhood-context estimation: uniform neighbor sampling without replacement followed by mean aggregation. Common frameworks implement this estimator through sampled-subgraph materialization and intermediate feature gathers, adding kernel launches, allocator pressure, and transient memory spikes. We present One-Pass Neighborhood Estimation, a fused PyTorch CUDA operator that samples neighbors and directly emits the sampled-neighborhood mean, avoiding explicit block construction while preserving GraphSAGE-mean semantics for the same sampled neighbor IDs. It supports seed-controlled sampling and optional saved-index replay for reproducible validation and regression testing. Across large-graph mini-batch workloads, it improves FP32 end-to-end step latency by 2.24x-3.48x over tuned DGL baselines and reduces transient GPU memory by up to 160x in our measurements. On OGB KG completion benchmarks such as WikiKG2 and BioKG, it reduces step time and peak VRAM while matching ranking quality within seed variability, improving time-to-quality for budgeted KG refresh.

Aleksandar Stanković, Haoran Du, Xinming Wang

University of Novi Sad, Novi Sad, Serbia · Shanghai Key Lab of Intelligent Information Processing,2026 College of Computer Science and Artificial Intelligence, Fudan University, China · Institute of Automation, Chinese Academy of Sciences, China

Subgraphs Knowledge Graph Embeddings Approximate Nearest-Neighbor Search Knowledge Graphs Inference Workloads Token Budget Allocation+1

Nov 7, 2025cs.CL

BudgetMem: Training-Free Selective Memory for Cost-Efficient Long-Context Processing in Language Models

Processing long documents with large language models (LLMs) is expensive: a single query over a 100K-token document can cost from tens of cents to over a dollar in API fees, depending on the model, and memory grows linearly with context length. We introduce BudgetMem, a training-free architecture that keeps only high-salience content under an explicit memory budget. Unlike token-level neural compressors such as LLMLingua, BudgetMem makes chunk-level keep-or-discard decisions from interpretable features: entity density, TF-IDF importance, position, numerical density, discourse markers, and question presence. Across four benchmarks, BudgetMem matches the uncompressed baseline on template-generated structured documents (F1 = 0.859 vs. 0.855) while discarding 70% of chunks. As a pre-retrieval filter on the same documents it outperforms LLMLingua-2 by a wide margin (0.859 vs. 0.554), because token-level compression destroys the phrasal structure that retrieval depends on; the advantage holds across model scale and family (Llama-3.2-3B, Qwen2.5-7B), under dense retrieval (0.918 vs. 0.530), and in LLMLingua-2's intended direct-feed mode (0.797 vs. 0.720). On real NLP research papers (Qasper), BudgetMem is competitive but not free, trailing the full baseline by 7.4% and LLMLingua-2 by 5.5% relative F1 at a 72% storage reduction. Removing discourse markers or numerical density hurts most, although TF-IDF alone scores as well on template documents. The pipeline needs no trained models or GPU for compression and runs on a $10/month Colab instance.

Chandra Vamsi Krishna Alla, Harish Naidu Gaddam, Manohar Kommi +1

University of Texas at Arlington

Large Language Model Memory Efficient Long-Context Inference Token Budget Allocation Token Compression Term Frequency-Inverse Document Frequency Document

Oct 26, 2025cs.LG

Managing Self-Learning Experts under Per-Round Budget Constraints

This paper addresses the problem of sequential decision-making under learning budget constraints. Such settings naturally arise in applications like managing a portfolio of bandit or reinforcement learning (RL) algorithms. We propose a novel UCB-type algorithm, M-LCB, designed to manage a pool of

K

self-learning experts in a stochastic environment while accounting for a limited per-round learning budget

M

. At each round, M-LCB selects one expert to make a decision and at most

M \le K

experts to learn. For selection, M-LCB uses confidence bounds constructed from limited prior knowledge about the experts (i.e., mild assumptions) and their observed training losses. We derive anytime regret bounds for M-LCB that scale with the individual regrets of the experts. In particular, if each expert has regret

\tilde O(T^α)

by round

T

, then M-LCB guarantees an overall regret of

\tilde O\left(\sqrt{KT/M} + (K/M)^{1-α}T^α\right)

relative to the best expert in hindsight. Finally, we demonstrate the applicability of M-LCB using self-learning experts instantiated as (i) parametric models and (ii) bandit algorithms.

Ilgam Latypov, Alexandra Suvorikova, Alexey Kroshnin +2

AI Center, Lomonosov Moscow State University MSU Institute for Artificial Intelligence Moscow, Russia · Weierstrass Institute for Applied Analysis and Stochastics Berlin, Germany · IITP RAS Moscow, Russia +1

Stochastic Multi-Armed Bandits Sequential Decision Making Regret Token Budget Allocation Experts

Sep 29, 2025cs.LG

BALF: Budgeted Activation-Aware Low-Rank Factorization for Fine-Tuning-Free Model Compression

Activation-aware low-rank factorization techniques yield strong compression results but are generally confined to linear layers, while existing whitening-based theory typically makes an implicit full-rank assumption on activations. We introduce a layer representation framework that extends activation-aware factorization beyond linear layers, including standard and grouped convolutions. Within this framework, our whitening-based formulation is more general than prior ones, naturally covering rank-deficient activations, and yields an optimal low-rank projection that attains the reconstruction error of the best low-rank approximation to layer activations. The resulting singular spectrum provides a closed-form per-layer distortion proxy, which we use to allocate per-layer ranks under explicit FLOP or parameter-count budgets via a Lagrangian relaxation with negligible overhead. Together, these components form BALF, an end-to-end pipeline for efficient vision model compression. Across CNNs and vision transformers on CIFAR-10 and ImageNet-1K, BALF generally achieves higher accuracy than SVD-based factorization baselines at matched FLOP or parameter count targets and remains competitive with other fine-tuning-free compression techniques.

David González-Martínez

Department of Computer Science and Artificial Intelligence, Universidad de Sevilla · Tübingen AI Center

Low-Rank Structure Data Compression Methods Model Activations Vision Transformer Whitening Factor+2

Aug 30, 2025cs.DB

Access Paths for Efficient Ordering with Large Language Models

In this work, we present the \texttt{LLM ORDER BY} semantic operator as a logical abstraction and conduct a systematic study of its physical implementations. First, we propose several improvements to existing semantic sorting algorithms and introduce a semantic-aware external merge sort algorithm. Our extensive evaluation reveals that no single implementation offers universal optimality on all datasets. From our evaluations, we observe a general scaling relationship between sorting cost and the ordering quality for comparison-based algorithms. Building on these insights, we design a budget-aware optimizer that utilizes heuristic rules, LLM-as-Judge evaluation, and consensus aggregation to dynamically select the near-optimal access path for LLM ORDER BY. In our extensive evaluations, our optimizer consistently achieves ranking accuracy on par with or superior to the best static methods across all benchmarks. We believe that this work provides foundational insights into the principled optimization of semantic operators essential for building robust, large-scale LLM-powered analytic systems.

Fuheng Zhao, Jiayue Chen, Yiming Pan +7

1Snowflake Inc. · University of Chicago · 3UC Los Angeles +1

Order Matters Order Token Budget Allocation Path

May 5, 2025cs.GT

Plan-Driven Adaptive Bidding for First-Price Auctions with Budget Constraints under Nonstationarity

We study budget pacing in repeated first-price auctions when an advertiser's private-value distributions change over time and the stationary competing-bid distribution is unknown. We ask how a feasible expenditure plan should enter online bid shading, learning, and hard budget control. We establish a plan-to-performance decomposition for a plan-driven projected-dual policy. The policy uses any feasible expenditure plan as a soft target, learns an unknown stationary competing-bid CDF from thresholds revealed after each auction, and enforces the campaign budget on every sample path. Against a distribution-informed expected-budget fluid benchmark, the uniform-plan reward gap is

O(\sqrt T)+O(\mathcal W_T)

, where

\mathcal W_T

measures heterogeneity in private-value distributions. With a supplied feasible plan, the global gap decomposes into a one-sided

O(\sqrt{T})

fixed-plan execution term and a plan-mismatch term bounded by

(b/2a)PlanError

. The same analysis provides guarantees for strict and relaxed period-cap comparators, exact recovery of the global benchmark under a specific allowance vector, and separate lower bounds establishing the necessity of the temporal-heterogeneity and Plan Error terms. An upstream planner can translate forecasts or managerial priorities into a feasible spending trajectory, while the online controller adapts bids using realized thresholds and expenditures. The guarantee is modular: it evaluates the final normalized or projected plan through

PlanError

. A specific forecasting model can be linked to the guarantee by establishing how its primitive estimation errors propagate to this plan-quality metric.

Yige Wang, Jiashuo Jiang

Department of Industrial Engineering & Decision Analytics, Hong Kong University of Science and Technology

First-Price Auctions Token Budget Allocation Non-Stationarity

Jun 9, 2024math.OC

Probabilistic Approach to Black-Box Binary Optimization with Budget Constraints: Application to Sensor Placement

This paper presents a fully probabilistic approach for solving optimal experimental design problems under budget constraints. The experimental design is viewed as a random variable and is associated with a parametric conditional distribution that inherently models the budget constraints. The original optimization problem is replaced with an optimization over the expected value of the original objective, which is then optimized over the distribution parameters. The resulting optimal parameter (policy) is used to sample the feasible region of binary space to produce estimates of the optimal solution(s) of the original optimization problem. In this work we extend the family of conditional Bernoulli models to model the random variable conditioned by the total number of nonzero entries, that is, the budget constraint. This approach (a) is generally applicable to binary optimization problems with nonstochastic black-box objective functions and budget constraints; (b) employs conditional probabilities to model and sample only the feasible region and thus considerably reduces the computational cost compared with employing soft constraints; and (c) does not employ soft constraints and thus does not require tuning of a regularization parameter, for example to promote sparsity, which is generally challenging. The proposed approach is verified numerically using an optimal sensor placement experiment based on an advection-diffusion forward model in a parameter identification setup.

Ahmed Attia

Mathematics and Computer Science Division, Argonne National Laboratory, Lemont, IL, USA

Bayesian Experimental Design Black-Box Optimization Optimal Sensor Placement Token Budget Allocation Probabilistic Model Conditional Distribution+1

Feb 3, 2023cs.LG

Robust Budget Pacing with a Single Sample

Major Internet advertising platforms offer budget pacing tools as a standard service for advertisers to manage their ad campaigns. Given the inherent non-stationarity in an advertiser's value and also competing advertisers' values over time, a commonly used approach is to learn a target expenditure plan that specifies a target spend as a function of time, and then run a controller that tracks this plan. This raises the question: how many historical samples are required to learn a good expenditure plan? We study this question by considering an advertiser repeatedly participating in

T

second-price auctions, where the tuple of her value and the highest competing bid is drawn from an unknown time-varying distribution. The advertiser seeks to maximize her total utility subject to her budget constraint. Prior work has shown the sufficiency of

T\log T

samples per distribution to achieve the optimal

O(\sqrt{T})

-regret. We dramatically improve this state-of-the-art and show that just one sample per distribution is enough to achieve the near-optimal

\tilde O(\sqrt{T})

-regret, while still being robust to noise in the sampling distributions.

Santiago Balseiro, Rachitesh Kumar, Vahab Mirrokni +2

DRO, Columbia Business School, New York, NY, USA · Google Research, New York, NY, USA · IEOR, Columbia University, New York, NY, USA

First-Price Auctions \Widetilde{\Mathcal{O}}(\Sqrt{T})$ Regret Token Budget Allocation Adaptive Sampling