acceptodds
Under review as a conference paper at ICLR 2027

Exact Frontier Coupling for Adaptive Language Model Policy Evaluation

Abstract

Independent evaluation of adaptive language-model agents often repeats identical model requests across policies. We introduce Exact Frontier Coupling (EFC), a joint evaluator that shares these requests while preserving each policy's standalone trajectory distribution. At a history shared by active policies, EFC groups identical conditional action distributions and solves a local multi-marginal optimal transport problem to minimize expected distinct-request cost. We prove marginal trajectory preservation under matched response kernels. On 1,200 constructed frontiers, EFC reduces expected weighted request cost by 1.65% relative to common-quantile coupling optimized over every action order. In paired evaluations of the same 52 BFCL tasks across four models, exact-request sharing reduces physical model calls by 29-44% and yields 1.66-1.82 warmed-worker speedups over independent execution, with identical observed trajectories and official outcomes. The resulting savings make it feasible to evaluate more adaptive agents across more tasks under the same inference budget.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Language model agents, policy evaluation, multi-marginal optimal transport, coupling, inference efficiency

Reviews

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

This paper proposes Exact Frontier Coupling (EFC), which jointly samples actions from multiple LLM agent policies using multi-marginal optimal transport. By preserving each policy's marginal trajectory distribution while maximizing the reuse of identical model requests, EFC aims to reduce the computational cost of policy evaluation.

Critical strengths

S1. Well-motivated problem and principled formulation. The paper addresses the practical cost of evaluating multiple adaptive LLM agents by combining multi-marginal optimal transport with exact-request sharing.

S2. Good theoretical analysis. The paper provides well-structured theoretical results, including duplicate-law compression, the request-set LP characterization, and marginal trajectory preservation. The three-policy example clearly illustrates the limitations of pairwise tree coupling.

S3. Careful experimental design and practical efficiency. The experiments include strong baselines, paired comparisons, and numerical validation. Exact-request sharing achieve inference savings (29–44% on BFCL52) while preserving observed trajectories and evaluation outcomes.

Critical weaknesses

W1. Limited end-to-end improvement over strong baselines. Although EFC achieves local optimality, it does not outperform optimized quantile in the complete-episode experiments. The planned confirmation study was also not conducted, leaving its practical advantage insufficiently demonstrated. (Sec. 6.1, Table 1; Sec. 8)

W2. Unclear attribution of inference savings. The substantial savings reported on BFCL and AgentDojo primarily result from exact-request deduplication rather than EFC's coupling optimization. The incremental benefit of EFC in realistic agent settings remains unclear. (Sec. 6.2; Sec. 8)

W3. Limited robustness of exact-request sharing. Three Qwen models in BFCL64 were excluded due to output mismatches across execution modes. The causes and implications of these failures are not sufficiently investigated. (Sec. 6.2; Appendix J)

W4. Scalability concerns. The tuple-based LP grows exponentially with the number of distinct action distributions, and the method falls back to approximate coupling for larger problems. Its scalability to larger policy banks remains unclear. (Sec. 3.2; Sec. 8)

W5. Limited experimental coverage. The stochastic agent evaluation relies on a small, manually designed policy bank and a limited number of tasks. More diverse and realistic stochastic agent evaluations are needed to establish the practical value of EFC. (Sec. 5; Sec. 8)

Questions for authors
  1. Can EFC demonstrate consistent improvements over optimized quantile in complete-episode evaluations?
  2. How much of the reported inference savings comes from EFC's coupling optimization rather than exact-request deduplication?
  3. What caused the output mismatches for the three Qwen models in BFCL64, and how do they affect the method's reliability?
  4. How does EFC scale to larger policy banks, considering the exponential LP complexity and optimization overhead?
  5. Can the authors validate EFC on larger, more diverse stochastic agent policy banks and held-out tasks?
1 comment

We thank the reviewer for their time and careful evaluation of our paper. The revised paper addresses the five concerns through a matched complete-episode study, component ablations, and scaling and reliability audits.

