Binding Paraphrased Instructions to Encountered Objects in sLLM Agents under Partial Observability

Chanyoung Kim; Harim Song; Byoungchan Ko; Keonyoung Lee; Myungwon Lee; Dahuin Jung

cs.LGNov 5, 2026

Binding Paraphrased Instructions to Encountered Objects in sLLM Agents under Partial Observability

Authors: Chanyoung Kim, Harim Song, Byoungchan Ko, Keonyoung Lee, Myungwon Lee, Dahuin Jung

Organizations: School of Computer Science and Engineering, Soongsil University, Seoul, Korea · Department of Artificial Intelligence, Chung-Ang University, Seoul, Korea

Abstract

Reliable deployment of LLM agents requires grounding diverse user expressions in their environments. Although RL-finetuned smaller large language model (sLLM) agents rival larger prompted LLMs on embodied tasks, their robustness to instruction paraphrases remains unclear. We introduce ALFWorld-Para to evaluate this robustness under controlled paraphrases, revealing 21-52% declines in success rates (SRs), predominantly driven by object synonyms. Despite retaining knowledge of synonym referents, agents often fail to take the corresponding objects even after observing them, exposing a gap between referential knowledge and object binding. Partial observability further complicates binding, as referents may remain unseen or have already been encountered under different labels. To address this challenge, we propose BINDIntent, a training-free framework that probabilistically binds referring expressions to observed labels using semantic proximity and estimated persistence against unseen candidates. Without additional training or LLM calls, BINDIntent improves synonym-paraphrase success of RL-finetuned sLLMs by 17.5-49.1 percentage points (pp) with only 0.4 ms of CPU overhead per step. It also raises GiGPO-7B's overall SR from 61.8% to 77.4%, surpassing a prompted 24B LLM. Code and benchmark are available at https://github.com/cau-hai-lab/ALFWorld-Para.

Figures & tables

Figure 1: Under partial observability, an sLLM agent that succeeds on a templated instruction fails on its paraphrased counterpart.

