From Interaction Trajectories to Prompt Rules: Credit Assignment for Multi-Agent Prompt Optimization

Bin Wu, Haoran Xu, Xiang Zhuang, Zonghao Chen, Zhu Li, Emine Yilmaz, Qiang Zhang
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:137252-137271, 2026.

Abstract

Large language model (LLM)-based multi-agent systems commonly rely on natural-language prompts to specify agent behavior, yet optimizing these prompts remains challenging when agent roles and interaction structures are fixed by design. In such systems, behaviors emerge over long, noisy interaction trajectories, making it difficult to determine which prompt components are responsible for success or failure. As a result, outcome-level feedback alone is insufficient, while existing prompt optimization methods typically rely on final task scores or global prompt rewrites, limiting their ability to exploit trajectory evidence or support the localized updates. We propose Trajectory-based Rule Credit Estimation (TRUCE), a framework for prompt optimization in multi-agent systems that explicitly addresses this credit assignment challenge. TRUCE performs trajectory-aware attribution by linking outcome feedback to informative sub-trajectories and translating the resulting credit signals into unit-level edits over prompt-defined behavioral rules. By preserving agent roles and interaction structures, TRUCE enables prompt refinement through localized updates aggregated across tasks. Experiments on multiple benchmarks demonstrate that TRUCE consistently improves task performance and efficiency over competitive baselines. Code is available at https://github.com/bingo-w/TRUCE.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-wu26bp, title = {From Interaction Trajectories to Prompt Rules: Credit Assignment for Multi-Agent Prompt Optimization}, author = {Wu, Bin and Xu, Haoran and Zhuang, Xiang and Chen, Zonghao and Li, Zhu and Yilmaz, Emine and Zhang, Qiang}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {137252--137271}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/wu26bp/wu26bp.pdf}, url = {https://proceedings.mlr.press/v306/wu26bp.html}, abstract = {Large language model (LLM)-based multi-agent systems commonly rely on natural-language prompts to specify agent behavior, yet optimizing these prompts remains challenging when agent roles and interaction structures are fixed by design. In such systems, behaviors emerge over long, noisy interaction trajectories, making it difficult to determine which prompt components are responsible for success or failure. As a result, outcome-level feedback alone is insufficient, while existing prompt optimization methods typically rely on final task scores or global prompt rewrites, limiting their ability to exploit trajectory evidence or support the localized updates. We propose Trajectory-based Rule Credit Estimation (TRUCE), a framework for prompt optimization in multi-agent systems that explicitly addresses this credit assignment challenge. TRUCE performs trajectory-aware attribution by linking outcome feedback to informative sub-trajectories and translating the resulting credit signals into unit-level edits over prompt-defined behavioral rules. By preserving agent roles and interaction structures, TRUCE enables prompt refinement through localized updates aggregated across tasks. Experiments on multiple benchmarks demonstrate that TRUCE consistently improves task performance and efficiency over competitive baselines. Code is available at https://github.com/bingo-w/TRUCE.} }
Endnote
%0 Conference Paper %T From Interaction Trajectories to Prompt Rules: Credit Assignment for Multi-Agent Prompt Optimization %A Bin Wu %A Haoran Xu %A Xiang Zhuang %A Zonghao Chen %A Zhu Li %A Emine Yilmaz %A Qiang Zhang %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-wu26bp %I PMLR %P 137252--137271 %U https://proceedings.mlr.press/v306/wu26bp.html %V 306 %X Large language model (LLM)-based multi-agent systems commonly rely on natural-language prompts to specify agent behavior, yet optimizing these prompts remains challenging when agent roles and interaction structures are fixed by design. In such systems, behaviors emerge over long, noisy interaction trajectories, making it difficult to determine which prompt components are responsible for success or failure. As a result, outcome-level feedback alone is insufficient, while existing prompt optimization methods typically rely on final task scores or global prompt rewrites, limiting their ability to exploit trajectory evidence or support the localized updates. We propose Trajectory-based Rule Credit Estimation (TRUCE), a framework for prompt optimization in multi-agent systems that explicitly addresses this credit assignment challenge. TRUCE performs trajectory-aware attribution by linking outcome feedback to informative sub-trajectories and translating the resulting credit signals into unit-level edits over prompt-defined behavioral rules. By preserving agent roles and interaction structures, TRUCE enables prompt refinement through localized updates aggregated across tasks. Experiments on multiple benchmarks demonstrate that TRUCE consistently improves task performance and efficiency over competitive baselines. Code is available at https://github.com/bingo-w/TRUCE.
APA
Wu, B., Xu, H., Zhuang, X., Chen, Z., Li, Z., Yilmaz, E. & Zhang, Q.. (2026). From Interaction Trajectories to Prompt Rules: Credit Assignment for Multi-Agent Prompt Optimization. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:137252-137271 Available from https://proceedings.mlr.press/v306/wu26bp.html.

Related Material