Sección

Investigación

Papers y preprints de los feeds de investigación que seguimos.

6365documentos

A Batched Hartigan's k-Means Clustering

Hartigan's k-means algorithm has theoretical advantages over the standard Lloyd's variant, which has become synonymous with "k-means". Yet, Hartigan's algorithm is far slower in practice due to its inherently sequential calculations. We devise a Batched Hartigan's method that enables vectorized calculation by exploiting the triangle inequality to expose a set of parallel-safe updates and a smaller set of sequential updates. This makes Hartigan's method competitive with Lloyd's in execution speed for the first time.

arXiv AI Papershace 12 días

GraCo: A Unified Toolkit of Graph Coarsening Algorithms and Metrics

Graph coarsening aims to reduce a graph to a smaller one that preserves chosen properties of the original. It is increasingly used to scale graph learning to large graphs, as a non-differentiable step applied once before training. Many coarsening methods have been proposed in recent years, each with its own implementation, notation and evaluation. In this work, we introduce GraCo, a unified toolkit of graph coarsening methods. It relies on a single definition: a coarsening is fixed by a partition of the nodes and by the Laplacian the coarsened graph is consistent with. The coarsened graph, and the reduction and lifting matrices that map signals from the original graph to the coarsened one and back, follow from these two choices. We implement 17 methods from the literature and a random baseline, grouped into five families, with the same notation, inputs and outputs. We also build a collection of metrics from different papers, applicable to any coarsening. We check the implementations on a synthetic stochastic block model, then we report the runtime and peak memory of each method on Cora, PubMed, ogbn-arxiv and ogbn-products. GraCo is open-source and available at https://github.com/Antonin-J/graco.

arXiv AI Papershace 12 días

Online Autotuning of Algebraic Multigrid via Contextual Bandits and Reinforcement Learning

Algebraic multigrid (AMG) methods are widely used for solving large sparse linear systems, but their efficiency depends strongly on interacting setup and solve parameters. Effective parameter choices typically depend on the problem. We develop a phase-aware online autotuning method for hypre's BoomerAMG to reduce cumulative time-to-solution over sequences of related linear systems. A LinUCB-based contextual bandit selects mixed-type parameters for AMG hierarchy construction using a shared cost model over PDE descriptors and configuration encodings. A recursive LSTDQ controller uses residual and timing observations to estimate the AMG solve time within each attempt and adapt relaxation weights between multigrid cycles. Both learners update from ongoing solves without offline pretraining. Across grids of sizes 40^3, 60^3, and 80^3, the joint autotuning method reduces total runtime, including recurring learner computation, by 36.1-43.3% for diffusion problems and 19.8-31.0% for diffusion-advection problems over sequences of 5000 linear systems, relative to the reference BoomerAMG default configuration. On a variable-flow diffusion-advection benchmark comprising 30,000 systems on a 60^3 grid, 2 systems fail to converge with joint autotuning, compared with 1677 for the reference configuration, under their respective attempt budgets.

arXiv AI Papershace 12 días

ArSciKids: Arabic Curriculum-Aligned Datasets for Scientific Experiment and Multiple-Choice Question Generation in Primary Education

Despite growing interest in Arabic natural language processing, curriculum-aligned educational resources remain scarce compared with English, and few public datasets for Arabic curriculum content with structured, generation-ready annotations are available, particularly for primary-school science. We introduce ArSciKids, a collection of two Arabic datasets designed for curriculum-aligned educational content generation: (1) a scientific-experiments dataset containing 999 manually curated records from official primary-school science textbooks in Saudi Arabia, Syria, and Jordan, and (2) an assessment-question dataset containing 2,167 multiple-choice questions collected from the Saudi Manhaji educational platform. The experiment records are structured with titles, objectives, tools, procedures, observations, conclusions, keywords, and grade levels, while the assessment records contain lesson references, questions, four answer options, correct answers, and explanations. Both datasets cover grades 1-6 and consist of real-life Arabic educational content rather than machine-translated or synthetically generated material. We assess the usefulness of these resources for generation by fine-tuning ten open models spanning sub-billion to several-billion parameter scales using LoRA. Models are evaluated using automatic metrics, including ROUGE and BLEU, and answer accuracy for multiple-choice generation. Moreover, we evaluate the results using a five-criterion human evaluation protocol. The results show substantial differences across model scales and tasks. ArSciKids will be publicly available, and we hope that it provides a manually curated, structured foundation for research on Arabic educational NLP, curriculum-aware generation, and low-resource language modeling.