W1/Q1. Complete-episode improvement (Section 6.1, Table 1; Appendix C). On 128 tasks with 24 stochastic policies, two models, and three seeds, request-set EFC uses 5,767 physical requests versus 7,099 for optimized quantile: an 18.76% reduction, with a multiplicity-adjusted task-cluster 95% interval of [12.22%, 24.86%]. It also improves on fragmentation-aware quantile, best-root TCAB, and tuple-based EFC. All four adjusted intervals are positive, and every comparison favors EFC in all six model–seed combinations.

The pilot's planned confirmation was not run because its continuation gate was not met (Appendix G). The 128-task evaluation was planned separately; its additional ablations reuse the same tasks.

W2/Q2. Attribution (Sections 3.1–3.2 and 6.2; Table 2). We implement the request-set formulation already presented in Section 3.1 of the original submission, retaining its primary objective and marginal constraints. The implementation in the original submission is retained as tuple-based EFC, including its behavior above the tuple-enumeration limit. All methods use the same exact-request-sharing executor and plan-cache budget, so the comparison measures coupling gains with sharing already available. Applying the tuple-based method's 2% acceptance threshold to request-set EFC retains 18.03% savings over optimized quantile; removing quantile-tie preservation retains 16.69%. Neither difference from full EFC is established after multiplicity correction. Section 6.2 separately attributes BFCL's 29–44% savings to exact-request reuse: its deterministic frontiers offer no coupling advantage.

W3/Q3. Qwen mismatches (Appendix L). The BFCL64 audit finds 14/766, 39/644, and 47/761 mismatching unique matched requests for Qwen3-4B/8B/14B, versus 0/2,981 for ToolACE-2-8B. Recorded inputs, seeds, and token limits agree. All 100 Qwen mismatches occurred with shared batches of eight versus independent batches of four, suggesting sensitivity to batch configuration. Full-trajectory checks detected these mismatches, and the affected runs are excluded from matched-trajectory serving claims. The stochastic study separately completed 24,228 repeated-request checks without mismatch.

W4/Q4. Scaling and overhead (Table 3; Appendix D). The primary LP uses 2K2^K variables for KK charged request identities. With four identities and 32 distinct laws, uncached optimization and conditional sampler construction take a median 12.44 ms. This audit retains the sampler implicitly; episode evaluation materializes joint assignments. We also vary request support and frontier fragmentation; complexity remains exponential in request support. Episode executor time including planning is 343.97 seconds versus 350.24 for optimized quantile, a descriptive 1.79% reduction (Appendix C, Table 5).

W5/Q5. Diversity and held-out tasks (Section 5; Appendix C). The bank covers all 24 permutations of four action priorities, with feedback-dependent action probabilities, on Qwen2.5 and Mistral. It was fixed before evaluation following development diagnostics. The 128 GSM8K training questions were held out from method development.

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

When multiple adaptive LLM-agent policies are evaluated on the same tasks, different policies often issue exactly the same model request at some step (identical prompt, decoding parameters, and tool state), so running them independently wastes inference. This paper aims to (i) execute each identical request only once and (ii) coordinate the policies’ random action choices so that they select the same requests more often, while keeping each policy’s standalone trajectory distribution unchanged. The proposed method, Exact Frontier Coupling (EFC), solves a linear program whenever several policies share the same history, choosing a joint action distribution that minimizes the expected number of distinct requests subject to preserving each policy’s own action distribution. The authors prove that, if shared requests return responses with the same distribution as standalone execution, each policy’s trajectory distribution is preserved.

On synthetic action distributions, EFC reduces the expected weighted request cost at a single decision point by 1.65% on average relative to optimized quantile coupling, in which all policies share one random number, and by 3.88% relative to TCAB. In a calculator-agent study with eight policies on 32 GSM8K tasks per model (two models, three runs), EFC uses 11% fewer requests than TCAB and 3% more than optimized quantile in total. On BFCL, sharing identical requests reduces model calls by 29–44% across four models with identical trajectories and outcomes. The authors note that every BFCL decision point had deterministic action laws, so EFC and quantile coupling attain the same cost there, and that this experiment measures the execution-level benefit of exact-request sharing.

