{"id":"31ba7f54-7d2f-44ac-82f3-42e045084054","arxiv_id":"2509.00280","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"A DRL agent learns bit-interleaving patterns for sparse tensor storage, delivering 1.4 to 1.46x geometric-mean speedups for tensor decomposition over expert formats.","lead":"This paper uses deep reinforcement learning to learn how to interleave the bits of sparse tensor indices, producing a storage format that speeds up tensor decomposition by 1.4 to 1.46x on average over expert-designed formats. A generalist should read it as a test of whether learned data layouts can beat hand-designed layouts for irregular sparse workloads.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No independent repeated validation of selected encodings; the headline speedup is the training objective's maximum, so measurement noise could inflate the 1.4–1.46x geomean.","rationale":"The paper presents a plausible systems contribution: the MDP formulation is interesting, and the roofline/cache-counter analysis provides supporting evidence that the learned encodings reduce memory traffic. However, the central claim depends on measured speedups being genuine rather than artifacts of selecting the best among many noisy runtime samples. Because the reward is exactly the speedup against ALTO and the best encoding is chosen during training on that reward, the reported numbers are not an unbiased estimate unless independently re-measured. The reader's conditional verdict already highlights the lack of error bars and the noise issue, though it also emphasizes the bit-order restriction, which I view as less load-bearing because ReLATE can still represent and beat ALTO within that restricted class. I therefore keep the verdict at CONDITIONAL/UNCHANGED: the concern is real but does not by itself disprove the existence of the speedups; it demands a repeated, held-out validation run to settle the claim.","tokens_in":19114,"tokens_out":14252,"duration_ms":190187,"concrete_test":"For each of the 10 tensors, after training, measure the final selected ReLATE encoding and the best expert format (ALTO/SPLATT) in alternating order for at least 10 repetitions on the same EMR node, turbo disabled, with per-repetition timings; compute the geometric-mean speedup and a 95% bootstrap CI. If the lower CI bound falls below 1.0—or below the paper's 1.4x claim—the headline speedup is not established by the current evidence.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central empirical claim is that ReLATE's encodings are 1.4–1.46x faster (geomean) than the best expert format. The reported number comes from the same noisy runtime measurements used as the reward: Algorithm 1 evaluates thousands of candidate encodings and keeps the fastest (line 20). On an HPC system with acknowledged run-to-run variability (§3.1), the maximum over many noisy samples is a biased estimate of true performance; the selected encoding may be one that got lucky on a single timing. The final evaluation (§4.1.3) is described only as 'evaluated against expert formats' and does not state that it uses independent, repeated, interleaved runs. Only tensors with <1B NNZs are repeated 10 times; for amazon/patents/reddit no repetition is specified, and no error bars or confidence intervals are reported. Thus the 1.4–1.46x geomean and the 2x 'up to' number may not be reproducible without further validation.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces ReLATE, a reinforcement-learning framework that constructs vectorized sparse-tensor encodings for MTTKRP-based tensor decomposition on multi-core CPUs. Encoding construction is formulated as an MDP over bit-interleaving actions: the agent chooses which mode contributes its next bit to the linearized position, with rule-driven masking to guarantee valid encodings. ReLATE combines double DQN with a learned reward model, reward shaping, a reward cache, and a decoupled server-client setup. The framework is evaluated on all ten FROSTT tensors on an Intel Emerald Rapids 128-thread system, reporting geometric-mean speedups of 1.40–1.46x over ALTO (up to 2x, and up to 16.9x over SPLATT) while using the same storage as ALTO.","tokens_in":19405,"tokens_out":5826,"duration_ms":74935,"significance":"If the empirical claim holds, the paper makes a practical contribution: it demonstrates that learned, data-adaptive bit-interleaving can outperform expert-designed linearized tensor formats for sparse MTTKRP, a kernel central to tensor decomposition. The MDP formulation, action masking, reward cache, and the use of a hybrid model-based/model-free agent are reasonable design choices, and evaluation over the full FROSTT suite is a strength. The paper provides no machine-checked proofs or code artifact; its contribution is empirical. The key evidence, however, is not yet conclusive because the reported speedup is the same quantity used as the training reward, is selected as the best of many noisy samples, and is not compared with blind search baselines over the same action space.","major_comments":[{"comment":"The headline speedup is the direct training objective. §3.3.4 defines the reward as the measured speedup over ALTO, and Algorithm 1 (line 20) retains the encoding with the highest reward seen during training. Thus the reported 1.40–1.46x geomean is a best-of-selected result over potentially thousands of noisy runtime measurements. §4.1.3 says tensors with fewer than 1B nonzeros are repeated 10 times; amazon, patents, and reddit are not, and Figure 5 shows no error bars or confidence intervals. Given the HPC noise acknowledged in §3.1, the maximum over noisy samples is biased upward. Please provide an independent validation protocol: repeated interleaved re-measurements of the selected ReLATE encoding and the baselines on all tensors, per-tensor confidence intervals, and a clear statement of whether the encoding selection was finalized before those validation runs.","section":"§4.1.3, §4.2, Algorithm 1 line 20"},{"comment":"The paper attributes the speedups to the learned agent, but no comparison is made against random or greedy search over the same action space of multinomial bit interleavings (Eq. 1). Since the algorithm evaluates many candidates and returns the fastest, some or all of the advantage could come from the search itself rather than from the learned value/policy. Please add ablations with matched evaluation budgets: random sampling of interleavings, greedy per-bit hill climbing, and, for the smaller tensors, exhaustive search over the restricted space. This is necessary to support the 'automatically constructs efficient encodings' claim as a learning result.","section":"§4.2, Algorithm 1"},{"comment":"The MDP restricts the search to interleavings that preserve each mode's low-to-high internal bit order, reducing the space from ℓ(p)! to the multinomial count in Eq. (1). This is a strong structural assumption: an optimal linearization might interleave within-mode bits, use higher bits before lower bits, or otherwise break the 'next low bit' rule. The paper motivates the restriction by tractability but gives no evidence that the optimal encoding lies in this subspace. Please add a sensitivity analysis or, at minimum, a direct argument that intra-mode bit order is irrelevant to the cache/parallel behavior of linearized MTTKRP.","section":"§3.3.2, Eq. (1)"}],"minor_comments":[{"comment":"The abstract and contributions report speedup 'over the best sparse format,' but Figure 5's y-axis is 'Speedup over ALTO' and the geomean labels 1.40/1.46 appear to be computed against ALTO. Please specify whether the per-tensor best baseline is always ALTO for these datasets, and if not, report the geomean against the per-tensor best baseline separately.","section":"Abstract, §4.2, Figure 5"},{"comment":"The claimed maxima ('up to 2x' and 'up to 16.9x') are not tied to specific tensors. Please state which tensors yield these extreme values, and mention the corresponding measured runtimes.","section":"§4.2"},{"comment":"Training is subject to a 6-hour timeout, but no actual training wall-clock time or number of terminal reward evaluations per tensor is reported. Reporting these would help judge the practical cost of the approach.","section":"§4.1.3"},{"comment":"Figure 8 reports the reward model's normalized error and mentions an error threshold, but the threshold is not drawn or quantified in the text beyond the 'Min. accuracy 90%' row in Table 2. Please make the threshold explicit in the figure or text.","section":"Figure 8, Table 2"},{"comment":"The reward-shaping formula 'r_t ← log(r_{ℓ(p)-1})/ℓ(p)' is ambiguous: log of a speedup ratio is usually signed, but the notation suggests a scalar division. Please clarify the exact shape and sign convention, especially for the 'slowdown' case discussed in §3.4.","section":"Algorithm 1, line 21"},{"comment":"No code, configuration files, or artifact link for ReLATE is provided. Since the contribution is empirical, releasing the agent implementation and the exact evaluation scripts would materially improve reproducibility.","section":"General"}],"recommendation":"major_revision","confidential_remarks":"The evaluation-overlap concern raised by the stress-test is real and lands precisely: §3.3.4 and Algorithm 1 line 20 show that the reported figure is the maximum of the reward signal, and §4.1.3 does not provide independent repeated validation for the largest tensors. I do not see this as misconduct, but as a methodology gap that can be fixed with a validation protocol and stronger baselines. The paper is within the scope of a systems/ML venue and the core idea is worth publishing if the empirical evidence is tightened."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things worth knowing up front. First, the actual contribution is real: this is the first work I know of that uses deep RL to construct a linearized sparse tensor encoding—a bit interleaving—rather than to pick among existing formats. Second, the headline number is not trustworthy as reported: the 1.4–1.46x geometric-mean speedup is the training objective's own best-of-N result on noisy HPC timings, and the paper does not provide the independent repeated validation needed to believe that magnitude.\n\nWhat the paper does well: the MDP formulation is clean and domain-appropriate. States are represented as a one-hot encoding matrix, actions map the next low bit of a mode into the linearized index, and action masking guarantees valid encodings. That is a sensible way to tame an otherwise enormous (N*l)! search space. The reward model, caching, and server-client decoupling are reasonable engineering for an expensive reward signal. The roofline analysis and perf-counter data show that learned encodings reduce memory traffic and miss ratios for several tensors, which is real evidence that the effect is not purely noise. The storage comparison is also useful: ReLATE matches ALTO and uses far less memory than SPLATT.\n\nThe soft spots are mostly in the evaluation protocol, and they are load-bearing. The reward is explicitly speedup vs ALTO (Section 3.3.4), and Algorithm 1 keeps the best encoding found across thousands of episodes. The final Figure 5 is essentially a best-of-N selected on the same noisy runtime signal that produced it. The paper reports no error bars, does not state how many independent repeated runs went into the final timings for the largest tensors (only sub-billion-NNZ tensors are repeated 10 times; amazon, patents, and reddit get no stated repetition), and gives no random-search or greedy-search baseline over the same action space. Without a baseline, the reader cannot tell how much of the gain comes from RL versus luck in sampling. That does not make the speedups false, but it makes the advertised geomean fragile.\n\nSecond, the model is trained from scratch for each tensor (up to 5000 episodes, 6-hour timeout) and then evaluated on that same tensor. So the practical claim is per-tensor autotuning, not a reusable learned policy, and training cost is not reported. Third, there is no code or data release, so the numbers cannot be independently checked. The citation pattern looks fine; prior ALTO and RL format-selection work are properly credited.\n\nWho is this for? HPC systems researchers working on sparse tensor formats and ML-for-systems people interested in learned autotuning. I would send it to peer review. A serious referee should ask for independent repeated runs with interleaved timings and confidence intervals, a random/greedy baseline, explicit training-cost numbers, and ideally code release. If those come back solid, this is a publishable systems contribution.","headline":"A credible systems contribution with a genuinely new RL formulation for constructing tensor encodings, but the headline speedup is currently the training objective's best-of-N result and needs independent validation.","tokens_in":19903,"tokens_out":3992,"would_cite":true,"duration_ms":47560,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"ReLATE uses reinforcement learning to find sparse tensor layouts that beat hand-tuned formats, with up to 2x speedup on large tensors.","keywords":["sparse tensor decomposition","MTTKRP","reinforcement learning","linearized tensor formats","bit interleaving","learned data structures","cache optimization","format autotuning"],"falsifier":"Enumerate or randomly sample the restricted interleaving space on the paper's test tensors and measure kernel time: if random search matches the reported 1.4x geometric-mean speedup, the learned policy adds nothing beyond the search space. Alternatively, relax the restriction to allow intra-mode bit permutations and find an encoding that clearly beats the best restricted interleaving on any test tensor, showing the restriction is the bottleneck.","tokens_in":1634,"feed_emoji":"⚡","tokens_out":2112,"duration_ms":102027,"temperature":0.7,"pith_summary":"ReLATE tries to show that the layout of a sparse tensor can be treated as a learnable object: instead of relying on hand-crafted formats, a reinforcement-learning agent searches over the many ways to interleave the bit sequences of the tensor's coordinate indices and picks the layout that makes the tensor-decomposition kernel run fastest on a given machine. The paper argues this is the first format-search method that needs no labeled training data, always produces a valid encoding within bounded time, and adapts to both the shape and the data distribution of each tensor. If correct, it means practitioners of tensor decomposition—used on recommendation, health-record, network, and financial data—can get 1.4x to 1.46x speedup on average and up to 2x on the hardest large sparse tensors simply by letting the layout be learned rather than designed.","feed_headline":"Learnable tensor layouts beat expert formats by up to 2x","feed_subtitle":"Automated bit-interleaving search cuts memory traffic and beats hand-tuned formats on ten real datasets.","key_machinery":"The environment state is an N-by-ell(p) one-hot matrix: each column, corresponding to one bit position of the packed linear index, carries the mode whose next low bit is placed there, and a state is terminal once all ell(p) columns are filled. The action space has N actions, one per mode, and validity masking forbids taking more than ell(n) bits from mode n, so the agent searches only interleavings of the mode bit-sequences rather than all permutations. The reward is the log of measured speedup relative to the baseline linearized format, distributed uniformly back over the episode's actions, and a prioritized replay buffer trains a CNN policy network with a slower-updated target network. To","core_discovery":"The central claim is that choosing a sparse tensor layout is a tractable sequential decision problem if the search is over bit interleavings: each step picks one mode whose next low-order bit goes into the packed linear index, and a full sequence defines the layout. ReLATE encodes the current partial layout as a one-hot matrix and uses a deep Q-network policy with validity masking, so the searched space is the multinomial number of interleavings, not all permutations. Terminal layouts are executed against a baseline linearized format, and the measured speedup (on a log scale) is the reward, shaped back across all actions. The learned layouts outperform the best expert formats on all ten real","pith_inferences":["The same MDP formulation would apply to other sparse kernels, such as sparse matrix-vector or matrix-matrix multiplication, with only the reward function changed, since it learns an ordering policy that is kernel-agnostic.","Because the search preserves each mode's internal bit order, the reported results upper-bound what interleavings alone achieve; allowing intra-mode bit swaps or block-level reversals could expand the space and may yield further gains on skewed tensors.","The reward-model switch suggests a path to online adaptation: if a tensor's nonzero distribution drifts over time, the agent could re-select an encoding from cached or model-predicted options without full retraining.","The fact that shuffled tensors also speed up indicates that bit interleaving exploits residual distributional structure even after random permutation, not merely shape asymmetries."],"forward_implications":["Large, low-density tensors—the hardest cases—gain the most, up to 2x over the best expert format.","The same storage footprint as the mode-agnostic linearized baseline is kept, since only the bit-interleaving order changes.","Speedups persist on randomly permuted tensors (1.46x geometric mean), so learned encodings adapt to data distribution, not just tensor shape.","Reward modeling and action filtering keep worst-case performance during learning at the level of a mode-specific format, making the method usable before training fully converges."],"supporting_citations":[{"why":"Defines the linearized sparse tensor format and its bit-interleaved encoding, the representation ReLATE starts from and the baseline it must outperform.","marker":"[11]"},{"why":"Provides the mode-agnostic linearized format implementation and benchmarks of prior formats; used as the expert-policy baseline in the reward function.","marker":"[16]"},{"why":"Supplies the parallel tensor-times-matrix kernel and the compressed sparse fiber format used as the mode-specific baseline.","marker":"[37]"},{"why":"Introduces the mode-specific compressed sparse formats that ReLATE compares against and that prior approaches relied on.","marker":"[36]"},{"why":"Supplies the deep Q-network learning framework, including experience replay and target networks, that the agent's training builds on.","marker":"[26]"},{"why":"Provides double DQN, the stabilization mechanism for Q-value estimates used in the policy and target network update.","marker":"[10]"},{"why":"Provides prioritized experience replay, used to sample the most informative transitions during training.","marker":"[32]"},{"why":"Supplies the real-world sparse tensor data sets used in all evaluations.","marker":"[34]"}],"fun_headline_variants":["RL discovers tensor layouts that beat experts by 2x","Learned sparse tensor encoding speeds up decomposition","AI-designed tensor format outperforms hand-tuned ones","ReLATE learns faster sparse layouts without labels"],"cache_read_input_tokens":21632,"weakest_assumption_plain":"The search space is restricted to interleavings that preserve the low-to-high bit order inside each mode index; if the fastest encoding for some tensor requires permuting bits within a mode, ReLATE cannot find it.","fun_headline_variants_meta":{"raw":{"variants":["RL discovers tensor layouts that beat experts by 2x","Learned sparse tensor encoding speeds up decomposition","AI-designed tensor format outperforms hand-tuned ones","ReLATE learns faster sparse layouts without labels"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000233,"raw_usage":{"total_tokens":1323,"prompt_tokens":729,"completion_tokens":594,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":473,"completion_tokens_details":{"reasoning_tokens":533}},"tokens_in":473,"tokens_out":594,"duration_ms":6819,"temperature":1.0,"reasoning_tokens":533,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T13:46:14.880250+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate or randomly sample the restricted interleaving space on the paper's test tensors and measure kernel time: if random search matches the reported 1.4x geometric-mean speedup, the learned policy adds nothing beyond the search space. Alternatively, relax the restriction to allow intra-mode bit permutations and find an encoding that clearly beats the best restricted interleaving on any test tensor, showing the restriction is the bottleneck.","supporting_citations":[{"cited_title":"Helal, Jan Laukemann, Fabio Checconi, Jesmin Jahan Tithi, Teresa Ranadive, Fabrizio Petrini, and Jeewhan Choi","cited_arxiv_id":null,"evidence_quote":"Defines the linearized sparse tensor format and its bit-interleaved encoding, the representation ReLATE starts from and the baseline it must outperform."},{"cited_title":"Helal, S","cited_arxiv_id":null,"evidence_quote":"Provides the mode-agnostic linearized format implementation and benchmarks of prior formats; used as the expert-policy baseline in the reward function."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the mode-specific compressed sparse formats that ReLATE compares against and that prior approaches relied on."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the deep Q-network learning framework, including experience replay and target networks, that the agent's training builds on."},{"cited_title":"Choi, Jiajia Li, Richard Vuduc, Jongsoo Park, Xing Liu, and George Karypis","cited_arxiv_id":null,"evidence_quote":"Supplies the real-world sparse tensor data sets used in all evaluations."}],"review_version":1}