arXiv AI Papershace 12 días

Zeroth-Order Policy Optimization for Scheduling in Queueing Networks

Reinforcement learning in queueing network scheduling presents significant challenges because of the countably infinite state space and the high stochasticity in transitions. In this paper, we propose zeroth-order policy optimization algorithms that are easy to implement and rely solely on estimates of the average cost, a single scalar quantity, without requiring the estimation of value or advantage functions. Our analysis focuses on back-pressure guarded policies and establishes uniform smoothness of the average cost objective with respect to the policy parameters. Building on this property, we establish finite-time convergence guarantees to an ε-stationary policy for the proposed algorithms. Numerical experiments on multiple queueing networks, including systems beyond classical exponential service distribution, demonstrate competitive performance, outperforming gradient-based RL methods like PPO and traditional queueing baselines.

arXiv AI Papershace 12 días

Satisfied, Not Solving: Wireheading of Bounded Homeostatic Rewards in Reinforcement Learning

Bounded intrinsic rewards are often assumed to be safe from exploitation: if a signal can yield at most a fixed amount, gaming it should not pay. We test this for a homeostatic satiation reward, in which needs build up and relieving them is rewarding, and give the agent a cheap action that resets its needs. In MiniGrid DoorKey-8x8, PPO agents with this action solved 2 of 80 seeds, against 71 of 80 on the same seeds without it; in KeyCorridorS3R1, 0 of 20 against 20 of 20. Their policies stayed near uniform. The reward does not ask for this: a telescoping argument caps any policy's satiation return at the needs' starting drive, and a post-hoc computation shows that, at every growth rate we trained, a solving trajectory beats that cap on all sampled layouts. In DoorKey with advantage normalization on, a satisfaction signal the agent could fill itself was worse than none (11 of 20 solved with task reward alone, 1 of 20 with the tamperable signal), and a per-press cost of 0.1 restored the task in every seed. Farming of positive reward cycles appeared in DoorKey but not persistently in KeyCorridorS3R1. All predictions were pre-registered, and hash-locked from round 3 on; 9 of our 23 hypotheses were not supported, and we report each.

arXiv AI Papershace 12 días

Fast and Exact Relative-Position Attention via Structure-Aware Kernels

Relative-position attention mechanisms offer compelling alternatives to RoPE across various transformer architectures, delivering superior performance in domains such as audio. These mechanisms typically modify attention scores by adding content-position or bias-position terms. Unlike RoPE, which encodes position via per-token rotations directly on the queries and keys, relative-position terms generally require pairwise offset-dependent computation or lookups, complicating their integration into fused attention kernels and introducing severe memory, bandwidth, and compute overheads as sequences scale. To address this bottleneck, we propose an exact attention algorithm that incorporates additive relative-position terms into FlashAttention-style tiled computation. Our method (1) uses offset-aware tiling to avoid redundant indexing and memory accesses, (2) computes only the necessary key/query-relation products and reuses them across token pairs in both forward and backward passes, and (3) uses offset-based gradient sharding and aggregation, eliminating atomic contention. We provide a unified, efficient Triton implementation across diverse relative-position attention mechanisms and evaluate it against naive and specialized implementations. For 8K-token sequences, our method speeds up the forward (backward) pass by 1.8-6.4(2.0-21) and reduces peak memory up to 2.9-128(1.4-54) over the strongest baseline for each mechanism, enabling long-context end-to-end transcription that is 1.8faster and uses 2.4less memory. Our method thus provides a drop-in, hardware-efficient solution for scaling relative-position attention transformers.

arXiv AI Papershace 12 días