Critical strengths
  1. The paper defines request identity as a complete executable key and proves that, provided shared requests return responses with the same distribution as standalone execution, each policy’s trajectory distribution is preserved under coupled execution. This guarantee is the minimum requirement for sharing inference across policies without biasing the evaluation of any individual policy.
  2. The paper shows with a clear example that tree-based coupling (TCAB) can be suboptimal when three or more distinct action distributions compete for the same requests. It also shows that the optimization scales with the number of distinct action distributions rather than the number of policies, and that for the primary objective it admits an equivalent formulation sized by the number of distinct requests. Conversely, with at most two distinct requests, a shared-random-number (quantile) coupling is already optimal. Together, these results give practitioners a diagnostic for deciding when joint optimization is worthwhile and when plain request deduplication is enough.
Critical weaknesses

The novelty is incremental. The problem and trajectory-preservation guarantee closely follow Fast A/B/n Testing: Exact Multi-Policy Comparison via Tree-Coupled Feedback Sharing (Wen, 2026). Minimizing the number of distinct outcomes under marginal constraints has been studied in Tight Bounds for Sampling q-Colorings via Coupling from the Past (Ding et al., 2026). The remaining components draw on standard optimal-transport coupling and request caching, so the contribution is mainly an instantiation of these ideas for LLM policy evaluation.

Questions for authors

Beyond replacing TCAB’s tree coupling with a global LP, what do you see as the main technical novelty of EFC relative to existing multi-marginal and grand-coupling formulations (e.g., Ding et al., 2026)?

1 comment

We thank the reviewer for their time and careful evaluation of our paper, and for the opportunity to clarify EFC’s technical contribution beyond existing coupling formulations.

Relation to prior formulations (Section 7). Wen (2026) establishes trajectory-preserving adaptive feedback sharing through tree coupling and identifies the unrestricted distinct-outcome objective as a multi-marginal transport problem. Ding et al. (2026) derive a reduced LP and an explicit optimal coupling for a structured family of uniform distributions over color-set complements.

EFC’s technical contribution is an exact request-set reduction for general finite, potentially nonuniform action laws and monotone request-set costs, together with a construction that turns its solution into executable actions with the prescribed marginals.

Technical contribution (Sections 3.1–3.2; Appendix B.4). After aggregation by request identity, UU distinct laws over KK charged identities and a free action can require (K+1)U(K+1)^U tuple variables. The equivalent formulation uses 2K2^K request-set probabilities and attains the same primary optimum for monotone request-set costs (Equation (4)). Building on the random-set selection criterion of Artstein (1983), a fractional Hall/max-flow construction converts these probabilities into executable actions while preserving every policy’s action marginal. Input processing and action construction still depend on UU, and the LP remains exponential in KK.

The theory also identifies when simpler coupling suffices: optimized quantile is already optimal for at most two charged identities plus free STOP under additive nonnegative costs (Lemma 2, Appendix K.3). The example in Section 3.1 isolates the limitation of TCAB’s Markov-tree construction.

Practical consequence (Section 6.1, Table 1; Appendix C). The request-set formulation was already presented in Section 3.1 of the original submission. We implement and evaluate it, retaining its primary objective and marginal constraints. The implementation in the original submission is retained as tuple-based EFC. At a frontier with 24 distinct laws and four charged identities plus free STOP, the reduction gives 16 set variables instead of 5245^{24} tuples.

On 128 GSM8K training questions held out from method development, with 24 stochastic policies, two models, and three seeds, request-set EFC uses 17.16% fewer complete-episode physical requests than tuple-based EFC and 18.76% fewer than optimized quantile, with positive multiplicity-adjusted 95% intervals. All methods use the same policy bank and exact-request-sharing executor. These results demonstrate the practical value of the reduction beyond the tuple-enumeration limit.

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

