acceptodds
Under review as a conference paper at ICLR 2027

SparseBank: Sparse Measurement for Fixed Workflow Banks

Abstract

SparseBank studies sparse measurement for selecting a fixed workflow bank and routing queries within it. On the Automated Programming Progress Standard (APPS), support-aware -opt lowers routed regret against Uniform without replacement at 200 and 280 unique edges. The gain persists after matching unique counts and reflects support and weights jointly. Prospective CodeContests supports the preregistered primary -opt–Uniform mixture against Uniform. The unchanged sampler is a secondary replication arm and performs better than the mixture. HumanEval+ marks a boundary: ordinary least squares (OLS) shows no stable acquisition advantage and loses to a development-set predictor. Supporting theory bounds completion error and its transfer to bank and routed regret for realizable linear models with fresh independent noise. A realized-design corollary covers outcome-independent acquisition with full rank. The real-task evidence concerns frozen observed tables; it does not certify expected fresh-execution utility.

Primary area:
learning theory
Keywords:
large language models, workflow banks, workflow routing, active matrix completion, experimental design, G-optimal design, adaptive evaluation

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_pKr8OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This work proposes SparseBank, which uses G-optimal design and OLS completion to enable sparse measurement for workflow-bank selection and routing. Theoretically, it establishes prediction error bounds and their implications for bank-selection and routing regret. Experiments on APPS, CodeContests, and HumanEval+ evaluate the effectiveness of the proposed method.

Critical strengths
  1. The work addresses a practically relevant problem of reducing workflow evaluation costs through sparse measurements. The empirical results on APPS and CodeContests demonstrate the effectiveness of the proposed approach.
  2. Theoretical guarantees are established linking utility estimation errors to downstream bank-selection and routing regret, providing a principled basis for analyzing the quality of the resulting decisions.
Critical weaknesses
  1. The theoretical guarantees rely on strong assumptions that are not verified in real-world experiments. On APPS, the sufficient sample size for Theorem 1 exceeds the 800 distinct query–workflow pairs. Although Corollary 4 does not require this sample size condition, its model and noise assumptions remain unverified.
  2. HumanEval+ does not seem to demonstrate a statistically conclusive acquisition advantage, raising concerns about the consistency of the empirical improvements across benchmarks.

The introduction could better motivate the key challenges and clarify how the proposed approach differs from existing experimental design methods. As I am not an expert in optimal experimental design, I find it difficult to fully assess its methodological novelty relative to prior work.

Questions for authors

Given that the sufficient sample-size condition in Theorem 1 exceeds the number of distinct query–workflow pairs on APPS, to what extent do the theoretical guarantees inform the observed empirical performance?

Reviewer_kWW7OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper investigates how to efficiently evaluate and select agentic workflows without executing every workflow on every query. The proposed approach uses G-optimal experimental design to choose informative evaluations, followed by OLS to predict unobserved utilities. The authors derive bounds connecting prediction error to workflow-selection and routing regret. Experiments on APPS and CodeContests show improvements over uniform sampling, while HumanEval+ reveals limitations of the approach.

Critical strengths

Greatest strength

  • The paper's greatest strength is the attentively controlled evaluation. The authors distinguish improvements caused by eliminating duplicate measurements. The experiments provide meaningful evidence that G-optimal acquisition can improve downstream routing decisions.

** Moderate Strengths **

  • The paper is honest in its limitations. I commend the authors for what they wrote in the paragraph on line 454.
  • The paper includes negative results. Once again, I commend the authors for transparently reporting inconclusive and unfavorable results, particularly in Tables 20–21, where SparseBank fails to demonstrate a statistically significant advantage over simpler acquisition baselines.
  • I checked the proofs of the paper, and they are correct. With that being said, the theorems are mostly combinations of established results from optimal experimental design and ordinary least squares. I would consider the theorems to be incremental.
Critical weaknesses

While the authors provide a thorough empirical evaluation, the paper could offer more actionable guidance on selecting an acquisition strategy in practice. In particular, it would be useful to identify measurable characteristics of the feature representation or utility matrix that could help practitioners predict when G-optimal acquisition is likely to outperform simpler baselines.