TRIAGE: Reliability- and Load-Conditioned Escalation for Two-Tier LLM Serving with a Semantic Evidence Judge

Two-tier LLM serving escalates selected requests from a small model to a large one, but prompt-based routers cannot see whether retrieved evidence supports an answer, and they treat the GPU cost of an escalation as constant. We study TRIAGE, which conditions escalation on a post-generation reliability state and on a load-dependent GPU price, and we report both what held and what did not on one A40 serving Qwen2.5-7B and 32B (AWQ) under VLLM. Escalation cost rose 21.9x from 1 to 10 requests/s but showed no monotone dependence on KV-cache headroom, and a pre-registered claim that the reliability state detects corrupted evidence (AUROC>=0.70) was falsified at 0.571, although any prompt-only router scores exactly 0.500 by construction. Post hoc, a semantic evidence judge raised detection to 0.846 (0.926 on never-served items) and predicted wrong small-model answers at AUROC 0.90-0.96 on RGB and three RouterBench model pairs; the resulting cascade stayed within about 3 pp of GPT-4 at 79.5% lower API cost for GPT-3.5->GPT-4, yet fell below random routing for open-model pairs with 2-3x price ratios. End to end, the 7B->32B pair showed only a +2.88 pp held-out gap, so the allocator rightly declined to escalate and the headline is a null that a small pre-launch gate failed to expose.

arXiv AI Papershace 13 días

Concept-Guided Prompting Strategies Increase Diversity in LLM-Generated Recipe Populations

Novelty in solution generation supports automated discovery, but LLM outputs can remain repetitive. To address this, we propose a simple concept-guided prompting method that generates thematic concepts before responses within each of these concepts. To demonstrate, we generated 1,000 recipes for a recipe book task and compared the results against a human-authored corpus. Two naive prompting strategies were compared as baselines. Concept-guided prompting outperformed both baselines in all cases and reached semantic coverage of 47.0% versus 35.1% and 13.1% in respective prior-title and nonce prompt strategies. These findings suggest broader population exploration and diversity, but remain contained to this specific task. Further work is needed to determine the quality of solutions and generalizability.

arXiv AI Papershace 13 días

Lightweight Representation Learning for Low Tucker Rank Tensors

Low Tucker rank tensors provide compact representations of multidimensional dependencies, but standard learning pipelines can incur substantial computational and memory overhead from redundant intermediate quantities. We reduce this overhead without modifying the underlying representation objective or parameterization. Our approach combines three complementary components: (i) sequential extraction of only task-required spectral components, avoiding unnecessary full decompositions; (ii) factor-wise multilinear contractions without materializing large Kronecker operators; and (iii) compact latent-state updates without storing full ambient tensor iterates. These components preserve the algebraic operations and learning trajectories of the original algorithms while reducing their computational and memory footprints. Across five low Tucker rank tensor estimators, our implementations match the original trajectories to numerical precision (relative discrepancies of 10^{-16} to 10^{-13}), while reducing per-iteration runtime by up to 3.12and resident memory by up to 616(99.8\%) on the main order-3 benchmark at n=100, with memory reductions exceeding 900across the full evaluation suite. These results show that substantial computational redundancy can be eliminated from Tucker representation learning without changing the underlying model or learned representation.

arXiv AI Papershace 13 días

Lower Bounds on Inference Complexity for Polyak-Ruppert Averaged Stochastic Gradient Descent

In this paper, we establish sharp lower bounds for Gaussian approximation of Polyak-Ruppert averaged stochastic gradient descent with polynomially decreasing step sizes. For every fixed exponent γ(1/2,1), a single one-dimensional smooth, strongly convex example has approximation error with the limiting variance of order n^{1/2-γ}+n^{γ-1} in Kolmogorov and convex distances. This matches the existing upper bound throughout the range of γ. The nonlinear bias contributes n^{1/2-γ} even when the Gaussian reference uses the finite linearized variance. We also derive a lower bound of order n^{-(1-γ)/2} for the relative mean error of estimating the limiting variance from one SGD trajectory, uniformly over a scalar quadratic family. With the limiting variance known, achieving approximation error on this example takes order ^{-4} iterations for the best choice γ=3/4. Achieving both Gaussian approximation and relative mean variance-estimation errors at most uniformly over the model class requires at least order ^{-6} iterations for every fixed γ.