This paper proposes Exact Frontier Coupling (EFC) for jointly evaluating adaptive language-model policies while sharing identical model requests. At each shared-history frontier, EFC solves a multi-marginal linear program that minimizes immediate expected distinct-request cost while preserving policy marginals. The paper provides theoretical properties, constructed-distribution experiments, a stochastic calculator-agent pilot, and serving measurements on BFCL and AgentDojo. However, the experiments do not establish that the proposed coupling optimizer improves practical evaluation efficiency over simpler coupling and memoization baselines.

Critical strengths
  • Reducing redundant inference across related agent policies is a practically relevant problem.

  • The distinction between preserving individual trajectory distributions and changing cross-policy dependence is important and explicitly addressed.

  • Duplicate-law compression and the request-set formulation provide useful structural observations about the optimization problem.

  • The serving experiments measure physical calls, tokens, and worker time, and the authors disclose unsuccessful confirmation gates and incomplete comparisons.

Critical weaknesses
  • The largest reported gains do not validate the proposed coupling optimizer. The BFCL experiments show substantial savings from exact-request sharing, but Section 6.2 states that the observed frontiers have deterministic action laws and that optimized quantile coupling and EFC attain the same immediate cost. Moreover, task-local distinct-key memoization exactly matches the shared call counts.

  • These results demonstrate the usefulness of executing repeated requests once, but do not establish an incremental benefit from the proposed multi-marginal optimization. The paper’s empirical emphasis on 29–44% call savings and substantial speedups therefore does not directly support its central algorithmic contribution.

  • The complete-episode experiment does not outperform the strongest coupling baseline. In the three-run calculator pilot, EFC uses 533 requests compared with 517 for optimized quantile coupling and 533 for fragmentation-aware quantile coupling. Thus, EFC is worse than one strong baseline and tied with the other. The prespecified continuation gate was not met, and the planned confirmation study was not conducted.

  • The positive 1.65% improvement on constructed frontiers establishes a local optimization advantage on those distributions, but does not show that this advantage translates into lower complete-episode cost. This distinction is central because coupling choices alter subsequent shared histories.

  • The theoretical guarantee is narrower than the practical evaluation objective. Local cost optimality does not imply optimal total evaluation cost. The disagreement-based tie-break is a heuristic for maintaining future sharing, and the pilot results illustrate that minimizing immediate cost can fail to improve complete episodes.

  • Marginal trajectory preservation is useful, but it also does not preserve the joint score distribution, selection probabilities, or statistical precision. Consequently, identical selected policies in the small pilot are insufficient evidence that evaluation quality is maintained at a lower budget. In particular, every method retains the protected incumbent under a conservative testing procedure, which may reflect limited selection power.

  • Scalability and applicability to realistic stochastic policy banks remain unclear. The evaluated tuple formulation grows exponentially with the number of distinct conditional action laws. The calculator experiment contains at most four distinct laws over five actions, requiring only 625 assignments, and never exercises the fallback branch. The larger benchmark experiments use deterministic controllers and therefore do not test nontrivial coupling optimization at scale.

  • Although the request-set formulation is potentially useful, it is not the implementation used for the reported agent evaluations. The paper needs measurements of planning overhead and total runtime as action support, policy diversity, and frontier fragmentation increase.

  • The presentation and evaluation protocols make the contribution difficult to assess. The paper moves among an exact LP candidate, a guarded execution procedure, and an exact-request-sharing executor, while the different experiments validate different parts of this system. Results from the original screen, later comparator study, development pilot, and several benchmark cohorts are spread across the main text and appendices.

  • The scope of the serving evidence is also conditional: only one model is admitted in BFCL64, and AgentDojo excludes an incomplete shard. These exclusions are disclosed, but their implications for operational reliability need clearer treatment. The reproducibility statement also leaves unclear whether executable code, numerical inputs, and audit records are available with the submission.