Prior Work	Perturbed Component	Instruction Para. Types (#)	RL Algorithms	Mitigation
Yang et al.,2024	Instruction	1	–	Training
Aissi et al.,2025	System	–	PPO	Training
Fu et al.,2025	System	–	–	Training
Xia et al.,2025	System	–	–	Training
Gu et al.,2026	System	–	–	–
Ye et al.,2026	System	–	GRPO	Training

Table 1: Comparison with prior work on LLM agent robustness in terms of perturbed component, instruction paraphrase types, RL algorithms, and whether mitigation requires training. † Evaluated on VLA models.

Type	Instruction
Original	put a book in sidetable
ACTION $\cdot$ Lexical
Addition	directly put a book in the sidetable
Same-Polarity	set a book in the sidetable
ACTION $\cdot$ Structural
Coordination	grasp a book and put it in the sidetable

Table 2: Paraphrase taxonomy in ALFWorld-Para. Colored italic text marks the span controlled by each axis; upright text is fixed.

Model	ALFWorld	ALFWorld-Para	SR Drop (%)
Pretrained (Prompting method: ReAct)
Mistral-S-24B	80.7	63.8	$-$ 20.9
Qwen3-14B	82.1	60.1	$-$ 26.8
Phi-4-14B	63.9	49.0	$-$ 23.3
Llama3.1-8B	31.4	17.8	$-$ 43.3
Qwen2.5-7B	54.0	29.0	$-$ 46.3

Table 3: Success rate (SR) (%) on ALFWorld and ALFWorld-Para. SR Drop: relative change.

Figure 2: Success rate (%) of pretrained (left) and RL-finetuned (right) LLMs on original ALFWorld (None) and on ALFWorld-Para, grouped by paraphrase axis and type. Each marker is one model, with marker size indicating parameter count; horizontal bars and diamonds denote the median and mean across models.

Figure 3: Paraphrase knowledge (%) of reference pretrained LLMs (top) and RL-finetuned sLLMs (bottom). Each RL row shows four algorithms on one backbone.

Figure 4: Taken rate (%): among steps in which the target object is observed, up to and including its first take, the proportion of those at which the agent takes it.

Figure 5: Overview of BINDIntent. The framework binds paraphrased object expressions to observed environment labels and forwards the rewritten instruction to a frozen agent.

Model	Baseline				Greedy				Self-clarification				BINDIntent SBERT				BINDIntent (ours)
Split =	None	Add	Same-P	All	None	Add	Same-P	All	None	Add	Same-P	All	None	Add	Same-P	All	None	Add	Same-P	All
Pretrained (Prompting method: ReAct)
Mistral-S-24B	76.5	72.0	44.2	63.8	38.1	38.2	28.7	34.9	70.2	68.8	55.0	64.5	71.6	70.4	44.6	61.9	73.7	70.9	56.5	66.8
Qwen3-14B	77.5	72.9	31.7	60.1	39.0	37.9	27.8	34.7	66.6	63.4	49.2	59.5	72.2	68.6	37.6	59.1	73.3	69.1	52.8	64.8
Phi-4-14B	59.9	58.0	30.1	49.0	30.5	30.1	22.0	27.4	60.3	59.1	40.8	53.2	55.3	56.5	32.5	47.8	56.6	55.9	44.9	52.3
Llama3.1-8B	30.2	21.6	0 2.8	17.8	15.2	14.5	11.7	13.7	25.1	28.0	15.8	22.9	24.5	23.0	8.7	18.5	29.2	25.7	12.4	22.2

Table 4: Success rate (%) on ALFWorld-Para by object-axis paraphrase type: None (object unchanged), Add (Addition), Same-P (Same-Polarity), and All. Best All score per row in bold . Averaged over three seeds.

Figure 6: Per-step latency introduced by each method across agent models. Note the discontinuous y-axis.

Task Type	Goal Instruction Templates
Pick & Place	put a {item} in {recep} put some {item} on {recep}
Examine in Light	look at {item} under the {lamp} examine the {item} with the {lamp}
Clean & Place	put a clean {item} in {recep} clean some {item} and put it in {recep}
Heat & Place	put a hot {item} in {recep} heat some {item} and put it in {recep}
Cool & Place	put a cool {item} in {recep} cool some {item} and put it in {recep}
Pick Two & Place	put two {item} in {recep} find two {item} and put them in {recep}

Table 5: The 6 task types in ALFWorld Shridhar et al. (2021) and their goal instruction templates. Each task type has 2 template variants.

Appendix figures & tables33 assets

Supplementary material from the paper’s appendix.

Appendix

Axis	Category	Type	Count
Object	Lexical	Same-Polarity	226
Object	Lexical	Addition	226
Action	Lexical	Same-Polarity	226
	Lexical	Addition	226
	Structural	Coordination	226
	Structural	Subordination	226

Appendix

Table 6: ALFWorld-Para dataset breakdown by axis, category, and type. Each of the 226 base instructions is perturbed into 11 single-perturbation types (2 object + 9 action) and 18 compositional ones (every object

\times

action pair), yielding

226\times 29=6{,}554

instructions.

Model	Codebase	Weights	Fine-tuning code
ALFWorld-Para
Pretrained (Prompting method: ReAct)
Mistral-S-24B	xxyQwQ/StraTA	RedHatAI/Mistral-Small-24B-Instruct-2501-FP8-dynamic	–
Qwen3-14B	xxyQwQ/StraTA	Qwen/Qwen3-14B-FP8	–
Phi-4-14B	xxyQwQ/StraTA	RedHatAI/phi-4-quantized.w8a8	–
Llama3.1-8B	xxyQwQ/StraTA	RedHatAI/Meta-Llama-3.1-8B-Instruct-FP8	–

Appendix

Table 7: Codebase and weights per model. Each model is evaluated in the codebase it was trained with; our checkpoints follow that codebase’s default training configuration. Codebases: StraTA, verl-agent, and BEACON ( Wang et al., 2026b ) . † The original GiGPO release does not include a ScienceWorld checkpoint.

Model	RTX 4090 h	A100 h
RL training
PPO-1.5B (ALFWorld)	–	94
GRPO-1.5B (ALFWorld)	–	50
GiGPO-1.5B (ALFWorld)	–	53
StraTA-1.5B (ALFWorld)	–	70
GiGPO-7B (ScienceWorld)	–	160

Appendix

Table 8: Compute in GPU hours. Models with up to 7B parameters on ALFWorld-Para are reported in RTX 4090 hours and all other rows in A100 hours, with H100 times converted at 2 A100 hours per H100 hour. Evaluation rows report a single pass (one seed) over each benchmark; some times are estimated from measured throughput.

Panel of Figure 7 — Figure 7: Query used by Self-clarification at every step. {observed_objects} lists the object types observed so far without instance indices, and {phrases} lists the quoted referring expressions of the instruction.

	GiGPO-7B				StraTA-1.5B
$\Delta\tau$	None	Add	Same-P	All	None	Add	Same-P	All
0.20	87.4	82.1	50.2	72.7	81.4	74.2	49.8	68.0
0.10	84.6	85.6	54.6	74.6	86.1	80.8	54.3	73.3
0.05	88.5	87.0	58.1	77.5	84.5	82.1	55.8	73.8
0.04	88.9	86.8	57.6	77.4	85.2	81.2	56.1	73.8
0.02	89.0	86.7	56.4	77.0	84.7	77.4	55.7	72.2

Appendix

Table 9: Ablation of the lexical allowance step

\Delta\tau

(

\tau_{t}=t\,\Delta\tau

);

\Delta\tau=0

permits only exact matches throughout the episode. Success rate (%) on ALFWorld-Para by object-axis paraphrase type; the shaded row is the setting used in all main experiments.

	GiGPO-7B				StraTA-1.5B
$\kappa$	None	Add	Same-P	All	None	Add	Same-P	All
0	85.5	81.6	65.4	77.2	82.1	75.9	63.4	73.5
0.25	88.0	86.7	63.1	78.9	84.9	81.0	60.8	75.2
0.5	89.4	86.2	61.7	78.7	85.4	81.6	58.1	74.7
1	88.9	86.8	57.6	77.4	85.2	81.2	56.1	73.8
2	88.6	87.3	52.4	75.7	85.4	81.7	51.9	72.6

Appendix

Table 10: Ablation of the scale

\kappa

on the number of remaining chances,

k_{t}\to\kappa\,k_{t}

;

\kappa=1

counts each unexplored unit once. Success rate (%) on ALFWorld-Para by object-axis paraphrase type; the shaded row is the setting used in all main experiments.

	GiGPO-7B				StraTA-1.5B
$c$	None	Add	Same-P	All	None	Add	Same-P	All
3	88.9	86.8	57.6	77.4	85.2	81.2	56.1	73.8
4	88.6	86.8	57.3	77.2	85.3	80.8	56.3	73.8
5	89.2	86.8	58.3	77.7	85.5	81.4	55.5	73.7
6	88.6	86.9	59.0	77.8	85.1	82.1	55.9	74.0
7	89.3	86.9	57.8	77.6	85.7	81.5	55.9	74.0

Appendix

Table 11: Ablation of the fallback threshold

c

below which Persistence falls back to the exchangeability-based estimate. Success rate (%) on ALFWorld-Para by object-axis paraphrase type; the shaded row is the setting used in all main experiments.

	GiGPO-7B				StraTA-1.5B
Variant	None	Add	Same-P	All	None	Add	Same-P	All
BINDIntent	88.9	86.8	57.6	77.4	85.2	81.2	56.1	73.8
Deterministic binding	88.2	84.1	59.0	76.7	84.5	78.4	58.1	73.2
Fallback-only persistence	89.3	82.1	38.3	69.2	85.6	76.4	36.7	65.6
No centering	88.4	87.1	54.9	76.4	85.1	81.0	53.1	72.7

Appendix

Table 12: Component ablation (SR, %) on ALFWorld-Para. Deterministic binding : bind once

P^{\max}_{t}>0.5

; Fallback-only persistence :

|V_{t}|/(|V_{t}|+k_{t})

in place of the Weibull model; No centering : Match on raw embeddings. Shaded: full method.

	Per stage
Method	Embed	Dist.	Weibull	LLM	Bind.	Total
Greedy	0.02	0.14	–	–	0.03	0.25
BINDIntent ${}_{\text{SBERT}}$	2.41	0.20	0.10	–	0.07	2.86
BINDIntent	0.02	0.15	0.09	–	0.06	0.38
Self-clarification, Pretrained
Qwen2.5-1.5B	–	–	–	29.92	0.32	30.43

Appendix

Table 13: Per-step latency breakdown (ms). Embed: embedding of the referring expression and observed object names; Dist.: candidate distance computation; Weibull: persistence estimation; LLM: additional call to the agent LLM; Bind.: binding decision. Greedy, BINDIntent

{}_{\text{SBERT}}

, and BINDIntent do not call the agent LLM and are averaged over all agent models; Self-clarification is reported per agent model. Total includes observation update and instruction rewriting.

Task	Action frame
Conductivity	Your task is to determine if [obj] is electrically conductive. The [obj] is located around the [obj] . First, focus on the [obj] . If it is electrically conductive, place it in the red [obj] . If it is electrically nonconductive, place it in the green [obj] .
Melting point	Your task is to measure the melting point of [obj] , which is located around the [obj] . First, focus on the [obj] . Next, focus on the [obj] . If the melting point of [obj] is above 150.0 degrees celsius, focus on the red [obj] . If the melting point of [obj] is below 150.0 degrees celsius, focus on the green [obj] . The [obj] are located around the [obj] .
Find	Your task is to find a(n) [obj] . First, focus on the thing. Then, move it to the green [obj] in the [obj] .
Life span	Your task is to find the [obj] with the longest life span. The [obj] are in the ‘outside’ location. Focus on the [obj] with the longest life span.
Chemistry	Your task is to use chemistry to create the substance ‘ [obj] ’. A [obj] and some of the ingredients might be found near the [obj] . When you are done, focus on the [obj] .
Paint mixing	Your task is to use chemistry to create green [obj] . When you are done, focus on the green [obj] .

Appendix

Table 14: Action frames of ScienceWorld-Para by task. [obj] denotes an object slot paraphrased on the object axis; all other text is kept fixed.

Model	ScienceWorld	ScienceWorld-Para	Score Drop (%)
PPO-7B	45.2	38.1	$-$ 15.7
GRPO-7B	30.7	27.6	$-$ 10.1
GiGPO-7B	63.7	50.8	$-$ 20.3
StraTA-7B	63.9	55.3	$-$ 13.5

Appendix

Table 15: Average score on ScienceWorld and ScienceWorld-Para. Score Drop: relative change.

	ScienceWorld	ScienceWorld-Para
		Action			Object		Action $\times$ Same-P
Model	None	Others	Quest.	Hint	Add	Same-P	Others	Quest.	Hint
PPO-7B	45.2	46.7	46.7	42.3	43.7	26.5	25.1	27.8	23.2
GRPO-7B	30.7	36.2	36.2	33.6	32.1	14.7	16.3	13.0	17.1
GiGPO-7B	63.7	63.2	55.3	63.8	54.9	36.0	35.7	35.4	36.5
StraTA-7B	63.9	62.8	63.3	61.8	60.3	42.5	43.4	46.1	41.0

Appendix

Table 16: Average score of RL-finetuned Qwen2.5-7B (Baseline) on ScienceWorld-Para by action and object paraphrase type. Others: mean over the seven action types other than Question and Hint.

Figure 8: Paraphrase knowledge (%) on ScienceWorld-Para of the pretrained Qwen2.5-7B backbone (top) and its RL-finetuned variants (bottom). The RL row shows four RL algorithms; error bars denote the standard deviation across the five probe templates.

Figure 9: Taken rate (%): among steps in which the target object is observed, up to and including its first take, the proportion of those at which the agent takes it. The top row denotes the shared Qwen2.5-7B backbone.

Model	Baseline				Greedy				Self-clarification				BINDIntent SBERT				BINDIntent (ours)
Split =	None	Add	Same-P	All	None	Add	Same-P	All	None	Add	Same-P	All	None	Add	Same-P	All	None	Add	Same-P	All
Base-7B	13.8	11.6	0 9.0	11.5	14.0	14.2	11.6	13.3	14.2	13.5	12.0	13.2	14.0	12.2	0 9.5	11.9	13.5	12.6	0 9.4	11.8
PPO-7B	46.1	42.8	25.3	38.1	22.1	18.8	18.2	19.7	43.3	43.8	37.9	41.7	44.3	41.7	32.6	39.5	45.8	43.0	34.3	41.0
GRPO-7B	35.4	31.5	15.9	27.6	22.3	19.9	18.2	20.1	35.3	32.8	23.6	30.6	32.9	33.5	23.7	30.0	36.5	30.3	26.1	31.0
GiGPO-7B	62.6	54.1	35.8	50.8	24.7	22.2	21.6	22.9	56.0	50.1	34.2	46.8	62.2	53.7	41.1	52.3	62.7	53.2	42.8	52.9
StraTA-7B	62.9	59.8	43.3	55.3	45.7	40.7	36.4	41.0	62.9	59.9	52.1	58.3	61.3	60.6	50.3	57.4	63.0	61.4	51.7	58.7

Appendix

Table 17: Average score (0–100) on ScienceWorld-Para by object-axis paraphrase type: None (object unchanged), Add (Addition), Same-P (Same-Polarity), and All. BINDIntent SBERT replaces Numberbatch embeddings with SBERT. Best per row in bold for Same-P and All.

	Qwen2.5-7B
Method	Base	PPO	GRPO	GiGPO	StraTA
Greedy	0.51	0.51	0.51	0.51	0.51
Self-clarification	140.5	129.5	160.3	139.9	132.9
BINDIntent ${}_{\text{SBERT}}$	12.4	12.4	12.4	12.4	12.4
BINDIntent	0.78	0.78	0.78	0.78	0.78

Appendix

Table 18: Per-step method latency (ms) on ScienceWorld-Para.

Panel of Figure 10 — Figure 10: Example interaction trajectory on ALFWorld. Environment observations (left, blue) provide text observations and admissible actions. The agent (right, green) selects actions based on the goal instruction. StraTA (orange) additionally generates a global strategy at Step 0, which is prepended to every subsequent action turn.

Panel of Figure 11 — Figure 11: Prompt used for generating action axis paraphrases. Placeholders {obj:FORM} , {recep:FORM} , and {toggle:FORM} are preserved in the output and filled with entity names at assembly time.

Panel of Figure 12 — Figure 12: Type-specific suffixes for the action axis (lexical types), appended to the action axis prefix (Figure 11 ).

Panel of Figure 13 — Figure 13: Type-specific suffixes for the action axis (structural types), appended to the action axis prefix (Figure 11 ).

Panel of Figure 14 — Figure 14: Type-specific suffixes for the action axis (pragmatic types), appended to the action axis prefix (Figure 11 ).

Panel of Figure 15 — Figure 15: Type-specific suffixes for the object axis, appended to the object axis prefix (Figure 16 ).

Panel of Figure 16 — Figure 16: Prompt used for generating object axis paraphrases. The {ALFWORLD_ENV_OBJECTS} placeholder is replaced with the full entity list at generation time.

Panel of Figure 17 — Figure 17: Verifier prompts for object axis (top) and action axis (bottom). Generated paraphrases are filtered through these verifiers before inclusion in ALFWorld-Para.

Panel of Figure 18 — Figure 18: Instruction (top) and object reference (bottom) provided to human evaluators for verifying semantic equivalence of paraphrased instructions.

Figure 19: Per-type breakdown of Figure 2 , showing every action paraphrase type individually. The top two rows show pretrained LLMs and the bottom two rows show RL-finetuned LLMs. In the first row of each group, success rate (%) is shown on original ALFWorld (None), on each of the nine action paraphrase types (grouped into lexical, structural, and pragmatic), and on the two object paraphrase types. The second row combines each action type with an object paraphrase, Addition (left) or Same-Polarity (right). As in Figure 2 , each marker is one model, with marker size indicating parameter count; horizontal bars and diamonds denote the median and mean across models.

Panel of Figure 20 — Figure 20: The five prompt templates of the ALFWorld paraphrase-knowledge probe. {p} is the paraphrased noun; {CHOICES_BLOCK} lists the 82 entity types in environment (lowercase) form, ordered as objects (42), receptacles (22), toggleable (1) and scenery (17); {TAIL} is identical to the ScienceWorld probe.

Panel of Figure 21 — Figure 21: Instruction (top) and object reference (bottom) provided to human evaluators for verifying semantic equivalence of paraphrased instructions in ScienceWorld-Para.

Figure 22: Success rate (SR) (%) on ALFWorld-Para for every action-axis (rows) and object-axis (columns) paraphrase type, without any mitigation (Baseline). Each panel is one model, grouped into ReAct-prompted pretrained LLMs (top) and RL-finetuned sLLMs on the Qwen2.5-7B (middle) and 1.5B (bottom) backbones.

Figure 23: Success rate (SR) (%) on ALFWorld-Para by paraphrase type under Greedy.

Figure 24: Success rate (SR) (%) on ALFWorld-Para by paraphrase type under Self-clarification.

Figure 25: Success rate (SR) (%) on ALFWorld-Para by paraphrase type under BINDIntent SBERT .

Figure 26: Success rate (SR) (%) on ALFWorld-Para by paraphrase type under BINDIntent (ours).

LLM Agents

Large language model agents use language models to plan, use tools, and act across multi-step tasks and environments.

See all 740 papers

LIBERO-Para: A Diagnostic Benchmark and Metrics for Paraphrase Robustness in VLA Models
Mar 30, 2026Chanyoung Kim, Minwoo Kim, Minseok Kang +2Vision-Language Grounding Vision-Language-Action Models
School of Computer Science and Engineering, Soongsil University, Seoul, Korea · Department of Artificial Intelligence, Chung-Ang University, Seoul, Korea
PhantomEnvironments: Training LLM Agents in Fictional Worlds
Sep 30, 2026Anmol Kabra, Swathi Saravana Selvam, Albert Gong +5Multi-Hop QA Reinforcement Learning
Cornell University · Stanford University
NeSyFS: A Neuro-symbolic Fast-Slow Thinking Framework for LLM Agent under Partial Observability
Jul 31, 2026Duo Xu, Faramarz FekriBelief-Space Planning LLM Agents
Georgia Institute of Technology 225 North Ave NW, Atlanta, GA 30332

Mar 30, 2026J/K move · Enter open · S save

LIBERO-Para: A Diagnostic Benchmark and Metrics for Paraphrase Robustness in VLA Models

Chanyoung Kim, Minwoo Kim, Minseok Kang, Hyunwoo Kim+1

School of Computer Science and Engineering, Soongsil University, Seoul, Korea · Department of Artificial Intelligence, Chung-Ang University, Seoul, Korea

Vision-Language Grounding Vision-Language-Action Models Robot Manipulation Benchmarks Instruction Generalization in VLA Models Robustness of VLA Models

Open paper AskPDF arXiv

Vision-Language-Action (VLA) models achieve strong performance in robotic manipulation by leveraging pre-trained vision-language backbones. However, in downstream robotic settings, they are typically fine-tuned with limited data, leading to overfitting to specific instruction formulations and leaving robustness to paraphrased instructions underexplored. To study this gap, we introduce LIBERO-Para, a controlled benchmark that independently varies action expressions and object references for fine-grained analysis of linguistic generalization. Across seven VLA configurations (0.6B-7.5B), we observe consistent performance degradation of 22-52 pp under paraphrasing. This degradation is primarily driven by object-level lexical variation: even simple synonym substitutions cause large drops, indicating reliance on surface-level matching rather than semantic grounding. Moreover, 80-96% of failures arise from planning-level trajectory divergence rather than execution errors, showing that paraphrasing disrupts task identification. Binary success rate treats all paraphrases equally, obscuring whether models perform consistently across difficulty levels or rely on easier cases. To address this, we propose PRIDE, a metric that quantifies paraphrase difficulty using semantic and syntactic factors. Our benchmark and corresponding code are available at: https://github.com/cau-hai-lab/LIBERO-Para

Abstract

LLM Agents

Explore similar work

LIBERO-Para: A Diagnostic Benchmark and Metrics for Paraphrase Robustness in VLA Models

PhantomEnvironments: Training LLM Agents in Fictional Worlds

NeSyFS: A Neuro-symbolic Fast-Slow Thinking Framework for LLM Agent under Partial Observability