arXiv AI Papershace 13 días

Discussing politics with a chatbot: How political beliefs shape prompt formulation for generative AI

By generating comprehensive and highly personalized answers to user prompts, AI chatbots such as ChatGPT and Gemini can serve as alternatives to search engines and substantially transform online information seeking. However, little research has examined how users interact with these tools to find information, particularly about politics. In this experiment, we examine how Swiss citizens (N = 563) formulate prompts to search for migration-related issues using AI chatbots and whether this process is affected by selective exposure. We find evidence of attitude-consistent prompting, whereby participants who were more critical of migration were more likely to formulate prompts with an anti-migration stance. This effect was stronger for a broad topic (migration in general) than for a specific one (anti-migration popular initiative put to a vote in Switzerland). However, exposure to an attitude-consistent AI response did not further amplify selectivity in prompting. We also did not find evidence that either AI attitudes or thinking styles moderated selectivity in prompting. These findings contribute to the understanding of selective exposure via AI chatbots and the use of generative AI for political information-seeking.

arXiv AI Papershace 13 días

Capacity Planning for Resource-Constrained Clinical LLM Serving

Deploying large language models (LLMs) under a fixed accelerator budget requires jointly deciding how computational capacity is allocated across model sizes and how incoming requests are routed across that capacity. Although prior work has extensively studied LLM routing and serving efficiency, the relative importance of fleet composition and routing under resource constraints remains less understood. We investigate this question using a controlled four-GPU serving environment with heterogeneous clinical NLP workloads spanning short factual verification, biomedical semantic matching, and long-context clinical summarization. We systematically vary fleet composition, routing policy, and offered load while holding the workload trace and hardware budget fixed. Across 24 configurations, descriptive main-effect shares attribute more variation to fleet composition than to the evaluated routing policies in time to first token, latency, and long-context coverage. All-small fleets provide the best responsiveness and throughput but substantially lower long-context coverage, whereas larger-model capacity improves coverage at the cost of serving efficiency. Heterogeneous fleets provide intermediate operating points but can introduce strong-model bottlenecks when large-model capacity is scarce. In a focused evaluation of this bottleneck, capacity-aware routing reduces mean latency and increases throughput while incurring a small reduction in long-context coverage. Within this measured regime, the results support prioritizing capacity allocation, with routing managing demand within the provisioned capacity.

arXiv AI Papershace 13 días

CivicBench: A Benchmark and Memory Framework for Web-Based Civic Data Analytics

Municipalities publish service requests, geographic boundaries, weather observations, demographic estimates, and operational guidance through independently maintained Web portals. Civic analysis must combine these sources while preserving their schemas, source links, spatial and temporal scopes, and interpretive limits. Tool-using language agents can perform this integration, but existing task benchmarks rarely test whether a computed claim remains supported by the records used. We present CivicBench, a 400-task benchmark over four cities and two years that materializes civic Web data into frozen bundles for reproducible evaluation. Executable contracts score computation, source linkage, coverage, scope, qualified answers, and refusal when the requested conclusion is not supported. We also introduce Task-State Memory (TSM), which compiles tool observations into typed assertions, reconciles records only within compatible scopes, and retrieves a bounded state organized around unresolved constraints. Across nine completed model pairs, eight yield positive mean-score differences with 95\% semantic-contract-cluster bootstrap intervals excluding zero; the ninth interval crosses zero. The benchmark and memory framework make the records behind a claim inspectable at the point of decision.

arXiv AI Papershace 13 días

GSLM2: Multi-Stream Speech Representation Learning and Generative Spoken Language Modeling

