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

Chanyoung Kim, Harim Song, Byoungchan Ko, Keonyoung Lee, Myungwon Lee, Dahuin JungarXiv 2026 · arXiv

TL;DR

Reinforcement learning (RL) makes small LLM (sLLM) agents highly capable at specific tasks, but surprisingly fragile when users use synonyms or paraphrases. This paper introduces BINDIntent, a training-free, probabilistic framework that fixes this "binding" failure by semantically mapping user expressions to observed environment objects, boosting success rates by up to 49 percentage points with negligible computational overhead.

What Problem Does This Paper Address?

While large language models (LLMs) are often used as high-level planners, smaller LLMs (sLLMs, <10B parameters) fine-tuned with RL have become competitive, cost-effective alternatives for embodied agents. However, these agents are typically trained and evaluated on rigid instruction templates (e.g., "Put a book in the sidetable").

The authors discover a major "robustness gap": when a user provides a paraphrased instruction using synonyms (e.g., "Can you set the novel in the end table?"), even the best RL-finetuned agents suffer a 21–52% drop in success rates.

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

Crucially, this isn't because the models don't know what a "novel" is. Probes show they retain the knowledge that a "novel" is a "book." The failure happens during object binding under partial observability. Because the agent only sees parts of the environment at a time, it struggles to decide if an observed object (labeled "book") is the intended referent of the instruction ("novel"), or if the "real" novel is still hidden in an unopened drawer.

Methods

To solve this, the authors propose BINDIntent, a modular, training-free layer that sits between the user and the frozen agent. It operates in three stages:

  1. Candidate Distance: It extracts object referring expressions from the instruction and calculates the semantic distance to all currently observed environment labels using word embeddings (ConceptNet Numberbatch).
  2. Best-Match Persistence: This is the "secret sauce." Under partial observability, you don't know if a better match is yet to be found. BINDIntent models the distribution of observed distances using a Weibull distribution to estimate "persistence"—the probability that the current best match will remain the best even after all unexplored units (like closed cabinets) are opened.
  3. Persistence-Driven Binding: As the agent explores and persistence increases, BINDIntent accumulates a binding probability. It uses a Bernoulli trial to decide when to "commit" and substitute the user's word with the environment's label (e.g., rewriting "novel" to "book") before passing the instruction to the agent.
Figure 1: Under partial observability, an sLLM agent that succeeds on a templated instruction fails on its paraphrased counterpart.

Datasets

The authors introduced two new benchmarks to evaluate linguistic robustness in embodied AI:

  • ALFWorld-Para: A paraphrased version of the ALFWorld benchmark, featuring 6,554 instructions across 29 paraphrase types (lexical, structural, and pragmatic).
  • ScienceWorld-Para: A similar adaptation of the ScienceWorld benchmark used for cross-benchmark validation.

Key Insights and Ideas

  • Knowledge vs. Binding: RL fine-tuning doesn't destroy the model's internal dictionary (referential knowledge), but it makes the model's policy overly dependent on specific lexical tokens found in training templates.
  • Synonyms are the Primary Culprit: While changes in sentence structure (e.g., turning a command into a question) cause some degradation, object synonym substitution is the dominant factor behind agent failure.
  • The Cost of Certainty: Agents often see the target object but refuse to interact with it because the label doesn't match the instruction. BINDIntent allows the agent to "recognize" the object semantically without needing to be retrained.
  • Efficiency Matters: Unlike "Self-clarification" methods that require extra LLM calls (adding 30–100ms of latency), BINDIntent is purely mathematical and adds only 0.4ms of overhead.
Figure 6: Per-step latency introduced by each method across agent models. Note the discontinuous y-axis.

Key Results

  • Performance Recovery: BINDIntent improves the success rate of RL-finetuned sLLMs on synonym-heavy instructions by 17.5–49.1 percentage points.
  • Surpassing Giants: A 7B parameter model (GiGPO-7B) equipped with BINDIntent achieved an overall success rate of 77.4%, outperforming a much larger 24B parameter Mistral model (63.8%).
  • Robustness Across Scales: The benefits were consistent across different model sizes (1.5B to 7B) and different RL algorithms (PPO, GRPO, GiGPO, StraTA).

Limitations and Future Work

  • Action Paraphrases: BINDIntent focuses primarily on object synonyms. Robustness to pragmatic action variations (like "Is the book in the sidetable yet?" instead of "Put the book in the sidetable") remains a challenge that BINDIntent doesn't fully address.
  • Exploration Policy: The framework is passive; it doesn't tell the agent where to look to resolve ambiguity faster. Future work could integrate binding confidence directly into the agent's exploration strategy.
  • Lexical Allowance: The current model uses a fixed schedule to widen the "lexical allowance" (how different a word can be to be considered a match). A more dynamic approach based on the specific environment context could be more robust.

Summary updated

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.
BibTeX
@misc{kim2026binding,
  author = {Chanyoung Kim and Harim Song and Byoungchan Ko and Keonyoung Lee and Myungwon Lee and Dahuin Jung},
  title = {{Binding Paraphrased Instructions to Encountered Objects in sLLM Agents under Partial Observability}},
  year = {2026},
  eprint = {2611.07599},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.07599},
}
Figure