Minor issues / subjective remarks:

  • Typo on line 101: "As in Introduction..." should be "As in the Introduction..."
  • I know that the authors write out what APPS stands for in the abstract, however they don't do this in the main paper. The scholarly convention is that the abstract and the main paper have separate name spaces.
  • I felt that the introduction lacked any discussion behind the motivation of their work. Although I recognize that the authors wrote this with a bespoke target audience, I suggest they make the exposition more accessible.
Questions for authors

The paper provides useful analyses of feature geometry, model misspecification, and acquisition budgets. Could the authors further characterize which measurable properties of a dataset or feature representation predict improvements in downstream routing regret? This would help practitioners determine when G-optimal acquisition is preferable to simpler baselines.

Reviewer_q1wiOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes SparseBank, a framework for reducing the evaluation cost of constructing and routing within a fixed bank of agentic workflows. Instead of exhaustively evaluating every query workflow pair, SparseBank uses G-optimal experimental design to select informative pairs for evaluation, fits an OLS model to predict unobserved utilities, and applies the original bank selection and routing procedures to the completed utility matrix. The method also considers support aware sampling without replacement to avoid redundant measurements. The authors establish uniform prediction error bounds and corresponding guarantees on bank selection and routing regret under linear realizability and independent noise assumptions.

The paper evaluates SparseBank through controlled synthetic experiments and APPS, CodeContests, and HumanEval+. On APPS, support aware G-optimal acquisition reduces routed regret relative to uniform sampling at matched unique measurement budgets, with similar improvements observed in a prospective CodeContests study. However, on HumanEval+ G-optimal acquisition shows no consistent advantage over alternative sampling strategies, and OLS completion underperforms a predictor trained on development data.

Critical strengths
  1. The paper goes beyond comparing G-optimal sampling against naive uniform sampling by explicitly controlling for duplicate observations and matching unique measurement budgets. On APPS, support aware G-optimal sampling reduces routed regret by approximately 26% relative to Uniform-WOR at both tested budgets, and CodeContests provides a prospective replication of the advantage. These experiments support the paper's claim that measurement allocation matters more than acquiring more distinct observations.

  2. Rather than evaluating matrix completion accuracy alone, the paper establishes how uniform utility-prediction error translates into bank selection and routing regret, provides sufficient conditions for exact decision recovery, and derives a dimension dependent lower bound. I like how this gives the paper coherent theoretical foundation tied to its actual decision objectives, rather than relying solely on improvements in prediction accuracy.

Critical weaknesses
  1. Although matching unique measurement budgets addresses duplicate sampling, the main support-aware method simultaneously changes the eligible support and the sampling probabilities. Its advantage over Uniform-WOR does not establish whether the gains arise from G-optimal weighting or simply restricting acquisition to a favorable subset of edges. A missing ablation is uniform sampling over the same G-optimal support, alongside alternative support-selection strategies.

  2. The real task comparisons use one cached execution outcome per query workflow pair, and the 100 seed replays vary acquisition masks rather than independently repeating workflow executions. Since the proposed theory concerns expected utilities, this leaves unclear whether the observed routing advantages persist when workflow outcomes are stochastic.

Questions for authors

My main questions are just to address the weaknesses from earlier.

  1. The support-aware G-optimal sampler differs from Uniform-WOR in both its sampling support and relative weights. Have the authors evaluated uniform sampling restricted to the same G-optimal support? This would help determine whether the reported gains are attributable to the G-optimal allocation itself or primarily to support selection.

  2. The real task evaluations rely on single observed utility tables, while the theoretical objective concerns expected workflow utilities. Is there any evidence from independently repeated workflow executions that the routing improvements persist when evaluated against expected utilities?

2 comments

Dear Reviewer q1wi,

We would like to briefly highlight that the revised manuscript now incorporates the additional analyses addressing your concerns, particularly the matched-support comparisons, alternative-support controls, and independent CodeContests execution results (Sections 6.4–6.5 and Appendices D–E).

We appreciate your review and would welcome any further questions or concerns during the remaining discussion period.

Thank you for your response and additional clarifications. I feel like my main concerns have been adequately addressed and I feel the overall contribution is solid. I will increase my score from 2 to 3, while noting to the AC that I have limited background in this area.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.