Generative spoken language models (SLMs) offer a route to learning linguistic structure purely from speech, yet they lag far behind text-based models in both capability and data scaling efficiency. We identify two bottlenecks underlying this gap: the limited linguistic quality of existing speech units and the reliance on a single stream of discrete units to represent speech. Multiple codebooks are widely used to encode acoustic features but rarely to represent speech semantics. We present GSLM2, which learns and models complementary properties of speech at multiple levels of abstraction. Its encoder, SpidR 2.0, uses self-supervised learning with differentiable prediction heads to induce high-quality discrete units at multiple levels. A multi-stream SLM then jointly models these units using a shared temporal backbone, stream-specific predictors, and an autoregressive head that captures cross-stream dependencies. Across training data sizes and model scales, up to 6M hours and 6.5B parameters, GSLM2 consistently improves linguistic competence while scaling more efficiently with data. As a result, it substantially narrows the gap between spoken and text-based LMs; across read and conversational speech domains, we shrink the gap by about two orders of magnitude on sWuggy, sBLIMP, and tSC, while also outperforming competitive speech-text systems on all three tasks. We open-source the training code and model checkpoints at https://github.com/facebookresearch/gslm2.

arXiv AI Papershace 13 días

EMG-Hybrid: A Dual-Engine Elite Memory--Guided Adaptive Optimization Framework for High-Dimensional Feature Selection

Feature selection in ultra-high-dimensional, noisy datasets remains a critical challenge due to exponential search space growth, where conventional binary metaheuristics often suffer from premature convergence. To address this, EMG-Hybrid is introduced as a novel three-level hierarchical optimization architecture designed around decoupled operational planes, feedback-driven scheduling, and isolated state refinement. At Level 1, a Dual-Engine Controller monitors population Shannon entropy and empirical fitness velocity, functioning as an architectural master-switch that dynamically routes execution between global exploration and local intensification. This control loop conditions the Level 2 active optimization plane, where an Adaptive Black Hole Gravity (ABHG) execution layer performs aggressive feature manifold pruning via a distance-decoupled penalty kernel driven by fitness similarities and Hamming metrics. To structurally isolate macro-exploration from micro-exploitation, Level 3 encapsulates an autonomous Elite Memory Archive that preserves high-fidelity sub-schemas and hosts a discrete bitwise Differential Evolution (DE) micro-refinement sandbox for resolving complex parameter epistasis. Theoretically, uniform combinatorial bounds derived via Vapnik--Chervonenkis (VC) dimension criteria demonstrate that this multi-level restriction mitigates high-dimensional overfitting. Empirical results across manifolds scaling up to d > 100{,}000 features, complemented by high-performance computing (HPC) profiling under lock-free atomic Compare-and-Swap (CAS) primitives, indicate strong performance gains over state-of-the-art baselines. The framework exhibits near-linear parallel speedups, sub-quadratic runtime scaling, and substantial dimensionality reduction, offering a scalable and structurally innovative paradigm for large-scale data mining.

arXiv AI Papershace 13 días

World Models Need Not Be Right to Rank Policies Right: Relative Bounds and Audit Limits

Selecting a reinforcement-learning (RL) policy usually requires additional environment interaction, while learned world models offer cheap but potentially biased evaluations. This raises two distinct questions: can shared model errors preserve pairwise rankings despite poor absolute values, and do they make a small number of real audits more informative? We derive an exact pairwise simulation identity and a relative bound separating common-mode Bellman residuals from policy-specific error. The analysis motivates RAVEL (Relative Auditing of Value Errors in Learned models), a selective policy tournament whose eliminations use held-out real outcomes. We test 45 SAC, TD3, and PPO policies per task in DMC cheetah-run and walker-walk. At rollout horizon 500, model rankings remain strong (Kendall tau = 0.962 and 0.800), and same-run differential-error ratios are 0.674 and 0.106. Yet mean paired audit-error correlations are only 0.007 and 0.090, and pairing changes standard deviation by -2.5 percent and +1.9 percent. Simultaneous intervals attain 99.98 percent and 99.75 percent coverage, but certify only 13.2 percent and 0 percent of decisions at eight audits. RAVEL improves low-budget walker-walk regret, whereas real-only successive halving is better at the largest budget, rejecting the precommitted twofold efficiency target. Frozen-model optimization lowers real return without increasing predicted return on average. Thus ranking fidelity, useful audit covariance, and upward model exploitation are distinct properties, separated in part by closed-loop trajectory divergence.