Questions for authors

Please refer to the weaknesses

1 comment

We thank the reviewer for their time and careful evaluation of our paper, and for emphasizing the need to distinguish coupling gains from exact-request reuse.

The revised paper shows complete-episode savings with request sharing available to every method (Section 6.1, Table 1). On 128 GSM8K training questions held out from method development, with 24 stochastic policies, two models, and three seeds, request-set EFC uses 5,767 physical requests:

ComparatorRequestsReduction with EFCAdjusted 95% interval
Tuple-based EFC6,96217.16%[9.26%, 24.49%]
Optimized quantile7,09918.76%[12.22%, 24.86%]
Fragmentation-aware quantile7,23420.28%[13.98%, 25.89%]
Best-root TCAB8,00627.97%[21.02%, 34.22%]

All four baseline comparisons favor EFC in all six model–seed combinations. The task-cluster bootstrap intervals use Bonferroni correction across six contrasts. Methods share the executor and plan-cache budget while following their own adaptive trajectories. The revised presentation separates coupling gains, evaluated with sharing available to every method in Section 6.1, from execution-level savings due to exact-request reuse in Section 6.2.

Mechanism and ablations (Sections 3.1–3.2; Table 2). We implement the request-set formulation already presented in Section 3.1 of the original submission, retaining its primary objective and marginal constraints. Four charged request identities require only 16 primary LP variables, enabling exact optimization beyond the tuple-enumeration limit. The implementation in the original submission is retained as tuple-based EFC, including its behavior above that limit. Applying its 2% acceptance threshold to request-set EFC still gives 18.03% savings over optimized quantile; removing quantile-tie preservation retains 16.69%. Most savings persist under either change; neither difference from full EFC is established after multiplicity correction.

Confirmation and scope (Appendices C and G). The pilot’s planned confirmation was not run because its continuation gate was not met. The 128-task evaluation was planned separately; its additional ablations reuse the same tasks. The bank covers all 24 permutations of four action priorities and was fixed before evaluation following development diagnostics.

Scaling and total cost (Table 3; Appendices C–D). Planning takes 8.59 seconds versus 115.59 for tuple-based EFC. Executor time including planning is 343.97 seconds, versus 457.16 for tuple-based EFC and 350.24 for optimized quantile; these timings are descriptive. The controlled scaling audit reaches 32 distinct laws and varies request support and frontier fragmentation; dependence on request support remains exponential.

Guarantees and reproducibility (Section 4; Appendices A, L–M). Marginal trajectory preservation assumes that model responses and environment transitions follow their standalone conditional laws. It guarantees neither optimal episode cost nor an unchanged joint score distribution or selection power. All 672 stochastic-study blocks completed, with no mismatch in 24,228 repeated-request checks. Appendices L–M document the Qwen mismatch audit and AgentDojo context-limit exclusion. The attached anonymous supplement provides executable code and records for reproducing the matched comparisons and supporting audits.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of paper revisions

We sincerely thank all reviewers for their thoughtful evaluation and constructive feedback. Their comments helped us clarify EFC’s contribution and strengthen the experimental evidence. We summarize the main revisions below:

  • Complete-episode evidence. On 128 GSM8K training questions held out from method development, with 24 stochastic policies, request-set EFC uses 18.76% fewer physical requests than optimized quantile, with exact-request sharing available to every method. We also compare with the implementation in the original submission, retained as tuple-based EFC, and include component ablations (Section 6.1, Tables 1–2; Appendix C).
  • Implementation and scaling. We implement the request-set formulation from the original submission and measure planning overhead and scaling (Sections 3.1–3.2, Table 3; Appendix D).
  • Contribution and attribution. We clarify the relation to prior coupling formulations and distinguish coupling gains from execution-level request reuse (Sections 7 and 6.2).
  • Reliability and reproducibility. We add the Qwen mismatch audit and clarify serving exclusions (Appendices L–M), and update the anonymous code in the supplementary material.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.