arXiv AI Papershace 13 días

SIDRec: End-to-End Semantic ID Representation and Modeling for Recommendation

Semantic IDs (SIDs) have emerged as a promising approach for discriminative recommendation by encoding continuous item rep- resentations into compact discrete identifiers. However, existing SID-based methods face two fundamental limitations: semantic mis- match between content semantics and collaborative preferences, and objective mismatch between SID construction and downstream recommendation optimization. To address these challenges, we propose SIDRec, an end-to-end recommendation-aware SID learn- ing framework that jointly models content and collaborative in- formation while aligning SID construction with recommendation objectives. Specifically, SIDRec introduces a self-updating fusion mechanism that explicitly integrates pretrained content represen- tations with collaborative embeddings initialized from a trained recommendation model, enabling preference-aware semantic mod- eling. Furthermore, SIDRec employs an MMoE-inspired joint opti- mization mechanism with shared experts and task-specific gates, allowing recommendation supervision to directly guide differen- tiable quantization and produce task-adaptive discrete representa- tions. Extensive experiments on three public benchmark datasets demonstrate that SIDRec consistently outperforms all competing methods across both AUC and GAUC, achieving up to 5.15% relative improvements over the strongest baselines. Further ablation stud- ies validate the effectiveness and complementarity of collaborative semantic modeling and end-to-end SID optimization.

arXiv AI Papershace 13 días

Compile as Hypothesis: A Headroom Typology for Prompt Optimization on Real Reasoning Models

Automated prompt compilers search for or rewrite prompts under the implicit assumption that optimization consistently improves downstream task performance. We evaluate this assumption on frontier reasoning models through rigorous paired, same-day measurements. Across four optimizer families (genome search, profile-guided mutation, GEPA, and ESPO) and eight tasks, structured search yields no statistically significant accuracy gains on strong reasoners. However, a discrete structural genome provides essential architectural stability, preventing catastrophic bimodal seed-collapse (where unconstrained search collapses toward the judge floor in 3/5 runs). Through 190-problem evaluations on knowledge-intensive benchmarks, we establish a three-dimensional headroom typology: prompt optimization cannot compensate for intrinsic knowledge deficits or physical token truncation, but successfully resolves protocol and formatting errors. On gpt-6, while free-text reflective search (GEPA) yields a +.14 gain on a task where structured search remains flat, qualitative ablation reveals that ~.035 stems from judge-rubric reconstruction while ~.105 reflects genuine instruction refinement. Our pre-registered AutoAPC-Select deployment gate matches the oracle policy in 5/7 groups and rescues seed-collapse arms with zero regret. Finally, we expose silent backend-mixing in commercial APIs during outage windows and provide automated per-call audit verification tools to ensure empirical evaluation fidelity.

arXiv AI Papershace 13 días

Rethinking LLM Pruning via Test-Time Scaling

Structured pruning reduces the size of large language models, often at the cost of lower accuracy. Whether this decline reflects diminished reasoning capacity or greater difficulty in sampling correct solutions is less clear. We examine this question across expert, FFN and layer pruning on four mathematical and coding benchmarks, comparing original and pruned models through pass@k at matched sampling budgets. Even after substantial pruning, some models match or exceed the original model's reasoning coverage despite lower pass@1, and solve problems left unsolved in the original samples. Retaining broad coverage, however, does not mean that correct solutions remain easy to obtain. Under severe pruning, diverse generated chain-of-thought (CoT) traces can coexist with increased repetition and less reliable generation. As correct answers become harder to sample, the additional attempts can sharply increase total token use even when individual responses become shorter. This separation between coverage and sampling efficiency also clarifies expert-selection gains, as methods with markedly different pass@1 can solve the same problems at large budgets yet require different numbers of attempts to reach a common coverage target. Pruning should therefore be assessed by both the range of problems a model can still solve and the sampling cost of obtaining correct solutions.